1、
2025年本科计算机科学与技术（算法设计与分析）试题及答案
（考试时间：90分钟 满分100分）
班级______ 姓名______
第I卷（选择题 共30分）
答题要求：本卷共6题，每题5分。每题只有一个选项符合题意，请将正确选项填在题后的括号内。
1. 以下关于算法的时间复杂度说法正确的是（ ）
A. 时间复杂度为O(n^2)的算法一定比时间复杂度为O(n)的算法运行速度慢
B. 时间复杂度是衡量算法执行时间随问题规模增长的变化趋势
C. 算法的时间复杂度只与问题规模有关，与算法的具体实现无关
D. 时间复杂度为O(log n)的算法是
2、对数阶算法，其效率比线性阶算法高很多
答案：B
2. 对一个有序数组进行二分查找，其时间复杂度为（ ）
A. O(n)
B. O(n^2)
C. O(log n)
D. O(n log n)
答案：C
3. 下列哪种排序算法在最坏情况下时间复杂度为O(n^2) （ ）
A. 快速排序
B. 归并排序
C. 冒泡排序
D. 堆排序
答案：C
4. 动态规划算法的基本思想是（ ）
A. 分而治之
B. 回溯法
C. 递归求解
D. 把原问题分解为子问题，通过求解子问题的解得到原问题的解
答案：D
5. 以下哪个不是贪心算法的特点（ ）
3、
A. 最优子结构性质
B. 贪心选择性质
C. 递归调用
D. 自顶向下求解
答案：C
6. 对于一个图的深度优先搜索遍历，以下说法错误的是（ ）
A. 深度优先搜索可能会陷入死循环
B. 深度优先搜索可以使用栈来实现
C. 深度优先搜索遍历的顺序与图的存储结构有关
D. 深度优先搜索遍历的时间复杂度为O(V+E)，其中V是顶点数，E是边数
答案：A
第II卷（非选择题 共70分）
二、填空题（每题5分，共20分）
答题要求：请在横线上填写正确答案。
1. 算法的五个重要特性是有穷性、确定性、输入、输出和______。
答案：可行性
4、
2. 选择排序算法在每一趟排序中从未排序的元素序列中选择一个最小（或最大）的元素，与未排序序列的______位置的元素交换。
答案：第一个
3. 动态规划算法求解问题时，通常需要建立一个______来保存子问题的解。
答案：表格（或数组等类似表述）
4. 图的广度优先搜索遍历类似于树的______遍历。
答案：层次
三、简答题（每题10分，共20分）
答题要求：简要回答问题，语言要简洁明了。
1. 简述分治法的基本步骤。
答案：分治法的基本步骤包括：分解，将原问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题；解决，若子问题规模较小而容易被解决
5、则直接解，否则递归地解各个子问题；合并，将各个子问题的解合并为原问题的解。
2. 简述快速排序算法的基本思想。
答案：快速排序的基本思想是选择一个基准元素，通过一趟排序将数组分为两部分，使得左边部分的元素都小于等于基准元素，右边部分的元素都大于等于基准元素。然后对左右两部分分别递归地进行排序，最终得到一个有序的数组。
四、算法设计题（每题15分，共30分）
答题要求：根据题目要求设计算法，描述算法的主要步骤和思路。
1. 给定一个整数数组，设计一个算法找出数组中出现次数超过一半的元素（假设数组中一定存在这样的元素）。
答案：可以采用摩尔投票法。遍历数组，用一个变量co
6、unt记录当前元素的出现次数，初始时count为1，当前元素设为候选元素。遍历过程中，如果遇到相同元素，count加1；遇到不同元素，count减1。当count为0时，更换候选元素并将count设为1。遍历结束后，候选元素即为出现次数超过一半的元素。因为出现次数超过一半的元素在抵消其他元素后，最终会剩下。
2. 有n个活动，每个活动有开始时间和结束时间，设计一个算法找出最多的相互兼容的活动集合。
答案：首先将活动按照结束时间从小到大排序。然后从第一个活动开始，依次选择活动。选择一个活动后，后续只能选择结束时间大于等于当前活动结束时间的活动。这样可以保证选择的活动相互兼容，并且能得到最
7、多的相互兼容的活动集合。因为按照结束时间排序后，优先选择结束早的活动，能为后续活动留出更多空间。
五、综合分析题（共10分）
答题要求：阅读材料，回答问题，分析要全面深入。
材料：有一个算法用于解决背包问题：给定一个背包的容量为C，有n个物品，每个物品有重量wi和价值vi。目标是选择一些物品放入背包，使得背包中物品的总价值最大且总重量不超过背包容量C。现有如下算法：对每个物品计算其单位重量价值vi/wi，然后按照单位重量价值从高到低对物品进行排序。接着从单位重量价值高的物品开始依次放入背包，直到背包不能再放入物品为止。
1. 分析该算法的正确性。
答案：该算法的基本思路
8、是合理的。通过计算单位重量价值并排序，优先选择单位重量价值高的物品放入背包，在一定程度上能够使背包中物品的总价值最大。因为单位重量价值高的物品能在相同重量下带来更多价值。但该算法并不一定能保证得到最优解。例如，可能存在一些物品虽然单位重量价值不是最高，但组合起来能达到更高的总价值，而该算法可能会因为只关注单位重量价值而错过这些组合。
2. 分析该算法的时间复杂度。
答案：该算法首先需要计算n个物品的单位重量价值，时间复杂度为O(n)。然后对n个物品按照单位重量价值进行排序，排序的时间复杂度为O(n log n)。最后依次放入物品，最多放入n次，每次判断背包是否能放入物品时间复杂度为O(1)，这部分时间复杂度为O(n)。所以总的时间复杂度为O(n log n)。
浙ICP备2021020529号-1 | 浙B2-20240490 
