吉林大学《算法与数据结构》2021-2022学年期末试卷

学校________________班级____________姓名____________考场____________准考证号学校________________班级____________姓名____________考场____________准考证号…………密…………封…………线…………内…………不…………要…………答…………题…………第1页，共3页吉林大学

《算法与数据结构》2021-2022学年期末试卷题号一二三总分得分一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、在图的遍历中，广度优先搜索使用的数据结构是（）A.栈B.队列C.链表D.树2、归并排序的合并操作的时间复杂度是？A.O(1)B.O(n)C.O(logn)D.O(nlogn)3、以下哪个排序算法在最坏情况下性能最优？（）A.冒泡排序B.插入排序C.归并排序D.堆排序4、在二叉搜索树中，查找一个元素的时间复杂度是？A.O(1)B.O(logn)C.O(n)D.O(n²)5、以下哪个不是动态规划算法的关键步骤？A.确定状态B.确定状态转移方程C.初始化状态D.随机选择状态6、算法的复杂度分析不包括（）A.时间复杂度B.空间复杂度C.代码复杂度D.平均复杂度7、在二叉搜索树中删除一个节点时，需要考虑几种情况？A.1种B.2种C.3种D.4种8、在动态规划中，通过保存子问题的解来避免（）A.重复计算B.错误计算C.遗漏计算D.以上都是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.不同状态之间的关系B.初始状态的计算方法C.最优解的计算方法D.以上都不是16、以下哪种数据结构常用于实现栈？（）A.数组B.链表C.树D.图17、以下哪种算法常用于构建最小生成树？（）A.Dijkstra算法B.Prim算法C.Kruskal算法D.Floyd算法18、二分查找算法要求数据必须是（）A.有序的B.无序的C.平衡的D.以上都不是19、以下哪个不是查找算法？（）A.顺序查找B.二分查找C.冒泡排序D.哈希查找20、在二叉搜索树中，插入一个新节点的时间复杂度是？A.O(1)B.O(logn)C.O(n)D.O(n²)二、简答题（本大题共4个小题，共40分)1、（本题10分）如何分析一个算法的时间复杂度？2、（本题10分）比较深度优先搜索和广度优先搜索的适用场景。3、（本题10分）阐述基数排序算法的基本原理和适用场景。4、（本题10分）简述在交通运输中的流量预测和路线规划算法。三、设计题（本