湖北职业技术学院《算法设计与分析（实验）》2025学年第一学期期末试卷含答案

湖北职业技术学院《算法设计与分析（实验）》2025学年第一学期期末试卷含答案一、单项选择题（每题2分，共20分）1.以下算法中，时间复杂度为O(nlogn)的是（）A.冒泡排序（最坏情况）B.快速排序（平均情况）C.插入排序（最好情况）D.选择排序（平均情况）答案：B2.对于长度为n的有序数组，采用二分查找的时间复杂度为（）A.O(n)B.O(n²)C.O(logn)D.O(nlogn)答案：C3.动态规划算法的核心是（）A.分解问题为独立子问题B.利用子问题重叠性质，存储子问题解C.贪心选择性质D.回溯试探答案：B4.以下不属于贪心算法典型应用的是（）A.活动选择问题B.01背包问题C.霍夫曼编码D.最小提供树（Kruskal算法）答案：B5.快速排序的枢轴（pivot）选择策略中，最可能导致最坏时间复杂度O(n²)的是（）A.选择首元素作为枢轴B.选择中间元素作为枢轴C.随机选择枢轴D.三数取中法选择枢轴答案：A6.用回溯法解决n皇后问题时，每一步选择的是（）A.当前行的列位置B.当前列的行位置C.当前对角线的位置D.当前斜线的位置答案：A7.计算斐波那契数列F(n)=F(n1)+F(n2)（F(0)=0,F(1)=1）时，若用递归算法的时间复杂度为（）A.O(2ⁿ)B.O(n)C.O(n²)D.O(nlogn)答案：A8.对于图的广度优先搜索（BFS），通常使用的辅助数据结构是（）A.栈B.队列C.优先队列D.二叉树答案：B9.以下算法中，不能解决单源最短路径问题的是（）A.Dijkstra算法B.BellmanFord算法C.FloydWarshall算法D.以上均能解决答案：C（注：FloydWarshall解决所有点对最短路径）10.归并排序的关键操作是（）A.选择枢轴并划分B.递归分解并合并有序子数组C.插入元素到正确位置D.交换相邻逆序元素答案：B二、填空题（每空2分，共20分）1.算法的五个重要特性是有穷性、确定性、可行性、输入和输出。2.大O表示法中，T(n)=3n²+2n+5的渐近时间复杂度为O(n²)。3.动态规划中，若问题的最优解包含其子问题的最优解，则该问题具有最优子结构性质；若子问题被多次重复求解，则具有子问题重叠性质。4.贪心算法求解活动选择问题时，通常按结束时间早的顺序选择活动。5.回溯法的搜索方式是深度优先搜索，当发现当前路径不可能得到解时，进行剪枝操作。6.对于n个元素的数组，堆排序的时间复杂度为O(nlogn)（平均和最坏情况）。三、算法设计题（共40分）1.（10分）设计一个分治算法，计算数组中所有元素的和。要求写出伪代码，并分析时间复杂度。答案：分治策略：将数组分成左右两部分，递归计算两部分的和，再合并结果。伪代码：functionsumDivideConquer(arr,left,right):ifleft==right:returnarr[left]mid=(left+right)//2leftSum=sumDivideConquer(arr,left,mid)rightSum=sumDivideConquer(arr,mid+1,right)returnleftSum+rightSum时间复杂度分析：递归式为T(n)=2T(n/2)+O(1)，根据主定理，T(n)=O(n)。2.（15分）使用动态规划解决最长公共子序列（LCS）问题。给定两个序列X="ABCBDAB"，Y="BDCAB"，要求：（1）构造LCS长度的二维表格；（2）输出LCS的具体序列。答案：（1）二维表格c[i][j]表示X前i个字符和Y前j个字符的LCS长度：||0|B|D|C|A|B||||||||||0|0|0|0|0|0|0||A|0|0|0|0|1|1||B|0|1|1|1|1|2||C|0|1|1|2|2|2||B|0|1|1|2|2|3||D|0|1|2|2|2|3||A|0|1|2|2|3|3||B|0|1|2|2|3|4|（2）LCS序列为"BCAB"（或"BDAB"，具体路径可能不同，但长度为4）。3.（15分）设计一个回溯算法，提供1到n的所有全排列（n≥2）。要求用Python代码实现，并输出n=3时的所有排列。答案：Python代码：defbacktrack(used,path,n,result):iflen(path)==n:result.append(path.copy())returnforiinrange(1,n+1):ifnotused[i]:used[i]=Truepath.append(i)backtrack(used,path,n,result)path.pop()used[i]=Falsedefgenerate_permutations(n):result=[]used=[False](n+1)索引0不用backtrack(used,[],n,result)returnresultn=3时输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]四、算法分析题（共20分）1.（10分）分析快速排序在最坏情况下的时间复杂度，并说明如何避免最坏情况。答案：最坏情况发生在每次划分后，枢轴将数组分为0和n1两部分（如已排序数组选择首元素为枢轴）。递归式为T(n)=T(n1)+O(n)，展开后T(n)=O(n²)。避免方法：采用随机选择枢轴、三数取中法（选择首中尾的中位数），或使用插入排序处理小规模子数组（减少递归深度）。2.（10分）比较Dijkstra算法与BellmanFord算法在求解单源最短路径问题中的异同点。答案：相同点：均能求解单源最短路径，要求图中边权非负时Dijkstra更高效（BellmanFord也可处理负权边，但不能有负权环）。不同点：数据结构：Dijkstra使用优先队列（贪心），BellmanFord使用松弛操作（动