西安工程大学《算法设计与分析》2021-2022学年期末试卷

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

《算法设计与分析》2021-2022学年期末试卷题号一二三总分得分一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、在动态规划中，优化子问题的解存储方式可以（）A.降低时间复杂度B.降低空间复杂度C.提高可读性D.以上都是2、在二叉树中，度为0的节点称为？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.贪心算法B.动态规划C.回溯法D.分治法12、在二叉搜索树中删除一个节点时，需要考虑几种情况？A.1种B.2种C.3种D.4种13、在贪心算法中，得到的解可能是（）A.最优解B.近似最优解C.可行解D.以上都可能14、归并排序的空间复杂度是？A.O(1)B.O(n)C.O(logn)D.O(nlogn)15、时间复杂度为O(n)的算法，其执行时间与输入规模n的关系是（）A.线性增长B.指数增长C.对数增长D.不变16、以下哪种算法常用于解决背包问题？（）A.贪心算法B.动态规划C.回溯法D.分治法17、在图的存储结构中，十字链表适合存储什么样的图？A.稀疏图B.稠密图C.有向图D.无向图18、时间复杂度为O(logn)的算法通常比时间复杂度为O(n)的算法（）A.更慢B.更快C.一样快D.无法比较19、在哈希表中，当发生冲突时，可以采用哪种方法来解决？A.线性探测法B.二次探测法C.链地址法D.以上都是20、以下哪个排序算法的空间复杂度最低？（）A.冒泡排序B.插入排序C.选择排序D.归并排序二、简答题（本大题共4个小题，共40分)1、（本题10分）解释拓扑排序算法的概念和用途。2、（本题10分）分析冒泡排序在数据基本有序时的效率提升。3、（本题10分）比较Dijkstra算法和Floyd算法的适用情况。4、（本题10分）阐述归并排序在二路归并和多路归并上的扩展。三、设计题（本大题共2个小题，共20分)1