一、选择题
1。应用Johnson法则的流水作业调度采用的算法是（D)
A. 贪心算法 B。 分支限界法 C.分治法 D。 动态规划算法 2。Hanoi塔问题如下图所示。现要求将塔座A上的的所有圆盘移到塔座B上，并仍按同样顺序叠置.移动圆盘时遵守Hanoi塔问题的移动规则。由此设计出解Hanoi塔问题的递归算法正确的为：（B） B. void hanoi(int n, int A, int B, int C)
{
if (n > 0)
{
hanoi(n-1, A, C, B);
move(n,a,b);
hanoi(n-1, C, B, A);
}
}
C. void hanoi(int n, int C, int B, int A)
{
if (n > 0)
{
hanoi(n-1, 图灵机A, C, B);
move(n,a,b);
hanoi(n-1, C, B, A);
D. void hanoi(int n, int C, int A, int B)
{
路径依赖 if (n > 0)
{
hanoi(n-1, A, C, B);
move(n,a,b);
hanoi(n-1, C, B, A);
}
}
3。 动态规划算法的基本要素为（C）
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. 预排序与递归调用
7。 回溯法在问题的解空间树中,按（D）策略，从根结点出发搜索解空间树。
A．广度优先 B. 活结点优先 C.扩展结点优先 D。 深度优先 8。 分支限界法在问题的解空间树中，按（A）策略,从根结点出发搜索解空间树。
A． 广度优先 B。 活结点优先 C.扩展结点优先 D. 深度优先
9。 程序块（A)是回溯法中遍历排列树的算法框架程序。
void backtrack (int t)
{
if (t>n) output(x);
else
for (int i=t;i<=n;i++) {
swap(x[t], x[i]);
if (legal(t)) backtrack(t+1);
swap(x[t], x[i]);
}
}
A.void backtrack (int t)
{
if (t>n) output(x);
else
for (int i=0;i<=1;i++) {
x[t]=i;
if (legal(t)) backtrack(t+1);
}
}
B。 void backtrack (int t)
{
if (t>n) output(x);
else
for (int i=0;i<=1;i++) {
x[t]=i;
张茹雅 if (legal(t)) backtrack(t-1);
}
}
C.D。void backtrack (int t)
{
if (t>n) output(x);
else
for (int i=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.。
C.k带图灵机处理所有长度为n的输入时，在k条带上所使用过的平均方格数.
D.k带图灵机处理所有长度为n的输入时,在某条带上所使用过的最小方格数.
13. NP类语言在图灵机下的定义为（D）
A.NP={L｜L是一个能在非多项式时间内被一台NDTM所接受的语言};
B.NP={L｜L是一个能在多项式时间内被一台NDTM所接受的语言};
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议