福建信息竞赛试题及答案

福建信息竞赛经典试题及答案考试时间：______分钟总分：______分姓名：______选择题（每题5分，共15分）1.给定一个包含'('、')'、'['、']'的字符串，判断括号是否匹配。以下哪个算法不能正确实现括号匹配？A.使用栈，遇到左括号入栈，遇到右括号判断栈顶是否匹配，匹配则出栈，否则失败。B.使用递归，每次检查字符串首尾是否匹配，然后递归处理中间子串。C.使用计数器，遍历字符串，遇到'('或'['计数器+1，遇到')'或']'计数器-1，最终计数器为0则匹配。D.使用哈希表记录括号对，遍历字符串时动态检查当前字符与哈希表中对应字符是否匹配。2.对于一棵二叉树，以下哪种操作的时间复杂度为O(n)，其中n为节点数？A.查找最大值B.计算树的高度C.插入一个新节点D.删除指定节点3.在排序算法中，快速排序的平均时间复杂度为：A.O(n)B.O(nlogn)C.O(n²)D.O(logn)填空题（每题7分，共35分）1.在图论中，用于求解单源最短路径的算法，当边权均为非负时，常用算法是________。2.动态规划中，状态转移方程描述了当前状态与________状态之间的关系。3.字符串匹配算法中，通过构建部分匹配表（next数组）来避免不必要的字符比较的算法是________。4.在数据结构中，栈的典型应用包括函数调用和________。5.贪心算法在解决区间调度问题时，通常按照区间的________进行排序以获得最优解。编程题（共50分）1.（15分）题目：活动选择问题。有n个活动，每个活动有开始时间s_i和结束时间f_i，要求选择尽可能多的活动，且任意两个活动时间不重叠。输入第一行是n，接下来n行每行s_i和f_i（1≤s_i≤f_i≤10^9）。输出最大活动数。2.（15分）题目：迷宫问题。给定一个m行n列的迷宫，'0'表示可走，'1'表示墙。起点(1,1)，终点(m,n)。使用BFS算法求从起点到终点的最短路径长度。输入第一行是m和n，接下来m行n列的迷宫矩阵。输出最短路径长度，若无法到达输出-1。3.（10分）题目：0-1背包问题。给定n个物品，每个物品有重量w_i和价值v_i，和一个容量为W的背包。选择物品装入背包，使总价值最大。输入第一行是n和W，接下来n行每行w_i和v_i（1≤w_i,v_i≤1000）。输出最大价值。4.（10分）题目：Dijkstra算法。给定一个有向图，节点数n，边数m，每条边有起点、终点和权值（非负）。求从节点1到节点n的最短路径长度。输入第一行是n和m，接下来m行每行u、v、w（1≤u,v≤n,1≤w≤1000）。输出最短路径长度，若无法到达输出-1。试卷答案1.C解析：选项A使用栈，遇到左括号入栈，右括号匹配栈顶出栈，正确；选项B使用递归检查首尾匹配，正确；选项C仅用计数器无法区分括号类型（如"(]"计数器为0但不匹配），错误；选项D用哈希表记录括号对动态检查，正确。因此C不能正确实现。2.A解析：查找最大值必须遍历所有节点，时间复杂度O(n)；计算高度需递归或遍历，O(n)；插入和删除需查找节点位置，最坏O(n)，但题目问的是“哪种操作”，查找最大值明确是O(n)，而其他操作可能因树结构不同而变化。3.B解析：快速排序平均时间复杂度为O(nlogn)，最坏O(n²)，但题目指定平均情况；O(n)是线性排序如计数排序，O(n²)是冒泡排序，O(logn)是二分查找。1.Dijkstra算法解析：单源最短路径问题，边权非负时，Dijkstra算法通过优先队列逐步扩展最短路径，确保每次选择当前最小距离节点，正确求解。2.子问题解析：动态规划中，状态转移方程描述当前状态与已求解的子问题状态之间的关系，通过子问题解组合得到当前状态解。3.KMP算法解析：KMP算法通过构建next数组（部分匹配表），在字符串匹配时利用已匹配信息跳过不必要的字符比较，提高效率。4.表达式求值解析：栈的典型应用包括函数调用（保存返回地址）和表达式求值（处理运算符优先级），符合后进先出特性。5.结束时间（或右端点）解析：贪心算法在区间调度中，按结束时间升序排序，优先选择结束时间早的活动，为后续活动留更多空间，确保活动数最大化。1.答案：贪心算法，按结束时间排序，遍历选择不重叠活动。解析：思路：将活动按结束时间升序排序；初始化计数器为0，记录上一个活动的结束时间；遍历每个活动，若当前活动开始时间大于上一个结束时间，则选择该活动并更新结束时间；最终计数器即为最大活动数。关键点：排序保证贪心选择最优，时间复杂度O(nlogn)。2.答案：BFS算法，从起点开始逐层遍历，记录最短路径。解析：思路：使用队列存储节点和距离；初始化距离数组为-1（未访问），起点距离为0；队列加入起点；当队列非空，取出节点，检查邻居；若邻居可走且未访问，更新距离并入队；若到达终点，返回距离；否则最终返回-1。关键点：BFS保证第一次到达即为最短路径，时间复杂度O(m*n)，其中m,n为迷宫行列数。3.答案：动态规划，二维数组dp[i][w]表示前i个物品容量为w的最大价值。解析：思路：定义dp数组，dp[i][w]=max(dp[i-1][w],dp[i-1][w-w_i]+v_i)ifw>=w_ielsedp[i-1][w]；初始化dp[0][w]=0；遍历物品和容量，填充dp数组；最终返回dp[n][W]。关键点：状态转移方程基于是否选择当前物品，时间复杂度O(n*W)。4.答案：Dijkstra算法，使用优先队列求单源最短路径。解析：思路：初始化距离数组dist，dist[1]=0，其余为无穷大；优先队列存储(dist[node],node)；队列加入(0,1)；当队