🏠

📘 NOIP2017 普及组初赛真题

第二十三届全国青少年信息学奥林匹克联赛初赛 · 普及组 C++ 语言试题 · 完整版逐题精讲与代码推演

📚 四大模块🎯 选择 30 分🧩 求解 10 分📖 阅读 32 分✍️ 完善 28 分⏱ 总分 100 分
← 返回主页
正在载入题库…

一、单项选择题（共 20 题，每题 1.5 分，共 30 分）

1. 易 在 8 位二进制补码中，10101011 表示的数是十进制下的（　）。
A. 43 B. -85 C. -43 D. -84
✅ 正确答案：B
解析：首位为 1，是负数。补码还原：减 1 后逐位取反——10101011 − 1 = 10101010，取反得 11010101 = -(64+16+4+1) = -85。
也可用权位法：最高位权值为 -128，故 -128 + 32 + 8 + 2 + 1 = -85。
2. 易 计算机存储数据的基本单位是（　）。
A. bit B. Byte C. GB D. KB
✅ 正确答案：B
解析：bit（位）是最小单位，而存储的基本编址单位是字节 Byte（1 Byte = 8 bit）。内存按字节编址，KB/GB 是更大的容量单位。
3. 易 下列协议中与电子邮件无关的是（　）。
A. POP3 B. SMTP C. WTO D. IMAP
✅ 正确答案：C
解析：SMTP 负责发送邮件，POP3 与 IMAP 负责接收邮件；WTO 是世界贸易组织，与网络协议无关。
4. 易 分辨率为 800×600、16 位色的位图，存储图像信息所需的空间为（　）。
A. 937.5KB B. 4218.75KB C. 4320KB D. 2880KB
✅ 正确答案：A
解析：800 × 600 × 16 bit = 7 680 000 bit = 960 000 Byte = 960000 ÷ 1024 = 937.5 KB。
注意 16 位色 = 每个像素 2 字节。
5. 易 计算机应用的最早领域是（　）。
A. 数值计算 B. 人工智能 C. 机器人 D. 过程控制
✅ 正确答案：A
解析：世界上第一台通用计算机 ENIAC 就是为火炮弹道数值计算而研制的，因此最早的应用领域是科学/数值计算。
6. 易 下列不属于面向对象程序设计语言的是（　）。
A. C B. C++ C. Java D. C#
✅ 正确答案：A
解析：C 是典型的面向过程语言；C++、Java、C# 都支持类、继承、多态等面向对象特性。
7. 易 NOI 的中文意思是（　）。
A. 中国信息学联赛 B. 全国青少年信息学奥林匹克竞赛 C. 中国青少年信息学奥林匹克竞赛 D. 中国计算机协会
✅ 正确答案：B
解析：NOI = National Olympiad in Informatics，中文为全国青少年信息学奥林匹克竞赛；NOIP 是联赛（省级）。
8. 中 2017 年 10 月 1 日是星期日，1999 年 10 月 1 日是（　）。
A. 星期三 B. 星期日 C. 星期五 D. 星期二
✅ 正确答案：C
解析：1999-10-01 到 2017-10-01 共 18 年，其中闰年 2000、2004、2008、2012、2016 共 5 个，总天数 = 18×365 + 5 = 6575。
6575 mod 7 = 2，即 1999 年那天比星期日前推 2 天 → 星期五。
9. 中 甲、乙、丙三位同学选修课程，从 4 门课程中，甲选修 2 门，乙、丙各选修 3 门，则不同的选修方案共有（　）种。
A. 36 B. 48 C. 96 D. 192
✅ 正确答案：C
解析：三人选择相互独立：C(4,2) × C(4,3) × C(4,3) = 6 × 4 × 4 = 96。
10. 中 设 G 是有 n 个结点、m 条边（n ≤ m）的连通图，必须删去 G 的（　）条边，才能使得 G 变成一棵树。
A. m − n + 1 B. m − n C. m + n + 1 D. n − m + 1
✅ 正确答案：A
解析：树的边数 = 顶点数 − 1 = n − 1，需删除 m − (n − 1) = m − n + 1 条边。
11. 中 对于给定的序列 {ak}，我们把 (i, j) 称为逆序对当且仅当 i < j 且 ai > aj。那么序列 1, 7, 2, 3, 5, 4 的逆序对数为（　）个。
A. 4 B. 5 C. 6 D. 7
✅ 正确答案：B
解析：逐个统计：(7,2)、(7,3)、(7,5)、(7,4)、(5,4)，共 5 个。
12. 中 表达式 a * (b + c) * d 的后缀形式是（　）。
A. a b c d * + * B. a b c + * d * C. a * b c + * d D. b + c * a * d
✅ 正确答案：B
解析：先算 b + c → b c +；再 a × (b+c) → a b c + *；最后 × d → a b c + * d *。
13. 中 向一个栈顶指针为 hs 的链式栈中插入一个指针 s 指向的结点时，应执行（　）。
A. hs->next = s; B. s->next = hs; hs = s; C. s->next = hs->next; hs->next = s; D. s->next = hs; hs = hs->next;
✅ 正确答案：B
解析：链式栈用头插法：新结点的 next 指向原栈顶，再把栈顶指针 hs 移到新结点上。即 s->next = hs; hs = s;
14. 中 若串 S = "copyright"，其子串的个数是（　）。
A. 72 B. 45 C. 46 D. 36
✅ 正确答案：C
解析：9 个字符互不相同，非空子串数 = 9 + 8 + … + 1 = 45，再加上空串共 46 个。
📌 易错点：教材定义中「空串也是子串」，故选 46 而非 45。
15. 中 十进制小数 13.375 对应的二进制数是（　）。
A. 1101.011 B. 1011.011 C. 1101.101 D. 1010.01
✅ 正确答案：A
解析：整数部分 13 = 8+4+1 = 1101；小数部分 0.375 = 1/4 + 1/8 = .011。合起来 1101.011。
16. 难 对于入栈顺序为 a, b, c, d, e, f, g 的序列，下列（　）不可能是合法的出栈序列。
A. a, b, c, d, e, f, g B. a, d, c, b, e, g, f C. a, d, b, c, g, f, e D. g, f, e, d, c, b, a
✅ 正确答案：C
解析：C 项：a 进 a 出 → 为让 d 第二个出栈，须先压入 b、c、d，弹出 d 后栈顶是 c，不可能下一个弹出 b，故 C 不合法。
17. 难 设 A 和 B 是两个长为 n 的有序数组，现在需要将 A 和 B 合并成一个排好序的数组，任何以元素比较作为基本运算的归并算法在最坏情况下至少要做（　）次比较。
A. n2 B. n log n C. 2n D. 2n − 1
✅ 正确答案：D
解析：最坏情况是两数组元素交替归并，共 2n 个元素、每次比较确定一个，最后一个元素无需比较 → 最多 2n − 1 次。
18. 易 从（　）年开始，NOIP 竞赛将不再支持 Pascal 语言。
A. 2020 B. 2021 C. 2022 D. 2023
✅ 正确答案：C
解析：CCF 于 2016 年发布公告：从 2022 年起 NOI 系列赛事（含 NOIP）不再支持 Pascal 语言。
19. 难 一家四口人，至少两个人生日属于同一月份的概率是（　）（假定每个人生日属于每个月份的概率相同且不同人之间相互独立）。
A. 1/12 B. 1/144 C. 41/96 D. 3/4
✅ 正确答案：C
解析：用对立事件：四人月份全不同 = 12×11×10×9 / 12⁴ = 11880/20736 = 55/96。
所求 = 1 − 55/96 = 41/96。
20. 易 以下和计算机领域密切相关的奖项是（　）。
A. 奥斯卡奖 B. 图灵奖 C. 诺贝尔奖 D. 普利策奖
✅ 正确答案：B
解析：图灵奖由 ACM 设立，被誉为「计算机界的诺贝尔奖」。

二、问题求解（共 2 题，每题 5 分，共 10 分）

21. 中 一个人站在坐标 (0, 0) 处，面朝 x 轴正方向。第一轮向前走 1 单位后右转，第二轮向前走 2 单位后右转……一直这样走下去。第 2017 轮后他的坐标是？
✅ 正确答案：（1009，1008）
解析：把每 4 轮看成一组，方向依次为 +x、−y、−x、+y。设第 4k 轮结束时记为 P(k)：
P(1) = (−2, 2)，P(2) = (−4, 4)，归纳得 P(k) = (−2k, 2k)，且朝向重新回到 +x。
2017 = 4 × 504 + 1，所以先走完 2016 轮到达 (−1008, 1008)，第 2017 轮朝 +x 前进 2017 步 → 横坐标 −1008 + 2017 = 1009。
答案：（1009，1008）
22. 难 图中共有 13 个格子（十字形）。对一个格子操作，会翻转它自己与上下左右相邻格子。要把所有格子都变为 0，至少需要几次操作？
✅ 正确答案：3
解析：操作次数只取决于「每个格子被翻转了几次」的奇偶性，且同一个格子操作两次等于没操作，因此只需在 13 个格子中挑一个操作集合。
十字形中心一格的翻转会波及四条臂的内侧端点，所以中心是否操作决定了后续必须如何配合；枚举可知：以中心配合两条对臂端点的 3 次操作可以恰好抵消所有 1，而 1 次或 2 次操作至多影响 5 + 5 = 10 个格子、无法覆盖需要翻转的全部位置。
答案：3

三、阅读程序写结果（共 4 题，每题 8 分，共 32 分）

阅读 1：字符出现次数（找第一个唯一字符）易

统计每个字符出现的次数，按原串顺序输出第一个只出现一次的字符；若没有则输出 no。

C++程序代码（点击行号可定位）
  1. 01#include <iostream>
  2. 02using namespace std;
  3. 03
  4. 04int main() {
  5. 05 int t[256];
  6. 06 string s;
  7. 07 int i;
  8. 08 cin >> s;
  9. 09 for (i = 0; i < 256; i++)
  10. 10 t[i] = 0;
  11. 11 for (i = 0; i < s.length(); i++)
  12. 12 t[s[i]]++;
  13. 13 for (i = 0; i < s.length(); i++)
  14. 14 if (t[s[i]] == 1) {
  15. 15 cout << s[i] << endl;
  16. 16 return 0;
  17. 17 }
  18. 18 cout << "no" << endl;
  19. 19 return 0;
  20. 20}
▶ 输入样例 
xyzxyw
▶ 输出样例 
z
🪜 逐字符统计并定位第一个唯一字符
1 执行L09~L10：把计数数组 t[0..255] 全部清零
2 执行L11~L12：扫描字符串，得到 t[x]=2, t[y]=2, t[z]=1, t[w]=1
3 执行L13~L18：按原串顺序复查——第 1 个字符 x 出现 2 次，跳过
4 第 2 个字符 y 出现 2 次，跳过；第 3 个字符 z 出现 1 次 → 命中
5 执行L15~L16：输出 z 并 return 0，后面的 w 不再判断
📤 程序输出？
✅ 答案：z
解析：t 数组以字符 ASCII 值为下标做计数。xyzxyw 中 x、y 各出现 2 次，z 与 w 各出现 1 次；程序按原串顺序找，z 在 w 之前，故输出 z。
💡 延伸：若输入改为 xyzxy 会输出什么？
✅ 答案：no
解析：所有字符都出现 2 次，循环结束都没有命中，执行L19输出 no。

阅读 2：整数拆分（递归枚举方案数）难

g(m, n, x) 统计：把 m 拆成 n 个非降、非负整数（第 1 个数从 x 起）的方案总数；当只剩 1 个数时返回 1。由于可以从 0 开始，实际等价于「m 拆成不超过 n 个正整数」的方案数。

C++程序代码（点击行号可定位）
  1. 01#include <iostream>
  2. 02using namespace std;
  3. 03
  4. 04int g(int m, int n, int x) {
  5. 05 int ans = 0;
  6. 06 int i;
  7. 07 if (n == 1)
  8. 08 return 1;
  9. 09 for (i = x; i <= m / n; i++)
  10. 10 ans += g(m - i, n - 1, i);
  11. 11 return ans;
  12. 12}
  13. 13
  14. 14int main() {
  15. 15 int t, m, n;
  16. 16 cin >> m >> n;
  17. 17 cout << g(m, n, 0) << endl;
  18. 18 return 0;
  19. 19}
▶ 输入样例 
7 3
▶ 输出样例 
8
🪜 递归展开 g(7, 3, 0)
1 L07 n=3 ≠ 1，进入循环：i 从 0 到 7/3 = 2，共 3 个分支
2 分支 i=0：g(7,2,0) → i ∈ [0, 3] → g(7,1,0)+g(6,1,1)+g(5,1,2)+g(4,1,3) = 4
3 分支 i=1：g(6,2,1) → i ∈ [1, 3] → g(5,1,1)+g(4,1,2)+g(3,1,3) = 3
4 分支 i=2：g(5,2,2) → i ∈ [2, 2] → g(3,1,2) = 1
5 求和 4 + 3 + 1 = 8，即把 7 拆成不超过 3 个正整数的 8 种方案：7｜1+6、2+5、3+4｜1+1+5、1+2+4、1+3+3、2+2+3
📤 程序输出？
✅ 答案：8
解析：允许拆分项取 0，所以「7 拆成 3 项非降非负整数」等价于「7 拆成不超过 3 个正整数」，共 8 种，输出 8。

阅读 3：二进制串的前缀和与最小值难

b[i] 是前 i 位的 1 的个数。倒序扫描时 t 统计「第 i 位到末尾中 0 的个数」，程序求的是 min（前 i−1 位中 1 的个数 + 第 i 位起 0 的个数）。

C++程序代码（点击行号可定位）
  1. 01#include <iostream>
  2. 02using namespace std;
  3. 03
  4. 04int main() {
  5. 05 string ch;
  6. 06 int a[200];
  7. 07 int b[200];
  8. 08 int n, i, t, res;
  9. 09 cin >> ch;
  10. 10 n = ch.length();
  11. 11 for (i = 0; i < 200; i++)
  12. 12 b[i] = 0;
  13. 13 for (i = 1; i <= n; i++) {
  14. 14 a[i] = ch[i - 1] - '0';
  15. 15 b[i] = b[i - 1] + a[i];
  16. 16 }
  17. 17 res = b[n];
  18. 18 t = 0;
  19. 19 for (i = n; i > 0; i--) {
  20. 20 if (a[i] == 0)
  21. 21 t++;
  22. 22 if (b[i - 1] + t < res)
  23. 23 res = b[i - 1] + t;
  24. 24 }
  25. 25 cout << res << endl;
  26. 26 return 0;
  27. 27}
▶ 输入样例 
1001101011001101101011110001
▶ 输出样例 
11
🪜 倒序扫描求最小值（串长 28，共 16 个 1）
1 L13~L17 先算前缀和：b[28] = 全串 1 的个数 = 16 → res 初值 16
2 倒序 i = 28 → 1：t 累加「已扫过的 0 的个数」，候选值 f(i) = b[i−1] + t
3 i = 28：b[27] = 15，t = 0 → 15，res 更新为 15
4 i = 21：b[20] = 11，t = 3 → 14；i = 16：b[15] = 8，t = 5 → 13
5 i = 13：b[12] = 6，t = 6 → 12；i = 5：b[4] = 2，t = 10 → 12
6 i = 4：b[3] = 1，t = 10 → 11（最小值）；i = 3：b[2] = 1，t = 11 → 12
7 循环结束输出 11
📤 程序输出？
✅ 答案：11
解析：枚举每一个「分割点」i，计算 f(i)= 前 i−1 位中 1 的个数 + 第 i 位起到末尾中 0 的个数，取最小值。全串共 16 个 1、12 个 0，最优分割在第 4 位：b[3] = 1，后段 0 的个数 = 10，合计 11。

阅读 4：矩形内弹球的反弹（找角落）中

小球从 (1,1) 出发，每步 x、y 各移动 dx、dy；撞到边界时该方向反向。当同一时刻两个方向都撞到边界（即到达某个角落）时停止，输出坐标。

C++程序代码（点击行号可定位）
  1. 01#include <iostream>
  2. 02using namespace std;
  3. 03
  4. 04int main() {
  5. 05 int n, m;
  6. 06 cin >> n >> m;
  7. 07 int x = 1;
  8. 08 int y = 1;
  9. 09 int dx = 1;
  10. 10 int dy = 1;
  11. 11 int cnt = 0;
  12. 12 while (cnt != 2) {
  13. 13 cnt = 0;
  14. 14 x = x + dx;
  15. 15 y = y + dy;
  16. 16 if (x == 1 || x == n) {
  17. 17 ++cnt;
  18. 18 dx = -dx;
  19. 19 }
  20. 20 if (y == 1 || y == m) {
  21. 21 ++cnt;
  22. 22 dy = -dy;
  23. 23 }
  24. 24 }
  25. 25 cout << x << " " << y << endl;
  26. 26 return 0;
  27. 27}
▶ 输入样例 
4 3

2017 1014
▶ 输出样例 
1 3

2017 1
🪜 输入 1（4 3）逐步模拟
1 起点 (1,1)，dx = dy = 1；每轮先移动，再判断是否撞墙
2 第 1 步 → (2,2)；第 2 步 → (3,3)，y = m 撞墙 cnt = 1，dy = −1
3 第 3 步 → (4,2)，x = n 撞墙 cnt = 1，dx = −1
4 第 4 步 → (3,1)，y = 1 撞墙，dy = +1；第 5 步 → (2,2)
5 第 6 步 → (1,3)：x = 1 与 y = m 同时成立，cnt = 2，循环结束 → 输出 1 3
📤 输入 1：4 3 → 输出？
✅ 答案：1 3
解析：逐步模拟 6 步到达左上角 (1,3)，此时两方向同时撞墙，cnt = 2 退出。
📤 输入 2：2017 1014 → 输出？（用周期性，别硬模拟）
✅ 答案：2017 1
解析：x 方向的三角波周期为 2(n−1) = 4032，y 方向为 2(m−1) = 2026。设出发后第 t 步（t = 0 为起点）：
· x = 1 当 t ≡ 0 (mod 4032)，x = n 当 t ≡ 2016 (mod 4032)
· y = 1 当 t ≡ 0 (mod 2026)，y = m 当 t ≡ 1013 (mod 2026)
联立求最小正解：t ≡ 2016 (mod 4032) 且 t ≡ 0 (mod 2026) → t = 2 042 208，此时 x = 2017、y = 1，输出 2017 1。

四、完善程序（共 2 题，每题 14 分，共 28 分）

完善 1：快速幂（分治求 xp mod m）中

利用「p 为偶数：xp = (x²)p/2；p 为奇数：xp = x·(x²)(p−1)/2」把幂运算降到 O(log p)。

C++程序代码（带 ①~⑤ 填空标记）
  1. 01#include <iostream>
  2. 02using namespace std;
  3. 03
  4. 04int x, p, m, i, result;
  5. 05
  6. 06int main() {
  7. 07 cin >> x >> p >> m;
  8. 08 result = ① ;
  9. 09 while ( ② ) {
  10. 10 if (p % 2 == 1)
  11. 11 result = ③ ;
  12. 12 p /= 2;
  13. 13 x = ④ ;
  14. 14 }
  15. 15 cout << ⑤ << endl;
  16. 16 return 0;
  17. 17}
📋 查看各空答案与解析

第①空：1　累乘器初始化为 1（乘法的单位元）。若为 0 则结果恒为 0。

第②空：p > 0（或 p != 0）　指数还没被除完就继续。p 每轮整除 2，直到 p = 0 时所有二进制位都处理完。

第③空：result * x % m　当前位为 1 时把这一位的权值乘进答案。写成 result * x % m，边乘边取模防止溢出。

第④空：x * x % m　底数不断平方：x → x² → x⁴ → x⁸…，对应二进制位的权值；同样要 % m。

第⑤空：result　循环结束时 result 即为 xp mod m，直接输出。

🪜 以 x = 3, p = 13, m = 100 为例走一遍
1 初始 result = 1, x = 3, p = 13（13 = 1101₂）
2 第 1 轮：p 为奇 → result = 1×3 % 100 = 3；p = 6，x = 3² = 9
3 第 2 轮：p 为偶 → result 不变；p = 3，x = 9² = 81
4 第 3 轮：p 为奇 → result = 3×81 % 100 = 43；p = 1，x = 81² % 100 = 61
5 第 4 轮：p 为奇 → result = 43×61 % 100 = 23；p = 0，循环结束
6 3¹³ = 1594323，末两位正是 23 ✓

完善 2：切割绳子（二分答案）中

先判断「切成 1 cm 一段」的总段数是否够 m 段；再用二分答案在区间 [1, 1000000] 中找能切出至少 m 段的最大长度。

C++程序代码（带 ①~⑤ 填空标记）
  1. 01#include <iostream>
  2. 02using namespace std;
  3. 03
  4. 04int n, m, i, lbound, ubound, mid, count;
  5. 05int len[100]; // 绳子长度
  6. 06
  7. 07int main() {
  8. 08 cin >> n;
  9. 09 count = 0;
  10. 10 for (i = 0; i < n; i++) {
  11. 11 cin >> len[i];
  12. 12 ① ;
  13. 13 }
  14. 14 cin >> m;
  15. 15 if ( ② ) {
  16. 16 cout << "Failed" << endl;
  17. 17 return 0;
  18. 18 }
  19. 19 lbound = 1;
  20. 20 ubound = 1000000;
  21. 21 while ( ③ ) {
  22. 22 mid = ④ ;
  23. 23 count = 0;
  24. 24 for (i = 0; i < n; i++)
  25. 25 ⑤ ;
  26. 26 if (count < m)
  27. 27 ubound = mid - 1;
  28. 28 else
  29. 29 lbound = mid;
  30. 30 }
  31. 31 cout << lbound << endl;
  32. 32 return 0;
  33. 33}
📋 查看各空答案与解析

第①空：count = count + len[i]　统计总长度（等价于每段切 1 cm 能得到的段数），为后面的可行性判断做准备。

第②空：count < m　总长度还不够 m 段 → 必然无解，输出 Failed 并结束。

第③空：lbound < ubound　二分循环条件：区间尚未收缩到唯一值就继续。注意这里是「求最大的可行值」，所以用 lbound < ubound 配合向上取整的 mid。

第④空：(lbound + ubound + 1) / 2　取中点时必须向上取整：(l + r + 1) / 2。若写成 (l + r) / 2，当 lbound = mid 时区间不再缩小，会陷入死循环。

第⑤空：count = count + len[i] / mid　按当前长度 mid 计算能切出多少段：第 i 根绳子可切 len[i] / mid 段。段数够则 lbound = mid（尝试更长），否则 ubound = mid − 1。

🪜 以 n = 3, len = [8, 6, 10], m = 5 为例
1 第 1 空累计总长 count = 24 ≥ 5，通过可行性检查
2 二分区间 [1, 1000000]，第一次 mid = (1+1000000+1)/2 = 500001
3 按 mid 统计段数：8/500001 + 6/500001 + 10/500001 = 0 < 5 → ubound = mid − 1
4 区间收缩到 [4, 5]：mid = 5 → 段数 = 1+1+2 = 4 < 5 → ubound = 4
5 区间收缩到 [4, 4]，循环结束，输出 lbound = 4；校验：段长 4 时 8/4 + 6/4 + 10/4 = 2+1+2 = 5 ≥ 5 ✓，而段长 5 只有 4 段，故 4 为最大值