🏠

📗 NOIP2018 普及组初赛真题

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

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

一、单项选择题（共 15 题，每题 2 分，共 30 分）

1. 易 以下哪一种设备属于输出设备：（　）
A. 扫描仪 B. 键盘 C. 鼠标 D. 打印机
✅ 正确答案：D
解析：扫描仪、键盘、鼠标都是输入设备；打印机把处理结果输出到纸张，是输出设备。
2. 易 下列四个不同进制的数中，与其它三项数值上不相等的是（　）。
A. (269)16 B. (617)10 C. (1151)8 D. (1001101011)2
✅ 正确答案：D
解析：逐个转成十进制：A = 2×256 + 6×16 + 9 = 617；B = 617；C = 512 + 64 + 40 + 1 = 617；D = 512 + 64 + 32 + 8 + 2 + 1 = 619。
📌 快速法：D 的二进制 1001 101 011 按三位分组 = (1153)₈ ≠ (1151)₈，一眼看出不同。
3. 易 1MB 等于（　）。
A. 1000 字节 B. 1024 字节 C. 1000 × 1000 字节 D. 1024 × 1024 字节
✅ 正确答案：D
解析：1 KB = 1024 字节，1 MB = 1024 KB = 1024 × 1024 字节 = 1 048 576 字节。
4. 易 广域网的英文缩写是（　）。
A. LAN B. WAN C. MAN D. LNA
✅ 正确答案：B
解析：LAN 局域网、MAN 城域网、WAN 广域网（Wide Area Network）。家里路由器接外网的口通常标注的就是 WAN。
5. 易 中国计算机学会于（　）年创办全国青少年计算机程序设计竞赛。
A. 1983 B. 1984 C. 1985 D. 1986
✅ 正确答案：B
解析：1984 年——同年邓小平提出「计算机的普及要从娃娃抓起」，中国科协与计算机学会举办了首届全国青少年程序设计竞赛。
6. 中 开始为小写输入状态，小老鼠按 CapsLock、A、S、D、F 循环按键，即 CapsLock、A、S、D、F、CapsLock、A、S、D、F……，屏幕上输出的第 81 个字符是（　）。
A. A B. S C. D D. a
✅ 正确答案：A
解析：CapsLock 不产生字符，所以每按 5 个键输出 4 个字母。81 = 4 × 20 + 1，即第 20 轮（从 0 数起）的第一个字母。
起始小写 → 第 0 轮大写、第 1 轮小写……第 20 轮为大写，第一个字母是 A。
7. 中 根节点深度为 0，一棵深度为 h 的满 k（k > 1）叉树共有（　）个结点。
A. (kh+1 − 1)/(k − 1) B. kh−1 C. kh D. (kh−1)/(k − 1)
✅ 正确答案：A
解析：各层结点数为 1, k, k², …, kh，等比数列求和= (kh+1 − 1)/(k − 1)。
📌 验证法：取 k = 2、h = 2 的满二叉树共 7 个结点，代入只有 A 得 7。
8. 中 以下排序算法中，不需要进行关键字比较操作的算法是（　）。
A. 基数排序 B. 冒泡排序 C. 堆排序 D. 直接插入排序
✅ 正确答案：A
解析：基数排序按「位」分桶收集，不比较关键字；冒泡、堆排序、插入排序都基于比较。
9. 难 最坏情况下，在 N 个互不相同的数中同时找最大与最小，至少需要（　）次比较。
A. ⌈3N/2⌉ − 2 B. ⌊3N/2⌋ − 2 C. 2N − 2 D. 2N − 4
✅ 正确答案：A
解析：成对处理：先两两比较（N/2 次）分出「小组大/小」，再用小组大者更新最大值、小组小者更新最小值，每对 3 次比较 → 约 3N/2 − 2 次。
N 为奇数时向上取整，故选 ⌈3N/2⌉ − 2。
10. 易 「从前有座山，山里有座庙……」这个故事与（　）算法异曲同工。
A. 枚举 B. 递归 C. 贪心 D. 分治
✅ 正确答案：B
解析：故事不断调用「自身」继续讲下去，正是递归思想。
11. 难 由四个没有区别的点构成的简单无向连通图的个数是（　）。
A. 6 B. 7 C. 8 D. 9
✅ 正确答案：A
解析：按边数分类（无标号、连通、简单图）：
3 条边 2 种（链、星）、4 条边 2 种（环、带一条弦）、5 条边 1 种、6 条边 1 种（完全图），共 6 种。
12. 中 含 10 个元素的集合的全部子集数为 S，其中由 7 个元素组成的子集数为 T，则 T / S 的值为（　）。
A. 5/32 B. 15/128 C. 1/8 D. 21/128
✅ 正确答案：B
解析：S = 2¹⁰ = 1024，T = C(10,7) = C(10,3) = 120，T/S = 120/1024 = 15/128。
13. 中 10000 以内，与 10000 互质的正整数有（　）个。
A. 2000 B. 4000 C. 6000 D. 8000
✅ 正确答案：B
解析：10000 = 2⁴ × 5⁴。能被 2 整除的有 5000 个、被 5 整除的有 2000 个、同时被 2 和 5 整除的有 1000 个 → 不互质共 5000 + 2000 − 1000 = 6000 个。
互质 = 10000 − 6000 = 4000 个（即 φ(10000) = 10000 × 1/2 × 4/5）。
14. 中 统计非负整数二进制中 1 的个数：while (x) { ret++; ______; }，空格内应填入（　）。
A. x >>= 1 B. x &= x − 1 C. x |= x >> 1 D. x <<= 1
✅ 正确答案：B
解析：x &= x − 1 每次消去最低位的一个 1，循环次数正好等于 1 的个数。
A 也能统计但要循环「位数」次；C、D 会死循环。
15. 易 图中「压入 A、压入 B、弹出 B、压入 C」所使用的数据结构是（　）。
A. 哈希表 B. 栈 C. 队列 D. 二叉树
✅ 正确答案：B
解析：只能在同一端插入删除、后进先出 —— 标准的栈。

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

16. 中 甲乙丙丁四人考虑周末郊游。已知：①下雨且乙不去 → 甲一定不去；②乙去 → 丁一定去；③丙去 → 丁一定不去；④丁不去且甲不去 → 丙一定不去。如果周末丙去了，则甲____、乙____、丁____、周末____。
✅ 正确答案：甲去了，乙没去，丁没去，没下雨
解析（倒推）：
· 由③「丙去 → 丁不去」，丙去了 ⇒ 丁没去。
· 由④「丁不去且甲不去 → 丙不去」，其逆否为「丙去 → 丁去或甲去」。已知丁没去，所以甲去了。
· 由②「乙去 → 丁去」，逆否为「丁不去 → 乙不去」⇒ 乙没去。
· 由①「下雨且乙不去 → 甲不去」，逆否为「甲去 → 不下雨或乙去」。已知甲去了、乙没去 ⇒ 没下雨。
📌 关键技巧：把蕴含式改写成逆否命题就能一路倒推。
17. 中 从 1 到 2018 这 2018 个数中，共有 ______ 个包含数字 8 的数。
✅ 正确答案：544
解析（正难则反）：先数不含 8 的数。
· 0000 ~ 1999：千位只能取 0 或 1（2 种），其余三位各取 0~9 中除 8 的 9 种 → 2 × 9³ = 1458 个（含 0000，即 0）。
· 2000 ~ 2018：去掉含 8 的 2008 与 2018，剩 19 − 2 = 17 个。
不含 8 的正整数（1~2018）= 1458 − 1（去掉 0）+ 17 = 1474 个。
含 8 的数 = 2018 − 1474 = 544 个。

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

阅读 1：大写字母后移一位易

逐个扫描字符，把大写字母的 ASCII 值加 1（A→B、G→H…），其余字符不变。

C++程序代码（点击行号可定位）
  1. 01#include <cstdio>
  2. 02char st[100];
  3. 03int main() {
  4. 04 scanf("%s", st);
  5. 05 for (int i = 0; st[i]; ++i) {
  6. 06 if ('A' <= st[i] && st[i] <= 'Z')
  7. 07 st[i] += 1;
  8. 08 }
  9. 09 printf("%s\n", st);
  10. 10 return 0;
  11. 11}
▶ 输入样例 
QuanGuoLianSai
▶ 输出样例 
RuanHuoMianTai
🪜 逐字符判断并后移
1 L05 循环条件 st[i] 即「没遇到字符串结束符 \0 就继续」
2 L06~L07 只有落在 'A'~'Z' 的字符才 +1
3 Q → R，u、a、n 不变，G → H，u、o 不变
4 L → M，i、a、n 不变，S → T，a、i 不变
5 得到 RuanHuoMianTai
📤 程序输出？
✅ 答案：RuanHuoMianTai
解析：四个大写字母 Q、G、L、S 分别变成 R、H、M、T，其余小写字母原样保留。

阅读 2：统计 i² mod x == 1 的个数中

枚举 i = 0 ~ x−1，统计满足 i² % x == 1 的 i 的个数。

C++程序代码（点击行号可定位）
  1. 01#include <cstdio>
  2. 02int main() {
  3. 03 int x;
  4. 04 scanf("%d", &x);
  5. 05 int res = 0;
  6. 06 for (int i = 0; i < x; ++i) {
  7. 07 if (i * i % x == 1) {
  8. 08 ++res;
  9. 09 }
  10. 10 }
  11. 11 printf("%d", res);
  12. 12 return 0;
  13. 13}
▶ 输入样例 
15
▶ 输出样例 
4
🪜 枚举 i = 0 ~ 14 检查 i² mod 15
1 i = 1：1 % 15 = 1 ✓
2 i = 4：16 % 15 = 1 ✓
3 i = 11：121 % 15 = 1 ✓
4 i = 14：196 % 15 = 1 ✓
5 其余 i 均不满足，共 4 个
📤 程序输出？
✅ 答案：4
解析：本质是求同余方程 i² ≡ 1 (mod 15) 的解的个数。由 CRT，模 3 有 2 个解、模 5 有 2 个解 → 模 15 共 2 × 2 = 4 个解：1、4、11、14。

阅读 3：二维递归 findans（表格法）难

f(n,0) = n % 3，f(0,m) = m，其余按 f(n,m) = f(n−1,m) − f(n,m−1) + f(n−1,m−1) 递推。求值时画表格逐行填最稳妥。

C++程序代码（点击行号可定位）
  1. 01#include <iostream>
  2. 02using namespace std;
  3. 03int n, m;
  4. 04int findans(int n, int m) {
  5. 05 if (n == 0) return m;
  6. 06 if (m == 0) return n % 3;
  7. 07 return findans(n - 1, m) - findans(n, m - 1) + findans(n - 1, m - 1);
  8. 08}
  9. 09int main(){
  10. 10 cin >> n >> m;
  11. 11 cout << findans(n, m) << endl;
  12. 12 return 0;
  13. 13}
▶ 输入样例 
5 6
▶ 输出样例 
8
🪜 造表：行 n = 0~5，列 m = 0~6
1 第 0 行 f(0,m) = m：　0　1　2　3　4　5　6
2 第 0 列 f(n,0) = n % 3：1（n=1）、2（n=2）、0（n=3）、1（n=4）、2（n=5）
3 第 1 行：f(1,1)=1−1+0=0，f(1,2)=2−0+1=3，f(1,3)=3−3+2=2，f(1,4)=5，f(1,5)=4，f(1,6)=7
4 第 2 行：f(2,1)=0−2+1=−1，f(2,2)=3−(−1)+0=4，f(2,3)=1，f(2,4)=6，f(2,5)=3，f(2,6)=8
5 第 3 行：f(3,1)=1，f(3,2)=2，f(3,3)=3，f(3,4)=4，f(3,5)=5，f(3,6)=6
6 第 4 行：f(4,1)=0 … f(4,6)=7；第 5 行：f(5,1)=−1 … f(5,5)=3，f(5,6)=7 − 3 + 4 = 8
7 故 findans(5,6) = 8
📤 程序输出？
✅ 答案：8
解析：注意 f(n,0) = n % 3（不是 n！这是最容易算错的地方），f(5,6) = f(4,6) − f(5,5) + f(4,5) = 7 − 3 + 4 = 8。
📌 递归有大量重复子问题，真实考试中直接造表（记忆化）最快。

阅读 4：置换环计数难

读入 n 与数组 d（d[i] 表示 i 指向谁），用 visited 标记沿指针走一遍，统计环的个数（等价于置换分解成循环的个数）。

C++程序代码（点击行号可定位）
  1. 01#include <cstdio>
  2. 02int n, d[100];
  3. 03bool v[100];
  4. 04int main() {
  5. 05 scanf("%d", &n);
  6. 06 for (int i = 0; i < n; ++i) {
  7. 07 scanf("%d", d + i);
  8. 08 v[i] = false;
  9. 09 }
  10. 10 int cnt = 0;
  11. 11 for (int i = 0; i < n; ++i) {
  12. 12 if (!v[i]) {
  13. 13 for (int j = i; !v[j]; j = d[j]) {
  14. 14 v[j] = true;
  15. 15 }
  16. 16 ++cnt;
  17. 17 }
  18. 18 }
  19. 19 printf("%d\n", cnt);
  20. 20 return 0;
  21. 21}
▶ 输入样例 
10 7 1 4 3 2 5 9 8 0 6
▶ 输出样例 
6
🪜 按 i = 0→9 依次找环（d = [7,1,4,3,2,5,9,8,0,6]）
1 i = 0：0 → 7 → 8 → 0（已访问）停，第 1 个环 {0,7,8}，cnt = 1
2 i = 1：1 → 1，自环 {1}，cnt = 2
3 i = 2：2 → 4 → 2，环 {2,4}，cnt = 3
4 i = 3：3 → 3，自环 {3}，cnt = 4
5 i = 5：5 → 5，自环 {5}，cnt = 5
6 i = 6：6 → 9 → 6，环 {6,9}，cnt = 6
7 i = 7、8、9 均已访问，跳过，输出 6
📤 程序输出？
✅ 答案：6
解析：程序统计置换中循环的个数：{0,7,8}、{1}、{2,4}、{3}、{5}、{6,9} 共 6 个。📌 注意 j = d[j] 是沿「下标 → 值」跳转，别误读成 d 数组的下标自增。

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

完善 1：约数两两最大公约数之和（getDivisor + gcd）中

例：4 的约数 1、2、4，两两 GCD 之和 = 1 + 2 + 1 = 4。要求 getDivisor 为 O(√n)，gcd 为 O(log max(a,b))，结果对 10007 取模。

C++程序代码（带 ①~⑤ 填空标记）
  1. 01#include <iostream>
  2. 02using namespace std;
  3. 03const int N = 110000, P = 10007;
  4. 04int n;
  5. 05int a[N], len;
  6. 06int ans;
  7. 07void getDivisor() {
  8. 08 len = 0;
  9. 09 for (int i = 1; ① <= n; ++i)
  10. 10 if (n % i == 0) {
  11. 11 a[++len] = i;
  12. 12 if ( ② != i) a[++len] = n / i;
  13. 13 }
  14. 14}
  15. 15int gcd(int a, int b) {
  16. 16 if (b == 0) {
  17. 17 ③ ;
  18. 18 }
  19. 19 return gcd(b, ④ );
  20. 20}
  21. 21int main() {
  22. 22 cin >> n;
  23. 23 getDivisor();
  24. 24 ans = 0;
  25. 25 for (int i = 1; i <= len; ++i) {
  26. 26 for (int j = i + 1; j <= len; ++j) {
  27. 27 ans = ( ⑤ ) % P;
  28. 28 }
  29. 29 }
  30. 30 cout << ans << endl;
  31. 31 return 0;
  32. 32}
📋 查看各空答案与解析

第①空：i * i　只需枚举到 √n：循环条件写成 i * i <= n，复杂度 O(√n)。

第②空：n / i　避免平方数把 √n 记两次：当 n / i ≠ i 时才把大因子 n / i 也存进去。

第③空：return a　辗转相除递归出口：b == 0 时最大公约数就是 a，返回 a。

第④空：a % b　递归步：gcd(a, b) = gcd(b, a % b)。

第⑤空：ans + gcd(a[i], a[j])　累加这一对约数的最大公约数：ans = (ans + gcd(a[i], a[j])) % P。注意括号位置——取模要作用在整个加法结果上。

🪜 以 n = 4 为例验证
1 getDivisor：i = 1 → 存入 1 与 4；i = 2 → 存入 2（因为 4/2 = 2 == i，不重复存）
2 得到 a = [1, 4, 2]，len = 3
3 双重循环枚举 (1,4)、(1,2)、(4,2) 三对
4 gcd(1,4) = 1，gcd(1,2) = 1，gcd(4,2) = 2
5 ans = 1 + 1 + 2 = 4，与题面示例一致 ✓

完善 2：双向链表求「下一个更大值的位置」难

排列 P 已读入，a[x] = x 所在的位置。按值从小到大依次把位置从双向链表中删除；删除时它的右邻居就是「后面第一个比它大的位置」。

C++程序代码（带 ①~⑤ 填空标记）
  1. 01#include <iostream>
  2. 02using namespace std;
  3. 03const int N = 100010;
  4. 04int n;
  5. 05int L[N], R[N], a[N];
  6. 06int main() {
  7. 07 cin >> n;
  8. 08 for (int i = 1; i <= n; ++i) {
  9. 09 int x;
  10. 10 cin >> x;
  11. 11 ① ;
  12. 12 }
  13. 13 for (int i = 1; i <= n; ++i) {
  14. 14 R[i] = ② ;
  15. 15 L[i] = i - 1;
  16. 16 }
  17. 17 for (int i = 1; i <= n; ++i) {
  18. 18 L[ ③ ] = L[a[i]];
  19. 19 R[L[a[i]]] = R[ ④ ];
  20. 20 }
  21. 21 for (int i = 1; i <= n; ++i) {
  22. 22 cout << ⑤ << " ";
  23. 23 }
  24. 24 cout << endl;
  25. 25 return 0;
  26. 26}
📋 查看各空答案与解析

第①空：a[x] = i　记录「值 x 在第 i 个位置」：a[x] = i（反查表）。后面循环 i 是「值」，a[i] 才是它的位置。

第②空：i + 1　初始化后继：R[i] = i + 1，与 L[i] = i − 1 一起构成位置 1..n 的双向链表（0 与 n+1 是天然哨兵）。

第③空：R[a[i]]　删除位置 a[i]：L[ R[a[i]] ] = L[a[i]]，即让右邻居的前驱指向左邻居。

第④空：a[i]　对称的另一半：R[ L[a[i]] ] = R[a[i]]，让左邻居的后继指向右邻居。注意删除后 a[i] 自己的 R 值不会被改写，正好保存了「删除那一刻的右邻居」＝答案。

第⑤空：R[i]　按位置输出：位置 i 的答案就是 R[i]（它在被删除的瞬间被冻结下来的右邻居）；若不存在更大值则为 n + 1。

🪜 用样例 n = 5, P = 1 5 4 2 3 验证（答案应为 2 6 6 5 6）
1 读入后 a[1] = 1、a[5] = 2、a[4] = 3、a[2] = 4、a[3] = 5
2 链表初始：1 ↔ 2 ↔ 3 ↔ 4 ↔ 5（R 分别为 2,3,4,5,6）
3 i = 1（值 1 在位置 a[1] = 1）：R[1] = 2 即答案；删除位置 1
4 i = 2（值 2 在位置 4）：R[4] = 5；删除位置 4
5 i = 3（值 3 在位置 5）：R[5] = 6（没有更大的）；删除位置 5
6 i = 4（值 4 在位置 3）：R[3] = 6；i = 5（值 5 在位置 2）：R[2] = 6
7 按位置 1..5 输出 R[i]：2 6 6 5 6 ✓ 与题面一致