2007.7算法设计与分析课程期末试卷

《2007.7算法设计与分析课程期末试卷》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、华南农业大学期末考试试卷（A卷）2006学年第二学期　考试科目：　算法分析与设计　考试类型：（开卷）　　　考试时间：　120　分钟学号姓名年级专业题号一二三总分得分评阅人一、选择题（30分，每题2分）1、一个算法应该包含如下几条性质，除了。（A）有限性（B）二义性（C）正确性（D）可终止性2、我们常用算法的最坏运行时间来估计算法的时间复杂度，下面不是这样做的原因：（A）在实际问题中，算法的运行时间常常达到这个上界（B）平均运行时间难以计算（C）假设每一个输入具有相同的概率有时没有意义（D）平均运行时间与最坏运行时间有相同的数量级3、当输入规模为n时，

2、算法增长率最小的是。（A）12n（B）100log2n（C）2n2（D）3nlog3n4、voidhanoi(intn,inta,intb,intc){if(n>0){hanoi(n-1,a,c,b);move(a,b);hanoi(n-1,c,b,a);}7}上述算法的时间复杂度为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）=

3、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的所有不同划分中

4、，将最大加数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、当一个确定性算法在最坏

5、情况下的计算复杂性与其在平均情况下的计算复杂性有较大差别时，可以使用来消除或减少问题的好坏实例间的这种差别。7（A）数值概率算法（B）舍伍德算法（C）拉斯维加斯算法（D）蒙特卡罗算法10、对于0－1背包问题和背包问题的解法，下面答案解释正确。（A）0－1背包问题和背包问题都可用贪心算法求解（B）0－1背包问题可用贪心算法求解，但背包问题则不能用贪心算法求解（C）0－1背包问题不能用贪心算法求解，但可以使用动态规划或搜索算法求解，而背包问题则可以用贪心算法求解（D）因为0－1背包问题不具有最优子结构性质，所以不能用贪心算法求解11、对于矩阵连乘问题，其

6、递推关系式为其中m[i，j]为计算A[i，j]所需的最少数乘次数。现在要计算矩阵连乘积A1A2A3A4，其中各矩阵维数分别为：A1A2A3A450´1010´4040´3030´5则计算矩阵连乘积A1A2A3A4所需要的最少数乘次数为。（A）10500（B）8000（C）8500（D）1450012、跳跃表是的一个典型例子。（A）贪婪算法（B）分治算法（C）概率数据结构（D）以上都不对13、7分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决子问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题。（A）问题规模

7、相同，问题性质相同（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(x>a[middle])left=middle;elseright=middle;}//whilereturn–1;

8、}（B）publicstaticintbinarySearch(int[]a,intx,intn){intl