搜索
1华南农业大学期末考试试卷（A卷）2006学年第二学期考试科目：算法分析与设计考试类型：（开卷）考试时间：120分钟学号姓名年级专业题号一二三总分得分评阅人一、选择题（30分，每题2分）1、一个算法应该包含如下几条性质，除了。（A）有限性（B）二义性（C）正确性（D）可终止性2、我们常用算法的最坏运行时间来估计算法的时间复杂度，下面不是这样做的原因：（A）在实际问题中，算法的运行时间常常达到这个上界（B）平均运行时间难以计算（C）假设每一个输入具有相同的概率有时没有意义（D）平均运行时间与最坏运行时间有相同的数量级3、当输入规模为n时，算法增长率最小的是。（A）12n（B）100log2n（C）2n2（D）3nlog3n4、voidhanoi(intn,inta,intb,intc){if(n0){hanoi(n-1,a,c,b);move(a,b);hanoi(n-1,c,b,a);}2}上述算法的时间复杂度为A．O（2n）B．O（nlogn）C．Θ（n！）D．Θ（nn）5、对于下列各组f（n）和g（n），下面答案不满足f（n）=O（g（n））（A）f（n）=logn2g（n）=logn+5（B）f（n）=lognng（n）=n（C）f（n）=n！g（n）=nn（D）f（n）=logng（n）=n6、在寻找n个元素中第k小元素问题中，如快速排序算法思想，运用分治算法对n个元素进行划分，如何选择划分基准？下面答案解释最合理。（A）随机选择一个元素作为划分基准（B）取子序列的第一个元素作为划分基准（C）用中位数的中位数方法寻找划分基准（D）以上皆可行。但不同方法，算法复杂度上界可能不同7、将一个正整数n表示成一系列正整数之和，n=n1+n2+…+nk（其中，n1≥n2≥…≥nk≥1，k≥1）正整数n的一个这种表示称为正整数n的一个划分。正整数n的不同的划分个数称为正整数n的划分数，记作p（n）；另外，在正整数n的所有不同划分中，将最大加数n1不大于m的划分个数记作q（n，m）。则当n=10时，p（n）=。（A）q（10，8）（B）1+q（9，9）（C）2+q（10，8）（D）以上都不对8、关于回溯算法和分支限界法，以下是不正确描述。（A）回溯法中，每个活结点只有一次机会成为扩展结点（B）分支限界法中，活结点一旦成为扩展结点，就一次性产生其所有儿子结点，在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子加入活结点表中（C）回溯法采用深度优先的结点生成策略（D）分支限界法采用广度优先或最小耗费优先（最大效益优先）的结点生成策略9、当一个确定性算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有较大差别时，可以使用来消除或减少问题的好坏实例间的这种差别。3（A）数值概率算法（B）舍伍德算法（C）拉斯维加斯算法（D）蒙特卡罗算法10、对于0－1背包问题和背包问题的解法，下面答案解释正确。（A）0－1背包问题和背包问题都可用贪心算法求解（B）0－1背包问题可用贪心算法求解，但背包问题则不能用贪心算法求解（C）0－1背包问题不能用贪心算法求解，但可以使用动态规划或搜索算法求解，而背包问题则可以用贪心算法求解（D）因为0－1背包问题不具有最优子结构性质，所以不能用贪心算法求解11、对于矩阵连乘问题，其递推关系式为其中m[i，j]为计算A[i，j]所需的最少数乘次数。现在要计算矩阵连乘积A1A2A3A4，其中各矩阵维数分别为：A1A2A3A4501010404030305则计算矩阵连乘积A1A2A3A4所需要的最少数乘次数为。（A）10500（B）8000（C）8500（D）1450012、跳跃表是的一个典型例子。（A）贪婪算法（B）分治算法（C）概率数据结构（D）以上都不对13、分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决子问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子jipppjkmkimjijimjki}],1[],[{min0],[1jki4问题。（A）问题规模相同，问题性质相同（B）问题规模相同，问题性质不同（C）问题规模不同，问题性质相同（D）问题规模不同，问题性质不同14、对于下列二分搜索算法，正确的是（A）publicstaticintbinarySearch(int[]a,intx,intn){intleft=0,right=n-1;while(left=right){intmiddle=(left+right)/2;if(x==a[middle])returnmiddle;if(xa[middle])left=middle;elseright=middle;}//whilereturn–1;}（B）publicstaticintbinarySearch(int[]a,intx,intn){intleft=0,right=n-1;while(left+1!=right){intmiddle=(left+right)/2;if(x=a[middle])left=middle;elseright=middle;}//whileif(x==a[left])returnleft;elsereturn–1;}（C）publicstaticintbinarySearch(int[]a,intx,intn){intleft=0,right=n-1;while(leftright-1){5intmiddle=(left+right)/2;if(xa[middle])right=middle;elseleft=middle;}//whileif(x==a[left])returnleft;elsereturn–1;}（D）publicstaticintbinarySearch(int[]a,intx,intn){if(n0&&x=a[0]){intleft=0,right=n-1;while(leftright){intmiddle=(left+right+1)/2;if(xa[middle])right=middle-1;elseleft=middle;}//whileif(x==a[left])returnleft;}//ifreturn–1;}15、在分支限界算法中，根据从活结点表中选择下一扩展结点的不同方式可有几种常用分类，以下描述最为准确（A）采用FIFO队列的队列式分支限界法（B）采用最小值堆的优先队列式分支限界法（C）采用最大值堆的优先队列式分支限界法（D）以上都常用，针对具体问题可以选择采用其中某种更为合适的方式二、简答题（30分，每题6分）1、设p（n）是将n划分成若干奇正整数之和的划分数，q（n）是将n划分成若干不同整数之和的划分数，请分别给出p（n），q（n）的递推关系式子。62、列出找n个数组成的序列的最长单调递增子序列的动态规划递归式3、试比较回溯法与分枝限界算法，分别谈谈这两个算法比较适合的问题？4、请解释什么是P问题，NP问题以及NP完全问题并描述这三者之间的关系；最后，请列举几个常见的NP完全问题。5、对于以下无向连通带权图，构造其最小生成树并计算该最小生成树的权值和。6、假设有一个数据文件包含100000个字符，现要用压缩的方式来存储它。该文件中各字符出现的频率如下表所示，abcde频率（千次）2035151218文件中共有5个不同字符出现，根据上述频率表构造其对应的哈夫曼编码，要求写出其编码过程。三、算法设计题（40分，每题10分）1、【特殊的0－1背包问题】给定n件物品和一个背包，物品i的重量是wi，体积是vi，价值是pi；背包的容量为C，容积为D。一件物品只能整个放进背包中或不放进背包中，也不允许重复放入。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大？请设计一个求解此问题的算法。72、【查找第k最小元问题】给定线性序集中n个元素和一个整数k，1≤k≤n，要求找出这n个元素中第k小的元素，请设计一个最坏时间复杂度为O（n）的算法，并对其时间复杂度进行分析说明。3、【钓鱼问题】在一条水平路边，有n（2≤n≤25）个钓鱼湖，从左到右编号为1、2、3、…、n。佳佳有H（1≤H≤16）个小时的空余时间，他希望用这些时间钓到尽量多的鱼。他从湖1出发，向右走，有选择的在一些湖边停留一定的时间钓鱼，最后在某一个湖边结束钓鱼。佳佳测出从第i个湖到第i+1个湖需要走5×Ti分钟的路，还测出在第i个湖边停留，第一个5分钟可以钓到鱼Fi，以后再每钓5分钟鱼，鱼量减少Di。为了简化问题，佳佳假定没有其他人钓鱼，也不会有其他因素影响他钓到期望数量的鱼。请设计一个算法求出佳佳能钓到最多鱼的方案。4、【农夫过河问题】农夫每天去种地都要过一条河，这条河很宽，过河要走上面的木桩。木桩有n支，排成一排，从左岸延伸到右岸，编号从1到n。左岸在1号桩的左边，右岸在n号桩的右边。但这些木桩会定时升降，因此他每天都花不少时间在过河上。所以他想找一种最快过河的方法。在时刻0，农夫在左岸，他要在最短时间内到达右岸。在任何时刻，每一支桩都只能处于升或降的其中一种状态。升起的桩才可以站上去，农夫只能站在升起的桩上或岸上。每一支桩在时刻0都是降的状态，接着升起A分钟，降下B分钟，再升起A分钟后，再降下B分钟，这样一直交替升降下去。例如：A＝2，B＝3的桩，在时刻0降，在时刻1、2升，在时刻3、4、5降，等等。A和B是常数时间，而且对于每一支桩都可能不同。设在时刻t农夫站在p桩，那么在时刻t＋1，农夫能走到p桩的左右5个桩或岸上，也可以原地不动，当然桩是可站立的。例如，在5号桩，他能走到1，2，3，4，5，6，7，8，9，10号桩，或到左岸。请帮农夫找到一种最快到达右岸的方法。