# 判断题

1. 算法能直接在计算机上执行。（×）
2. 对稀疏图，Kruskal 算法比 Prim 算法有效。（√）
3. 算法的时间复杂度一定与输入序列有关。（×）
4. 分治法中，子问题一般不相互独立。（×）
5. 回溯法和分支限界法中，两种算法的当前扩展结点的扩展方式相同。（×）
6. 价值大的物品优先装入背包。（×）
7. 单位重量的价值大物品优先装入背包。（√）
8. 所有 NP 完全问题都属于 NP 类问题。（√）
9. P 类问题和 NP 完全问题有交集。（×）
10. NP 完全问题中若一个问题在多项式时间内能够解决，则所有的 NP 问题都能在多项式时间内解决。（√）

# 填空题

1. 时间复杂度表达式 $T(n) = 30n^3 + 20n^2 + 40n + 100$，它的渐进意义符号为_____
2. 用于描述算法的三种工具是自然语言、程序语言、___
3. 给定一个网络 $G = (V, E)$ 及其上的可行流 flow。假设网络 $G$ 上的某条边 $(v, w)$ 的流量为 0，容量为 105，那么该边对应于残流网络中同方向的一条边，它的容量为_____
4. 给定 $n$ 个城市交通图，起点为 1 号城市，旅行售货员问题的解空间树是_____
5. 分支限界法中，从活结点表中选择下一个扩展结点的不同方式导致了不同的分支限界法，最常见的有队列式分支限界法和_____
6. 二分查找的时间复杂度为_____
7. 用 $A[1:n]$ 表示 $A_1 \cdots A_n$ 连乘，给定 $A[1:10]$，用动态规划算法求解时，用来存储各子问题最优值的二维数组共有___个存储单元。
8. 矩阵：$M_1(5 \times 10), M_2(10 \times 4), M_3(4 \times 6)$。矩阵链乘 $M_1M_2M_3$ 需要的最少乘法次数为_____
9. 用___方法对状态空间树进行搜索时，每个结点有可能多次成为扩展结点。
10. 回溯法求 $n$ 个顶点的图的 $m$ 着色问题，最坏情况下时间复杂度是_____

• $O(n^3)$
• 流程图
• 105
• 排列树
• 优先队列式分支限界法
• $O(\log n)$
• 100
• 320
• 深度优先搜索
• $O(m^n)$

# 简答题

1. 贪心算法包括哪些内容？
2. 单源最短路径问题的 Dijkstra 算法内容有哪些？
3. 最小生成树的 Kruskal 算法内容有哪些？
4. 哈夫曼编码算法核心内容有哪些？
5. 快速排序算法内容有哪些？
6. 分治法包括哪些内容？
7. 动态规划算法包括哪些内容？
8. 回溯法包括哪些内容？
9. 分支限界法包括哪些内容？
10. NP 完全理论包括哪些内容？

# 计算与求解题

1. 请用 Prim 算法求解如右边图所示的最小生成树（要求写出生成最小生成树的过程）
   ![[dd54f265-e518-4001-901f-a4d1a6cc7f4e.png]]
2. 设 $n = 4$，背包容量 $W = 7$，物品重量 $w = (3, 5, 2, 1)$，物品价值 $p = (9, 10, 7, 4)$。分别使用以下四种方法计算该 0-1 背包问题的最大价值：
   • 贪心算法
   • 跳跃点算法
   • 回溯法
   • 分支限界法
3. 使用回溯法解决 4 皇后问题，画出搜索树。
4. 采用归并排序的方法将给定序列 $T[1:9] = (5, 3, 8, 2, 1, 9, 23, 12, 6)$ 由小到大排序。

# 算法设计题

1. 使用伪代码和编程语言设计一个算法，解决旅行售货员问题（TSP）：某售货员要到若干城市去推销商品，已知各城市之间的路程（或旅费）。他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程（或总旅费）最小。
2. 设计关于布线问题的算法，写出算法策略的思想和实现步骤。