算法设计与分析

学校: 无

原文来源：公众号【江开搜题】

原文来源：公众号【江开搜题】

原文来源：公众号【江开搜题】

问题 1: 1. 动态规划算法的基本要素为（ ）。

选项:

A. 预排序与递归调用

B. 重叠子问题性质与贪心选择性质

C. 最优子结构性质与重叠子问题性质

D. 最优子结构性质与贪心选择性质

答案: 最优子结构性质与重叠子问题性质

问题 2: 2. 二分搜索算法是利用（ ）实现的算法。

选项:

A. 动态规划法

B. 回溯法

C. 分治策略

D. 贪心法

答案: 分治策略

问题 3: 3. FIFO是（ ）的一搜索方式。

选项:

A. 分治界限法

B. 动态规划法

C. 贪心法

D. 回溯法

答案: 分治界限法

问题 4: 4. 秦始皇吞并六国使用的远交近攻，逐个击破的连横策略采用了以下哪种算法思想？（ ）。

选项:

A. 迭代

B. 分治

C. 递归

D. 模拟

答案: 分治

问题 5: 5. 最长公共子序列算法利用的算法是（ ）。

选项:

A. 分支界限法

B. 回溯法

C. 动态规划法

D. 贪心法

答案: 动态规划法

问题 6: 6. 下列算法中通常以自底向上的方式求解最优解的是（ ）。

选项:

A. 回溯法

B. 备忘录法

C. 动态规划法

D. 贪心法

答案: 动态规划法

问题 7: 7. 衡量一个算法好坏的标准是（ ）。

选项:

A. 代码短

B. 占用空间少

C. 运行速度快

D. 时间复杂度低

答案:

问题 8: 8. 以下不可以使用分治法求解的是（ ）。

选项:

A. 选择问题

B. 归并排序

C. 棋盘覆盖问题

D. 0/1背包问题

答案:

问题 9: 9. 实现循环赛日程表利用的算法是（ ）。

选项:

A. 贪心法

B. 动态规划法

C. 回溯法

D. 分治策略

答案:

问题 10: 10. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ ）。

选项:

A. 最优子结构性质

B. 定义最优解

C. 重叠子问题

D. 贪心选择性质

答案:

问题 11: 11. 实现最大子段和利用的算法是（ ）。

选项:

A. 动态规划法

B. 贪心法

C. 回溯法

D. 分治策略

答案:

问题 12: 12. 实现棋盘覆盖算法利用的算法是（ ）。

选项:

A. 回溯法

B. 动态规划法

C. 贪心法

D. 分治法

答案:

问题 13: 13. 实现合并排序利用的算法是（ ）。

选项:

A. 贪心法

B. 分治策略

C. 动态规划法

D. 回溯法

答案:

问题 14: 14. 下列是动态规划算法基本要素的是（ ）。

选项:

A. 子问题重叠性质

B. 构造最优解

C. 算出最优解

D. 定义最优解

答案:

问题 15: 15. 对线性表进行二分查找时，要求线性表必须（ ）。

选项:

A. 以顺序方式存储

B. 以链接方式存储

C. 以链接方式存储，且结点按关键字有序排序

D. 以顺序方式存储，且结点按关键字有序排序

答案:

问题 16: 16. 分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决子问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题（ ）。

选项:

A. 问题规模不同，问题性质相同

B. 问题规模相同，问题性质相同

C. 问题规模相同，问题性质不同

D. 问题规模不同，问题性质不同

答案:

问题 17: 17. 所有的递归函数都能找到对应的非递归定义。

选项:

A. 错误

B. 正确

答案:

问题 18: 18. 定义递归函数时可以没有初始值。

选项:

A. 正确

B. 错误

答案:

问题 19: 19. 动态规划算法基本要素的是最优子结构。

选项:

A. 错误

B. 正确

答案:

问题 20: 20. 回溯法中限界函数的目的是剪去得不到最优解的子树。

选项:

A. 正确

B. 错误

答案:

问题 21: 21. 动态规划算法求解问题时，分解出来的子问题相互独立。

选项:

A. 错误

B. 正确

答案:

问题 22: 22. 选择排序、插入排序和归并排序算法中， 算法是分治算法。

选项:

答案:

问题 23: 23. 动态规划算法中存储子问题的解是为了

选项:

答案:

问题 24: 24. 随机算法的一个基本特征是对于同一组输入，不同的运行可能得到 的结果

选项:

答案:

问题 25: 25. 在快速排序、插入排序和合并排序算法中， 算法不是分治算法。

选项:

答案:

问题 26: 26. 下列是基于分治策略的二分查找算法的部分代码，请补全空格中的缺失代码。 int BinarySearch( int ArrayData[], int left, int right, int *x ) { if ( left > right ) return -1; int middle = ; if ( *x == ArrayData[ middle ] ) return middle; if ( *x > ArrayData[ middle ] ) return BinarySearch( ); else return BinarySearch( ); }

选项:

答案:

问题 27: 27. 应用Johnson法则的流水作业调度采用的算法是（ ）。

选项:

A. 分治法

B. 分支限界法

C. 贪心算法

D. 动态规划算法

答案:

问题 28: 28. 下列不是动态规划算法基本步骤的是（ ）。

选项:

A. 算出最优解

B. 构造最优解

C. 找出最优解的性质

D. 定义最优解

答案:

问题 29: 29. k带图灵机的空间复杂性S(n)是指（ ）。

选项:

A. k带图灵机处理所有长度为n的输入时，在k条带上所使用过的平均方格数。

B. k带图灵机处理所有长度为n的输入时，在k条带上所使用过的方格数的总和。

C. k带图灵机处理所有长度为n的输入时，在某条带上所使用过的最大方格数。

D. k带图灵机处理所有长度为n的输入时，在某条带上所使用过的最小方格数。

答案:

问题 30: 30. 最大效益优先是（ ）的一搜索方式。

选项:

A. 分支界限法

B. 回溯法

C. 贪心法

D. 动态规划法

答案:

问题 31: 31. 若对一个问题的求解可转化为对其性质相同的子问题的求解，则称该问题满足 。

选项:

答案:

问题 32: 32. 秦始皇吞并六国使用的远交近攻，逐个击破的连横策略采用了以下哪种算法思想？（ ）。

选项:

A. 递归

B. 迭代

C. 模拟

D. 分治

答案:

问题 33: 33. k带图灵机的空间复杂性S(n)是指（ ）。

选项:

A. k带图灵机处理所有长度为n的输入时，在某条带上所使用过的最大方格数。

B. k带图灵机处理所有长度为n的输入时，在k条带上所使用过的平均方格数。

C. k带图灵机处理所有长度为n的输入时，在k条带上所使用过的方格数的总和。

D. k带图灵机处理所有长度为n的输入时，在某条带上所使用过的最小方格数。

答案:

问题 34: 34. 选择排序、插入排序和归并排序算法中，

选项:

答案:

问题 35: 35. 若对一个问题的求解可转化为对其性质相同的子问题的求解，则称该问题满足

选项:

答案:

问题 36: 36. 动态规划算法中存储子问题的解是为了

选项:

答案:

问题 37: 37. 随机算法的一个基本特征是对于同一组输入，不同的运行可能得到

选项:

答案:

问题 38: 38. 在快速排序、插入排序和合并排序算法中，

选项:

答案:

问题 39: 39. 下列是基于分治策略的二分查找算法的部分代码，请补全空格中的缺失代码。 int BinarySearch( int ArrayData[], int left, int right, int *x ) { if ( left > right ) return -1; int middle =

选项:

答案: