2026年CCF CSP-S信息学奥赛初赛试卷（含详细答案解析）

2026年CCFCSP-S信息学奥赛初赛试卷（含详细答案解析）考试时间：2026年9月满分：100分答题时长：2小时注意事项：1.本试卷全部为笔试题，包含选择题、程序阅读题、程序完善题三部分，答案需规范书写在答题纸上；2.单项选择题选错、不选均不得分；多项选择题多选、少选、错选均不得分；3.程序题需结合代码逻辑、算法原理作答，解析过程需贴合竞赛标准。一、单项选择题（共15题，每题2分，共30分）1.下列不属于线性数据结构的是（）A.队列B.栈C.二叉树D.链表答案：C解析：线性数据结构的元素仅有前后单一前驱后继关系，栈、队列、链表均为典型线性结构。二叉树为树形非线性结构，每个节点可存在多个子节点，不满足线性特征。2.十进制数127转换为二进制数为（）A.1111111B.10000000C.11111110D.1010101答案：A解析：2⁷-1=127，7位二进制全1即为1111111，是8位二进制有符号数的最大正数。3.时间复杂度为O(nlogn)的排序算法是（）A.冒泡排序B.快速排序C.选择排序D.插入排序答案：B解析：冒泡、选择、插入排序平均与最坏时间复杂度均为O(n²)；快速排序平均时间复杂度为O(nlogn)，仅最坏情况退化为O(n²)，是常规O(nlogn)级排序算法。4.一棵有1024个叶子节点的完全二叉树，总结点数为（）A.2047B.2048C.2049D.1024答案：A解析：完全二叉树性质：n₀=n₂+1（叶子节点数=度2节点数+1）。本题n₀=1024，则n₂=1023；完全二叉树无度1节点，总节点数=1024+1023=2047。5.哈希冲突解决方法中，不属于开放定址法的是（）A.线性探测B.二次探测C.链地址法D.随机探测答案：C解析：开放定址法包含线性探测、二次探测、随机探测，核心是在原哈希表内寻找空闲位置；链地址法是为每个哈希位置建立链表存储冲突元素，属于单独的冲突解决机制。6.石子合并问题中，给定序列4、1、3、2、5，仅允许相邻石子合并，最小总合并代价为（）A.32B.33C.34D.35答案：C解析：经典区间DP模型，dp[l][r]表示合并l~r区间石子的最小代价，前缀和预处理区间和。最优合并方案：先合并1+3=4、2+5=7，逐步迭代计算，最终最小总代价为34。7.树状数组维护长度n=16的序列，查询前缀和sum(11)、单点修改add(3,x)分别需要访问的下标个数为（）A.3和4B.4和4C.3和5D.4和3答案：A解析：树状数组依靠lowbit运算遍历下标。sum(11)：11-lowbit(11)=10，10-lowbit(10)=8，8-lowbit(8)=0，共访问11、10、8三个下标；add(3,x)：3→4→8→16，共访问4个下标。8.有向图拓扑排序的核心作用是（）A.求图的最短路径B.判断图是否存在环C.统计图的边数D.计算图的直径答案：B解析：拓扑排序仅适用于有向无环图，若图存在环则无法完成完整拓扑排序，因此常用来判定有向图的环结构，其余功能均不属于拓扑排序范畴。9.下列关于贪心算法的说法，正确的是（）A.所有问题都可以用贪心求解最优解B.贪心局部最优一定推导全局最优C.活动选择问题可用贪心求解D.贪心算法时间复杂度一定高于动态规划答案：C解析：贪心仅适用于具备贪心选择性质和最优子结构的问题，局部最优不一定全局最优；活动选择、区间覆盖等经典问题可通过贪心得到最优解；贪心时间复杂度通常低于动态规划。10.一个栈的入栈序列为1、2、3、4、5，不可能的出栈序列是（）A.3、2、1、5、4B.4、3、5、2、1C.2、1、5、3、4D.1、2、3、4、5答案：C解析：栈遵循后进先出规则。C选项中5出栈后，栈内剩余3、4，后续出栈必须先4后3，无法出现3先出、4后出的序列。11.二分查找算法的最坏时间复杂度为（）A.O(n)B.O(n²)C.O(logn)D.O(1)答案：C解析：二分查找每次将查找区间缩小一半，无论最优、最坏情况，时间复杂度均稳定为O(logn)，是有序序列高效查找算法。12.无向连通图有n个顶点、m条边，其最小生成树的边数为（）A.nB.n-1C.m-1D.m-n答案：B解析：n个节点的连通树结构恰好包含n-1条边，且无环、连通，最小生成树是原图的极小连通子图，固定为n-1条边。13.下列程序片段的输出结果为（）PlainText

ints=0;

for(inti=1;i<=5;i++)

if(i%2==1)s+=i;

cout<<s;A.6B.9C.15D.5答案：B解析：程序累加1~5中的奇数，即1+3+5=9，最终输出9。14.图的深度优先遍历（DFS）采用的辅助数据结构是（）A.队列B.栈C.堆D.哈希表答案：B解析：DFS遵循“先深入、后回溯”的逻辑，适配栈后进先出特性；广度优先遍历（BFS）采用队列实现。15.状态压缩DP主要适用于哪种场景（）A.数据规模n≤20的状态枚举B.超大批量数据排序C.图的最短路求解D.字符串匹配答案：A解析：状态压缩通过二进制位记录状态，状态总数为2ⁿ，仅适配n≤20的小规模场景，是信奥经典DP优化模型。二、多项选择题（共5题，每题3分，共15分）1.下列属于稳定排序的有（）A.冒泡排序B.归并排序C.快速排序D.基数排序答案：ABD解析：稳定排序指相等元素相对顺序不变。冒泡、归并、基数排序均稳定；快速排序的交换操作会打乱相等元素顺序，属于不稳定排序。2.下列关于树状数组与线段树的说法，正确的有（）A.树状数组代码更简洁、常数更小B.线段树可支持区间修改、区间查询C.树状数组可完全替代线段树D.线段树适用场景更广答案：ABD解析：树状数组仅支持单点修改、前缀查询，无法处理复杂区间操作，不能替代线段树；线段树功能全面、场景更广，树状数组常数更优、代码简洁。3.能够求解图最短路径的算法有（）A.DijkstraB.SPFAC.FloydD.Kruskal答案：ABC解析：Dijkstra、SPFA求解单源最短路，Floyd求解多源最短路；Kruskal是最小生成树算法，与最短路无关。4.下列算法中，属于分治思想的有（）A.归并排序B.快速排序C.二分查找D.暴力枚举答案：ABC解析：分治核心是分而治之，将大问题拆分为同质小问题求解。归并、快排、二分查找均基于分治思想；暴力枚举无拆分优化，不属于分治。5.下列关于栈和队列的说法，正确的有（）A.栈先进后出B.队列先进先出C.两者均为线性结构D.两者均可随机访问元素答案：ABC解析：栈和队列均为线性结构，分别遵循后进先出、先进先出规则；两者仅能操作首尾元素，不支持随机访问。三、程序阅读题（共3题，每题10分，共30分）阅读程序1PlainText

#include<iostream>

usingnamespacestd;

intf(intn){

if(n==0)return0;

if(n==1)return1;

returnf(n-1)+2*f(n-2);

}

intmain(){

cout<<f(6);

return0;

}问题：写出程序输出结果，并推导递推公式。答案：输出结果为31详细解析：递推公式：f(0)=0，f(1)=1，f(n)=f(n-1)+2f(n-2)逐步计算：f(2)=f(1)+2f(0)=1+0=1f(3)=f(2)+2f(1)=1+2=3f(4)=f(3)+2f(2)=3+2=5f(5)=f(4)+2f(3)=5+6=11f(6)=f(5)+2f(4)=11+10=31阅读程序2PlainText

#include<iostream>

usingnamespacestd;

intmain(){

inta[]={3,8,15,6,10};

intcnt=0;

for(inti=0;i<5;i++){

if(a[i]>5&&a[i]%2==1)

cnt++;

}

cout<<cnt;

return0;

}问题：程序输出结果为多少？说明统计逻辑。答案：输出结果为1详细解析：程序统计数组中大于5且为奇数的元素个数。数组元素遍历判断：3（小于5，不满足）、8（偶数，不满足）、15（大于5且奇数，满足）、6（偶数，不满足）、10（偶数，不满足）。仅1个元素符合条件，最终cnt=1。阅读程序3PlainText

#include<iostream>

#include<algorithm>

usingnamespacestd;

intmain(){

ints=0;

for(inti=1;i<=8;i++){

if(i%3==0)s+=i;

elses-=i;

}

cout<<s;

return0;

}问题：计算程序最终输出值。答案：输出结果为-12详细解析：遍历1~8，3的倍数累加，非3的倍数累减：s=-1-2+3-4-5+6-7-8=(-1-2)+3+(-4-5)+6+(-7-8)=-3+3-9+6-15=-12四、程序完善题（共2题，第1题10分，第2题15分，共25分）完善程序1（最大公约数）题目功能：利用欧几里得算法求解两个正整数的最大公约数，补全空缺代码。PlainText

#include<iostream>

usingnamespacestd;

intgcd(inta,intb){

if(____①____)returna;

return____②____;

}

intmain(){

intx,y;

cin>>x>>y;

cout<<gcd(x,y)<<endl;

return0;

}答案：①b==0②gcd(b,a%b)详细解析：欧几里得算法核心：gcd(a,b)=gcd(b,amodb)，递归终止条件为余数b=0，此时a即为最大公约数。递归不断将b作为新的a、a%b作为新的b，直至满足终止条件。完善程序2（考试答案最优构造）题目描述：有n名学生，m道AB选择题，每题答对得1分、答错得0分。给定每名学生的作答答案，构造一套唯一标准答案（每题为A或B），最大化所有学生得分的绝对值差值总和∑|rPlainText

#include<iostream>

#include<cmath>

usingnamespacestd;

constintN=1005;

stringans[N];

intn,m;

intmain(){

cin>>n>>m;

for(inti=1;i<=n;i++)cin>>ans[i];

intres=0;

for(intj=0;j<m;j++){

intcntA=0,cntB=0;

for(inti=1;i<=n;i++){

if(ans[i][j]=='A')____①____;

else____②____;

}

//贪心选择最优答案，最大化单题贡献

res+=max(____③____);

}

cout<<res<<endl;

return0;

}