资源描述：
《算法分析期末试题集2016年春.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、《算法分析与设计》期末复习题(一)一、选择题1．下列关于排序算法的叙述，不正确的是？（）A)堆排序的最差情形运行时间为Θ(nlgn)B)快速排序平均情形运行时间为Θ(nlgn)C)任何排序算法的最差情形运行时间都不可能比Ω(nlgn)更小D)插入排序在最好情形下的运行时间为Θ(n)2.Hanoi塔问题如下图所示。现要求将塔座A上的的所有圆盘移到塔座B上，并仍按同样顺序叠置。移动圆盘时遵守Hanoi塔问题的移动规则。由此设计出解Hanoi塔问题的递归算法正确的为：（）A.voidhanoi(intn
2、,intA,intC,intB){if(n>0){hanoi(n-1,A,C,B);move(n,a,b);hanoi(n-1,C,B,A);}}Hanoi塔B.voidhanoi(intn,intA,intB,intC){if(n>0){hanoi(n-1,A,C,B);move(n,a,b);hanoi(n-1,C,B,A);}}C.voidhanoi(intn,intC,intB,intA){if(n>0){hanoi(n-1,A,C,B);move(n,a,b);hanoi(n-1,C,B
3、,A);}}D.voidhanoi(intn,intC,intA,intB){if(n>0){hanoi(n-1,A,C,B);move(n,a,b);hanoi(n-1,C,B,A);}}3.动态规划算法的基本要素为（）A.最优子结构性质与贪心选择性质B．重叠子问题性质与贪心选择性质C．最优子结构性质与重叠子问题性质D.预排序与递归调用4.算法分析中，记号O表示（B），记号表示（A），记号表示（）。A.渐进下界B.渐进上界C.非紧上界D.紧渐进界E.非紧下界5.以下关于渐进记号的性质是正确的有：
4、（A）A.B.C.O(f(n))+O(g(n))=O(min{f(n),g(n)})D.6.能采用贪心算法求最优解的问题，一般具有的重要性质为：（）A．重叠子问题性质与贪心选择性质B．最优子结构性质与贪心选择性质A．最优子结构性质与重叠子问题性质B．预排序与递归调用7.回溯法在问题的解空间树中，按（）策略，从根结点出发搜索解空间树。C．广度优先B.活结点优先C.深度优先D.扩展结点优先8.分支限界法在问题的解空间树中，按（）策略，从根结点出发搜索解空间树。A．深度优先B.活结点优先C.扩展结点优先
5、D.广度优先9.程序块（）是回溯法中遍历排列树的算法框架程序。voidbacktrack(intt){if(t>n)output(x);elsefor(inti=t;i<=n;i++){swap(x[t],x[i]);if(legal(t))backtrack(t+1);swap(x[t],x[i]);}}A.voidbacktrack(intt){if(t>n)output(x);elsefor(inti=0;i<=1;i++){x[t]=i;if(legal(t))backtrack(t+1)
6、;}}B.voidbacktrack(intt){if(t>n)output(x);elsefor(inti=0;i<=1;i++){x[t]=i;if(legal(t))backtrack(t-1);}}C.D.voidbacktrack(intt){if(t>n)output(x);elsefor(inti=t;i<=n;i++){swap(x[t],x[i]);if(legal(t))backtrack(t+1);}}10.回溯法的效率不依赖于以下哪一个因素？（）A.满足约束函数和上界函数约
7、束的所有x[k]的个数；B.问题的解空间的形式；C.计算上界函数bound的时间；D.计算约束函数constraint的时间；11.常见的两种分支限界法为（）A.队列式（FIFO）分支限界法与优先队列式分支限界法；B.队列式（FIFO）分支限界法与堆栈式分支限界法；C.排列树法与子集树法；D.广度优先分支限界法与深度优先分支限界法；12.记号O的定义正确的是（）。A.O(g(n))={f(n)
8、存在正常数c和n0使得对所有nn0有：0cg(n)f(n)}；B.O(g(n))={f(n)
9、存在正常数
10、c和n0使得对所有nn0有：0f(n)cg(n)}；C.O(g(n))={f(n)
11、对于任何正常数c>0，存在正数和n0>0使得对所有nn0有：0f(n)12、对于任何正常数c>0，存在正数和n0>0使得对所有nn0有：0cg(n)13、存在正常数c和n0使得对所有nn0有：0f(n)cg(n)}；B.(g(n))={f(n)
14、对于任何正常数c>0，存在正数和n0>0使得
