🎯问题：
一. 单选题（共12题，79.9分）
1. (单选题)
【单选题】哈夫曼编码是一种最优前缀码方案，给出待编码的8个字符及出现的频率，若干步贪心选择之后，树的集合为：
接下来的贪心选择选出的两个树的权分别为（）和（），让它们作为左右子树构造一课新树，新树的根权值是（）。
A. 15、14、23
B. 15、19、14
C. 14、15、29
D. 15、19、29
2. (单选题)【单选题】给定一个有向连通带权图G=(V,E),n个顶点,e条边,Dijsktra算法的时间复杂度为()
A. O(n 2)
B. O(n 3)
C. O(eloge)
D. O(nlogn)
3. (单选题)【单选题】背包问题: n个物品和1个背包。对物品i,其价值为vi,重量为wi,背包的容量为W。如何选取物品装入背包,使背包中所装入的物品的总价值最大?物品可以分割。该问题的贪心策略是（）
A. 重量小的优先装入背包
B. 体积小的优先装入背包
C. 价值大的优先装入背包
D. 单位重量的价值大的优先装入背包
4. (单选题)
【单选题】给定一个无向连通带权图G=(V,E),下述关于prim算法说法不正确的是( )。
A. prim算法先选出一个顶点加入到集合S,把图的顶点分成两个集合,一个S,一个V-S
B. prim算法总是选择连接S和V-S的边中权最小的加入到最小生成树中。
C. prim算法停止的条件是S=V
D. prim算法的时间复杂度O(n3),n为图的顶点个数。
5. (单选题)【单选题】单源最短路径问题算法中,把出发点定为源点,根据该算法思想,与源点在同一集合中的点是（）
A. 确定了最短路径的点
B. 尚未确定最短路径的点
C. 不明确是哪些点
D. 以上都不对（）
6. (单选题)【单选题】单源最短路径问题算法中,采用了前驱pre数组,用于记录（）
A. 当前最短路径长度
B. 图中每个顶点的前驱
C. 特殊路径
D. 以上都不对
7. (单选题)【单选题】给定一个无向连通带权图G=(V,E),n个顶点,e条边,kruskal算法的时间复杂度为()
A. O(n 2)
B. O(n 3)
C. O(eloge)
D. O(nlogn)
8. (单选题)【单选题】单源最短路径问题算法中,V是图的顶点集,S记录已确定最短路径长度的点,算法的贪心策略是()
A. 选择特殊路径长度最短的,把相连的V-S中的点加入到S中,检查新增加的特殊路径,若比原来的短,则优化。
B. 选择特殊路径长度最短的,把相连的S中的点加入到V-S中,检查新增加的特殊路径,若比原来的短,则优化。
C. 选择路径长度最短的,把相连的点加入到S中,检查新增加的路径,若比原来的短,则优化。
D. 以上都不对
9. (单选题)
【单选题】调度问题:有n个客户带来n项任务,每项加工时间已知,设为ti,i=1,2,…,n。从0时刻开始,陆续安排到一台机器上加工。每个任务的完成时间是从0时刻到该任务加工完成的时间。为了使尽可能多的客户满意,我们希望找到是的总等待时间最少的调度方案。该问题的贪心策略是( )
A. 加工时间长的优先安排
B. 加工时间短的优先安排
C. 完成时间早的优先安排
D. 等待时间长的优先安排
10. (单选题)【单选题】给定字符集及其出现的频率:{a:90%,b:5%,c:3%,d:2%},下述哪种编码是最优前缀码()?
A. a:1,b:01,c:000,d:001
B. a:0,b:01,c:000,d:001
C. a:1,b:10,c:000,d:001
D. a:0,b:10,c:000,d:001
11. (单选题)
【单选题】哈夫曼编码是一种最优前缀码方案，给出待编码的8个字符及出现的频率，若干步贪心选择之后，树的集合为：
这是经过多少次贪心选择之后得到的结果。（）
A. 1
B. 2
C. 3
D. 4
12. (单选题)【单选题】给定一个无向连通带权图G=(V,E),n个顶点,e条边,Prim算法的时间复杂度为()
A. O(n 2)
B. O(n 3)
C. O(eloge)
D. O(nlogn)
二. 多选题（共3题，20.1分）
13. (多选题)【多选题】给定一个无向连通带权图G=(V,E),下述关于prim算法说法正确的是( )。
A. prim算法先选出一个顶点加入到集合S,把图的顶点分成两个集合,一个S,一个V-S
B. prim算法总是选择连接S和V-S的边中权最小的加入到最小生成树中
C. prim算法停止的条件是S=V
D. prim算法的时间复杂度O(n2),n为图的顶点个数
E. prim算法的时间复杂度和图的顶点数有关,也和图的边数也有关
F. prim算法的时间复杂度O(n3),n为图的顶点个数
14. (多选题)贪心算法的正确性证明包括证明
A. 可行性
B. 贪心选择性质
C. 最优子结构性质
D. 存在最优解
E. 可分为独立子问题
15. (多选题)【多选题】给定一个无向连通带权图G,下述有关生成树的说法正确的是()。
A. G的生成树可能有多棵
B. G的生成树唯一
C. G的最小生成树耗费最小
D. G的最小生成树唯一
🎯答案：
1-5:CADDA
6-10：BCABA
11-12:CA
13：ABCD
14：BC
15：AC
