长春大学《算法分析与设计》2022-2023学年期末试卷

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

2022-2023学年期末试卷题号一二三总分得分批阅人一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、以下哪种数据结构常用于实现栈？（）A.数组B.链表C.树D.图2、以下哪种算法常用于解决凸包问题？（）A.Graham扫描法B.Dijkstra算法C.Prim算法D.Kruskal算法3、在回溯法中，通过（）来避免无效搜索。A.剪枝B.贪心选择C.动态规划D.分治4、在二叉树中，度为2的节点有10个，度为1的节点有8个，那么叶子节点有多少个？A.9B.10C.11D.125、以下哪种算法常用于解决活动安排问题？（）A.贪心算法B.动态规划C.回溯法D.分治法6、在有向图中，顶点的入度是指？A.以该顶点为起点的边的数量B.以该顶点为终点的边的数量C.与该顶点相邻的顶点数量D.该顶点的度数7、以下哪个数据结构常用于查找操作？（）A.栈B.队列C.二叉搜索树D.链表8、归并排序的递归实现中，每次将数组分成两部分，那么递归的深度是多少？A.O(1)B.O(logn)C.O(n)D.O(nlogn)9、以下哪个不是图的基本操作？A.插入顶点B.删除顶点C.查找顶点D.排序顶点10、在图的遍历中，深度优先搜索和广度优先搜索的主要区别是？A.遍历的顺序不同B.时间复杂度不同C.空间复杂度不同D.适用的图类型不同11、算法的最优性是指（）A.时间复杂度最低B.空间复杂度最低C.得到的解最优D.以上都是12、以下哪个排序算法在最坏情况下的时间复杂度最低？A.冒泡排序B.插入排序C.选择排序D.归并排序13、算法的正确性是指（）A.对于任意输入都能得到正确结果B.对于大部分输入能得到正确结果C.对于特定输入能得到正确结果D.以上都不是14、在图的存储结构中，邻接矩阵适合存储什么样的图？A.稀疏图B.稠密图C.有向图D.无向图15、在哈希表中，装填因子的取值范围是？A.0到1B.0到正无穷C.负无穷到正无穷D.1到正无穷16、以下哪个数据结构可以用于实现集合的交集、并集和差集等操作？A.数组B.链表C.栈D.哈希表17、以下哪种排序算法在数据量较大时性能较好？（）A.冒泡排序B.插入排序C.快速排序D.选择排序18、在二叉树中，后序遍历的顺序是？A.根节点、左子树、右子树B.左子树、根节点、右子树C.左子树、右子树、根节点D.右子树、根节点、左子树19、空间复杂度为O(1)的算法意味着（）A.不使用额外空间B.使用固定大小的额外空间C.使用少量的额外空间D.以上都不是20、动态规划算法的核心是？A.递归B.贪心选择C.记忆化搜索D.分治二、简答题（本大题共4个小题，共40分)1、（本题10分）以字符串匹配问题为例，说明动态规划算法的应用。2、（本题10分）简述在移动计算中的节能算法。3、（本题10分）解释插入排序算法的工作原理，并比较它与选择排序的差异。4、（本题10分）解释插入排序在实时数据插入时的特点。三、设计题