第8章 算法设计与分析
题库 9 · 章节 76 · 共 17 题
1. 若某算法在问题规模为 
时，其基本操作的重复次数可由下式表示，则该算法的时间复杂度为______。 
- A.
- B.
- C.
- D.
答案：B
解析：
本题考查复杂度计算基础知识。
根据题中给出的递归定义式进行推导，可得 
，因此时间复杂度为 。
难度 2 · 作答 1507 次 · 正确率 49.8%
2. 某算法的时间复杂度可用递归式 
表示，若用 
表示，则正确的是______。
- A.
- B.
- C.
- D.
答案：A
解析：
本题考查复杂度计算基础知识。
（主定理分析）设 
和 
为常数， 
为函数， 
为定义在非负整数上的递归式， 
，其中 
，那么 可能有如下的渐进紧致界。（1）若对于常数 
，有 
，则 
。（2）若 
，则 
。（3）若对于常数 ，有 
，则对于常数 
与所有足够大的 有 
，则 
。
根据主定理分析，题中 
，属于第一种情况，因此有 
。
难度 2 · 作答 1441 次 · 正确率 60.2%
3. （复合题 1/2）（1）正确的选项是?
共用题干： 已知算法A的运行时间函数为
，其中
，其中
- A.
- B.
- C.
- D.
答案：D
解析：
本题考查复杂度计算基础知识。
（主定理分析）设 和 为常数， 为函数， 为定义在非负整数上的递归式， ，其中 ，那么 可能有如下的渐进紧致界。（1）若对于常数 ，有 ，则 。（2）若 ，则 。（3）若对于常数 ，有 ，则对于常数 与所有足够大的 有 ，则 。
根据主定理分析，先计算算法A的时间复杂度， 
，而 
，因此时间复杂度为 ，然后计算算法B的复杂度， 
，而 ，若算法B和算法A的效率一样，则 
，现在要求算法B比算法A快，则X应该比64小，因此X的最大值为63。
难度 2 · 作答 1549 次 · 正确率 61.0%
4. （复合题 2/2）（2）正确的选项是?
共用题干： 已知算法A的运行时间函数为
- A. 15
- B.
- C.
- D. 65
答案：C
解析：
本题考查复杂度计算基础知识。
（主定理分析）设 和 为常数， 为函数， 为定义在非负整数上的递归式， ，其中 ，那么 可能有如下的渐进紧致界。（1）若对于常数 ，有 ，则 。（2）若 ，则 。（3）若对于常数 ，有 ，则对于常数 与所有足够大的 有 ，则 。
根据主定理分析，先计算算法A的时间复杂度， ，而 ，因此时间复杂度为 ，然后计算算法B的复杂度， ，而 ，若算法B和算法A的效率一样，则 ，现在要求算法B比算法A快，则X应该比64小，因此X的最大值为63。
难度 2 · 作答 1493 次 · 正确率 74.3%
5. 要在 
的棋盘上摆放 
个"皇后"，要求"皇后"之间不能发生冲突，即任何两个"皇后"不能在同一行、同一列和相同的对角线上，则一般采用______来实现。
- A. 分治法
- B. 动态规划法
- C. 贪心法
- D. 回溯法
答案：D
解析：
本题考查算法设计与分析基础知识。 N-皇后问题是一个经典的计算问题，该问题基于一些约束条件来求问题的可行解。该问题不易划分为子问题求解，因此分治法不适用;由于不是要求最优解，因此不具备最优子结构性质，也不宜用动态规划法和贪心法求解。而系统搜索法——回溯法可以有效地求解该问题。
难度 2 · 作答 1249 次 · 正确率 54.0%
6. 在有n个无序无重复元素值的数组中查找第i小的数的算法描述如下:任意取一个元素r，用划分操作确定其在数组中的位置，假设元素r为第k小的数。若i等于 k，则返回该元素值;若i小于k，则在划分的前半部分递归进行划分操作找第i小的数;否则在划分的后半部分递归进行划分操作找第k-1小的数。该算法是一种基于______策略的算法。
- A. 分治
- B. 动态规划
- C. 贪心
- D. 回溯
答案：A
解析：
本题考查算法的设计与分析基础知识。 从题干可以看出，划分操作与快速排序中的划分操作是一样的，确定某个元素如r的最终位置，划分后，在r之前的元素都小于r，在r之后的元素都大于r(假设无重复元素)。因此可以据此确定r是数组中第几小的数。题干所述的算法把找第i小的数转换为确定任意一个元素是第几小的数，然后根据这个结果再在依据该元素划分后得到的结果在前一部分还是后一部分来继续确定某个元素为第几小的数，重复这种处理，直到找到第i小的数。这是分治策略的一个典型应用。
难度 2 · 作答 1140 次 · 正确率 77.5%
7. （复合题 1/2）（1）正确的选项是?
共用题干： 在求解某问题时，经过分析发现该问题具有最优子结构性质，求解过程中子问题被重复求解，则采用（1）算法设计策略;若定义问题的解空间，以深度优先的方式搜索解空间，则采用（2）算法设计策略。
- A. 分治
- B. 动态规划
- C. 贪心
- D. 回溯
答案：B
解析：
本题考查算法分析与设计基础知识。 存在几种常用的算法设计策略:分治法、动态规划、贪心、回溯发和分支限界法等。其中，分治法一般用于将大问题分解为一个或多个规模较小的子问题，通常采用自顶向下的递归方法来求解。动态规划求解问题的特征是，问题具有最优子结构和重叠子问题，求解时一般采用自底向上的方法来进行。贪心法求解问题的特征是，问题具有最有子结构和贪心选择性质，求解时可以用自底向上或自顶向下的方法进行。回溯法和分支限界法是系统搜索解空间来求解问题的方法，一般先定义解空间，前者以深度优先的方式搜索，后者通常以广度优先的方式搜索。
难度 2 · 作答 1600 次 · 正确率 68.4%
8. （复合题 2/2）（2）正确的选项是?
共用题干： 在求解某问题时，经过分析发现该问题具有最优子结构性质，求解过程中子问题被重复求解，则采用（1）算法设计策略;若定义问题的解空间，以深度优先的方式搜索解空间，则采用（2）算法设计策略。
- A. 动态规划
- B. 贪心
- C. 回溯
- D. 分支限界
答案：C
解析：
本题考查算法分析与设计基础知识。 存在几种常用的算法设计策略:分治法、动态规划、贪心、回溯发和分支限界法等。其中，分治法一般用于将大问题分解为一个或多个规模较小的子问题，通常采用自顶向下的递归方法来求解。动态规划求解问题的特征是，问题具有最优子结构和重叠子问题，求解时一般采用自底向上的方法来进行。贪心法求解问题的特征是，问题具有最有子结构和贪心选择性质，求解时可以用自底向上或自顶向下的方法进行。回溯法和分支限界法是系统搜索解空间来求解问题的方法，一般先定义解空间，前者以深度优先的方式搜索，后者通常以广度优先的方式搜索。
难度 2 · 作答 1610 次 · 正确率 65.4%
9. 采用贪心策略求解______问题，一定可以得到最优解。
- A. 分数背包
- B. 0-1背包
- C. 旅行商
- D. 最长公共子序列
答案：A
解析：
贪心法的典型实例: ①活动选择问题 活动选择问题是指若干个具有竞争性的活动要求互斥使用某一公共资源时如何选择最大的相容活动集合。 ②背包问题 与0-1背包问题不同的是，在背包问题里，每个物品可以部分装入背包。
难度 2 · 作答 1448 次 · 正确率 50.6%
10. 以下的算法设计方法中，______以获取问题最优解为目标。
- A. 回溯方法
- B. 分治法
- C. 动态规划
- D. 递推
答案：C
解析：
本题考查算法设计与分析基础知识。 回溯法的实质是在包含问题的所有解的解空间树中，按照深度优先的策略，从根节点出发搜索解空间树。若进入某子节点的子树后没有找到解(或者需要找出全部解)，则需要从子节点回退(回溯)至父节点，从而可以选择其他子节点进行搜索。回溯法有"通用的解题法"之称，用它可以系统地搜索一个问题的所有解或任一解。 分治与递归就像一对孪生兄弟，经常同时应用于算法设计之中。分治的思路是将一个难以直接解决的大问题分解成一些规模较小的相同问题，以便各个击破，分而治之。如果规模为n的问题可分解成k个子问题，1<k≤n，这些子问题互相独立且与原问题相同。 动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是独立的。若用分治法来解这类问题，则相同的子问题会被求解多次，以至于最后解决原问题需要耗费指数级时间。动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解，每个解都对应于一个值，我们希望找到具有最优值(最大值或最小值)的那个解。
难度 2 · 作答 1202 次 · 正确率 77.8%
11. 归并排序采用的算法设计方法属于______。
- A. 归纳法
- B. 分治法
- C. 贪心法
- D. 回溯法
答案：B
解析：
本题考查归并排序与算法基础知识。 以2-路归并排序为例进行说明。2-路归并是指将两个有序序列合并成一个有序序列，其基本过程为:从两个序列中各取一个元素，进行比较，输出较小的元素，从较小元素所在序列取下一个元素，与未输出的那个元素比较，输出较小者。依此类推，直到输出序列包含了两个初始有序序列的全部元素。 对于一个初始无序的序列，可以先将其等分为两个无序的子序列，对这两个子序列再次二分，重复该过程，直到分出的子序列中仅包含一个元素时(一个元素自然是有序的)为止，然后再反复进行2-路归并的过程，最后完成排序。
难度 2 · 作答 1257 次 · 正确率 74.1%
12. ______算法策略与递归技术的联系最弱。
- A. 分治
- B. 动态规划
- C. 贪心
- D. 回溯
答案：C
解析：
本题考查对递归算法的理解。 分治法:对于一个规模为n的问题，若该问题可以容易地解决（如说规模n较小）则直接解决否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。 动态规划法:这种算法也用到了分治思想，它的做法是将问题实例分解为更小、相似的子问题，并存储子问题的解而避免计算重复的子问题。 贪心算法:它是一种不追求最优解，只希望得到较为满意解的方法。贪心算法一般可以快速得到满意的解，因为它省去了为找到最优解而穷尽所有可能所必须耗费的大量时间。贪心算法常以当前情况为基础做最优选择，而不考虑各种可能的整体情况，所以贪心算法不要回溯。 回溯算法（试探法）:它是一种系统地搜索问题的解的方法。回溯算法的基本思想是从一条路往前走，能进则进，不能进则退回来，换一条路再试。其实现一般要用到递归和堆栈。 以上算法中的分治法和动态规划法通常要用到回溯算法，而回溯算法又一般要用到递归，所以只有贪心算法与递归技术联系最弱。
难度 2 · 作答 1368 次 · 正确率 55.1%
13. （复合题 1/2）（1）正确的选项是?
共用题干： 快速排序算法在排序过程中，在待排序数组中确定一个元素为基准元素，根据基准元素把待排序数组划分成两个部分，前面一部分元素值小于等于基准元素，而后面一部分元素值大于基准元素，再分别对前后两个部分进行进一步划分。根据上述描述，快速排序算法采用了（1）算法设计策略。已知确定基准元素操作的时间复杂度为
- A. 分治
- B. 动态规划
- C. 贪心
- D. 回溯
答案：A
解析：
快速排序采用分治法的思想。快速排序在最好情况下的时间复杂度为 
;在最坏情况下，即初始序列按关键字有序或基本有序时，时间复杂度为 。
难度 2 · 作答 1401 次 · 正确率 83.6%
14. （复合题 2/2）（2）正确的选项是?
共用题干： 快速排序算法在排序过程中，在待排序数组中确定一个元素为基准元素，根据基准元素把待排序数组划分成两个部分，前面一部分元素值小于等于基准元素，而后面一部分元素值大于基准元素，再分别对前后两个部分进行进一步划分。根据上述描述，快速排序算法采用了（1）算法设计策略。已知确定基准元素操作的时间复杂度为
- A. 和
- B. 和
- C. 和
- D. 和
答案：D
解析：
快速排序采用分治法的思想。快速排序在最好情况下的时间复杂度为 ;在最坏情况下，即初始序列按关键字有序或基本有序时，时间复杂度为 。
难度 2 · 作答 1478 次 · 正确率 55.7%
15. （202505）以下问题中，肯定可以用贪心算法求得最优解的是 。
- A. 0-1背包
- B. 部分背包
- C. 旅游问题
- D. 公共子序列
答案：B
解析：
贪心算法适用场景： ①活动选择问题 活动选择问题是指若干个具有竞争性的活动要求互斥使用某一公共资源时如何选择最大的相容活动集合。 ②背包问题（分数背包） 与0-1背包问题不同的是，在背包问题里，每个物品可以部分装入背包。
难度 1 · 作答 789 次 · 正确率 73.6%
16. (202511)以下代码的时间复杂度是 。 for(i = 0;i < n;i++){ j = 1; while(j < n){ j = j * 2; } }
- A. logn
- B. n2
- C. nlogn
- D. 2n
答案：C
解析：
循环体为j = j * 2;循环次数为nlogn次，因此时间复杂度为nlogn次。
难度 1 · 作答 421 次 · 正确率 62.0%
17. 2026上半年 某算法的时间复杂度由递归式 T(n)=2T(n/2)+nlogn定义，其渐近紧致界为 。
- A. (n2)
- B. (n log n)
- C. (n log2n)
- D. (n2 logn)
答案：C
解析：
难度 1 · 作答 183 次 · 正确率 38.8%