福建师范大学《算法分析与设计》2022-2023学年期末试卷

装订线装订线PAGE2第1页，共3页福建师范大学

《算法分析与设计》2022-2023学年期末试卷院(系)_______班级_______学号_______姓名_______题号一二三总分得分一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、归并排序的空间复杂度是？A.O(1)B.O(n)C.O(logn)D.O(nlogn)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.子数组长度为0或1B.子数组长度为2C.子数组长度为3D.子数组长度为49、动态规划算法的核心是？A.递归B.贪心选择C.记忆化搜索D.分治10、以下哪种算法常用于构建最小生成树？（）A.Dijkstra算法B.Prim算法C.Kruskal算法D.Floyd算法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.O(n)B.O(nlogn)C.O(n²)D.O(logn)18、在二叉树中，后序遍历的顺序是？A.根节点、左子树、右子树B.左子树、根节点、右子树C.左子树、右子树、根节点D.右子树、根节点、左子树19、一个算法的时间复杂度为O(n²)，如果输入规模扩大一倍，那么运行时间会变为原来的几倍？A.2倍B.4倍C.8倍D.16倍20、快速排序的空间复杂度主要取决于？A.递归调用的深度B.数据的规模C.枢轴元素的选择D.排序的稳定性二、简答题（本大题共4个小题，共40分)1、（本题10分）简述在计算机网络中使用的路由算法。2、（本题10分）分析图算法中的连通分量求解方法。3、（本题10分）比较Dijkstra算法和Floyd算法的适用情况。4、（本题10分）阐述归并排序在数据压缩中的作用。三、设计题（本大题