惠州学院《算法设计与分析》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.1种B.2种C.3种D.4种5、以下哪种算法常用于解决皇后问题？（）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、在递归算法中，当递归深度过大时可能会导致（）A.运行速度加快B.内存溢出C.结果更准确D.以上都不是11、在回溯法中，通过（）来避免无效搜索。A.剪枝B.贪心选择C.动态规划D.分治12、在有向无环图中，进行拓扑排序的时间复杂度是？A.O(1)B.O(n)C.O(nlogn)D.O(n²)13、以下哪种算法常用于解决凸包问题？（）A.Graham扫描法B.Dijkstra算法C.Prim算法D.Kruskal算法14、时间复杂度和空间复杂度需要在设计算法时进行（）A.单独考虑B.综合考虑C.先考虑时间复杂度D.先考虑空间复杂度15、在贪心算法中，如果局部最优解不能导致全局最优解，该算法（）A.仍然有效B.无效C.可能有效D.以上都不是16、在分治法中，合并子问题的解的时间复杂度通常为（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)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分）解释插入排序在不同操作系统中的性能差异原因。三、设计题（本大题共