深圳大学《算法设计与分析》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.子数组长度为0或1B.子数组长度为2C.子数组长度为3D.子数组长度为412、以下哪种算法常用于解决旅行商问题？（）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、在二叉树中，度为0的节点称为？A.叶子节点B.根节点C.内部节点D.分支节点二、简答题（本大题共4个小题，共40分)1、（本题10分）以图像压缩问题为例，说明动态规划算法的应用。2、（本题10分）阐述基数排序算法的基本原理和适用场景。3、（本题10分）分析希尔排序的时间复杂度分析方法。4、（本题10分）说明如何用分支限界法解决车辆路径规划问题。三、设计题（