2026年《算法设计与分析》期末考试试题及答案

2026年《算法设计与分析》期末考试试题及答案一、单项选择题（每题3分，共15分）1.已知某算法的递推关系式为T(n)=4T(n/2)+n²logn，其时间复杂度的渐近紧确界为（）A.Θ(n²(logn)²)B.Θ(n²logn)C.Θ(n³)D.Θ(n²)2.以下关于贪心算法和动态规划的描述中，错误的是（）A.贪心算法需要满足贪心选择性质，动态规划需要满足最优子结构B.动态规划通常自底向上计算，贪心算法通常自顶向下选择C.0-1背包问题无法用贪心算法得到最优解，而分数背包可以D.活动选择问题既能用贪心算法也能用动态规划求解3.对于带权无向图G=(V,E)，若使用Dijkstra算法求单源最短路径，当图中存在负权边时（）A.算法一定无法终止B.算法可能提前终止但结果错误C.算法仍能正确计算最短路径D.算法时间复杂度退化为O(|V|³)4.设主串长度为n，模式串长度为m，KMP算法的预处理（构建部分匹配表）的时间复杂度为（）A.Θ(m)B.Θ(n)C.Θ(m+n)D.Θ(m²)5.下列问题中，属于NP完全问题的是（）A.求无向图的最小提供树B.求解线性方程组C.子集和问题D.拓扑排序二、填空题（每空2分，共20分）1.若算法的时间复杂度为T(n)=2T(n/3)+n，根据主定理，其渐近时间复杂度为______。2.快速排序在平均情况下的时间复杂度为______，最坏情况下的时间复杂度为______。3.动态规划求解最长公共子序列（LCS）问题时，若两个序列长度分别为m和n，其状态转移方程为：当X[i]=Y[j]时，c[i][j]=______；否则c[i][j]=______。4.贪心算法求解活动选择问题时，其关键性质是______和______。5.归并排序的核心思想是______，其时间复杂度的递推式为______。三、算法设计题（共45分）1.（15分）设计一个算法，求解带权无向图中从起点s到终点t的“k跳最短路径”，即路径中边的数量不超过k时的最短路径长度（若不存在则返回-1）。要求：（1）给出算法思路；（2）写出伪代码；（3）分析时间复杂度。2.（15分）字符串编辑距离通常定义为将字符串A转换为字符串B所需的最少操作次数（操作包括插入、删除、替换一个字符）。现修改操作定义：增加“交换相邻两个字符”（记为交换操作，代价为1），其余操作代价不变。设计一个动态规划算法计算修改后的编辑距离。要求：（1）定义状态；（2）推导状态转移方程；（3）举例说明（如A=“abc”，B=“acb”时的计算过程）。3.（15分）给定一棵二叉树的根节点，每个节点存储一个正整数权值，设计算法找到树中两个节点u和v，使得u到v的路径上所有节点权值之和最大（路径长度至少为1）。要求：（1）说明算法思路（可结合递归或动态规划）；（2）给出实现步骤；（3）分析时间复杂度。四、算法分析题（共20分）1.（10分）随机化快速排序通过随机选择主元来优化性能。分析该优化如何影响最坏时间复杂度的概率分布，并证明其期望时间复杂度仍为Θ(nlogn)。2.（10分）证明：在带权连通图中，Prim算法通过每次添加连接当前提供树和剩余节点的最小权边，最终能得到最小提供树（需结合贪心选择性质和最优子结构证明）。答案一、单项选择题1.A（主定理中，a=4,b=2,f(n)=n²logn，log_ba=2，f(n)=Ω(n²(logn)^1)，满足主定理情况3，故T(n)=Θ(n²(logn)²)）2.B（动态规划可自顶向下（记忆化搜索）或自底向上，贪心算法通常自顶向下选择）3.B（Dijkstra算法假设边权非负，存在负权边时可能提前终止但结果错误）4.A（KMP预处理仅遍历模式串一次，时间复杂度Θ(m)）5.C（子集和问题是NP完全问题，其余为P类问题）二、填空题1.Θ(n)（主定理中，a=2,b=3,log_ba≈0.63<1，f(n)=n=Ω(n^0.63+ε)，故T(n)=Θ(n)）2.Θ(nlogn)；Θ(n²)3.c[i-1][j-1]+1；max(c[i-1][j],c[i][j-1])4.贪心选择性质；最优子结构性质5.分而治之（或分治）；T(n)=2T(n/2)+Θ(n)三、算法设计题1.（k跳最短路径算法）（1）思路：使用动态规划思想，定义dp[i][v]为从s到v经过恰好i跳的最短距离。初始化dp[0][s]=0，其余为∞。对于每跳数i（1≤i≤k），遍历所有边(u,w)，更新dp[i][w]=min(dp[i][w],dp[i-1][u]+weight(u,w))。最终取min{dp[1][t],dp[2][t],...,dp[k][t]}。（2）伪代码：输入：图G=(V,E)，起点s，终点t，最大跳数k输出：最短路径长度（或-1）初始化dp为k+1行|V|列的数组，所有值设为∞dp[0][s]=0forifrom1tok:foreachedge(u,w)inE:ifdp[i-1][u]+weight(u,w)<dp[i][w]:dp[i][w]=dp[i-1][u]+weight(u,w)min_dist=∞forifrom1tok:ifdp[i][t]<min_dist:min_dist=dp[i][t]returnmin_distifmin_dist<∞else-1（3）时间复杂度：外层循环k次，内层遍历所有边|E|次，总时间复杂度为O(k|E|)。2.（带交换操作的编辑距离）（1）状态定义：设A[1..i]表示A的前i个字符，B[1..j]表示B的前j个字符，dp[i][j]表示将A[1..i]转换为B[1..j]的最小操作次数。（2）状态转移方程：若i≥2且j≥2，且A[i]=B[j-1]且A[i-1]=B[j]（可交换）：dp[i][j]=min(dp[i][j],dp[i-2][j-2]+1)基本操作：插入：dp[i][j]=min(dp[i][j],dp[i][j-1]+1)删除：dp[i][j]=min(dp[i][j],dp[i-1][j]+1)替换：若A[i]≠B[j]，则dp[i][j]=min(dp[i][j],dp[i-1][j-1]+1)；否则dp[i][j]=dp[i-1][j-1]（3）举例（A=“abc”，B=“acb”）：初始化dp[0][0]=0，dp[i][0]=i（删除i次），dp[0][j]=j（插入j次）。计算dp[2][2]：A[2]=b，B[2]=c，不相等。检查是否可交换：A[1]=a=B[2]=c？否；A[2]=b=B[1]=a？否，故dp[2][2]=min(dp[1][2]+1,dp[2][1]+1,dp[1][1]+1)=min(3,3,2)=2（替换）。计算dp[3][3]：A[3]=c，B[3]=b。检查交换条件：A[2]=b=B[3]=b，A[3]=c=B[2]=c，满足交换！故dp[3][3]=dp[1][1]+1=1+1=2（原dp[1][1]为0，因A[1]=a=B[1]=a）。最终编辑距离为2（交换b和c）。3.（二叉树最大路径和）（1）思路：路径可能有三种情况：仅左子树内路径、仅右子树内路径、经过根节点的左右子树路径。递归计算每个节点的“单边最大和”（从该节点向下延伸的最大路径和），同时更新全局最大路径和。（2）步骤：定义递归函数maxPathSum(node)，返回以node为起点向下的最大单边和（可包含node自身）。递归终止：若node为空，返回0。计算左子树单边最大和left=max(0,maxPathSum(node.left))，右子树同理right=max(0,maxPathSum(node.right))。当前节点的路径和为node.val+left+right，更新全局最大值。返回node.val+max(left,right)（单边延伸的最大值）。（3）时间复杂度：每个节点仅访问一次，时间复杂度为Θ(n)（n为节点数）。四、算法分析题1.（随机化快速排序分析）随机化快速排序通过随机选择主元，避免了最坏情况（如已排序数组）的确定性发生。最坏时间复杂度（Θ(n²)）的概率取决于主元选择是否总是分割极不平衡（如每次选最小或最大元素）。设每次主元为随机均匀选择，则分割为1和n-1的概率为2/n（选最小或最大）。通过概率分析，期望递归深度为O(logn)，每一层处理总时间为Θ(n)，故期望时间复杂度为Θ(nlogn)。严格证明可通过指示变量法：设X为比较次数，E[X]=Σ_{i<j}Pr(i和j被比较)。由于随机选择主元，i和j被比较当且仅当其中一个是i到j之间第一个被选为主元的元素，概率为2/(j-i+1)。求和得E[X]=O(nlogn)。2.（Prim算法正确性证明）（1）贪心选择性质：设当前提供树为T，剩余节点集合为S，选择连接T和S的最小权边e=(u,v)。假设存在最小提供树T不包含e，则T中存在从u到v的路径P，其中至少有一条边e’连接T和S（否则T和S不连通）。由于e是最小权边，替换e’为e后得到的新树权值更小，与T是最小提供树矛盾，故e必在某棵最小提供树中。（1）贪心选择性质：设当前提供树为T，剩余节点集合为S，选择连接T和S的最小权边e=(u,v)。假设存在最小提供树T不包含e，则T中存在从u到v的