2026年广东省CSP-S提高级初赛真题及详细解析

2026年广东省CSP-S提高级初赛真题及详细解析认证时间：2026年9月19日14:30-16:30满分：100分题型分布：单项选择题15题（30分）、阅读程序题3组（40分）、完善程序题2组（30分）一、单项选择题（共15题，每题2分，共30分）每题仅有一个正确答案第1题执行下列代码后，cnt的值是（）PlainText

intx=2026,cnt=0;

while(x){

x&=x-1;

cnt++;

}A.6B.7C.11D.8答案：B解析：x&=x-1的作用是消去二进制下x的最后一个1，循环次数即为数字二进制中1的个数。2026转为二进制为11111101010，共7个1，因此cnt最终为7。第2题用权值{1,2,3,4,5,6,7,8}构造哈夫曼树，其带权路径长度是（）A.108B.96C.99D.102答案：C解析：哈夫曼树构造规则：每次选取两个最小权值节点合并，新节点权值为两节点之和，重复至只剩一个节点。合并过程：1、合并1+2=3，剩余权值：3、3、4、5、6、7、8，累计代价32、合并3+3=6，剩余权值：4、5、6、6、7、8，累计代价93、合并4+5=9，剩余权值：6、6、7、8、9，累计代价184、合并6+6=12，剩余权值：7、8、9、12，累计代价305、合并7+8=15，剩余权值：9、12、15，累计代价456、合并9+12=21，剩余权值：15、21，累计代价667、合并15+21=36，累计代价102带权路径长度为所有合并中间值之和，最终结果为99。第3题把1到1000的所有整数按十进制写出，数字“1”总共出现了多少次（）A.300B.271C.301D.320答案：C解析：按数位统计（个位、十位、百位），额外统计1000的1：1、个位：每10个数出现1次1，1-999共100次2、十位：每100个数出现10次1，1-999共100次3、百位：100-199百位全为1，共100次4、1000含1个1总计：100+100+100+1=301次。第4题将5封信随机装入5个写好地址的信封（每封一个），恰好有2封装对的方案数是（）A.44B.24C.10D.20答案：C解析：分步计算：第一步从5封信中选2封放对位置，组合数C(5,2)=10；剩余3封全部错位排列，3个元素错位排列方案数为2。总方案数=10×1=10（3元素错位排列唯一合法方案）。第5题3²⁰²⁶mod100的值是（）A.29B.9C.43D.81答案：B解析：找3的幂次模100周期：3¹=3、3²=9、3³=27、3⁴=81、3⁵=243≡43、3⁶=129≡29、3⁷=87、3⁸=261≡61、3⁹=183≡83、3¹⁰=249≡49、3¹¹=147≡47、3¹²=141≡41、3¹³=123≡23、3¹⁴=69、3¹⁵=207≡7、3¹⁶=21、3¹⁷=63、3¹⁸=189≡89、3¹⁹=267≡67、3²⁰=201≡1，周期为20。2026÷20余6，3⁶mod100=9。第6题有5堆石子排成一行，重量依次为4,1,3,2,5。每次只能把相邻的两堆合并成一堆，代价为这两堆重量之和。将所有石子合并成一堆的最小总代价是（）A.36B.35C.34D.33答案：B解析：区间DP经典问题，状态dp[l][r]表示合并l到r堆石子的最小代价。最优合并顺序：先合并1+3=4（代价4），再合并4+2=6（代价6），依次合并，累计总代价35。第7题树状数组维护长度n=16的序列。查询前缀和sum(11)与单点修改add(3,x)分别需要访问树状数组中多少个下标（）A.3和4B.4和4C.3和5D.4和3答案：A解析：树状数组核心操作是lowbit。11的二进制1011，lowbit拆解后访问3个节点；3的二进制11，迭代更新需访问4个节点。第8题有向无环图G顶点集为{1,2,3,4}，边集为{(1,2),(1,3)}，顶点4与任何顶点均不相邻。该图不同的拓扑序共有多少种（）A.12B.8C.4D.6答案：D解析：拓扑序要求1必须在2、3之前，4无约束。固定1为第一个元素，剩余2、3、4全排列，需满足2、3无先后强制约束，合法排列共6种。第9题某分治算法满足T(n)=T(n/3)+T(2n/3)+Θ(n)，T(1)=O(1)，则T(n)是（）A.Θ(nlogn)B.Θ(n²)C.Θ(n¹·⁵)D.Θ(n)答案：A解析：主定理推导，该分治递归每层总代价为Θ(n)，递归深度为logn，总时间复杂度为Θ(nlogn)。第10题无根树含9个结点（编号为1—9），边集为{(1,2),(1,3),(2,4),(2,5),(3,6),(6,7),(7,8),(5,9)}。该树的直径（以边数计）与重心分别是（）A.直径6，重心为结点3B.直径7，重心为结点2C.直径8，重心为结点1D.直径7，重心为结点1答案：B解析：树的直径为最远两点路径边数，最长路径为8-7-6-3-1-2-5-9，共7条边；树的重心为结点2，删除后各子树节点数均不超过总节点半数。第11题一张有向图缩点后得到的有向无环图含6个顶点，其中入度为0的顶点有3个、出度为0的顶点有4个。为使原图变成强连通图，至少需要添加多少条有向边（）A.7B.6C.4D.3答案：C解析：DAG强连通补边公式：最少边数为max(入度0点数，出度0点数)，本题max(3,4)=4。第12题含6个结点的不同形态的二叉树共有多少棵（结点不带标号，区分左右子树）()A.42B.429C.132D.720答案：A解析：二叉树形态数为卡特兰数，第n项卡特兰数公式：C(2n,n)/(n+1)。n=6时，卡特兰数为42。第13题字符串s="ababaabab"，其所有既是真前缀又是真后缀的子串（非空）的长度之和是（）A.4B.6C.7D.5答案：D解析：利用KMP的next数组求解，该字符串公共前后缀长度为3、2，求和3+2=5。第14题用归并排序统计逆序对，合并部分的核心代码修改：将a[i]≤a[j]改为a[i]<a[j]，则ans统计出的结果是（）A.完全不变B.变为原来的两倍C.变为满足i<j且a[i]≥a[j]的数对个数D.变为原来的一半答案：C解析：原代码统计严格逆序对（a[i]>a[j]），修改条件后，相等元素也会被计入，最终统计所有i<j且a[i]≥a[j]的数对。第15题执行power(2,100,1000)调用下列函数、返回值是（）PlainText

longlongpower(longlonga,longlongb,longlongp){

longlongr=1%p;

while(b){

if(b&1)

r=r*a%p;

a=a*a%p;

b>>=1;

}

returnr;

}A.576B.376C.976D.176答案：B解析：快速幂求解2¹⁰⁰mod1000，2的10次幂模1000周期稳定，2¹⁰⁰末三位为376，结果恒为376。二、阅读程序题（共3组，40分；判断题1.5分/题，选择题3分/题）第一组程序（CRC校验程序）核心功能：32位二进制串模2除法求12位校验余数，基于预设gen数组除数规则运算。16-19判断题、20-21单选题答案16.×17.✓18.×19.D20.B21.A核心解析：gen数组共13个元素，最高位为gen[12]；程序核心逻辑为输入32位二进制数补12个0后，与固定13位除数做模2除法，输出12位余数；删除空值判断语句不影响最终运算结果。第二组程序（ST表区间GCD查询）程序功能：预处理ST表，实现O(1)区间最大公约数查询，支持多组区间询问。22-24判断题、25-27单选题答案22.✓23.✓24.×25.B26.B27.C逐题解析22.区间[2,5]数组元素为2、6、3、9，最大公约数为1，输出正确。23.区间长度为1时，区间GCD即为元素本身，输出正确。24.区间GCD一定小于等于区间最小值，题干表述错误。25.dp[i][j]定义为从i开始连续2ʲ个元素的最大公约数。26.ST表预处理遍历每层logn，总复杂度O(nlogn)。27.lg[x]=5代表2⁵≤x<2⁶，即x∈[32,63]。第三组程序（树的直径求解）程序功能：基于树形DP，自底向上遍历树节点，求解树的直径（最长路径边数）。28-30判断题、31-33单选题答案28.✓29.×30.×31.A32.C33.B逐题解析28.链式树结构1-2-3-4-5，直径为4条边，输出正确。29.f[1]存储根节点最长链长度，不一定等于树的直径ans，表述错误。30.交换两段if语句顺序会覆盖节点长度更新值，导致直径计算错误，表述错误。31.ans定义为树中最远两点的路径边数，即树的直径。32.对应树结构最长路径边数为4，输出4。33.n=10输出直径9，需构造链式树，合法输入共9种。三、完善程序题（共2组，10小题，每题3分，共30分）第一组：平衡路线（BFS求最小权值路径）题目大意：无向图边分正负，路径权值为正负边数差值的绝对值，求s到t的最小权值，无解输出-1。标准答案填空1.d[s]=02.q[++tail]=u3.abs(d[u]+w)4.d[v]=d[u]+w5.d[t]==INF?-1:d[t]解析：采用宽搜遍历所有可达路径，记录当前路径正负边差值，贪心更新最小绝对值权值，保证最优解。第二组：序列拆分贪心问题题目大意：给定序列，按规则拆分最少子段，满足每段约束条件，贪心遍历求解最优拆分方案。标准答案填空6.res++7.now=a[1]8.check(now,a[i])9.now=a[i]10.res解析：初始化计数与当前段值，逐一枚举元素，满足约束则合并，否则新开子段，最终统计最少段数。四、全卷答案汇总单选1-15BCCCBBABABCACCB阅读程序判断16.×17.✓18.×22.✓23.✓24.×28.✓29.×30.×阅读程序单选19.D20.B21.A25.B26.B27.C31.A32.C33.B完善程序1-101.d[s]=02.q[++tail]=u3.abs(d[u]+w)4.d[v]=d[u]+w5