企业官网建设流程全解析

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

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

1.八进制数(154)₈转换为十六进制数是（ ）。

A.(6C)₁₆B.(6D)₁₆C.(6E)₁₆D.(6A)₁₆

2.已知x = 15，y = 9，则表达式(x ^ y) | (x & y)的值是（ ）。

A. 15 B. 14 C. 13 D. 12

3.表达式(2 << 3) | (5 & 3)的值是（ ）。

A. 17 B. 18 C. 20 D. 16

4.一棵深度为 6 的满二叉树（根深度为1）共有（ ）个结点。

A. 63 B. 64 C. 31 D. 32

5.已知一棵二叉树的前序遍历序列为GDAFEMHZ，中序遍历序列为ADEFGHMZ，则该二叉树的后序遍历序列为（ ）。

A.AEFDHZMGB.AEFDMZHGC.AEFDHZGMD.AEFDZMGH

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

A. 85 B. 90 C. 95 D. 100

7.一个具有 8 个顶点的无向图，若所有顶点的度数之和为 24，则该图有（ ）条边。

A. 8 B. 12 C. 16 D. 24

8.入栈序列为1, 2, 3, 4, 5，以下哪个是不可能的出栈序列？（ ）

A.3, 4, 2, 1, 5B.3, 5, 4, 2, 1C.4, 5, 3, 2, 1D.4, 3, 5, 1, 2

9.以下排序算法中，不稳定的是（ ）。

A. 冒泡排序 B. 插入排序 C. 选择排序 D. 归并排序

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

A.11001110B.11001101C.11001111D.10011010

11.若int x = 5，则~x在 8 位二进制下表示为（ ）。

A.11111010B.11111011C.00000101D.00000100

12.以下逻辑表达式，与!(A && B)等价的是（ ）。

A.!A && !BB.!A || !BC.A || BD.A && !B

13.队列的入队顺序为x, y, z，经过若干入队出队操作后，以下哪个可能是出队序列？（ ）

A.z, y, xB.x, z, yC.y, x, zD.x, y, z

14.递归函数fib(n)定义如下：fib(0)=0, fib(1)=1, fib(n)=fib(n-1)+fib(n-2)（n≥2），则fib(6)的值为（ ）。

A. 5 B. 8 C. 13 D. 21

15.从 6 个不同元素中选出 2 个元素的排列数（有序）为（ ）。

A. 15 B. 30 C. 36 D. 12

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

（一）（本题10分）

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

#include<iostream>usingnamespacestd;intn;intfact(intx){if(x==0)return1;returnx*fact(x-1);}intmain(){cin>>n;cout<<fact(n)<<endl;return0;}

判断题（每题2分）

16.若输入n=4，程序输出为 24。（ ）

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

18.该程序可以改为循环实现，且时间复杂度仍为O(n)。（ ）

选择题（每题2分）

19.若输入n=5，程序输出为（ ）。

A. 120 B. 24 C. 60 D. 720

20.当输入n为负数时，程序会（ ）。

A. 输出 0 B. 无限递归导致栈溢出 C. 输出负数 D. 正常返回

（二）（本题14分）

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

#include<iostream>usingnamespacestd;intn,m;intg[55][55];intvis[55];voiddfs(intu){vis[u]=1;for(intv=1;v<=n;v++){if(g[u][v]&&!vis[v])dfs(v);}}intmain(){cin>>n>>m;for(inti=1;i<=m;i++){intu,v;cin>>u>>v;g[u][v]=1;g[v][u]=1;}intans=0;for(inti=1;i<=n;i++){if(!vis[i]){ans++;dfs(i);}}cout<<ans<<endl;return0;}

判断题（每题2分）

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

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

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

选择题（每题4分）

24.若将g[u][v] = 1; g[v][u] = 1;改为g[u][v] = 1;（仅保留单向边），则程序功能将（ ）。

A. 不变
B. 无法正确统计原无向图的连通分量
C. 统计有向图中的强连通分量
D. 程序运行出错

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

A. 1 B. 2 C. 3 D. 4

（三）（本题16分）

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

#include<iostream>#include<cstring>usingnamespacestd;chars[100];intcnt[26];intmain(){cin>>s;intlen=strlen(s);for(inti=0;i<len;i++){cnt[s[i]-'a']++;}intmaxc=0;charans='a';for(inti=0;i<26;i++){if(cnt[i]>maxc){maxc=cnt[i];ans='a'+i;}}cout<<ans<<maxc<<endl;return0;}

判断题（每题2分）

26.若输入"abc"，程序输出为a1。（ ）

27.若输入"aabb"，程序输出为a2。（ ）

28.若输入"zz"，程序输出为z2。（ ）

选择题（每题5分）

29.若输入"hello"，程序输出为（ ）。

A.h1B.e1C.l2D.o1

30.该程序的时间复杂度为（ ）。

A.O(n)B.O(n log n)C.O ( n 2 ) O(n^2)O(n2)D.O(26n)

三、完善程序题（共2题，每题15分，共30分；每空3分）

（一）（本题15分）

（二分查找）给定一个长度为n的非降序整数数组a[1..n]和一个目标值x，请补全程序，使用二分查找在数组中找到x第一次出现的位置（下标从 1 开始）。若不存在则输出-1。

算法提示：二分查找。当中间值大于等于x时，向左缩小区间，否则向右。

#include<iostream>usingnamespacestd;intn,x;inta[100];intmain(){cin>>n>>x;for(inti=1;i<=n;i++)cin>>a[i];intl=1,r=n,ans=-1;while(①){intmid=②;if(③){ans=mid;r=④;}else{l=⑤;}}cout<<ans<<endl;return0;}

34.①处应填（ ）

A.l <= rB.l < rC.l >= rD.l == r

35.②处应填（ ）

A.(l + r) / 2B.(l + r + 1) / 2C.l + (r - l) / 2D.l + (r - l + 1) / 2

36.③处应填（ ）

A.a[mid] >= xB.a[mid] > xC.a[mid] <= xD.a[mid] == x

37.④处应填（ ）

A.mid - 1B.midC.mid + 1D.r - 1

38.⑤处应填（ ）

A.mid + 1B.midC.mid - 1D.l + 1

（二）（本题15分）

（前缀和与区间和）给定一个长度为n的整数数组a[1..n]，以及q次查询，每次查询给出区间[l, r]，求该区间内所有元素的和。请补全程序，利用前缀和数组实现快速查询。

#include<iostream>usingnamespacestd;intn,q;inta[100],sum[100];intmain(){cin>>n;for(inti=1;i<=n;i++)cin>>a[i];①for(inti=1;i<=n;i++){②}cin>>q;while(q--){intl,r;cin>>l>>r;intans=③;cout<<ans<<endl;}return0;}

39.①处应填（ ）

A.sum[0] = 0;B.sum[1] = 0;C.sum[n] = 0;D. 不需要

40.②处应填（ ）

A.sum[i] = sum[i-1] + a[i];B.sum[i] = sum[i-1] + a[i-1];C.sum[i] = sum[i] + a[i];D.sum[i] = a[i];

41.③处应填（ ）

A.sum[r] - sum[l-1]B.sum[r] - sum[l]C.sum[l] - sum[r-1]D.sum[r-1] - sum[l-1]

42.若将数组a改为从下标 0 开始存储，即输入a[0]到a[n-1]，并采用正确的前缀和初始化方式sum[0] = 0; for (i = 0; i < n; i++) sum[i+1] = sum[i] + a[i];，则查询区间[l, r]（0 ≤ l ≤ r < n）的和的正确表达式为（ ）。

A.sum[r] - sum[l]
B.sum[r+1] - sum[l]
C.sum[r] - sum[l-1]
D.sum[r+1] - sum[l-1]

43.若n=5, a = {1, 2, 3, 4, 5}，查询[2, 4]（下标从 1 开始），程序输出应为（ ）。

A. 9 B. 10 C. 14 D. 12

参考答案与解析

一、单项选择题

1. A
解析：(154)₈ = 1×8² + 5×8¹ + 4×8⁰ = 64 + 40 + 4 = 108。将 108 转换为十六进制：108 ÷ 16 = 6 余 12（12 对应 C），6 ÷ 16 = 0 余 6，故结果为(6C)₁₆。

2. A
解析：(x ^ y) | (x & y) = x | y（异或与与再或等于按位或）。15 | 9 = 1111₂ | 1001₂ = 1111₂ = 15。

3. A
解析：2 << 3 = 16（0010左移3位得10000），5 & 3 = 0101₂ & 0011₂ = 0001₂ = 1，16 | 1 = 17。

4. A
解析：深度为 h 的满二叉树结点数为2^h - 1，h=6 时，2^6 - 1 = 63。

5. A
解析：前序根为 G，中序中 G 左侧ADEF为左子树，右侧HMZ为右子树。左子树前序DAFE、中序ADEF，递归可得左子树后序AEFD；右子树前序MHZ、中序HMZ，右子树后序HZM。整体后序 = 左子树后序 + 右子树后序 + 根 =AEFD+HZM+G=AEFDHZMG。

6. A
解析：哈夫曼构造：合并3,6→9；合并7,9→16；合并10,12→22；合并16,22→38。
叶子深度：3和6深度为3，7深度为2，10和12深度为2。
WPL = 3×3 + 6×3 + 7×2 + 10×2 + 12×2 = 9 + 18 + 14 + 20 + 24 = 85。

7. B
解析：无向图中，度数之和 = 2 × 边数。24 = 2E ⇒ E = 12。

8. D
解析：选项 A、B、C 均为合法出栈序列。选项 D 中，先出 4、3，此时栈中剩余 1、2（1在底，2在顶）。接下来出 5，但 5 尚未入栈，需先入栈 5 再出 5，之后栈中仍为 1、2，出栈顺序应为 2、1，而 D 给出 1、2，故不可能。

9. C
解析：选择排序是不稳定的（例如对(2a, 2b, 1)排序，两个2的相对顺序可能改变）。冒泡、插入、归并均为稳定排序。

10. A
解析：50的二进制为00110010，取反得11001101，加1得11001110，即为 -50 的补码。

11. A
解析：5的 8 位二进制为00000101，按位取反得11111010。

12. B
解析：德摩根律：!(A && B) = !A || !B。

13. D
解析：队列是先进先出，入队顺序 x, y, z，出队顺序必须与入队顺序相同，即 x, y, z。

14. B
解析：fib(0)=0, fib(1)=1, fib(2)=1, fib(3)=2, fib(4)=3, fib(5)=5, fib(6)=8。

15. B
解析：排列数P(6,2) = 6×5 = 30。

二、阅读程序题

（一）程序一

16. 正确（2分）
解析：fact(4) = 4×3×2×1 = 24。

17. 正确（2分）
解析：函数递归调用 n 次，时间复杂度为O(n)。

18. 正确（2分）
解析：可以用循环int res=1; for(i=1;i<=n;i++) res*=i;实现，时间复杂度仍为O(n)。

19. A（2分）
解析：fact(5) = 5! = 120。

20. B（2分）
解析：当 n 为负数时，递归无终止条件（永远不会到达 x=0），会无限递归，最终栈溢出。

（二）程序二

21. 正确（2分）
解析：程序将输入的每条边在邻接矩阵中双向置1（g[u][v]=1; g[v][u]=1;），因此读入的是无向图。

22. 正确（2分）
解析：DFS 从每个未访问顶点出发遍历整个连通分量，ans统计了连通分量个数。

23. 正确（2分）
解析：4 个顶点、3 条边构成一条链1-2-3-4，全部连通，连通分量数为1。

24. B（4分）
解析：改为g[u][v]=1;后，图变为有向图，DFS 只能沿有向边遍历，无法正确统计原无向图的连通分量，故功能改变。

25. B（4分）
解析：边(1,2),(2,3),(1,3)使顶点 1、2、3 全连通；(4,5)连通顶点 4、5，故共有 2 个连通分量。

（三）程序三

26. 正确（2分）
解析：输入"abc"，各字母出现一次，最大次数为1，取最小字母 ‘a’，输出a1。

27. 正确（2分）
解析：输入"aabb"，‘a’ 出现2次，‘b’ 出现2次，最大为2，取较小字母 ‘a’，输出a2。

28. 正确（2分）
解析：输入"zz"，‘z’ 出现2次，其他为0，输出z2。

29. C（5分）
解析："hello"中，‘l’ 出现2次，其余字母出现1次，最大次数为2，对应字母 ‘l’，输出l2。

30. A（5分）
解析：程序遍历字符串一次（O(n)），然后遍历常数26个字母（O(26)），总时间复杂度为 O(n)。

三、完善程序题

（一）二分查找

34. A（3分）
解析：标准二分查找循环条件为l <= r。

35. C（3分）
解析：用l + (r - l) / 2可避免整数溢出，效果与(l+r)/2相同。

36. A（3分）
解析：要找第一个等于 x 的位置，当a[mid] >= x时，答案在 mid 或左侧，故记录 ans=mid 并缩小右边界。

37. B（3分）
解析：当a[mid] >= x时，mid 可能是答案，所以右边界应设为mid（而非mid-1），以保证不丢失候选。

38. A（3分）
解析：当a[mid] < x时，答案一定在右侧，左边界设为mid+1。

（二）前缀和与区间和

39. A（3分）
解析：前缀和数组需要sum[0] = 0，作为递推的初始值。

40. A（3分）
解析：正确递推公式为sum[i] = sum[i-1] + a[i]。

41. A（3分）
解析：区间[l, r]的和为sum[r] - sum[l-1]。

42. B（3分）
解析：在 0-based 前缀和中，sum[i]表示前 i 个元素的和（即a[0..i-1]），因此区间[l, r]的和 = 前r+1个元素的和 - 前l个元素的和 =sum[r+1] - sum[l]。选项 A 缺少 +1，选项 C 需要处理 l=0 的边界，选项 D 错误。

43. A（3分）
解析：a[2]+a[3]+a[4] = 2+3+4 = 9。按前缀和计算：sum[4]=1+2+3+4=10，sum[1]=1，10-1=9。

更多内容请关注专栏：信奥赛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 点击跳转

· 文末祝福 ·

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