2026年信奥赛C++普及组csp-j初赛模拟卷（三）【文末附答案和解析】

一、单项选择题（共15题，每题2分，共30分；每题有且仅有一个正确选项）

1.二进制数1101.101对应的十进制数是（）。

A. 13.625

B. 13.5

C. 13.25

D. 13.125

2.八进制数( 753 ) 8 (753)_8(753)8转换为十六进制数是（）。

A.( 1 E B ) 16 (1EB)_{16}(1EB)16

B.( 1 E C ) 16 (1EC)_{16}(1EC)16

C.( 1 E D ) 16 (1ED)_{16}(1ED)16

D.( 1 E E ) 16 (1EE)_{16}(1EE)16

3.已知x = 12，y = 7，则表达式(x & y) | (x ^ y)的值是（）。

A. 4

B. 12

C. 15

D. 7

4.表达式8 | 3 << 2的值是（）。（提示：<<优先级高于|）

A. 11

B. 12

C. 14

D. 20

5.一棵完全二叉树共有 1000 个结点，则该二叉树中叶子结点的个数为（）。

A. 500

B. 501

C. 499

D. 500 或 501

6.已知一棵二叉树的前序遍历序列为ABDECFG，中序遍历序列为DEBACFG，则该二叉树的后序遍历序列为（）。

A.EDBFGCA

B.EDBGCFA

C.DEBGFCA

D.DBEGFCA

7.用权值{5, 6, 8, 9, 12}构造哈夫曼树，该树的带权路径长度（WPL）为（）。

A. 85

B. 90

C. 91

D. 100

8.一棵哈夫曼树共有 11 个结点，则其叶子结点的个数为（）。

A. 5

B. 6

C. 7

D. 8

9.一个具有 8 个顶点的无向连通图，至少需要（）条边才能保证是连通的；若要构成一棵树，则需要（）条边。

A. 7，8

B. 8，9

C. 7，7

D. 8，8

10.在一个有向图中，所有顶点的入度之和为 20，则该有向图的边数为（）。

A. 10

B. 20

C. 40

D. 无法确定

11.以下关于图的说法中，错误的是（）。

A. 无向完全图K n K_nKn的边数为n ( n − 1 ) / 2 n(n-1)/2n(n−1)/2

B. 树是连通且无环的无向图

C. 有向图中所有顶点的入度之和等于出度之和

D. 连通无向图的边数一定大于等于顶点数

12.int类型变量x的值为-8（32位补码表示），则x >> 2的结果为（）。

A.-2

B.-3

C.2

D.3

13.十进制数-27的 8 位二进制补码表示为（）。

A.11100101

B.11100100

C.11100110

D.10011011

14.栈是一种特殊的线性表，具有（）的特性。

A. 先进先出

B. 先进后出

C. 随机存取

D. 只能插入不能删除

15.以下排序算法中，最坏情况下时间复杂度为O(n²)的是（）。

A. 归并排序

B. 快速排序

C. 堆排序

D. 以上都是

二、阅读程序题（共3题，共40分）（一）（本题8分）

阅读下面的程序，回答 16~20 题。

#includeusingnamespacestd;intn,ans;inta[100];voiddfs(intx,intsum){if(x>n){if(sum>ans)ans=sum;return;}dfs(x+1,sum);dfs(x+2,sum+a[x]);}intmain(){cin>>n;for(inti=1;i<=n;i++)cin>>a[i];ans=0;dfs(1,0);cout<<ans<<endl;return0;}

判断题（每题1分）

16.若输入n=3，a = {1, 2, 3}，程序输出为 4。（）

17.函数dfs的时间复杂度为O ( 2 n ) O(2^n)O(2n)。（）

18.若将所有a[i]都改为正数，程序输出的含义是：从数组a中选取若干个不相邻的元素，使总和最大。（）

19.若输入n=4，a = {10, 1, 10, 1}，程序输出为 20。（）

20.该程序可以用动态规划优化为O(n)的时间复杂度。（）

（二）（本题12分）

阅读下面的程序，回答 21~26 题。

#includeusingnamespacestd;intn,m;intg[105][105];intvis[105];intq[105],head,tail;voidbfs(ints){head=1;tail=1;q[1]=s;vis[s]=1;while(head<=tail){intu=q[head];head++;for(intv=1;v<=n;v++){if(g[u][v]&&!vis[v]){vis[v]=1;tail++;q[tail]=v;}}}}intmain(){cin>>n>>m;for(inti=1;i<=m;i++){intu,v;cin>>u>>v;g[u][v]=1;g[v][u]=1;}intcnt=0;for(inti=1;i<=n;i++){if(!vis[i]){cnt++;bfs(i);}}cout<<cnt<<endl;return0;}

判断题（每题1.5分）

21.该程序读入的是一个有向图。（）

22.变量cnt最终输出的是图中连通分量的个数。（）

23.若输入n=5, m=4，边为(1,2), (2,3), (3,4), (4,5)，程序输出为 2。（）

24.若将g[u][v] = 1; g[v][u] = 1;改为g[u][v] = 1;，程序功能不变。（）

25.该程序在最坏情况下的时间复杂度为O ( n 2 ) O(n^2)O(n2)。（）

选择题（3分）

26.若输入n=6, m=5，边为(1,2), (2,3), (4,5), (5,6), (1,6)，程序输出为（）。

A. 1

B. 2

C. 3

D. 4

（三）（本题20分）

阅读下面的程序，回答 27~33 题。

#include#includeusingnamespacestd;chars[100];intstk[100],top;intmain(){cin>>s;intlen=strlen(s);top=0;boolflag=true;for(inti=0;i<len;i++){if(s[i]=='('||s[i]=='['||s[i]=='{'){stk[++top]=s[i];}else{if(top==0){flag=false;break;}charc=stk[top--];if((s[i]==')'&&c!='(')||(s[i]==']'&&c!='[')||(s[i]=='}'&&c!='{')){flag=false;break;}}}if(top!=0)flag=false;cout<<(flag?"YES":"NO")<<endl;return0;}

判断题（每题2分）

27.输入"()"时，程序输出"YES"。（）

28.输入"([)]"时，程序输出"YES"。（）

29.输入"{"时，程序输出"NO"。（）

30.该算法的时间复杂度为O(n)，其中n为字符串长度。（）

31.若输入字符串中包含数字字符（如"(1)"），程序会因数组越界而崩溃。（）

选择题（每题5分）

32.输入"({[]})"时，程序的输出是（）。

A."YES"

B."NO"

C. 程序出错

D. 无法确定

33.输入"((()))"时，程序的输出是（）。

A."YES"

B."NO"

C. 程序出错

D. 无法确定

三、完善程序题（共2题，每题15分，共30分）（一）（本题15分）

（二叉树的层序遍历）给定一棵二叉树，每个结点用整数编号表示，左、右孩子用-1表示空。请补全程序，输出该二叉树的层序遍历序列（从根结点开始，逐层从左到右输出每个结点的编号）。

算法提示：层序遍历可以使用队列实现。先将根结点入队，然后每次从队首取出一个结点并输出，再将其非空的左、右孩子依次入队，重复此过程直到队列为空。

试补全程序。

#includeusingnamespacestd;structNode{intleft,right;}tree[100];intq[100],head,tail;voidlevelOrder(introot){if(root==-1)return;head=①;tail=②;q[++tail]=root;while(③){intu=q[++head];cout<<u<<' ';if(④)q[++tail]=tree[u].left;if(⑤)q[++tail]=tree[u].right;}}intmain(){intn,root;cin>>n;for(inti=1;i<=n;i++){cin>>tree[i].left>>tree[i].right;}cin>>root;levelOrder(root);return0;}

34.①处应填（）

A.0B.1C.-1D.root

35.②处应填（）

A.0B.1C.-1D.root

36.③处应填（）

A.head < tailB.head <= tailC.head == tailD.head > tail

37.④处应填（）

A.tree[u].left != -1B.tree[u].left == -1C.tree[u].leftD.tree[u].left > 0

38.⑤处应填（）

A.tree[u].right != -1B.tree[u].right == -1C.tree[u].rightD.tree[u].right > 0

（二）（本题15分）

（最大连续子段和）给定一个长度为n的整数序列a[1..n]，求其最大连续子段和。例如，序列{-2, 1, -3, 4, -1, 2, 1, -5, 4}的最大子段和为6（对应子段{4, -1, 2, 1}）。本题保证子段非空，即序列中至少有一个正数。

算法提示：使用动态规划。令dp[i]表示以a[i]结尾的最大连续子段和，则状态转移方程为：

若dp[i-1] > 0，则dp[i] = dp[i-1] + a[i]；
否则dp[i] = a[i]。

答案ans为所有dp[i]中的最大值。

试补全程序。

#includeusingnamespacestd;intn,a[100],dp[100];intmain(){cin>>n;for(inti=1;i<=n;i++)cin>>a[i];intans=①;dp[0]=②;for(inti=③;i<=n;i++){if(④)dp[i]=dp[i-1]+a[i];elsedp[i]=a[i];if(⑤)ans=dp[i];}cout<<ans<<endl;return0;}

39.①处应填（）

A.a[1]B.0C.-100000D.a[n]

40.②处应填（）

A.0B.a[1]C.-100000D.1

41.③处应填（）

A.1B.2C.0D.n

42.④处应填（）

A.dp[i-1] > 0B.dp[i-1] < 0C.dp[i-1] >= 0D.dp[i-1] <= 0

43.⑤处应填（）

A.dp[i] > ansB.dp[i] < ansC.dp[i] >= ansD.dp[i] <= ans

参考答案与解析

一、单项选择题

1. A 解析：1101.101₂ = 1×8 + 1×4 + 0×2 + 1×1 + 1×0.5 + 0×0.25 + 1×0.125 = 13.625。

2. A 解析：(753)₈ = 7×64 + 5×8 + 3 = 491。491 ÷ 16 = 30 余 11(E)，30 ÷ 16 = 1 余 14(E)，1 ÷ 16 = 0 余 1，得(1EB)₁₆。

3. C 解析：(x & y) | (x ^ y) = x | y = 12 | 7 = 15（二进制1100 | 0111 = 1111）。

4. B 解析：3 << 2 = 12（0011左移两位得1100），8 | 12 = 12（1000 | 1100 = 1100）。

5. A 解析：完全二叉树中，叶子结点数 =⌈n/2⌉ = 500。

6. A 解析：由前序知A为根，中序左子树DEB，右子树CFG。递归得后序为EDBFGCA。

7. C 解析：构造哈夫曼树：合并5、6得11；合并8、9得17；合并11、12得23；合并17、23得40。WPL = 11 + 17 + 23 + 40 = 91。

8. B 解析：哈夫曼树中度为2的结点数 = 叶子数 - 1，总结点数 = 2n - 1 = 11 ⇒ n = 6。

9. C 解析：连通图至少n-1=7条边，树也是n-1=7条边。

10. B 解析：有向图中入度之和 = 出度之和 = 边数。

11. D 解析：连通无向图边数至少为n-1，可以等于n-1（树），不一定大于等于n。

12. A 解析：-8的补码右移2位（算术右移）得-2。

13. A 解析：27的二进制00011011，取反11100100，加1得11100101。

14. B 解析：栈是先进后出（LIFO）。

15. B 解析：快速排序最坏情况O(n²)。

二、阅读程序题（一）阅读程序一

16. 正确（1分）解析：枚举不相邻选取，最大为1+3=4。

17. 正确（1分）解析：每个位置两种选择，递归规模2^n。

18. 正确（1分）解析：选当前则跳过下一个，即不相邻。

19. 正确（1分）解析：选10+10=20。

20. 正确（1分）解析：可用dp[i] = max(dp[i-1], dp[i-2]+a[i])优化。

（二）阅读程序二

21. 错误（1.5分）解析：同时设置g[u][v]和g[v][u]，表示无向图。

22. 正确（1.5分）解析：BFS遍历每个连通块，cnt为连通分量数。

23. 错误（1.5分）解析：5个顶点4条边形成一条链，全部连通，cnt=1。

24. 错误（1.5分）解析：改为有向图后，BFS只能沿单向边，功能改变。

25. 正确（1.5分）解析：两层循环，最坏O(n²)。

26. B（3分）解析：边形成两个连通分量：{1,2,3,6}和{4,5}。

（三）阅读程序三

27. 正确（2分）解析：()匹配，栈空，输出 YES。

28. 错误（2分）解析：([)]中，遇到)时栈顶为[，不匹配，输出 NO。

29. 正确（2分）解析：{入栈后，循环结束，栈非空，flag=false，输出 NO。

30. 正确（2分）解析：每个字符处理一次，时间复杂度 O(n)。

31. 错误（2分）解析：数字字符进入else，若栈空则 flag=false，否则与栈顶比较，不会越界（stk[top--]在top>0时访问合法）。

32. A（5分）解析：({[]})括号完全匹配，输出 YES。

33. A（5分）解析：((()))完全匹配，输出 YES。

三、完善程序题（一）二叉树的层序遍历

34. A队列头指针初始化为 0

35. A队列尾指针初始化为 0

36. A当head < tail时队列非空，继续循环

37. A左孩子非空（!= -1）时才入队

38. A右孩子非空（!= -1）时才入队

（二）最大连续子段和

39. Aans初始为a[1]，保证子段非空

40. Adp[0] = 0，方便i=1时判断

41. A循环从 1 开始，包含第一个元素

42. A经典 Kadane 算法：若前一个最大和为正则累加，否则重新开始

43. A若当前dp[i]更大则更新答案

更多内容请关注专栏：信奥赛C++普及组csp-j初赛&复赛真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

【秘籍汇总】（完整csp信奥赛C++学习资料）：

1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

2、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转 https://edu.csdn.net/course/detail/41081 点击跳转

3、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划： https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL： https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践： https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转

4、csp信奥赛冲刺一等奖有效刷题题解：

信奥赛C++普及组CSP-J一等奖通关刷题题单及题解： https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

信奥赛C++普及组csp-j初赛&复赛真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）： https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转

5、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

GESP(C++ 七级+八级)真题题解（持续更新）： https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转

· 文末祝福 ·

#includeusingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}

2026年信奥赛C++普及组csp-j初赛模拟卷（三）【文末附答案和解析】