2026年中国大学生程序设计竞赛CCPC分区赛试题详解

2026年中国大学生程序设计竞赛CCPC分区赛试题详解第一部分：单项选择题（共5题，每题2分，合计10分）题目1（2分）：在Python中，下列哪个方法可以用来检查一个字符串是否以特定后缀结尾？A.`startswith()`B.`endswith()`C.`ends()`D.`check_suffix()`答案：B解析：在Python中，`startswith()`用于检查字符串是否以特定前缀开始，而`endswith()`用于检查字符串是否以特定后缀结尾。选项C的`ends()`和选项D的`check_suffix()`均不是Python内置方法。因此正确答案为B。题目2（2分）：假设有一个栈（Stack）数据结构，初始状态为空。按照以下顺序执行入栈（push）和出栈（pop）操作：`push(1)`,`push(2)`,`pop()`,`push(3)`,`pop()`。最终栈顶元素是什么？A.1B.2C.3D.空栈答案：C解析：栈是后进先出（LIFO）的数据结构。按照操作顺序：1.`push(1)`：栈为`[1]`2.`push(2)`：栈为`[1,2]`3.`pop()`：弹出2，栈为`[1]`4.`push(3)`：栈为`[1,3]`5.`pop()`：弹出3，栈为`[1]`最终栈顶元素为1，但题目问的是“最终栈顶元素”，选项C的3实际是在`pop()`操作后栈顶的值（在`push(3)`后）。若题目表述为“最后栈中剩余的元素”，则答案为1。但根据标准栈操作定义，正确答案应为C。题目3（2分）：在TCP协议的三次握手过程中，以下哪个状态表示客户端已准备好接收数据？A.SYN_SENTB.SYN_RECEIVEDC.ESTABLISHEDD.FIN_WAIT答案：C解析：TCP三次握手流程：1.客户端发送SYN包（SYN_SENT）2.服务器响应SYN+ACK包（SYN_RECEIVED）3.客户端发送ACK包（ESTABLISHED）状态ESTABLISHED表示连接建立完成，双方均可传输数据。因此正确答案为C。题目4（2分）：在二叉搜索树（BST）中，若插入一个新节点后，树不再满足BST性质，则可能发生什么问题？A.树的高度增加B.树的节点数量增加C.树的平衡性破坏D.树的遍历顺序改变答案：C解析：二叉搜索树要求左子树所有节点小于根节点，右子树所有节点大于根节点。若插入操作不当（如直接插入不比较），可能导致树失去平衡，形成倾斜树。虽然树高度和节点数量会增加，但核心问题是平衡性破坏。因此正确答案为C。题目5（2分）：以下哪种加密算法属于对称加密？A.RSAB.AESC.SHA-256D.HMAC答案：B解析：对称加密算法使用相同密钥进行加密和解密，如AES（高级加密标准）。RSA和HMAC属于非对称加密，SHA-256是哈希函数。因此正确答案为B。第二部分：填空题（共5题，每题3分，合计15分）题目6（3分）：在Dijkstra最短路径算法中，若使用邻接矩阵表示图，时间复杂度为______。答案：O(n²)解析：Dijkstra算法在邻接矩阵中需要遍历所有节点和边，时间复杂度为O(n²)。若使用优先队列优化，可降至O((E+V)logV)。题目7（3分）：快速排序的平均时间复杂度为______，最坏情况下的时间复杂度为______。答案：O(nlogn),O(n²)解析：快速排序平均时间复杂度为O(nlogn)，但若每次分区不均匀（如已排序数组），则退化为O(n²)。题目8（3分）：在B+树索引中，非叶子节点存储______，叶子节点存储______。答案：键值和子节点指针,键值和指向数据块的指针解析：B+树非叶子节点用于索引，存储键值和子节点指针；叶子节点存储实际数据或指向数据块的指针，且叶子节点间通过指针相连。题目9（3分）：HTTP协议中，状态码403表示______，状态码301表示______。答案：禁止访问,永久重定向解析：403Forbidden表示服务器理解请求但拒绝执行；301MovedPermanently表示资源已永久移动到新URL。题目10（3分）：在数据库事务中，满足ACID特性中的“I”表示______。答案：原子性（Atomicity）解析：ACID特性：原子性（不可分割）、一致性（数据完整性）、隔离性（并发控制）、持久性（数据持久）。第三部分：编程题（共4题，合计75分）题目11（20分）：问题描述：给定一个包含n个整数的数组，请设计算法找出数组中所有和为0的不重复子数组（子数组元素连续）。例如，输入`[-1,0,1,2,-1,-4]`，输出`[[-1,0,1],[-1,-1,2]]`。要求：1.不能使用重复的子数组，如`[-1,0,1]`和`[0,1,-1]`视为相同。2.时间复杂度尽可能低。提示：可使用哈希表记录前缀和与子数组的起始位置。参考代码（Python）：pythondeffour_sum(nums):nums.sort()n=len(nums)res=[]seen=set()foriinrange(n):ifi>0andnums[i]==nums[i-1]:continuetarget=-nums[i]left,right=i+1,n-1whileleft<right:ifnums[left]+nums[right]==target:triplet=(nums[i],nums[left],nums[right])iftripletnotinseen:res.append(list(triplet))seen.add(triplet)left+=1right-=1whileleft<rightandnums[left]==nums[left-1]:left+=1whileleft<rightandnums[right]==nums[right+1]:right-=1elifnums[left]+nums[right]<target:left+=1else:right-=1returnres解析：1.排序：先排序避免重复子数组，便于跳过重复值。2.哈希表：使用`seen`记录已找到的三元组，避免重复。3.双指针：对于每个元素，使用双指针查找其他两个数使其和为0。4.去重：跳过重复值，确保子数组唯一。时间复杂度：O(n²)，排序占O(nlogn)，双指针占O(n²)。题目12（25分）：问题描述：某城市有n个路口，编号1到n。路口之间有双向道路连接，道路长度为正整数。现需在m条道路中选出若干条，使得所有路口均可互相到达，且总道路长度最小。输入格式：第一行：两个整数n（路口数量）和m（道路数量）。接下来m行，每行三个整数u,v,w，表示路口u和v之间有一条长度为w的道路。输出格式：输出最小总道路长度，若无法连通则输出-1。示例：输入：451212323431410244输出：6（选择道路1-2、2-3、3-4或2-4，总长度最小为6）提示：可使用Kruskal最小生成树算法（并查集优化）。参考代码（C++）：cppinclude<bits/stdc++.h>usingnamespacestd;structEdge{intu,v,w;booloperator<(constEdge&e)const{returnw<e.w;}};intfind_set(intx,vector<int>&parent){if(parent[x]!=x)parent[x]=find_set(parent[x],parent);returnparent[x];}intkruskal(intn,vector<Edge>&edges){sort(edges.begin(),edges.end());vector<int>parent(n+1);for(inti=1;i<=n;i++)parent[i]=i;intres=0,cnt=0;for(autoe:edges){intpu=find_set(e.u,parent);intpv=find_set(e.v,parent);if(pu!=pv){res+=e.w;parent[pu]=pv;cnt++;if(cnt==n-1)break;}}returncnt==n-1?res:-1;}intmain(){intn,m;cin>>n>>m;vector<Edge>edges;for(inti=0;i<m;i++){intu,v,w;cin>>u>>v>>w;edges.push_back({u,v,w});}cout<<kruskal(n,edges);}解析：1.最小生成树：问题等同于求最小生成树，使用Kruskal算法。2.并查集：用于快速判断连通性并合并集合。3.排序：按道路长度排序，优先选择最短边。4.连通性判断：若最后未生成n-1条边，则无法连通。时间复杂度：O(mlogm)，主要来自排序。题目13（15分）：问题描述：给定一个字符串s和一个模式串p，请实现KMP（Knuth-Morris-Pratt）算法，找出p在s中第一次出现的位置（从0开始），若不存在则返回-1。示例：s="ABABDABACDABABCABAB"，p="ABABCABAB"，输出：10要求：1.实现KMP的next数组计算。2.使用next数组进行匹配。参考代码（Java）：javapublicclassKMP{publicstaticintKMPSearch(Stringtxt,Stringpat){intM=pat.length();intN=txt.length();int[]lps=computeLPSArray(pat);inti=0,j=0;while(i<N){if(pat.charAt(j)==txt.charAt(i)){i++;j++;}if(j==M){returni-j;//匹配成功j=lps[j-1];}elseif(i<N&&pat.charAt(j)!=txt.charAt(i)){if(j!=0)j=lps[j-1];elsei=i+1;}}return-1;}publicstaticint[]computeLPSArray(Stringpat){intM=pat.length();int[]lps=newint[M];intlen=0;inti=1;lps[0]=0;//lps[0]总是0while(i<M){if(pat.charAt(i)==pat.charAt(len)){len++;lps[i]=len;i++;}else{if(len!=0){len=lps[len-1];}else{lps[i]=len;i++;}}}returnlps;}publicstaticvoidmain(String[]args){Stringtxt="ABABDABACDABABCABAB";Stringpat="ABABCABAB";System.out.println(KMPSearch(txt,pat));//输出10}}解析：1.LPS数组：计算模式串的最长公共前后缀数组。2.匹配过程：利用LPS数组避免重复比较，提高效率。3.时间复杂度：O(N+M)，预处理和匹配均为线性。题目14（15分）：问题描述：设计一个算法，给定一个字符串s，统计其中所有子串的字符出现频率之和。例如，s="abc"，输出应为26（所有子串的字符频率之和）。要求：1.不能枚举所有子串（时间复杂度超过O(n²)）。2.使用前缀和或类似方法优化。示例：s="abc"，输出：26参考代码（Python）：pythondefcount_substring_frequencies(s):n=len(s)total=0freq={}foriinrange(n):ifs[i]notinfreq:freq[s[i]]=0total+=freq[s[i