《算法分析与设计》期末考试复习题-学生版.doc

《算法分析与设计》期末考试复习题-学生版.doc

ID:58400440

大小:214.50 KB

页数:14页

时间:2020-05-08

《算法分析与设计》期末考试复习题-学生版.doc_第1页
《算法分析与设计》期末考试复习题-学生版.doc_第2页
《算法分析与设计》期末考试复习题-学生版.doc_第3页
《算法分析与设计》期末考试复习题-学生版.doc_第4页
《算法分析与设计》期末考试复习题-学生版.doc_第5页
资源描述:

《《算法分析与设计》期末考试复习题-学生版.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(n-1,A,C,B);move(n,a,b);hanoi(n-1,C

2、,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,A);}}D.voidhanoi(intn,intC,intA,intB){if(n>0){hanoi(n-1,A,C,B);

3、move(n,a,b);hanoi(n-1,C,B,A);}}3.动态规划算法的基本要素为(C)A.最优子结构性质与贪心选择性质B.重叠子问题性质与贪心选择性质C.最优子结构性质与重叠子问题性质D.预排序与递归调用4.算法分析中,记号O表示(B),记号表示(A),记号表示(D)。A.渐进下界B.渐进上界C.非紧上界D.紧渐进界E.非紧下界5.以下关于渐进记号的性质是正确的有:(A)A.B.C.O(f(n))+O(g(n))=O(min{f(n),g(n)})D.6.能采用贪心算法求最优解的问题,

4、一般具有的重要性质为:(A)A.最优子结构性质与贪心选择性质B.重叠子问题性质与贪心选择性质C.最优子结构性质与重叠子问题性质D.预排序与递归调用7.回溯法在问题的解空间树中,按(D)策略,从根结点出发搜索解空间树。A.广度优先B.活结点优先C.扩展结点优先D.深度优先8.分支限界法在问题的解空间树中,按(A)策略,从根结点出发搜索解空间树。A.广度优先B.活结点优先C.扩展结点优先D.深度优先9.程序块(A)是回溯法中遍历排列树的算法框架程序。voidbacktrack(intt){if(t>

5、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);}}B.voidbacktrack(intt){if(t>n)output(x);elsefor(inti=

6、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.回溯法的效率不依赖于以下哪一个因素?(C)A.产生x[k]的时间;B.满足显约束的x[k]值的个数;C.问题的解空间的形式;D.计算上界函数bound的时间;E.满足约束函数和

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

8、理所有长度为n的输入时,在k条带上所使用过的平均方格数。D.k带图灵机处理所有长度为n的输入时,在某条带上所使用过的最小方格数。13.NP类语言在图灵机下的定义为(D)A.NP={L

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

10、L是一个能在多项式时间内被一台NDTM所接受的语言};C.NP={L

11、L是一个能在多项式时间内被一台DTM所接受的语言};D.NP={L

12、L是一个能在多项式时间内被一台NDTM所接受的语言};14.记号O的定义正确的是(A)。A.O(g(n))

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。