北京工业大学《算法设计》2021-2022学年期末试卷.doc
自觉遵守考场纪律如考试作弊此答卷无效密
自觉遵守考场纪律如考试作弊此答卷无效
密
封
线
第PAGE1页，共NUMPAGES3页
北京工业大学《算法设计》
2021-2022学年期末试卷
院(系)_______班级_______学号_______姓名_______
题号
一
二
三
总分
得分
批阅人
一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）
1、以下哪种排序算法对近乎有序的数组效果较好？（）
A.快速排序
B.插入排序
C.冒泡排序
D.选择排序
2、以下哪个不是图的基本操作？
A.插入顶点
B.删除顶点
C.查找顶点
D.排序顶点
3、以下哪个算法可以用于求解图的最小生成树问题？
A.迪杰斯特拉算法
B.弗洛伊德算法
C.普里姆算法
D.克鲁斯卡尔算法
4、在有向图中，顶点的入度是指？
A.以该顶点为起点的边的数量
B.以该顶点为终点的边的数量
C.与该顶点相邻的顶点数量
D.该顶点的度数
5、在哈希表中，当发生冲突时，可以采用哪种方法来解决？
A.线性探测法
B.二次探测法
C.链地址法
D.以上都是
6、归并排序的合并操作的时间复杂度是？
A.O(1)
B.O(n)
C.O(logn)
D.O(nlogn)
7、以下哪个算法可以用于求解最大子数组和问题？
A.贪心算法
B.回溯法
C.分治法
D.动态规划法
8、算法的稳定性对于（）操作较为重要。
A.多次排序
B.查找
C.插入
D.删除
9、以下哪个排序算法在最坏情况下的时间复杂度最低？
A.冒泡排序
B.插入排序
C.选择排序
D.归并排序
10、在有向无环图中，进行拓扑排序的时间复杂度是？
A.O(1)
B.O(n)
C.O(nlogn)
D.O(n2)
11、算法的最优性是指（）
A.时间复杂度最低
B.空间复杂度最低
C.得到的解最优
D.以上都是
12、在递归算法中，当递归深度过大时可能会导致（）
A.运行速度加快
B.内存溢出
C.结果更准确
D.以上都不是
13、在图的深度优先搜索中，使用的辅助数据结构是（）
A.栈
B.队列
C.优先队列
D.哈希表
14、在贪心算法中，最终的解依赖于（）
A.子问题的选择顺序
B.问题的规模
C.数据的分布
D.以上都是
15、以下哪种算法常用于解决旅行商问题？（）
A.贪心算法
B.动态规划
C.回溯法
D.模拟退火算法
16、快速排序的枢轴元素选择对算法的性能有很大影响，以下哪种选择方式通常比较好？
A.第一个元素
B.最后一个元素
C.中间元素
D.随机元素
17、以下哪个算法可以用于求解图的单源最短路径问题？
A.深度优先搜索
B.广度优先搜索
C.迪杰斯特拉算法
D.克鲁斯卡尔算法
18、在哈希表中，解决冲突的方法有哪些？
A.线性探测法和二次探测法
B.链地址法和开放定址法
C.再哈希法和建立公共溢出区
D.以上都是
19、在贪心算法中，得到的解可能是（）
A.最优解
B.近似最优解
C.可行解
D.以上都可能
20、以下哪种算法常用于解决活动安排问题？（）
A.贪心算法
B.动态规划
C.回溯法
D.分治法
二、简答题（本大题共4个小题，共40分)
1、（本题10分）分析在艺术创作中的生成算法。
2、（本题10分）简述分治法的基本思想，并举例说明其在算法设计中的应用。
3、（本题10分）阐述堆排序在大规模数据排序中的适用性。
4、（本题10分）以最长回文子串问题为例，说明动态规划算法的解法。
三、设计题（本大题共2个小题，共20分)
1、（本题10分）实现一个算法，在给定的红黑树中查找一个节点。
2、（本题10分）设计一个算法，找出一个有向图中的所有负权环。