扫描下方二维码关注公众号：

关闭

×

作业辅导
扫码关注
论文指导
轻松解决学习难题!

中国大学MOOC算法设计与分析作业答案

算法设计与分析

学校: 九八五题库

学校: 超星学习通

题目如下：

1. 1. 有关随机化算法正确的是（）

A. 随机化算法的特征是对所求解问题的同一实例用同一随机化算法求解两次可能得到完全不同的效果，这两次求解问题所需的时间甚至所得到的结果可能会有相当大的差别。

B. 数值随机化算法常用于数值问题的求解，所得到的解往往都是近似解，而且近似解的精度随计算时间的增加不断提高。

C. 蒙特卡罗算法用于求问题的准确解，但解不一定正确。

D. 拉斯维加斯算法绝不返回错误的解，但有时得不到问题的解。可以通过多次执行提高算法得到解的概率。

E. 舍伍德算法用于当一个确定性算法在最坏情况下的计算时间复杂性与其在平均情况下的计算复杂性有较大差异时。

F. 舍伍德算法引入随机性来降低最坏情况出现的概率，从而消除或减少问题好坏实例之间的时间消耗的差异。

答案: 随机化算法的特征是对所求解问题的同一实例用同一随机化算法求解两次可能得到完全不同的效果，这两次求解问题所需的时间甚至所得到的结果可能会有相当大的差别。# 数值随机化算法常用于数值问题的求解，所得到的解往往都是近似解，而且近似解的精度随计算时间的增加不断提高。# 蒙特卡罗算法用于求问题的准确解，但解不一定正确。# 拉斯维加斯算法绝不返回错误的解，但有时得不到问题的解。可以通过多次执行提高算法得到解的概率。# 舍伍德算法用于当一个确定性算法在最坏情况下的计算时间复杂性与其在平均情况下的计算复杂性有较大差异时。# 舍伍德算法引入随机性来降低最坏情况出现的概率，从而消除或减少问题好坏实例之间的时间消耗的差异。

2. 2. 有关估算π值的随机化算法说法错误的是（）

A. 估算π值的随机化算法估算的精度随算法消耗的时间的增加而提高

B. 估算π值的随机化算法随机实验次数越多，估算的π值精度越高

C. 估算π值的随机化算法随机实验次数越多，估算的π值精度越低

D. 估算π值的随机化算法估算的近似值的精度随算法消耗的时间的增加而降低

答案: 估算π值的随机化算法随机实验次数越多，估算的π值精度越低# 估算π值的随机化算法估算的近似值的精度随算法消耗的时间的增加而降低

3. 3. 有关主元素问题的蒙特卡罗算法说法错误的是（）

A. 主元素问题的蒙特卡罗算法每次执行都返回True 或False，True表示有主元素，False表示没有主元素。

B. 主元素问题的蒙特卡罗算法返回True的解是正确解，False的解不一定是正确解。

C. 主元素问题的蒙特卡罗算法返回False的解是正确解，True的解不一定是正确解。

D. 主元素问题的蒙特卡罗算法得到的解为正确解的概率大于0.5

E. 主元素问题的蒙特卡罗算法得到正确解的概率随算法消耗的时间的增加而降低

答案: 主元素问题的蒙特卡罗算法返回False的解是正确解，True的解不一定是正确解。# 主元素问题的蒙特卡罗算法得到正确解的概率随算法消耗的时间的增加而降低

4. 4. 有关素数测试问题算法说法正确的是（）

A. 根据Wilson定理，可以设计素数测试的确定性算法。

B. 可以采用试除法，设计素数测试的确定性算法。

C. 根据费马定理，可以设计素数测试的随机化算法。当算法返回True时，解不一定正确；当返回False时，解一定是正确的。

D. 根据二次探测定理，可以设计素数测试的蒙特卡罗算法，当算法返回True时，解一定正确；当返回False时，解不一定正确。

E. 根据二次探测定理设计的素数测试蒙特卡罗算法得到的解为正确解的概率大于0.5

F. 根据费马定理设计的素数测试蒙特卡罗算法得到的解为正确解的概率小于0.5

答案: 根据Wilson定理，可以设计素数测试的确定性算法。# 可以采用试除法，设计素数测试的确定性算法。# 根据费马定理，可以设计素数测试的随机化算法。当算法返回True时，解不一定正确；当返回False时，解一定是正确的。# 根据二次探测定理设计的素数测试蒙特卡罗算法得到的解为正确解的概率大于0.5

5. 5. 有关n皇后问题的拉斯维加斯算法说法正确的是（）

A. n皇后问题的拉斯维加斯算法得到接的概率大于0。

B. n皇后问题的拉斯维加斯算法得到接的概率小于0。

C. n皇后问题的拉斯维加斯算法每次运行都能得到一种n个皇后的放置方案。

D. 多次运行n皇后问题的拉斯维加斯算法可以提高算法得到解的概率。

E. n皇后问题的拉斯维加斯算法可以采用对所有能放置的列位置进行随机。

F. n皇后问题的拉斯维加斯算法可以采用对不冲突的多个列位置进行随机。

答案: n皇后问题的拉斯维加斯算法得到接的概率大于0。# n皇后问题的拉斯维加斯算法每次运行都能得到一种n个皇后的放置方案。# 多次运行n皇后问题的拉斯维加斯算法可以提高算法得到解的概率。# n皇后问题的拉斯维加斯算法可以采用对所有能放置的列位置进行随机。# n皇后问题的拉斯维加斯算法可以采用对不冲突的多个列位置进行随机。

6. 6. 有关随机快速排序算法说法正确的是（）

A. 随机快速排序与快速排序的区别是随机快速排序随机选择基准元素，而快速排序的确定性算法选择固定位置的元素作为基准元素。

B. 随机快速排序通过对快速排序引入随机性，降低了快速排序最好情况出现的概率。

C. 随机快速排序的时间复杂度趋于O(nlogn)。

D. 随机快速排序每次运行都能够得到解，但解不一定正确。

答案: 随机快速排序与快速排序的区别是随机快速排序随机选择基准元素，而快速排序的确定性算法选择固定位置的元素作为基准元素。# 随机快速排序的时间复杂度趋于O(nlogn)。

7. 7. 有关整数n的因子分解问题说法正确的是（）

A. 整数的因子分解就是将整数n分解为素数的乘积。

B. 整数的因子分解问题可以转化为因子分割问题。

C. 因子分割不可以采用试除法找出整数n的因子。

D. Pollard算法，只要给足够的时间，肯定能找到整数n的因子。

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

8. 8. 以下有关随机选择第k小算法错误的是（）

A. 随机选择第k小算法中的随机性和随机快速排序的随机性一样，都是随机选择基准元素。

B. 随机选择第k小算法是对线性时间选择算法中划分部分进行了随机，其他和线性时间选择算法一样。

C. 随机选择第k小算法是对线性时间选择算法中选取基准元素部分进行了随机，其他和线性时间选择算法一样。

D. 随机选择第k小算法中的随机性和随机快速排序的随机性不同，随机快速排序是随机选择基准元素，随机选择第k小算法随机划分、比较。

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

9. 9. 以下随机化算法能得能保证得到的解是正确解的算法是（）

A. 蒙特卡罗算法

B. 拉斯维加斯算法

C. 数值随机化算法

D. 舍伍德算法

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

10. 1. n个元素的冒泡排序代码如下： def bubble_sort(arr): for i in range(len(arr)-1): for j in range(len(arr) - i - 1): if arr[j] > arr[j + 1]: arr[j], arr[j + 1] = arr[j + 1], arr[j] return arr 请分析算法的时间复杂度，用O表示

A. O(1)

B. O(n)

C. O(n2)

D. O(nlogn)

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

11. 2. 百元买白鸡问题：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，则翁、母、雏各几何？设计一算法，则该算法的输入是（）

A. 100元

B. 100只鸡

C. 各种鸡的单价

D. 无需任何输入

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

12. 3. 调度问题的算法设计策略是（）

A. 加工时间短的优先安排

B. 加工时间长的优先安排

C. 等待时间短的优先安排

D. 以上都不对

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

13. 4. 背包问题的算法设计策略是（）

A. 重量小的优先装

B. 价值大的优先装

C. 单位重量价值大的优先装

D. 以上都不对

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

14. 5. 下述描述算法的方式采用的是算法的哪种描述方式（）？ 算法：gcd(m,n) 输入：非负整数m,n，其中m,n不全为0 输出：m与n的最大公约数 1.while m>0 do 2. r←n mod m 3. n ←m 4. m ←r 5.return n

A. 自然语言

B. 程序流程图

C. 伪码

D. 程序设计语言

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

15. 6. 汉诺塔问题的时间复杂度是（）。

A. n!

B. 2^n

C. 2n

D. logn

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

16. 7. 二分搜索（二分查找）算法的时间复杂度是（）。

A. n

B. logn

C. n^2

D. 2n

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

17. 8. 阶乘问题求n!算法的时间复杂度为（）。

A. n

B. n!

C. 2n

D. n^2

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

18. 9. 算法的基本特性不包括

A. 先进性

B. 有穷性

C. 有输入输出

D. 无二义性

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

19. 10. 算法的常见描述方式不包括

A. 代码

B. 甘特图

C. 伪代码

D. 流程图

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

20. 11. 渐进复杂性的含义是（）情况下的复杂性。

A. 在最佳输入情况下

B. 问题规模趋向于无穷

C. 在最坏输入情况下

D. 平均各种输入之后

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

21. 12. 平均时间复杂度是指

A. 各种情况时间复杂度按概率的加权平均

B. 最好情况和最坏情况的时间复杂度的算术平均

C. 各种情况时间复杂度按概率的算术平均

D. 出现可能性最高的情况下的时间复杂度

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

22. 13. 递归是指自己间接或直接调用自身

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

23. 14. n!的时间复杂度为O(n)

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

24. 15. 针对顺序查找算法，影响它时间复杂度的因素只有算法的输入序列

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

25. 16. logn2=θ(logn+5)

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

26. 17. 2n=O(3n)

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

27. 18. 10=θ(log10)

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

28. 19. 2n=O(100n2)

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

29. 20. def heap_adjust(L, start, end): temp = L[start] i = start j = 2 * i while j <= end: if (j < end) and (L[j] < L[j + 1]): j += 1 if temp < L[j]: L[i] = L[j] i = j j = 2 * i else: break L[i] = temp 上述代码的功能是堆调整，规模为n的堆，调整操作的时间复杂度是logn

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

30. 1. 合并排序的分治算法时间复杂度的是()

A. O(logn)

B. O(nlogn)

C. O(logn2)

D. O(n2)

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

31. 2. 分治算法核心就是分而治之,其中的“治”描述正确的是()。

A. 分治法通过治理小问题来治理大问题。

B. 分治法递归治理小问题。

C. 分治法需要将子问题的解归并成大问题的解。

D. 治理子问题时,会有重复性治理子问题的现象。

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

32. 3. 分治算法的基本思想描述正确的是()

A. 分治法将规模大的问题分解成规模较小的问题解决。

B. 分治法划分的小问题相互重叠。

C. 分治法一般采用递归的方法解决子问题。

D. 分治法划分的小问题规模小到一定程度时容易解决。

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

33. 4. 关于二分查找时间复杂度描述正确的是()

A. 二分查找算法最好情况下的时间复杂度为O(1).

B. 二分查找算法最坏情况下的时间复杂度为O(n).

C. 二分查找算法最坏情况下的时间复杂度为O(logn).

D. 二分查找算法平均情况下的时间复杂度为O(logn).

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

34. 5. 有关循环赛日程表分治算法描述正确的是()

A. 循环赛日程表给定2 k个运动员,采用2 k/2的方法将运动员分成两组。

B. 循环赛日程表算法先安排组内的赛程,再安排两组对打。

C. 循环赛日程表算法的边界条件是两个运动员,一天的比赛。

D. 循环赛日程表算法为2 k个运动员安排了2 k-1天的比赛。

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

35. 6. 有关合并排序的分治算法描述正确的是()

A. 合并排序A[left,right]的元素,采用的分解方法是(left+right)/2。

B. 合并排序A[left,right]的元素,采用的分解方法是(right-left)/2。

C. 合并排序A[left,right]的元素,需要治理规模大致等于(right-left+1)/2的两个子问题。

D. 合并排序需要将两个有序的子序列归并成一个有序的子序列。

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

36. 7. 有关快速排序的分治算法描述正确的是()。

A. 快速排序A[left,right],选取基准元素的方法,将待排序元素分解为两个子问题。

B. 快速排序基准元素的选取可以是待排序元素中的任何一个元素。

C. 快速排序划分的两个子问题规模大致相等。

D. 快速排序A[left,right],递归算法的边界条件是left≥right

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

37. 8. 关于快速排序分治算法时间复杂度描述正确的是()

A. 快速排序分治算法最好情况下的时间复杂度为O(nlogn).

B. 快速排序分治算法最坏情况下的时间复杂度为O(n 2).

C. 快速排序分治算法平均情况下的时间复杂度为O(n 2).

D. 二快速排序分治算法平均情况下的时间复杂度为O(nlogn).

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

38. 9. 大整数A和B的乘法,将A分成位数大致相等的两部分A1和A2 ，将B分成位数大致相等的两部分B1和B2,以下描述正确的是()。

A. 子问题的解归并为原问题解的方法为:A×B=10nA1B1+10n/2(A1B2+A2B1)+A2B2

B. 子问题的解归并为原问题解的方法为:A×B=10nA1B1+10n/2((A1-A2)(B2-B1)+A1B1+A2B2)+A2B2

C. 子问题的解归并为原问题解的方法为:A×B=10nA1B1+10n/2((A1+A2)(B1+B2)-A1B1-A2B2)+A2B2

D. 以上方法都不对。

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

39. 1. 有关分支限界法说法正确的是（）

A. 分支限界法是一种深度优先搜索的搜索算法

B. 分支限界法是一种“能进则进、进不了则换、换不了则退（回溯）”的搜索方法

C. 分支限界法是一种宽（广）度优先搜索的搜索算法

D. 分支限界法是一种最大效益或最小费用优先搜索的搜索算法

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

40. 2. 有关n皇后问题说法正确的是（）

A. 该问题的解的形式为(x1, x2, … , xn)，xi表示第i个皇后位于第i行、第xi列(i=1,2,3,...n)

B. 该问题的初始状态为：(0,0,...,0)

C. 该问题的解空间的组织结构可以是排列树，也可以是满n叉树。

D. 该问题能用回溯法求解

E. 该问题能用队列式分支限界法，也能用优先队列式分支限界法。

F. 该问题解向量中的任意两个分量xi,xj满足：xi≠xj且|i-j|≠|xi-xj|

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

41. 3. 下述有关分支限界法搜索过程描述错误的是（）

A. 当解空间结构是一棵树时，搜索从根开始

B. 搜索过程中，扩展节点一次性生成所有的孩子节点

C. 搜索过程中，舍弃导致不可行解和非最优解的节点

D. 搜索过程中，保留下来的孩子节点是可能导致可行解或最优解的节点

E. 搜索过程中，保留下来的孩子节点是活结点，被插入活结点表中。

F. 当活结点表为空时或找到所需要的解时，算法结束。

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

42. 4. 以下有关回溯法和分支限界法的描述中，正确的是（）

A. 回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解。

B. 回溯法以宽度优先或以最小耗费（最大效益）优先的方式搜索解空间树，而分支限界法则以深度优先的方式搜索解空间树。

C. 在分支限界法中，当前扩展结点一次性生成所有的孩子结点。

D. 在回溯法中，当前扩展结点选择其中某一个孩子结点进行扩展。

E. 回溯法中，每一个活结点最多只有一次机会成为扩展结点。

F. 分支限界法中，每一个活结点有可能多次成为扩展结点

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

43. 5. 有关0-1背包问题的分支限界法说法正确的是（）

A. 0-1背包问题可以用队列式分支限界法

B. 0-1背包问题可以用优先队列式分支限界法。

C. 0-1背包问题的约束条件是装入的背包重量小于等于背包容量

D. 0-1背包问题的限界条件可以是当前已装入背包的价值加上剩余物品的总价值大于当前找到的最大价值。

E. 0-1背包问题的限界条件可以是当前已装入背包的价值加上剩余物品装入剩余空间装入的最大价值大于当前找到的最大价值。

F. 0-1背包问题的优先队列式分支限界法也可以不设置节点的优先级。

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

44. 6. 有关旅行售货员问题的分支限界解法，说法错误的是（）

A. 旅行售货员问题可以用队列式分支限界法，也可以用优先队列式分支限界法

B. 旅行售货员问题可以用回溯法，也可以用分支限界法。

C. 旅行售货员问题的约束条件是当前城市和要去的城市之间有边相连。

D. 旅行售货员问题的限界条件可以是当前已走过的路径长度。

E. 旅行售货员问题的限界条件可以是当前已走过的路径长度加上未走过的城市最小出边权之和

F. 旅行售货员问题的优先队列式分支限界法优先级可以设置为当前已经走过的路径长度。

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

45. 7. 有关旅行售货员问题的分支限界法说法正确的是（）

A. 旅行售货员问题可以用队列式分支限界法，也可以用优先队列式分支限界法。

B. 旅行售货员问题的约束条件是当前城市和要去的城市之间有路相连。

C. 旅行售货员问题的限界条件可以是当前当前已走过的路径长度小于当前找到的最优路径长度。

D. 旅行售货员问题的限界条件可以是当前当前已走过的路径长度加上为走过的城市最小出边权之和小于当前找到的最优路径长度。

E. 旅行售货员问题的优先队列式分支限界法优先级可以设置为当前已走过的路径长度加上为走过的城市最小出边权之和。

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

46. 8. 有关布线问题的分支限界法说法正确的是（）

A. 布线问题可以用队列式分支限界法，也可以用优先队列式分支限界法。

B. 布线问题只能用队列式分支限界法。

C. 布线问题只能用优先队列式分支限界法。

D. 布线问题采用相对位移表示搜索的上、下、左、右四个方向。

E. 布线问题采用“围墙”技巧表示搜索的边界。

F. 布线问题不需要设置约束条件和限界条件

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

47. 9. 比较分支限界法和回溯法，两者的不同是（）

A. 在一般情况下，分支限界法与回溯法的求解目标不同

B. 分支限界法与回溯法的搜索方式不同

C. 分支限界法需要借助活结点表数据结构，而回溯法则不需要。

D. 扩展节点的扩展方式不同。

E. 回溯法需要确定搜索范围，分支限界法则不需要。

F. 分支限界法保留下来的活结点是有可能导致可行解或最优解的节点，回溯法则不是。

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

48. 10. 部落卫队问题。原始部落byteland中的居民们为了争夺有限的资源，经常发生冲突。几乎每个居民都有他的仇敌。部落酋长为了组织一支保卫部落的队伍，希望从部落的居民中选出最多的居民入伍，并保证队伍中任何2 个人都不是仇敌。给定byteland部落中居民间的仇敌关系，编程计算组成部落卫队的最佳方案。以下有关部落卫队问题说法正确的是（）

A. 该问题的解的形式为(x1,x2,...,x3)，xi(i-1,2,3,...,n)=0或1，0表示居民未被选入部落卫队，1表示居民被选入部落卫队。

B. 该问题的解空间组织结构为一棵排列树，规模为n时，树的深度为n。

C. 该问题可以用分支限界法求解，也可以用回溯法求解。

D. 该问题需要设置约束条件，也需要设置限界条件。

E. 将给定的仇敌关系图转换成它的补图，则成为友好关系图，部落卫队问题实质就是最大团问题。

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

49. 1. 以下算法设计模式中，哪个是排列树模型的算法设计模式（）

A. def Backtrack (t): if (t>n): output(x) else: for i in range(1,m+1): if (constraint(t) and bound(t)): x[t]=i 做其他相关标识 Backtrack(t+1) 做其他相关标识的反操作

B. def Backtrack (t): if (t>n): output(x) else: for i in range(t,n+1): x[t], x[i]←x[i], x[t] if (constraint(t) and bound(t)): Backtrack(t+1) x[t], x[i]←x[i], x[t]

C. def Backtrack (int t): if (t>=n): output(x) else: for i in range(s(n,t),e(n,t)): x[t]=d(i) if (constraint(t) and bound(t)): Backtrack(t+1)

D. def Backtrack (int t): if (t>n): output(x) if(constraint(t)): 做相关标识 Backtrack(t+1) 做相关标识的反操作 if(bound(t)): 做相关标识 Backtrack(t+1) 做相关标识的反操作

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

50. 2. 有关回溯法说法正确的是（）

A. 回溯法是一种深度优先搜索的搜索算法

B. 回溯法是一种“能进则进、进不了则换、换不了则退（回溯）”的搜索方法

C. 回溯法是一种宽（广）度优先搜索的搜索算法

D. 回溯法是一种最大效益或最小费用优先搜索的方法

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

51. 3. 有关n皇后问题说法正确的是（）

A. 该问题的解的形式为(x1, x2, … , xn)，xi表示第i个皇后位于第i行、第xi列(i=1,2,3,...n)

B. 该问题的初始状态为：(0,0,...,0)

C. 该问题的解空间的组织结构可以是排列树，也可以是满n叉树。

D. 该问题只需要设置约束条件，不需要限界条件。

E. 该问题解向量中的任意两个分量xi,xj满足：xi≠xj且|i-j|≠|xi-xj|

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

52. 4. 下述有关搜索过程描述错误的是（）

A. 当解空间结构是一棵树时，搜索从根开始

B. 搜索过程中，正在生成孩子的节点称为扩展节点

C. 搜索过程中，所有孩子节点均已生成的节点称为扩展节点

D. 搜索过程中，所有孩子节点均已生成的节点称为活结点节点

E. 搜索过程中，所有孩子节点均已生成的节点称为死节点

F. 搜索过程动态生成的树称为搜索树

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

53. 5. 以下描述中，影响回溯法的搜索效率的是（）

A. 问题的解空间，即搜索范围

B. 设定的约束函数和限界函数

C. 搜索方法

D. 满足约束条件和限界条件的节点数目

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

54. 6. 以下有关子集树的描述中说法正确的是（）

A. 当所给的问题是从n个元素组成的集合S中找出满足某种性质的一个子集时，相应的解空间树称为子集树。

B. 子集树模型解的形式为n元组（x1,x2,…,xn），分量xi(i=1,2,…,n)表示第i个元素是否在子集中。

C. 子集树模型的解向量中，分量xi的取值为0或1，xi=0表示第i个元素不在子集中；xi=1表示第i个元素在子集中。

D. 旅行售货员问题可以开用子集树模型求解

E. 最优装载问题可以采用子集树模型求解

F. 0-1背包问题可以采用子集树模型求解

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

55. 7. 有关子集树描述中，说法正确的是（）

A. 子集树的根结点为问题的初始状态

B. 子集树的中间结点为搜索过程中形成的某中间状态

C. 子集树的叶子结点为问题结束状态

D. 子集树的分支表示从一个状态过渡到另一个状态的行为

E. 子集树中从根结点到叶子结点的路径是一个可行解（一个子集）

F. 子集树的深度等于问题的规模加1

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

56. 8. 有关0-1背包问题说法正确的是（）

A. 该问题的解的形式为(x1, x2, … , xn)，xi(i=1,2,3,...n)的取值为0或1

B. 该问题的解空间的组织结构可以是排列树。

C. 该问题需要设置约束条件，也需要限界条件。

D. 该问题只需要设置约束条件，不需要限界条件。

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

57. 9. 有关最大团问题说法正确的是（）

A. 该问题的解的形式为(x1, x2, … , xn)，xi(i=1,2,3,...n)的取值为0或1

B. 该问题的解空间的组织结构是子集树，深度为n。

C. 该问题的约束条件为团里的任意两个顶点都有边相连

D. 该问题的限界条件为当前状态下在团里的顶点个数加上剩余未判定的顶点个数大于当前找到的最大团的顶点个数。

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

58. 10. 有关下图说法正确的是（）

A. 该树表示的问题的规模为3

B. 该树为一棵排列树

C. 该树表示的问题规模为4。

D. 该树为一棵子集树

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

59. 11. 有关批处理作业调度问题说法正确的是（）

A. 该问题的解形式为(x1,x2,…,xn)，xi取值范围为：令S={1,2,…,n}，则xi∈S-{x1,x2,…,xi-1}，i=1,2,...,n

B. 该问题的解空间的组织结构是排列树。

C. 该问题需要设置约束条件，不需要限界条件。

D. 该问题不需要设置约束条件，只需要限界条件。

E. 该问题既需要设置约束条件，也需要限界条件。

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

60. 12. 有关旅行售货员问题说法正确的是（）

A. 该问题的解形式为(x1,x2,…,xn)，xi取值范围为：令S={1,2,…,n}，则xi∈S-{x1,x2,…,xi-1}

B. 该问题的解空间的组织结构是排列树。

C. 该问题需要设置约束条件，不需要限界条件。

D. 该问题不需要设置约束条件，只需要限界条件。

E. 该问题既需要设置约束条件，也需要限界条件。

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

61. 13. 有关图的m着色问题说法正确的是（）

A. 该问题的解形式为(x1,x2,…,xn)，xi表示第i个顶点着xi号色，其取值范围为：令S={1,2,…,m}为颜色集合，则xi∈S

B. 该问题的解空间的组织结构是排列树。

C. 该问题需要设置约束条件，不需要限界条件。

D. 该问题不需要设置约束条件，只需要限界条件。

E. 该问题既需要设置约束条件，也需要限界条件。

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

62. 14. 有关最小重量机器设计问题说法正确的是（）

A. 该问题的解形式为(x1,x2,…,xn)，xi取值范围为：令S={1,2,…,n}，则xi∈S-{x1,x2,…,xi-1}

B. 该问题的解空间的组织结构是满m叉树。

C. 该问题需要设置约束条件，不需要限界条件。

D. 该问题不需要设置约束条件，只需要限界条件。

E. 该问题既需要设置约束条件，也需要限界条件。

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

63. 1. 0-1背包问题的跳跃点算法的时间复杂度为()

A. O(n 2)

B. O(2 n)

C. O(nW)

D. min(nW,2 n)

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

64. 2. 规模为5的有序序列,二叉搜索树共有()棵。

A. 14棵

B. 5棵

C. 40棵

D. 42棵

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

65. 3. n个工件加工顺序问题依据贝尔曼法则设计的动态规划算法的时间复杂度为()

A. O(n)

B. O(n 2)

C. O(nlogn)

D. O(logn)

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

66. 4. 规模为n,背包容量为W的0-1背包问题的动态规划算法的时间复杂度为()

A. O(n 2)

B. O(n2 n)

C. O(nW)

D. O(W 2)

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

67. 5. 有关最优二叉搜索树说法正确的是()

A. 最优二叉搜索树的左孩子的节点都比根节点小,右孩子节点都比根节点大。

B. 最优二叉搜索树的平均比较次数最少。

C. 最优二叉搜索树的平均比较次数最多。

D. 最优二叉搜索树中有n个是节点,n+1个虚节点。

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

68. 6. 有关工件加工顺序问题算法描述正确的是()

A. 该问题的子问题:M1开始处理S集合的工件时,M2需要t时间才能停下来情况下,加工S集合中的工件总加工时间最短,可以用T(S,t)表示最短的总加工时间。

B. 该问题的最短加工时间用T(S,t),则递推方程为:T(S,t)=min i∈S{t 1i+T(S-{i},max{t-t 1i,0}+t 2i)}

C. 该问题的动态规划算法依据Johnson Bellman’s Rule.

D. 该算法将第一台机器处理时间小于第二台机器处理时间的工件后安排加工,并按照第一台机器处理时间非降序排列的顺序加工。

E. 该算法将第一台机器处理时间大于等于第二台机器处理时间的工件后安排加工,并按照第二台机器处理时间非降序排列的顺序加工。

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

69. 7. 规模为n的0-1背包问题,有关子问题描述正确的是()

A. 子问题可以描述为规模为i的0-1背包问题,即:1...i共i个物品,背包容量为j

B. 用c[i][j]描述子问题:1...i共i个物品,背包容量为j的最优值(装入背包的最大价值),则其子问题为:1...i-1共i-1个物品,背包容量为j-w ix i的最优值为c[i-1][j-w i]。

C. 用c[i][j]描述子问题:1...i共i个物品,背包容量为j的最优值(装入背包的最大价值),则其子问题为:1...i-1共i-1个物品,背包容量为j-w ix i的最优值为c[i-1][j-w ix i],其中x i等0或1。

D. 用c[i][j]描述子问题:1...i共i个物品,背包容量为j的最优值(装入背包的最大价值),则其子问题为:1...i-1共i-1个物品,背包容量为j-w ix i的最优值为c[i-1][j]。

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

70. 8. 有关0-1背包问题的跳跃点算法描述正确的是()

A. 跳跃点(x,c[i][x])表示装入重量为x时,装入最大价值为c[i][x]。

B. 初始跳跃点为(0,0)。

C. 用p[i]描述c[i][j]的跳跃点,用q[i]描述p[i-1]+(w i,v i),则p[i+1]=p[i]∪q[i],其中i=1,2,...,n

D. 用p[i]描述c[i][j]的跳跃点,用q[i]描述p[i-1]+(w i,v i),则p[i+1]=p[i]∪q[i]去掉重量不减,价值反而减少的受控点。其中i=1,2,...,n

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

71. 9. 有关0-1背包问题,用c[i][j]描述子问题:1...i共i个物品,背包容量为j的最优值(装入背包的最大价值),则其子问题为:1...i-1共i-1个物品,背包容量为j-wixi,以下说法正确的是()

A. 当i=0时或j=0时,c[i][j]=0。

B. 当ji时,物品无法装入,其x i=0,则背包容量依旧为j,c]i][j]=c[i-1][j].

C. 当j≥w i时,物品可以装入,装呢还是不装呢?这取决于哪个决策能够让c[i][j]最小。故c]i][j]=min(c[i-1][j],c[i-1][j-w i]+v i)

D. 当j≥w i时,物品可以装入,装呢还是不装呢?这取决于哪个决策能够让c[i][j]最大。故c]i][j]=max(c[i-1][j],c[i-1][j-w i]+v i)

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

72. 1. 规模为5凸多边形三角剖分方法有()种。

A. 2

B. 5

C. 14

D. 15

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

73. 2. 有关规模为n+1的凸多边形(v0,v1,...,vn)最优三角剖分问题,设凸多边形vi-1...vj最优三角剖分的权函数之和为c[i][j],凸多边形vi-1...vj的子问题为:矩阵凸多边形vi-1...vk的最优三角剖分、矩阵凸多边形vk...vj的最优三角剖分和三角形vi-1vkvj,设vi-1vkvj是最优决策，则计算最优值的递推方程表示为()。

A. c[i][j]=c[i][k]+c[k][j]+w(vi-1vkvj)

B. c[i][j]=c[i-1][k]+c[k][j]+w(vi-1vkvj)

C. c[i][j]=c[i][k]+c[k+1][j]+w(vi-1vkvj)

D. 以上都不对

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

74. 3. 按照顺序排列动态规划的求解步骤,正确的是() （1)递归定义最优值。 （2)以自底向上的方式计算出最优值,并记录相关信息。 （3）分析最优解子结构性质。 （4)构造出最优解。

A. (1),(2),(3),(4)

B. (1),(3),(2),(4)

C. (3),(1),(2),(4)

D. (1),(2),(4),(3)

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

75. 4. 最长公共子序列问题的动态规划算法时间复杂度为()

A. O(nm)

B. O(mn 2)

C. O(nm 2)

D. O(lognm)

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

76. 5. 规模为5矩阵连乘问题,计算次序有()种。

A. 10

B. 12

C. 14

D. 16

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

77. 6. 有关矩阵连乘问题说法正确的是()

A. 矩阵A i...A j连乘,其中A k的行列为(p k×q k),k=i,i+1,...,j,其结果矩阵的行列为(p i×q j)。

B. n个矩阵连乘A 1...A n,其子问题为A i...A j连乘,1≤i≤j≤n,其中i=j表示规模为1的子问题,其需要的乘法次数为0。

C. 设矩阵A i...A j连乘最少的乘法次数为c[i][j],矩阵A i...A j连乘的子问题为矩阵A i...A k连乘和矩阵A k+1...A j连乘,则最优值的递归关系式表示为c[i][j]=c[i][k]+c[k+1][j]+p iq jq k

D. 矩阵连乘问题的时间复杂度为O(n 2)

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

78. 7. 有关最长公共子序列问题的动态规划算法说法正确的是()

A. X n和Y m的代表了两个长度为n和m的字符串,求X n和Y m的最长公共子序列的子问题是:求X i和Y j的最长公共子序列,i=0,1,...n,j=0,1,...,m。

B. X i和Y j的最长公共子序列当i=0时,最长公共子序列的长度为0;j=0时,最长公共子序列的长度也为0。

C. 设X i和Y j的最长公共子序列的长度c[i][j],求最优值的递归关系式为:c[i][j]=c[i-1][j]。

D. 设X i和Y j的最长公共子序列的长度c[i][j],求最优值的递归关系式为:c[i][j]=c[i-1][j]+1。

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

79. 8. 有关动态规划描述正确的是()

A. 动态规划将多阶段决策问题转化为单阶段决策问题。

B. 动态规划往往用于求解某种最优性质的问题。

C. 适用动态规划求解的问题经分解得到的各个子问题往往不是相互独立的。

D. 动态规划求解时往往采用填表的方法记录问题最优值。

E. 动态规划划分的各子问题与原问题相同,一般递归求解子问题。

F. 动态规划求解某种最优性质的问题时,整体的最优值和子问题的最优值之间存在递归关系。

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

80. 9. 有关凸多边形三角剖分问题说法正确的是()

A. n+1边形的凸多边形最优三角剖分问题与n个矩阵连乘问题。

B. n+1边形的凸多边形任意一种三角剖分方法可以用一棵二叉树唯一表示。

C. n+1边形的凸多边形V 0V 1...V n,其子问题为V i-1...V j连乘,0≤i≤j≤n,其中i=j表示一条直线,即退化的多边形,其三角形权函数为0。

D. 矩阵连乘问题的时间复杂度为O(n 3)

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

81. 10. 动态规划的基本要素是()

A. 重叠子问题

B. 最优子结构性质

C. 自底向上的求解方式

D. 自顶向下的递归求解方式

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

82. 1. 调度问题的算法设计策略是（）

A. 加工时间短的优先安排

B. 加工时间长的优先安排

C. 等待时间短的优先安排

D. 以上都不对

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

83. 2. 背包问题的算法设计策略是（）

A. 重量小的优先装

B. 价值大的优先装

C. 单位重量价值大的优先装

D. 以上都不对

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

84. 3. 算法的常见描述方式不包括

A. 代码

B. 甘特图

C. 伪代码

D. 流程图

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

85. 4. n个连续自然数a1...an连加和问题算法（利用等差数列求和公式）的输入可以是什么（）。

A. a1，n

B. an,n

C. a1,an

D. a1,an,n

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

86. 5. 算法的基本特征有（）

A. 输入

B. 输出

C. 有限性

D. 确定性

E. 可行性

答案：请关注【九八五题库】微信公众号，发送题目获取正确答案。

打赏

如果觉得文章对您有用，请随意打赏。
您的支持是我们继续创作的动力！

微信扫一扫

支付宝扫一扫