算法设计与分析 26春 期末考试
本文最后更新于 2026年6月28日 上午
不定项选择 15*2%
少选多选漏选错选均不得分
重点：排序的稳定性，属于什么解决方法
什么问题属于什么解决方法（比如合并排序属于分治）
题目我想不起来了，但是你可以做的：给 LLM 发送这段 Prompt：
这是我们这门课的考试的题型：
算法课考试题型
第一大题：不定项选择题，15题，每题2分,共30分。四个选项，可以选1~4个，少选多选漏选错选均不得分
第二大题：简答题，4题，共28分。
第三大题：算法应用题,4题,共42分。
复习与答题要点
简答题务必扣住题目核心,只写关键词,不要东拉西扯、不要靠堆字数凑分,达不到核心就赶紧做其他题。
算法应用题若要求写算法思想,题目没指定形式时可自由发挥(伪代码、流程图、自然语言、代码均可);若题目明确要求某种形式,就按要求来。
请你先帮我生成30个不定项选择，不定项选择大部分以考察概念为主。我要自己练习。我希望最好是交互式的，如果不能是，那也可以是先给我题目和答案分离。
再加之以课件，可以生成和考试的不定项很相似的多选（本人亲测）。
简答题 28%
1
- 简述分治法和减治法的思想
- 各举两个例子
2
- 一个问题能用动态规划求解，需要满足哪两个条件？
- 说明这两个条件
3
考虑经典的找零问题，有[1, 3, 4]这三种面额，需要找6元，最少的方案：
- 使用贪心求解，说明贪心的思路，给出结果
- 给出正确的结果
- 解释为什么贪心无法得到正确结果
4
- 阐述分支限界法和回溯法的区别
- 各举一例使用这两种方法能解决的问题
- 解释为什么分支界限法通常效率较高
算法题 42%
给的数据记不太清楚了，让 AI 编的，题目的意思都是对的。
1 8%
司机开车，一路上有n个收费站，抵达第i个收费站，需要收费cost[i]。司机一次最多往前开 1 或 2 个收费站。设计一个动态规划算法求解到达第n个收费站的最低花费。
2 14%
某公司有若干个独立项目需要完成。每个项目完成后可以获得一定奖金，但项目必须在其截止时间之前或当天完成，才能获得对应奖金。已知每个项目都需要连续工作 1 天 才能完成，并且每天最多只能完成 1 个项目。如果某个项目未能在其截止时间前完成，则不能获得该项目奖金。
现有 7 个项目，其截止时间和奖金如下表所示：
| 项目 | 截止时间 (d_i) | 奖金 (p_i) |
|---|---|---|
| A | 1 | 35 |
| B | 2 | 30 |
| C | 2 | 25 |
| D | 1 | 20 |
| E | 3 | 45 |
| F | 3 | 15 |
| G | 2 | 40 |
请完成以下问题：
（1）建立数学模型。 将该问题抽象为一个优化问题，定义必要的变量，并说明约束条件是什么、优化目标是什么。
（2）设计高效算法。 请设计一个高效算法来求解该问题，使得在满足截止时间限制的前提下，获得的总奖金最大。要求说明算法的基本思想和具体步骤。
（3）用所设计算法求解上述实例。 请按照第（2）问中的算法，对表中 7 个项目进行调度，写出每一步的选择过程，最终给出应完成的项目顺序以及可获得的最大奖金。
（4）分析算法复杂度。 请分析所设计算法的时间复杂度。
3 10%
题目：正整数序列的逆序数问题
给定一个长度为 $n$ 的正整数序列： $$ A = (a_1, a_2, \dots, a_n) $$ 若存在一对下标 $(i, j)$，满足：
$1 \leq i < j \leq n$ 且 $a_i > a_j$
则称 $(a_i, a_j)$ 是序列中的一个逆序对。序列中所有逆序对的总数称为该序列的逆序数。
例如，对于序列：
$A = (7, 3, 5, 2, 6, 1)$
其中存在若干逆序对，如 $(7,3)、(7,5)、(3,2)、(6,1)$ 等。要求计算该序列的逆序数。
请完成以下问题：
（1）蛮力法及其复杂度分析。 说明如何用蛮力法求给定正整数序列的逆序数，并分析该方法的时间复杂度。
（2）设计高效算法。 请设计一个比蛮力法更高效的算法来求解该问题。要求说明算法的基本思想和具体步骤。
（3）递推式与复杂度分析。 根据第（2）问所设计的算法，写出其时间复杂度的递推式，并求解该递推式，得到算法的渐进时间复杂度。
4 10%
某企业计划从 6 个备选研发项目中选择若干个进行投资。每个项目一旦选择，就必须完整投入所需预算，不能只投入其中一部分；每个项目最多只能选择一次。企业本年度可用于研发项目的总预算为 20 万元。
各项目所需预算和预计产出价值如下表：
| 项目 | 所需预算 | 预计产出价值 |
|---|---|---|
| A | 7 | 49 |
| B | 4 | 40 |
| C | 8 | 40 |
| D | 5 | 45 |
| E | 3 | 18 |
| F | 6 | 48 |
要求在总预算不超过 20 的前提下，选择若干项目，使得总预计产出价值最大。
（1）使用动态规划算法求解该问题的最大产出价值。要求给出状态表示、状态转移方程和边界条件
（2）使用优先队列式分支限界法求解该问题。要求自行设计合适的结点优先级函数或限界函数，并说明该函数为什么可以作为搜索时的上界。每个结点应至少包含：当前考虑到的项目编号、当前已用预算、当前已获得产出价值、当前价值上界以及已选择项目的情况。
在搜索过程中，用最大优先队列保存活结点，每次选择优先级最高的结点作为下一个扩展结点。请写出主要搜索过程，说明哪些结点可以被剪枝，并最终给出最优项目集合和最大产出价值。