《算法设计与分析》考试题目

《《算法设计与分析》考试题目》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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

2、(n>0)hanoi(n-1,A,C,B);move(n,a,b);hanoi(n~l,C,B,A);C.voidhanoi(intn,intC,intB,intA)if(n>0)hanoi(n-1,A,C,B);move(n,a,b);hanoi(n~l,C,B,A);D.voidhanoi(intn,intC,intA,intB){if(n〉0){hanoi(n-1,A,C,B);move(n,a,b);hanoi(n~l,C,B,A);}1.动态规划算法的基本要素为(C)A.最优子结构性质与贪心选择性质B.重叠子问题性质与贪心选择性质C

3、.最优子结构性质与重叠子问题性质D.预排序与递归调用2.算法分析中，记号O表示(B),记号£1表示(A),记号O表示(D)。A.渐进下界B.渐进上界C.非紧上界D.紧渐进界E.非紧下界3.以下关于渐进记号的性质是正确的有：(A)A.f(n)=©(g(n))，g(n)=0(h(n))^>f(n)=0(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),g(n)})D.f(n)=O(g(n))»g(n)=O(f(n))4.能采用贪心算法求最优解的M题

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

5、inti二t;i〈=n;i++){swap(x[t],x[i]);if(legal(t))backtrack(t+1);swap(x[t],x[i]);voidbacktrack(intt){if(t>n)output(x);elsefor(inti二0;i〈：l;i++){x[t]=i;if(legal(t))backtrack(t+1);C.voidbacktrack(intt){if(t>n)output(x);elsefor(inti:0;i〈：l;i++){x[t]=i;if(legal(t))backtrack(t—1);void

6、backtrack(intt){if(t>n)output(x);elsefor(inti=t;i<=n;i++){swap(x[t],x[i]);if(legal(t))backtrack(t+1);}}4.冋溯法的效率不依赖于以下哪一个因素？(C)A.产生x[k]的时间；A.满足显约束的x[kl值的个数；B.问题的解空间的形式；C.计算上界函数bound的时间；D.满足约束函数和上界函数约束的所宥x[k]的个数。E.计算约束函数constraint的时间;1.常见的两种分支限界法为(D)A.广度优先分支限界法与深度优先分支限界法；B.队列

7、式(FIFO)分支限界法与堆栈式分支限界法；C.排列树法与子集树法：D.队列式(HFO)分支限界法与优先队列式分支限界法；2.k带图灵机的空间复杂性S(n)是指(B)A.k带图灵机处理所有长度为n的输入时，在某条带上所使用过的最大方格数。B.k带阁灵机处理所有长度为n的输入时，在k条带上所使用过的方格数的总和。C.k带图灵机处理所冇长度为n的输入吋，在k条带上所使用过的平均方格数。D.k带图灵机处理所有长度为n的输入吋，在某条带上所使用过的最小方格数。3.NP类语言在图灵机下的定义为(D)A.NP={L

8、L是一个能在非多项式吋间A被一台NDT

9、M所接受的语言};B.NP={L

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

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