2025年信息技术算法试题及答案

2025年信息技术算法试题及答案一、单项选择题（每题3分，共24分）1.对长度为n的有序数组进行二分查找，最坏情况下的时间复杂度为（）。A.O(n)B.O(nlogn)C.O(logn)D.O(n²)2.以下排序算法中，不稳定的是（）。A.冒泡排序B.归并排序C.插入排序D.快速排序3.若一棵完全二叉树有768个节点，则该树的叶子节点数为（）。A.383B.384C.385D.3864.KMP算法中，模式串“ABABC”的部分匹配值（前缀函数）数组为（）。A.[0,0,1,2,0]B.[0,0,1,1,2]C.[0,1,0,1,2]D.[0,0,1,2,3]5.用动态规划解决背包问题时，状态转移方程通常定义为dp[i][j]表示前i个物品放入容量为j的背包的最大价值，其递推关系为（）。A.dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])B.dp[i][j]=max(dp[i][j-1],dp[i-1][j]+v[i])C.dp[i][j]=min(dp[i-1][j],dp[i][j-w[i]]+v[i])D.dp[i][j]=dp[i-1][j]+dp[i][j-w[i]]6.对于有向无环图（DAG），拓扑排序的结果可能有多个，其根本原因是（）。A.图中存在多个入度为0的节点B.图中边的方向不唯一C.节点的处理顺序可以不同D.图中存在环7.若使用Dijkstra算法计算带权图中单源最短路径，当图中存在负权边时，算法（）。A.仍能正确计算所有节点的最短路径B.可能无法正确计算某些节点的最短路径C.会陷入死循环D.时间复杂度变为O(n³)8.给定一个长度为n的数组，要求找出其中第k小的元素（k远小于n），最优算法的平均时间复杂度为（）。A.O(n)B.O(nlogn)C.O(nk)D.O(n+klogn)二、填空题（每题4分，共20分）1.对于序列[5,3,8,1,7,2,6,4]，使用快速排序（选择第一个元素为枢轴）进行第一次划分后，序列变为__________。2.若哈希表的负载因子为0.75，表长为16，则已存储的元素个数为__________。3.一棵高度为h（根节点高度为1）的平衡二叉树（AVL树），最少节点数为__________（用含h的表达式表示）。4.用Prim算法从节点A出发构造下图的最小提供树，第二步选择的边是__________（边用节点对表示，如A-B）。图结构：A连接B（权2）、C（权5）；B连接C（权1）、D（权3）；C连接D（权4）；D连接E（权6）。5.计算递归式T(n)=2T(n/2)+nlogn的时间复杂度为__________（用大O表示）。三、算法设计与分析题（共56分）1.（12分）给定一个字符串s和一个正整数k，要求删除s中所有相邻重复次数至少为k次的字符块。例如，输入s="deeedbbcccbdaa"，k=3，输出应为"aa"（过程：先删除"eee"和"ccc"，得到"dbbbdaa"；再删除"bbb"，得到"daa"；最后无符合条件的块，保留"daa"？注：实际正确输出应为"aa"，需重新验证逻辑）。请描述算法思路，并写出时间复杂度分析。2.（14分）设计一个算法，判断一个给定的二叉树是否为二叉搜索树（BST）。要求：（1）给出递归解法的思路；（2）写出递归实现的伪代码；（3）分析时间复杂度和空间复杂度。3.（16分）某城市的地铁线路图用带权无向图表示，节点为站点，边权为两站间的距离。要求设计一个算法，找出从起点S到终点T的所有最短路径（路径长度相同且最短），并输出路径数量。（1）描述算法步骤；（2）写出关键数据结构的设计；（3）分析时间复杂度。4.（14分）给定一个整数数组nums和一个目标值target，要求找出所有满足i<j<k且nums[i]+nums[j]+nums[k]=target的三元组（i,j,k）。要求三元组不重复（即不同索引但值相同的三元组视为重复）。（1）给出优化后的算法思路（要求时间复杂度低于O(n³)）；（2）写出具体实现步骤；（3）举例说明（如nums=[-1,0,1,2,-1,-4],target=0，输出应包含[[-1,-1,2],[-1,0,1]]）。答案一、单项选择题1.C（二分查找最坏情况比较次数为log₂n+1，时间复杂度O(logn)）2.D（快速排序在划分过程中可能改变相同元素的相对顺序，不稳定）3.B（完全二叉树叶子节点数为⌈n/2⌉，768/2=384）4.A（模式串“ABABC”的前缀函数计算：0（A），0（AB），1（ABA与前缀A匹配），2（ABAB与前缀AB匹配），0（ABABC无公共前后缀））5.A（动态规划背包问题中，对第i个物品，选或不选的最大值）6.A（拓扑排序每次选择入度为0的节点，若存在多个则顺序不同，导致结果不同）7.B（Dijkstra算法假设路径权重非负，负权边可能导致已确定的最短路径被更短路径覆盖）8.A（基于快速选择算法，平均时间复杂度O(n)）二、填空题1.[4,3,2,1,5,7,6,8]（以5为枢轴，小于5的放左，大于的放右，第一次划分后5的位置为索引4）2.12（负载因子=元素数/表长，0.75×16=12）3.F(h)=F(h-1)+F(h-2)+1（斐波那契变种，h=1时1个，h=2时2个，h=3时4个，递推式为前两层节点数加1）4.B-C（Prim算法第一步选A，加入边A-B（权2）；此时已选节点A、B，可选边B-C（1）、A-C（5）、B-D（3），选最小权边B-C）5.O(n(logn)²)（主定理：a=2,b=2,f(n)=nlogn，n^log_ba=n，f(n)比n多项式级大，故T(n)=O(n(logn)²)）三、算法设计与分析题1.算法思路：使用栈结构，栈中每个元素保存字符和连续出现次数。遍历字符串，若当前字符与栈顶字符相同则计数加1，否则压入新字符（计数1）。若计数达到k则弹出栈顶。最后将栈中剩余字符按计数拼接。时间复杂度：O(n)，每个字符入栈和出栈各一次，遍历一次字符串。2.（1）递归思路：每个节点的值需大于左子树所有节点的最大值，小于右子树所有节点的最小值。递归时传递当前节点的允许范围（下界low和上界high）。（2）伪代码：functionisBST(node,low,high):ifnodeisnull:returnTrueifnode.val<=lowornode.val>=high:returnFalsereturnisBST(node.left,low,node.val)andisBST(node.right,node.val,high)初始调用：isBST(root,-infinity,+infinity)（3）时间复杂度O(n)（遍历所有节点），空间复杂度O(h)（递归栈深度，h为树高）。3.（1）算法步骤：①使用Dijkstra算法计算S到所有节点的最短距离dist[]；②从T出发反向遍历，构建前驱节点表（每个节点的前驱为所有满足dist[u]+weight(u,v)=dist[v]的节点u）；③通过深度优先搜索（DFS）或广度优先搜索（BFS）遍历前驱表，统计所有从S到T的路径。（2）关键数据结构：dist数组（存储最短距离）、prev字典（存储每个节点的前驱列表）。（3）时间复杂度：Dijkstra算法O(m+nlogn)（使用优先队列），构建前驱表O(m)，统计路径O(P)（P为路径数，最坏O(n!)，但实际中最短路径数通常远小于n!）。4.（1）优化思路：排序数组后，固定第一个数nums[i]，用双指针法在i+1到末尾区间找j和k，使得nums[j]+nums[k]=target-nums[i]。通过跳过重复元素避免重复三元组。（2）实现步骤：①排序nums；②遍历i从0到n-3：a.若nums[i]>target（若target为正）可提前终止；b.跳过重复的nums[i]；c.设左指针j=i+1，右指针k=n-1；d.计算剩余值remain=target-nums[i]；e.当j<k时：i.若nums[j]+nums[k]==remain，记录三元组，同时跳过j和k的重复值；ii.若和小于remain，j右移；iii.若和大于remain，k左移。（3）示例：nums=[-1,0,1,2,-1,-4]排序后[-4,-1,-1,0,1,2]，target=0。i=0（nums[i]=-4），remain=4，j=1,k=5：-1+2=1≠4，j=2（-1）+2=1≠4，j=3（0）+2=2≠4，j=4（1）+2=3≠4，无结果。i=1（nums[i]=-1），rema