济宁学院《算法设计与分析》2021-2022学年期末试卷

学校________________班级____________姓名____________考场____________准考证号学校________________班级____________姓名____________考场____________准考证号…………密…………封…………线…………内…………不…………要…………答…………题…………第1页，共3页济宁学院《算法设计与分析》

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、空间复杂度为O(1)的算法意味着（）A.不使用额外空间B.使用固定大小的额外空间C.使用少量的额外空间D.以上都不是6、归并排序的基本思想是？A.分而治之，合并有序子序列B.选择最小元素逐步构建有序序列C.通过交换相邻元素进行排序D.随机选择元素进行排序7、以下哪种算法常用于解决旅行商问题？（）A.贪心算法B.动态规划C.回溯法D.模拟退火算法8、以下哪个不是图的存储结构？（）A.邻接矩阵B.邻接表C.十字链表D.顺序表9、以下哪个算法常用于图的最短路径问题？（）A.Dijkstra算法B.Prim算法C.Kruskal算法D.Floyd算法10、一个算法的时间复杂度为O(n²)，如果输入规模扩大一倍，那么运行时间会变为原来的几倍？A.2倍B.4倍C.8倍D.16倍11、在算法分析中，大O记号表示的是？A.算法的精确运行时间B.算法的平均运行时间C.算法运行时间的上界D.算法运行时间的下界12、以下哪个数据结构可以用于实现集合的交集、并集和差集等操作？A.数组B.链表C.栈D.哈希表13、以下哪个排序算法在最坏情况下的时间复杂度最低？A.冒泡排序B.插入排序C.选择排序D.归并排序14、以下哪种算法常用于解决凸包问题？（）A.Graham扫描法B.Dijkstra算法C.Prim算法D.Kruskal算法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个