-
【算法设计与分析】— —基础概念题（one）可作为日常联系或期末复习
🎃个人专栏：
🐬 算法设计与分析：算法设计与分析_IT闫的博客-CSDN博客
🐋c语言：c语言_IT闫的博客-CSDN博客
🐟MySQL：数据结构_IT闫的博客-CSDN博客
🐠数据结构：数据结构_IT闫的博客-CSDN博客
💎C++：C++_IT闫的博客-CSDN博客
🥽C51单片机：C51单片机（STC89C516）_IT闫的博客-CSDN博客
💻基于HTML5的网页设计及应用：基于HTML5的网页设计及应用_IT闫的博客-CSDN博客
🥏python：python_IT闫的博客-CSDN博客
欢迎收看，希望对大家有用！
目录
1. (单选题)【单选题】哈夫曼编码是一种最优前缀码方案，给出待编码的8个字符及出现的频率，若干步贪心选择之后，树的集合为：
2. (单选题)【单选题】给定一个有向连通带权图G=(V,E),n个顶点,e条边,Dijsktra算法的时间复杂度为()
4. (单选题)【单选题】给定一个无向连通带权图G=(V,E),下述关于prim算法说法不正确的是( )。
5. (单选题)【单选题】单源最短路径问题算法中,把出发点定为源点,根据该算法思想,与源点在同一集合中的点是（）
6. (单选题)【单选题】单源最短路径问题算法中,采用了前驱pre数组,用于记录（）
7. (单选题)【单选题】给定一个无向连通带权图G=(V,E),n个顶点,e条边,kruskal算法的时间复杂度为()
8. (单选题)【单选题】单源最短路径问题算法中,V是图的顶点集,S记录已确定最短路径长度的点,算法的贪心策略是()
10. (单选题)【单选题】给定字符集及其出现的频率:{a:90%,b:5%,c:3%,d:2%},下述哪种编码是最优前缀码()?
11. (单选题)【单选题】哈夫曼编码是一种最优前缀码方案，给出待编码的8个字符及出现的频率，若干步贪心选择之后，树的集合为：
12. (单选题)【单选题】给定一个无向连通带权图G=(V,E),n个顶点,e条边,Prim算法的时间复杂度为()
13. (多选题)【多选题】给定一个无向连通带权图G=(V,E),下述关于prim算法说法正确的是( )。
15. (多选题)【多选题】给定一个无向连通带权图G,下述有关生成树的说法正确的是()。
🎯问题：
一. 单选题（共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:CA13：ABCD
14：BC
15：AC
-
相关阅读:
【Linux】文件
LeetCode20.有效的括号
JVM详解
单片机只会调库和复制别人的代码是什么水平？
实用技巧：在C和cURL中设置代理服务器爬取www.ifeng.com视频
计算机网络基础一
Gitlab使用
Nacos支持https
【微机原理笔记】第 5 章 - 存储器系统与接口
[kubernetes]二进制部署k8s集群-基于containerd
- 原文地址：https://blog.csdn.net/shsjssnn/article/details/134242145