湖北工业大学《算法分析与设计》2021-2022学年期末试卷

装订线装订线PAGE2第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、以下哪个数据结构可以用于实现栈的功能？A.数组B.链表C.队列D.二叉树6、以下哪个数据结构常用于实现图？（）A.数组B.链表C.邻接矩阵和邻接表D.栈7、以下关于算法复杂度的说法中，错误的是？A.时间复杂度是指算法执行所需的时间B.空间复杂度是指算法执行所需的存储空间C.算法的时间复杂度和空间复杂度可以相互独立D.算法的时间复杂度总是小于空间复杂度8、在图的存储结构中，十字链表适合存储什么样的图？A.稀疏图B.稠密图C.有向图D.无向图9、分治法的基本思想是？A.把大问题分解成多个小问题分别求解B.从一个初始解逐步优化得到最终解C.通过随机选择来找到最优解D.对问题进行暴力搜索10、以下哪个不是贪心算法的局限性？A.不一定能得到全局最优解B.算法的时间复杂度较高C.对问题的性质有一定要求D.难以证明算法的正确性11、快速排序在最好情况下的时间复杂度是？A.O(n)B.O(nlogn)C.O(n²)D.O(logn)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.冒泡排序B.插入排序C.归并排序D.堆排序18、以下哪种算法常用于解决数独问题？（）A.贪心算法B.回溯法C.动态规划D.分治法19、算法的空间复杂度是指（）A.算法执行过程中所需的最大存储空间B.算法执行过程中所需的平均存储空间C.算法执行过程中所需的最小存储空间D.算法执行过程中所需的存储空间的变化情况20、在哈希表中，解决冲突的方法有哪些？A.线性探测法和二次探测法B.链地址法和开放定址法C.再哈希法和建立公共溢出区D.以上都是二、简答题（本大题共4个小题，共40分)1、（本题10分）简述B树和B+树的结构和应用场景。2、（本题10分）解释如何处理边界情况和特殊输入。3、（本题10分）阐述如何用分支限界法解决装箱问题。4、（本题10分）解释插入排序在不同操作系统中的性能差异原因。三、设计题（本大题共2个小题，共2