2024年粤港澳青少年信息学创新大赛初中组真题解析（C++）
欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！
专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。
适合人群：
- 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
- 希望系统学习C++/Python编程的初学者
- 想要提升算法与编程能力的编程爱好者
第1题
NOI Linux系统中，用于调出文件夹内所有文件的命令是（ ）
A.cd
B.ls
C.find
D.pwd
【答案】：B
【解析】
A选项是进入目录，B选项是查看文件夹内所有文件，C选项为查找文件，D选项为确认当前目录
（图片来源网络，侵删）第2题
三进制下的整数 ( 1010201 ) 3 (1010201)_3 (1010201)3和 ( − 212102 ) 3 (-212102)_3 (−212102)3注意这是负数，两者的和在三进制下等于多少？（ ）
（图片来源网络，侵删）A. ( 21022 ) 3 (21022)_3 (21022)3
B. ( 121022 ) 3 (121022)_3 (121022)3
（图片来源网络，侵删）C. ( 2000010 ) 3 (2000010)_3 (2000010)3
D. ( 101102 ) 3 (101102)_3 (101102)3
【答案】：A
【解析】
( 1010201 ) 3 (1010201)_3 (1010201)3转为十进制是829， ( − 212102 ) 3 (-212102)_3 (−212102)3转为十进制是-632，两者之和为197，再转为三进制 ( 21022 ) 3 (21022)_3 (21022)3
第3题
表达式的中缀形式是(a+b*c)/(d+e)，请问其后缀形式是（ ）。
A./*+abc+de
B./+a*bc+de
C.ab+c*de+/
D.abc*+de+/
【答案】：D
【解析】
使用二叉树的形式来记录中缀形式，再采用后序遍历的方法来遍历二叉树，得到结果为D
第4题
令根结点的高度为1,则一棵含有2024个结点的二叉树的高度至多为（ ）。
A.10
B.11
C.12
D.2024
【答案】：D
【解析】
最大的高度即2024个结点为一条链
第5题
对于长度为5的排列P, 有多少个满足：存在1 ⋯ > P 5 P_1\lt P_2\lt \dots \lt P_k\gt P_{k+1}\gt \dots \gt P_5 P1P5（ ）。
A.10
B.11
C.16
D.120
【答案】：B
【解析】
k为1时有1种。k=2时有4种， P 2 P_2 P2 是 5， P 1 P_1 P1 从剩下的4个数中选1个， P 3 , P 4 , P 5 P_3,P_4,P_5 P3,P4,P5 三个数严格递减，只有一个选择。k=3时有6种， P 1 , P 2 P_1,P_2 P1,P2 从剩下的 4 4 4 个数中选 2 2 2 个， P 4 , P 5 P_4,P_5 P4,P5 两个数严格递减，只有一个选择。
第6题
字符a,b,c,d,e,f在文本中出现的频率为5%,13%,45%,9%,16%,12%。为其用01进行哈夫曼编码，合理的是：
A.1111,100,0,1110,110,101
B.1010,011,00,1001,010,1000
C.000,011,11,011,10,010
D.10101,111,01,1011,00,110
【答案】：A
【解析】
将字符按频率从小到大排序，d: 9%, a: 5%, f: 12%, b: 13%, e: 16%, c: 45%。每次合并频率最小的两个结点，直到只剩一个根结点。得到abcdef的编码为1111,100,0,1110,110,101
第7题
从线段上随机挑选两个点，其距离不小于线段长度一半的概率为？（ ）
A.1/3
B.2/3
C.1/4
D.1/2
【答案】：D
【解析】
设两个点为x和y，计算|x−y|≥0.5 的概率。
将 x 和 y 看作平面上的点，所有可能的点 (x,y) 落在单位正方形 [0,1]×[0,1] 内。满足 |x−y|≥0.5 的区域是正方形中位于两条直线 y=x+0.5 和 y=x−0.5 之外的部分。
单位正方形的总面积为 1，因此概率为满足条件的面积除以总面积：
P ( ∣ x − y ∣ ≥ 0.5 ) = 0.5 1 = 1 2 P(|x−y|≥0.5)=\frac{0.5}{1}=\frac{1}{2} P(∣x−y∣≥0.5)=10.5=21
第8题
从男女数量相同的8个人中随机选取三个人做大作业。则选出的3个人不都是同性的概率为（ ）。
A.1/7
B.6/7
C.25/28
D.2/7
【答案】：B
【解析】
3个人不是同性的概率就是排除“3人全是男性”和“3人全是女性” 的情况。8人中选3人的总组合数为56，“3人都是男性”、"3人都是女性“的总选法为8，所以答案是56-8=48，概率为48/56=6/7
第9题
下列有关排序的说法不正确的是（ ）。
A. 桶排序是一种有效的排序方式，时间复杂度为O(n+V)
B. 堆排序是一种有效的排序方式，是一种稳定排序
C.mutiset 是一种有效的数据结构，可以用来排序，但是常数很大
D. 归并排序的最劣复杂度为 O(nlogn)
【答案】：B
【解析】
堆排序不稳定
第10题
已知运算优先级： ¬ > ∩ > ∪ \lnot \gt \cap\gt \cup ¬>∩>∪。下列表达式的值与取值为0,1的变量x y z 有关的是（ ）。
A. ( x ∪ y ) ∩ ( ¬ x ∪ ¬ y ) (x\cup y) \cap (\lnot \ x \cup \lnot \ y) (x∪y)∩(¬ x∪¬ y)
B. ¬ x ∪ ¬ y ∪ ( x ∩ y ) \lnot \ x\cup \lnot \ y\cup (x\cap y) ¬ x∪¬ y∪(x∩y)
C. ¬ y ∩ ( ( x ∪ z ) ∩ y ∪ z ) \lnot \ y \cap ((x\cup z)\cap y\cup z) ¬ y∩((x∪z)∩y∪z)
D. ( x ∩ y ) ∪ ( y ∩ ¬ z ) ∪ ( ¬ z ∩ x ) (x\cap y)\cup (y\cap \lnot \ z)\cup(\lnot \ z\cap x) (x∩y)∪(y∩¬ z)∪(¬ z∩x)
【答案】：D
【解析】
x y z A B C D 0 0 0 0 1 0 0 0 0 1 0 1 1 0 0 1 0 1 1 0 1 0 1 1 1 1 0 0 1 0 0 1 1 0 1 1 0 1 1 1 1 0 1 1 0 0 1 0 1 1 1 1 0 1 0 1 A、B选项，与z无关，不符合题意。
C选项，与x无关，不符合题意。
第11题
以下代码片段中，若x，y，z>0, 且函数执行过程中变量的值不会超过类型范围，则代码可简写为（ ）。
void func(int x, int &y, int z) { x+=y; while (--z) x=x*2; y+=x; }A.y+=(x+y)
