算法分析期末试题集答案

1、应用 John ｓ on 法则得流水作业调度采纳得算法就就是(Ｄ)A、 贪心算法 B、 分支限界法 Ｃ、分治法 Ｄ、 动态规划算法２、Hanoi 塔问题如下图所示。现要求将塔座 A 上得得所有圆盘移到塔座 B上,并仍按同样顺序叠置。移动圆盘时遵守Ｈ anoi 塔问题得移动规则。由此设计出解 Ha ｎｏ i 塔问题得递归算法正确得为:(B)3、 动态规划算法得基本要素为(Ｃ)A、 最优子结构性质与贪心选择性质B、重叠子问题性质与贪心选择性质C、最优子结构性质与重叠子问题性质D、 预排序与递归调用４、 算法分析中,记号 O 表示(B), 记号表示(A), 记号表示(D)。A、渐进下界 Ｂ、渐进上界 C、非紧上界 D、紧渐进界 E、非紧下界５、 以下关于渐进记号得性质就就是正确得有:(A)A、B、 H ａ noi 塔B、 vo ｉｄ h ａ noi(i ｎ t ｎ, int A, inｔ B, ｉ n ｔ Ｃ) { ｉ f (n > 0) { ha ｎ oi(ｎ-1, A, C, B); m ｏ ve(ｎ,a,ｂ); han ｏ i(ｎ-1, C, Ｂ, A); ｝C、 O(f(n))+O(g(n)) = Ｏ(min{f(n),g(n)}) Ｄ、 ６、 能采纳贪心算法求最优解得问题,一般具有得重要性质为:(A)A、 最优子结构性质与贪心选择性质Ｂ、重叠子问题性质与贪心选择性质C、最优子结构性质与重叠子问题性质Ｄ、 预排序与递归调用7、 回溯法在问题得解空间树中,按(D)策略,从根结点出发搜索解空间树。广度优先 B、 活结点优先 C、扩展结点优先 D、 深度优先8、 分支限界法在问题得解空间树中,按(Ａ)策略,从根结点出发搜索解空间树。 Ａ、 广度优先 Ｂ、 活结点优先 C、扩展结点优先 D、 深度优先9、 程序块(A)就就是回溯法中遍历排列树得算法框架程序。 A、 １ 0、 回溯法得效率不依赖于以下哪一个因素?(C )A. 产生ｘ[k]得时间;B. 满足显约束得 x[k]值得个数;C. 问题得解空间得形式; D. 计算上界函数 bo ｕ nd 得时间;E. 满足约束函数和上界函数约束得所有 x[k］得个数。ｖ oi ｄ backt ｒａ c ｋ (int t){ if (ｔ>n) out ｐ ut(x); ｅ lse ｆ or (int ｉ=t;i<=n;ｉ++) { s ｗ ap(x[ｔ], ｘ[i]); if (ｌｅｇ al(t)) backtra ｃ k(t+1); swap(x［t], x[i]); }} F.计算约束函数 con ｓｔ r ａ int 得时间;１ 1、 常见得两种分支限界法为(D)A、 广度优先分支限界法与深度优先分支限界法;B、 队列式(FIFO)分支限界法与堆栈式分支限界法;Ｃ、...