2025粤港澳信息学创新大赛市选拔赛模拟题初中组

（满分：100 分 考试时间：120 分钟）

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

1. 在C++中，表达式 (13 & 7) 的值是多少？

{{ select(1) }}

• 5
• 6
• 7
• 20

答案解析：A

13的二进制：1101

7的二进制： 0111

逐位相与：答案为A

2. 以下哪个是合法的IPv4地址？

{{ select(2) }}

• 192.168.1.256
• 10.0.0.1
• 300.120.50.10
• 172.16.255.255.1

答案解析：B

IPv4地址规则： 由4个用点分隔的数字组成 每个数字范围：0~255 不能以0或255开头（特殊用途）

选项分析： A) 非法（256 > 255）

B) ✅合法（10开头的私有地址）

C) 非法（300 > 255）

D) 非法（有5个数字）

3. 在C++中，执行以下代码后，变量result的值和类型分别是？

int a = 5;
double b = 2.0;
auto result = a / b;

{{ select(3) }}

• 2，int
• 2.5，double
• 2.0，double
• 2，double

答案解析：B

运算规则：

a是int，b是double

混合运算时，int会自动提升为double（隐式类型转换）

实际计算：5.0 / 2.0 = 2.5

auto类型推导： 运算结果为double类型

result的类型与表达式类型一致（double）

4. 在C++中，定义数组 int arr[5] = {1, 2};，执行语句 cout << arr[3]; 会输出什么？

{{ select(4) }}

• 0
• 1
• 2
• 随机值

答案解析：A

数组初始化规则：

部分初始化时，未显式赋值的元素自动设为0

arr实际值为：{1, 2, 0, 0, 0}

访问元素：

arr[3]是第4个元素（下标从0开始）

其值为初始化默认值 0

5. 在C++中，表达式 5 + 3 * 2 == 11 ? 1 : 0 的最终值是？

{{ select(5) }}

• 0
• 1
• 11
• 编译错误

答案解析：B 考点说明：

算术运算符优先级（*/高于+-）

关系运算（==）的结果为bool类型

三目运算符的求值规则

符合CSP-J对基础运算的考察要求

易错点提示：

若误认为加法优先：(5 + 3) * 2 = 16 ≠ 11 会返回 0

C++中 true 可隐式转换为 1（非0即真）

6. 关于二叉树的叙述，以下哪项是正确的？

{{ select(6) }}

• 二叉树中每个节点的度都为2
• 高度为3的二叉树最多有7个节点
• 二叉树的左右子树不能为空
• 完全二叉树只允许最后一层有缺失节点

答案解析：B

7. 以下哪种排序算法在最坏情况下时间复杂度是O(n²)，但通过优化可以使平均时间复杂度达到O(n log n)？()

{{ select(7) }}

• 冒泡排序
• 快速排序
• 归并排序
• 堆排序

答案解析：B

快速排序（B选项）：

最坏情况（已排序数组）：O(n²)

优化方法（随机化/三数取中）：平均O(n log n)

其他选项分析：

A) 冒泡排序始终O(n²)

C) 归并排序稳定O(n log n)

D) 堆排序稳定O(n log n)

需要看清楚题目描述

8. 给定单向链表的节点定义和头指针 head，以下代码的功能是：

ListNode* moveTailToHead(ListNode* head) {
	if (!head || !head->next) return head;
	ListNode *prev = nullptr, *curr = head;
	while (curr->next) {
		prev = curr;
		curr = curr->next;
	}
	prev->next = nullptr;
	curr->next = head;
	return curr;  
}

{{ select(8) }}

• 删除链表尾节点
• 将尾节点移动到链表头部
• 反转整个链表
• 查找链表中间节点

答案解析：B

代码执行过程：

while 循环定位到尾节点 curr 及其前驱 prev

断开尾节点（prev->next = nullptr）

将尾节点连接到原头节点（curr->next = head）

更新头指针指向原尾节点

9. 以下代码段执行后，变量 x 的值是多少 ( )

int* f(int* p) {
	*p += 10;
	int q = *p / 2;
	return &q;
}

int main() {
	int x = 20;
	int* r = f(&x);
	x = *r + 5;
	return 0;
}

{{ select(9) }}

• 20
• 25
• 30
• 程序行为未定义

答案解析：D

关键问题：

函数 f() 返回了局部变量 q 的地址（&q），而 q 在函数返回后被销毁

通过 r 访问已释放的内存属于未定义行为（UB）

执行过程：

f(&x) 修改 x = 30（20 + 10），计算 q = 15

r 成为悬空指针（指向无效内存）

x = *r + 5 可能崩溃、输出随机值或看似“正常”工作

10. 关于无向图的叙述，以下哪项是正确的？

{{ select(10) }}

• 所有顶点的度数之和等于顶点数
• 边数不可能超过顶点数的平方
• 连通图中任意两顶点间都有唯一路径
• 有n个顶点的树一定有n条边

答案解析：

A选项：错误（度数之和=2×边数，握手定理）

B选项：正确（n个顶点的无向图最多有n(n-1)/2条边）

C选项：错误（唯一路径仅限树，普通连通图可能有多个路径）

D选项：正确但非最优（题目问"无向图"，树是连通无环图的特例）

11. @用ASCII码存储字符串"2024"需要占用多少字节？

{{ select(11) }}

• 2
• 4
• 8
• 16

答案解析：

ASCII编码规则：

每个字符（包括数字）固定占用1字节

字符串"2024"包含4个字符：'2','0','2','4'

计算过程：

存储空间 = 字符数 × 1字节 = 4字节

12. 以下哪种语言是编译型语言？

{{ select(12) }}

• Python
• Java
• C++
• JavaScript

答案解析：

编译型语言（C选项）：

源代码需一次性转换为机器码后执行（如C++通过g++编译生成.exe）

特点：执行速度快，但需要编译步骤

解释型/混合型语言：

A) Python：解释执行（逐行翻译）

B) Java：编译为字节码后由JVM解释执行

D) JavaScript：浏览器解释执行

13. 二进制数 1101 转换为十进制后的结果是？（）

{{ select(13) }}

• 11
• 12
• 13
• 14

答案解析：C

K进制转十进制：加权求和法

十进制转K进制：整数部分：短除求余；小数部分：相乘取整

14. 已知栈的初始状态为空，依次进行以下操作后栈顶元素是：

压入元素A
压入元素B
弹出栈顶
压入元素C
弹出栈顶

{{ select(14) }}

• A
• B
• C
• 空

答案解析：

操作过程：

压入A → [A]

压入B → [A, B]

弹出B → [A]

压入C → [A, C]

弹出C → [A]

栈的特性：

后进先出（LIFO）原则

每次操作仅影响栈顶

15. 用分治法解决"在有序数组中查找数字"的问题，最适合采用以下哪种方法？()

{{ select(15) }}

• 从第一个元素开始逐个比较
• 随机选择一个元素进行比较
• 每次与中间元素比较，缩小一半范围
• 先排序数组再进行查找

答案解析：

分治法核心思想：

分：选取数组中间元素

治：与目标比较，决定查找左半或右半

合：直接返回结果（无需合并）

二分查找（C选项）：

每次排除一半数据，时间复杂度O(log n)

示例：在[1,3,5,7,9]中找5，先比较5找到目标

错误选项：

A) 顺序查找（O(n)）

B) 随机查找（效率不稳定）

D) 已有序则无需再排序

正确答案：C) 每次与中间元素比较，缩小一半范围

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 √，错误填 ⨉ ；除特殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分）

1.程序一

#include <iostream>
#include <vector>
using namespace std;

vector<int>sieve(int n) {
	vector<bool>is_prime(n +1,true);
	is_prime[0]=is_prime[1]=false;
	for(int i=2; i*i<=n; i++) {
		if(is_prime[i]) {
			for(int j=i*i; j<=n; j+=i) {
				is_prime[j]=false;
			}
		}
	}
	vector<int>primes;
	for(int i=2; i<=n; i++) {
		if(is_prime[i])primes.push_back(i);
	}
	return primes;
}
int main() {
	int n;
	cin >>n;
	vector <int> primes =sieve(n);
	cout<<primes.size() << " ";
	int sum =0;
	for(int p:primes)sum +=p;
	cout<<sum<<endl;
	return 0;
}

根据上述程序，完成下面的判断题和单选题：

程序解析：这是埃氏筛法求素数，输出n前素数的个数，并求出所有n之前的素数和。

时间复杂度为$O(nlog{log{n}})$，这个时间复杂度要优于线性筛（欧拉筛）的$O(n)$。

16. （2分）请判断对错：当输入为 20 时，程序输出的第一个数字是 8。（ ）

{{ select(16) }}

• 对
• 错

答案解析：A

20以内素数：2,3,5,7,11,13,17,19 → 共8个

17. （2分）请判断对错：若将内层循环的起始条件 j = i * i 改为 j = 2 * i，程序仍能正确筛选素数。（ ）

{{ select(17) }}

• 对
• 错

答案解析：A

修改后，只是把前面已经标记的部分重复标记了一遍，但不影响结果，只是效率降低

18. （2分）请判断对错：该算法的时间复杂度优于暴力判断每个数是否为素数。（ ）

{{ select(18) }}

• 对
• 错

答案解析：A

暴力判断每个数时间复杂度为$O(n\sqrt{n})$,所以埃氏筛法要优秀的多

19. 当输入为 30 时，程序输出的第二个数字（素数和）是（ ）

{{ select(19) }}

• 129
• 106
• 112
• 100

答案解析：A

30以内素数和：2+3+5+7+11+13+17+19+23+29=129

20. 该筛法算法的最坏时间复杂度是（ ）

{{ select(20) }}

• $O(n)$
• $O(n log n)$
• $O(n log log n)$
• $O(n²)$

答案解析：C

（埃氏筛理论复杂度）

21. 若输入 n 为 100，则标记为 false 的最大合数是。（）

{{ select(21) }}

• 99
• 100
• 98
• 97

答案解析：B

求100以内最大的合数

2.程序二

#include <iostream>
#include <algorithm>
using namespace std;
const int MAX_N =1000;
int maxSum(int nums[],int n) {
	if(n ==0)return 0;
	int dp[MAX_N]= {0};
	dp[0]=nums[0];
	if(n >1)dp[1]=max(nums[0],nums[1]);
	for(int i=2; i<n; i++) {
		dp[i]=max(dp[i-1],dp[i-2]+nums[i]);
	}
	return dp[n-1];
}
int main() {
	int n;
	cin >>n;
	int nums[MAX_N];
	for(int i=0; i<n; i++) {
		cin >>nums[i];
	}
	cout<<maxSum(nums,n)<<endl;
	return 0;
}

程序解析：动态规划算法（递推）求n个正整数序列的最大不相邻的子序列的和。这段代码只能求正整数序列的解，当出现全部为负数的时候，代码的解是错误的。思考：如果要求负数学列应该怎么改代码？

这题的原题见https://www.bcoi.cn/p/D2073O

22. 当输入数据为 4 1 2 3 1 时（第一个数表示数组长度），程序输出为 4。（）

{{ select(22) }}

• 对
• 错

答案解析：A

1+3=4

这个动态规划求最大不相邻元素和

23. 若将 dp[1] = max(nums[0], nums[1]) 改为 dp[1] = nums[1]，输入 4 2 1 1 2 时输出会变为 3。（）

{{ select(23) }}

• 对
• 错

答案解析：A

原输出3→改为1+2=3

24. 该算法的时间复杂度为 O(n)。（）。

{{ select(24) }}

• 对
• 错

答案解析：A

单层循环，时间复杂度为O(n)

25. 当输入数据为 5 2 7 9 3 1 时，程序输出是（）。

{{ select(25) }}

• 10
• 12
• 11
• 13

答案解析：B

第一个数5表示序列长度：

选择2+9+1=12

26. 该算法解决的是以下哪个问题？（）。

{{ select(26) }}

• 求数组最大子序列和
• 求不相邻元素的最大和
• 求数组中最长递增子序列
• 求数组中相邻元素的最小和

答案解析：B

核心在第11行

27. 若输入数组所有元素均为负数，则输出（ ）

{{ select(27) }}

• 0
• 前两个数中较大的那个
• 数组中最小的负数（绝对值最大）
• 程序会报错

答案解析B

当全部是负数时候，这段代码的执行过程是，首先$dp[1]$初始化选择前两数最大值，然后第11行的状态转移方程会始终把 $dp[1]$的值传递到$dp[n]$。

如果要想得到包括负数数列的解，那么要修改两个地方：

1、第8行改为：数组初始化为$dp[i]=nums[i]$,即每个数单独一个为答案;

2、第11行改为：$dp[i]=max3(dp[i],dp[i-1],dp[i-2]+nums[i])$;//$max3$为自定义函数求三个数的最大值。

3.程序三：

#include <iostream>
using namespace std;
int mystery(int n,int k) {
	if(k ==0)return 1;
	if(k %2 ==0) {
		int temp =mystery(n,k/2);
		return temp*temp;
	} else {
		return n*mystery(n,k-1);
	}
}
int main() {
	int a,b;
	cin >>a >>b;
	cout<<mystery(a,b)<<endl;
	return 0;
}

完成下面的判断题和单选题。

程序解析：这是快速幂模板题，快速幂算法是根据幂的性质，利用分治算法，在$O(log{(n)})$时间复杂度内快速的计算出幂函数的值

28. 当输入为 2 5 时，程序输出 32。（ ）

{{ select(28) }}

• 对
• 错

答案解析：A

求 $2^5=32$

29. 若将 k % 2 == 0 改为 k % 3 == 0，输入 3 4 时输出会变为 81。（ ）

{{ select(29) }}

• 对
• 错

答案解析：B

修改后逻辑错误,所以不可能输出 $3^4$

30. 该递归算法的时间复杂度是 $O(log k)$（ ）

{{ select(30) }}

• 对
• 错

答案解析：

快速幂的时间复杂度

31. 当输入为 5 0 时，程序输出是（ ）

{{ select(31) }}

• 0
• 1
• 5
• 程序报错

答案解析：B $5^0=1$

32. 该算法实现的是以下哪种数学运算？（ ）

{{ select(32) }}

• 加法
• 乘法
• 幂运算
• 阶乘

答案解析C

见程序分析

33. 当输入为 2 10 时，mystery 函数总共被调用了（ ）次。（ ）

{{ select(33) }}

• 5
• 11
• 10
• 6

答案解析：D

mystery(2,10) 1

└─ mystery(2,5) 2

└─ mystery(2,4) 3

└─ mystery(2,2) 4

 └─ mystery(2,1)   5

    └─ mystery(2,0)   6

三、完善程序（单选题，每小题 3 分，共计 30 分）

1.程序一

以下程序使用BFS计算从起点(0,0)到终点的最短步数，补全缺失代码。 （假设地图用 grid 二维数组表示，0可通过，1为障碍）

#include <iostream>
#include <queue>
using namespace std;
const int N =100;
int grid[N][N];
int dist[N][N];//记录到每个点的步数
int dx[4]= {-1,1,0,0}; //上下左石移动
int dy[4]= {0,0,-1,1};

int bfs(int n,int m) {
	queue<pair<int,int>>q;
	q.push(make_pair(0,0));
	dist[0][0]=0;
	while(!q.empty()) {
		pair<int,int> current =q.front();
		q.pop();
		int ×=current.first;
		int y=current.second;
		//到达终点
		if(×==n-1 && y ==m-1) {
			return_1_____;
		}

		//遍历四个方向
		for(int i=0; i<4; i++) {
			int nx =×+dx[i];
			int ny=y+dy[i];
			//检查新位置是否合法
			if(nx >=0 &&nx<n &&ny >=0 &&ny<m && ___2___) {
				dist[nx][ny]=____3______;
				q.push(_______4______);
			}
		}
	}
	return -1;//不可达
}
int main() {
	int n,m;
	cin >>n >>m;
	for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			cin >>grid[i][j];
			dist[i][j]=-1;
		}
	}
	int ans= bfs(n,m);
	if(ans== ___5___) {
		cout<<"No path"<<endl;
	}
	e1se {
		cout<<ans<<endl;
	}
	return 0;
}

34. 1处应填（ ）

{{ select(34) }}

• x + y
• dist[n-1][m-1]+1
• n + m
• dist[x][y]

答案解析：D

到达终点时返回当前步数

35. 2处应填（ ）

{{ select(35) }}

• grid[nx][ny] == 0 && dist[nx][ny] == -1
• grid[nx][ny] == 1
• dist[nx][ny] > dist[x][y]
• nx + ny < x + y

答案解析：A

检查新位置是否可通行且未被访问过

36. 3处应填（ ）

{{ select(36) }}

• dist[x][y]
• dist[x][y] + 1
• 0
• 1

答案解析：B

新位置的步数是当前位置步数加1

37. 4处应填（ ）

{{ select(37) }}

• make_pair(x, y)
• make_pair(nx, ny)
• make_pair(dx[i], dy[i])
• make_pair(n, m)

答案解析：B

将新位置加入队列

38. 5处应填（ ）

{{ select(38) }}

• "No path"
• false
• -1
• 0

答案解析：C

找不到时返回-1

2、程序二

补全程序，统计字符串中所有回文子串的数量。函数check判断子串s[l..r]是否回文，count_substrings枚举所有子串并计数。注意边界处理和返回值逻辑。

输入示例："abcba" 输出示例：7

（回文子串：a,b,c,b,a,bcb,abcba）

#include<iostream>
#include<string>
using namespace std;
bool check(const string &s,int l,int r) {
	while(l<r) {
		if(s[l]!=s[r]) {
			return ①;//填空1
			填空1
		}
		l++;
		r--;
	}
	return ②;//填空2
}
int count_substrings(const string &s) {
	int n =s.length();
	int cnt =0;
	for(int i=0; i<n; i++) {
		for(int j =i; j<n; j++) {
			if(③) { //填空3
				cnt++;
			}
		}
	}
	return ④;//填空4
}
int main() {
	string s;
	cin >>s;
	cout<< ⑤<<endl;//填空5
	return 0;
}

39. ①处应填（ ）

{{ select(39) }}

• true
• s[l] == s[r]
• l < r
• false

答案解析：D

发现不对称立即返回false

40. ②处应填（ ）

{{ select(40) }}

• true
• false
• l >= r
• s[l] == s[r]

答案解析：A

全部字符对称返回true

41. ③处应填（ ）

{{ select(41) }}

• i <= j
• check(s, i, j)
• s[i] == s[j]
• i < j

答案解析：B

检查子串s[i..j]是否满足条件

42. ④处应填（ ）

{{ select(42) }}

• n
• cnt
• j - i + 1
• s.length()

答案解析：B

返回统计结果

43. ⑤处应填（ ）

{{ select(43) }}

• s
• count_substrings(s)
• check(s, 0, s.length()-1)
• n

答案解析：B

输出满足条件的子串数量