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

装订线装订线PAGE2第1页，共3页福建师范大学《算法设计与分析》

2022-2023学年期末试卷院(系)_______班级_______学号_______姓名_______题号一二三总分得分一、单选题（本大题共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.O(n)B.O(nlogn)C.O(n²)D.O(logn)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.贪心算法B.动态规划C.回溯法D.分治法13、以下哪个数据结构可以用于实现图的深度优先搜索？A.数组B.链表C.栈D.队列14、以下哪种算法常用于解决组合优化问题？（）A.贪心算法B.回溯法C.分治法D.动态规划15、归并排序的基本思想是？A.分而治之，合并有序子序列B.选择最小元素逐步构建有序序列C.通过交换相邻元素进行排序D.随机选择元素进行排序16、以下哪个算法可以用于解决0-1背包问题？A.贪心算法B.回溯法C.分治法D.动态规划法17、以下哪种算法常用于解决旅行商问题？（）A.贪心算法B.动态规划C.回溯法D.模拟退火算法18、以下哪个算法可以用于求解图的所有顶点之间的最短路径问题？A.迪杰斯特拉算法B.弗洛伊德算法C.普里姆算法D.克鲁斯卡尔算法19、以下哪种算法常用于解决背包问题？（）A.贪心算法B.动态规划C.回溯法D.分治法20、以下哪种算法常用于构建最小生成树？（）A.Dijkstra算法B.Prim算法C.Kruskal算法D.Floyd算法二、简答题（本大题共4个小题，共40分)1、（本题10分）以快速排序算法为例，说明算法的时间复杂度分析过程。2、（本题10分）简述在生物信息学中的序列比对算法。3、（本题10分）以棋盘覆盖问题为例，说明分治法的应用。4、（本题10分）说明如何用分支限界法解决资源分配的最优解搜索问题。三、设计题（本大题共2