《算法设计与分析报告》考精彩试题目及问题详解(DOC)

《《算法设计与分析报告》考精彩试题目及问题详解(DOC)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实用标准《算法分析与设计》期末复习题一、选择题1.应用Johnson法则的流水作业调度采用的算法是（D）A.贪心算法B.分支限界法C.分治法D.动态规划算法2.Hanoi塔问题如下图所示。现要求将塔座A上的的所有圆盘移到塔座B上，并仍按同样顺序叠置。移动圆盘时遵守Hanoi塔问题的移动规则。由此设计出解Hanoi塔问题的递归算法正确的为：（B）A.voidhanoi(intn,intA,intC,intB){if(n>0){Hanoi塔hanoi(n-1,A,C,B);move(n,a,b);hanoi(n-1,C,B,A);}B.v

2、oidhanoi(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,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

3、.动态规划算法的基本要素为（C）A.最优子结构性质与贪心选择性质B．重叠子问题性质与贪心选择性质C．最优子结构性质与重叠子问题性质D.预排序与递归调用4.算法分析中，记号O表示（B），记号表示（A），记号表示（D）。A.渐进下界B.渐进上界C.非紧上界D.紧渐进界E.非紧下界5.以下关于渐进记号的性质是正确的有：（A）A.f(n)(g(n)),g(n)(h(n))f(n)(h(n))B.f(n)O(g(n)),g(n)O(h(n))h(n)O(f(n))C.O(f(n))+O(g(n))=O(min{f(n

4、),g(n)})D.f(n)O(g(n))g(n)O(f(n))6.能采用贪心算法求最优解的问题，一般具有的重要性质为：（A）A.最优子结构性质与贪心选择性质B．重叠子问题性质与贪心选择性质C．最优子结构性质与重叠子问题性质文档大全实用标准D.预排序与递归调用7.回溯法在问题的解空间树中，按（D）策略，从根结点出发搜索解空间树。A．广度优先B.活结点优先C.扩展结点优先D.深度优先8.分支限界法在问题的解空间树中，按（A）策略，从根结点出发搜索解空间树。A．广度优先B.活结点优先C.扩展结点优先D.深度优先9.程序块（A）是回溯

5、法中遍历排列树的算法框架程序。A.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]);}}B.voidbacktrack(intt){if(t>n)output(x);elsefor(inti=0;i<=1;i++){x[t]=i;if(legal(t))backtrack(t+1);}}C.voidbacktrack(intt){if(t>n)o

6、utput(x);elsefor(inti=0;i<=1;i++){x[t]=i;if(legal(t))backtrack(t-1);}D.}voidbacktrack(intt){文档大全if(t>n)output(x);elsefor(inti=t;i<=n;i++){swap(x[t],x[i]);实用标准10.回溯法的效率不依赖于以下哪一个因素？（C）A.产生x[k]的时间；B.满足显约束的x[k]值的个数；C.问题的解空间的形式；D.计算上界函数bound的时间；E.满足约束函数和上界函数约束的所有x[k]的个数。F.计算

7、约束函数constraint的时间；11.常见的两种分支限界法为（D）A.广度优先分支限界法与深度优先分支限界法；B.队列式（FIFO）分支限界法与堆栈式分支限界法；C.排列树法与子集树法；D.队列式（FIFO）分支限界法与优先队列式分支限界法；12.k带图灵机的空间复杂性S(n)是指（B）A.k带图灵机处理所有长度为n的输入时，在某条带上所使用过的最大方格数。B.k带图灵机处理所有长度为n的输入时，在k条带上所使用过的方格数的总和。C.k带图灵机处理所有长度为n的输入时，在k条带上所使用过的平均方格数。D.k带图灵机处理所有长度为n

8、的输入时，在某条带上所使用过的最小方格数。文档大全实用标准13.NP类语言在图灵机下的定义为（D）A.NP={L

9、L是一个能在非多项式时间内被一台NDTM所接受的语言}；B.NP={L

10、L是一个能在多项式时间内被一台ND