《算法分析与设计》期末复习题一、选择题1.应用Johnson法则的流水作业调度采用的算法是（D）A.贪心算法B.分支限界法C.分治法D.动态规划算法2.Hanoi塔问题如下图所示。现要求将塔座A上的的所有圆盘移到塔座B上，并仍按同样顺序叠置。移动圆盘时遵守Hanoi塔问题的移动规则。由此设计出解Hanoi塔问题的递归算法正确的为：（B）Hanoi塔A.voidhanoi(intn,intA,intC,intB){if(n>0){hanoi(n-1,A,C,B);move(n,a,b);hanoi(n-1,C,B,A);}}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);}}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.能采用贪心算法求最优解的问题，一般具有的重要性质为：（A）A.最优子结构性质与贪心选择性质B．重叠子问题性质与贪心选择性质C．最优子结构性质与重叠子问题性质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);}}D.预排序与递归调用7.回溯法在问题的解空间树中，按（D）策略，从根结点出发搜索解空间树。A．广度优先B.活结点优先C.扩展结点优先D.深度优先8.分支限界法在问题的解空间树中，按（A）策略，从根结点出发搜索解空间树。A．广度优先B.活结点优先C.扩展结点优先D.深度优先9.程序块（A）是回溯法中遍历排列树的算法框架程序。A.B.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);swap(x[t],x[i]);}}voidbacktrack(intt){if(t>n)output(x);elsefor(inti=0;i<=1;i++){x[t]=i;if(legal(t))backtrack(t+1);}}voidbacktrack(intt){if(t>n)output(x);elsefor(inti=0;i<=1;i++){x[t]=i;if(legal(t))backtrack(t-1);}}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.满足约束函数和上界函数约束的所有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.k带图灵机处理所有长度为n的输入时，在k条带上所使用过的平均方格数。D.k带图灵机处理所有长度为n的输入时，在某条带上所使用过的最小方格数。13.NP类语言在图灵机下的定义为（D）A.NP={L|L是一个能在非多项式时间内被一台NDTM所接受的语言}；B.NP={L|L是一个能在多项式时间内被一台NDTM所接受的语言}；C.NP={L|L是一个能在多项式时间内被一台DTM所接受的语言}；D.NP={L|L是一个能在多项式时间内被一台NDTM所接受的语言}；14.记号O的定义正确的是（A）。A.O(g(n))={f(n)|存在正常数c和n0使得对所有nn0有：0f(n)cg(n)}；B.O(g(n))={f(n)|存在正常数c和n0使得对所有nn0有：0cg(n)f(n)}；C.O(g(n))={f(n)|对于任何正常数c>0，存在正数和n0>0使得对所有nn0有：0f(n)0，存在正数和n0>0使得对所有nn0有：0cg(n)
