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

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

2023-2024学年期末试卷题号一二三总分得分批阅人一、单选题（本大题共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(nlogn)？（）A.冒泡排序B.插入排序C.快速排序D.选择排序6、在贪心算法中，最终的解依赖于（）A.子问题的选择顺序B.问题的规模C.数据的分布D.以上都是7、一个算法的时间复杂度为O(n²)，如果输入规模扩大一倍，那么运行时间会变为原来的几倍？A.2倍B.4倍C.8倍D.16倍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.0到1B.0到正无穷C.负无穷到正无穷D.1到正无穷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分）简述贪心算法的基本策略，以及它可能存在的局限性。三、设计题（本大题共