北京邮电大学《算法与数据结构课程设计》2021-2022学年期末试卷

学校________________班级____________姓名____________考场____________准考证号学校________________班级____________姓名____________考场____________准考证号…………密…………封…………线…………内…………不…………要…………答…………题…………第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.KMP算法B.冒泡排序C.快速排序D.插入排序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.冒泡排序B.插入排序C.归并排序D.堆排序18、在动态规划中，优化子问题的解存储方式可以（）A.降低时间复杂度B.降低空间复杂度C.提高可读性D.以上都是19、以下哪个算法可以用于求解字符串的最长回文子串问题？A.贪心算法B.回溯法C.分治法D.动态规划法20、时间复杂度为O(n)的算法，其执行时间与输入规模n的关系是（）A.线性增长B.指数增长C.对数增长D.不变二、简答题（本大题共4个小题，共40分)1、（本题10分）阐述堆排序在数据排序稳定性方面的特点。2、（本题10分）以最优切割问题为例，分析动态规划算法的解法。3、（本题10分）解释插入排序在不同操作系统中的性能差异原因。4、（本题10分）简述在生物信息学中的序列比对算法。三、设