第 7 章 历年真题解析

7.1 计算机常识

NOIP2019

1. 中国的国家顶级域名是（ ）
2. A. .cn
3. B. .ch
4. C. .chn
5. D. .china
6. 答案：A

7. 解析：典型的国家顶级域名有 .cn（中国）、.us（美国）、.uk（英国）、.jp（日本）、.sg（新加坡）等。典型的通用顶级域名有 .edu（教育机构）、.gov（政府部门）、.net（网络组织）、.com（商业组织）、.org（非营利机构）、.mil（军事部门）等。

8. 一个 32 位整型变量占用（ ）个字节。

9. A. 32
10. B. 128
11. C. 4
12. D. 8
13. 答案：C

14. 解析：8 位是 1 字节，因此 32 位是 4 字节。在 C++ 语言中，int 是最常用的带符号 32 位整型变量，可表示数值：$[-2^{31}, 2^{31}-1]$；unsigned int 是最常用的无符号 32 位整型变量，可表示数值 $[0, 2^{32}-1]$。

15. 以下哪个奖项是计算机科学领域的最高奖？（ ）

16. A. 图灵奖
17. B. 鲁班奖
18. C. 诺贝尔奖
19. D. 普利策奖
20. 答案：A
21. 解析：图灵奖由美国计算机协会于 1966 年设立，其名称取自计算机科学之父图灵，专门奖励对计算机事业作出重要贡献的个人，被誉为“计算机界的诺贝尔奖”。

NOIP2018

1. 以下哪一种设备属于输出设备：（ ）
2. A. 扫描仪
3. B. 键盘
4. C. 鼠标
5. D. 打印机

6. 答案：D

7. 1MB 等于（ ）。

8. A. 1000 字节
9. B. 1024 字节
10. C. $1000 \times 1000$ 字节
11. D. $1024 \times 1024$ 字节

12. 答案：D

13. 广域网的英文缩写是（ ）。

14. A. LAN
15. B. WAN
16. C. MAN
17. D. LNA
18. 答案：B

19. 解析：WAN: Wide area network（广域网），LAN: local area network（局域网），MAN: Metropolitan Area Network（城域网）。

20. 中国计算机学会于（ ）年创办全国青少年计算机程序设计竞赛。

21. A. 1983
22. B. 1984
23. C. 1985
24. D. 1986
25. 答案：B
26. 解析：考察比赛相关历史。1984 年邓小平指出：“计算机的普及要从娃娃做起。”教育部和中国科协委托中国计算机学会举办了全国青少年计算机程序设计竞赛（简称：NOI），1984 年参加竞赛的有 8000 多人。

NOIP2017

1. 计算机存储数据的基本单位是（ ）。
2. A. bit
3. B. Byte
4. C. GB
5. D. KB

6. 答案：B

7. 下列协议中与电子邮件无关的是（ ）。

8. A. POP3
9. B. SMTP
10. C. WTO
11. D. IMAP
12. 答案：C

13. 解析：邮件相关的协议包括 SMTP（Simple Mail Transfer Protocol，简单邮件传输协议）、POP3（Post Office Protocol，邮局协议）、IMAP（Internet Mail Access Protocol，Internet 邮件访问协议）。WTO 是世界贸易组织。

14. 计算机应用的最早领域是（ ）。

15. A. 数值计算
16. B. 人工智能
17. C. 机器人
18. D. 过程控制

19. 答案：A

20. 下列不属于面向对象程序设计语言的是（ ）。

21. A. C
22. B. C++
23. C. Java
24. D. C#
25. 答案：A

26. 解析：C 语言是面向过程的结构化程序设计语言。

27. NOI 的中文意思是（ ）。

28. A. 中国信息学联赛
29. B. 全国青少年信息学奥林匹克竞赛
30. C. 中国青少年信息学奥林匹克竞赛
31. D. 中国计算机协会

32. 答案：B

33. 从（ ）年开始，NOIP 竞赛将不再支持 Pascal 语言。

34. A. 2020
35. B. 2021
36. C. 2022
37. D. 2023

38. 答案：C

39. 以下和计算机领域密切相关的奖项是（ ）。

40. A. 奥斯卡奖
41. B. 图灵奖
42. C. 诺贝尔奖
43. D. 普利策奖
44. 答案：B

NOIP2016

1. 以下不是微软公司出品的软件是（ ）。
2. A. Powerpoint
3. B. Word
4. C. Excel
5. D. Acrobat Reader
6. 答案：D

7. 解析：A、B、C 均为微软 Office 办公软件，D 为 Adobe 公司出品的 PDF 阅读软件。

8. 以下不属于无线通信技术的是（ ）。

9. A. 蓝牙
10. B. WiFi
11. C. GPRS
12. D. 以太网
13. 答案：D

14. 解析：以太网（Ethernet）是一种基于有线电缆（如双绞线、同轴电缆）的局域网技术。

15. 以下不是 CPU 生产厂商的是（ ）。

16. A. Intel
17. B. AMD
18. C. Microsoft
19. D. IBM
20. 答案：C

21. 解析：Microsoft（微软）是软件开发商，而 Intel、AMD、IBM 均涉及 CPU 芯片设计与制造。

22. 以下不是存储设备的是（ ）。

23. A. 光盘
24. B. 磁盘
25. C. 固态硬盘
26. D. 鼠标

27. 答案：D

28. 以下是 32 位机器和 64 位机器的区别的是（ ）。

29. A. 显示器不同
30. B. 硬盘大小不同
31. C. 寻址空间不同
32. D. 输入法不同

33. 答案：C

34. 参加 NOI 比赛，以下不能带入考场的是（ ）。

35. A. 钢笔
36. B. 适量的衣服
37. C. U 盘
38. D. 铅笔
39. 答案：C
40. 解析：U 盘属于可移动存储设备，严禁带入赛场以防作弊。

NOIP2015

1. 1MB 等于（ ）。
2. A. 1000 字节
3. B. 1024 字节
4. C. $1000 \times 1000$ 字节
5. D. $1024 \times 1024$ 字节

6. 答案：D

7. 在 PC 机中，PENTIUM (奔腾）、酷睿、赛扬等是指（ ）。

8. A. 生产厂家名称
9. B. 硬盘的型号
10. C. CPU 的型号
11. D. 显示器的型号

12. 答案：C

13. 操作系统的作用是（ ）

14. A. 把源程序译成目标程序
15. B. 便于进行数据管理
16. C. 控制和管理系统资源
17. D. 实现硬件之间的连接
18. 答案：C

19. 解析：操作系统是管理计算机硬件、软件资源，调度用户作业程序和处理各种中断，从而保证计算机各部分协调高效地工作的系统软件。

20. 在计算机内部用来传送、存贮、加工处理的数据或指令都是以（ ）形式进行的。

21. A. 二进制码
22. B. 八进制码
23. C. 十进制码
24. D. 智能拼音码

25. 答案：A

26. 下列说法正确的是（ ）。

27. A. CPU 的主要任务是执行数据运算和程序控制
28. B. 存储器具有记忆能力，其中信息任何时候都不会丢失（注：RAM断电易失）
29. C. 两个显示器屏幕尺寸相同，则它们的分辨率必定相同
30. D. 个人用户只能使用 Wifi 的方式连接到 Internet

31. 答案：A

32. 所谓的“中断”是指（ ）。

33. A. 操作系统随意停止一个程序的运行
34. B. 当出现需要时，CPU 暂时停止当前程序的执行转而执行处理新情况的过程
35. C. 因停机而停止一个程序的运行
36. D. 电脑死机

37. 答案：B

38. 计算机病毒是（ ）。

39. A. 通过计算机传播的危害人体健康的一种病毒
40. B. 人为制造的能够侵入计算机系统并给计算机带来故障的程序或指令集合
41. C. 一种由于计算机元器件老化而产生的对生态环境有害的物质
42. D. 利用计算机的海量高速运算能力而研制出来的用于疾病预防的新型病毒

43. 答案：B

44. FTP 可以用于（ ）。

45. A. 远程传输文件
46. B. 发送电子邮件
47. C. 浏览网页
48. D. 网上聊天
49. 答案：A

50. 解析：FTP：File Transfer Protocol，文件传输协议。

51. 下面哪种软件不属于即时通信软件（ ）。

52. A. QQ
53. B. MSN
54. C. 微信
55. D. P2P
56. 答案：D

57. 解析：P2P（Peer-to-Peer）是对等网络技术，不属于具体的即时通信聊天软件。

58. 下列选项中不属于视频文件格式的是（ ）。

59. A. TXT
60. B. AVI
61. C. MOV
62. D. RMVB
63. 答案：A

64. 解析：TXT 是纯文本文件格式。

65. 在 NOI 系列赛事中参赛选手必须使用由承办单位统一提供的设备。下列物品中不允许选手自带的是（ ）。

66. A. 鼠标
67. B. 笔
68. C. 身份证
69. D. 准考证
70. 答案：A
71. 解析：考场通常统一提供键盘、鼠标等外设，选手严禁自带鼠标。

7.2 基本运算

NOIP2019

1. 二进制数 11 1011 1001 0111 和 01 0110 1110 1011 进行逻辑与运算的结果是（ ）。
2. A. 01 0010 1000 1011
3. B. 01 0010 1001 0011
4. C. 01 0010 1000 0001
5. D. 01 0010 1000 0011
6. 答案：D
7. 解析：逐位进行与（&）运算：1&0=0, 1&1=1, 0&1=0, 1&0=0 等。

NOIP2018

1. 下列四个不同进制的数中，与其它三项数值上不相等的是（ ）。
2. A. $(269)_{16}$
3. B. $(617)_{10}$
4. C. $(1151)_8$
5. D. $(1001101011)_2$
6. 答案：D
7. 解析：
8. A：$(269)_{16} = 2 \times 16^2 + 6 \times 16^1 + 9 \times 16^0 = 512 + 96 + 9 = (617)_{10}$
9. B：$(617)_{10}$
10. C：$(1151)_8 = 1 \times 8^3 + 1 \times 8^2 + 5 \times 8^1 + 1 \times 8^0 = 512 + 64 + 40 + 1 = (617)_{10}$
11. D：$(1001101011)_2$ 转十进制计算不等。

NOIP2017

1. 在 8 位二进制补码中，10101011 表示的数是十进制下的（ ）。
2. A. 43
3. B. -85
4. C. -43
5. D. -84
6. 答案：B

7. 解析：反码为 10101010，原码为 11010101，对应十进制下的 -85。

8. 十进制小数 13.375 对应的二进制数是（ ）。

9. A. 1101.011
10. B. 1011.011
11. C. 1101.101
12. D. 1010.01
13. 答案：A
14. 解析：整数部分 13 转二进制为 1101；小数部分 $0.375 \times 2 = 0.75 (0), 0.75 \times 2 = 1.5 (1), 0.5 \times 2 = 1.0 (1)$，故小数部分为 .011。

NOIP2016

1. 二进制数 00101100 和 00010101 的和是（ ）。
2. A. 00101000
3. B. 01000001
4. C. 01000100
5. D. 00111000

6. 答案：B

7. 与二进制小数 0.1 相等的八进制数是（ ）。

8. A. 0.8
9. B. 0.4
10. C. 0.2
11. D. 0.1
12. 答案：B
13. 解析：二进制小数 0.1（$1 \times 2^{-1} = 0.5$），转八进制：补零为 0.100，即 $4 \times 8^{-1} = 0.4$。

NOIP2015

1. 二进制数 00100100 和 00010100 的和是（ ）。
2. A. 00101000
3. B. 01000001
4. C. 01000100
5. D. 00111000

6. 答案：D

7. 与二进制小数 0.1 相等的十六进制数是（ ）

8. A. 0.8
9. B. 0.4
10. C. 0.2
11. D. 0.1
12. 答案：A
13. 解析：将二进制按每 4 位转换，`(0.1000)2 = (0.8){16}$。

7.3 数据结构与算法

NOIP2019

1. 设有 100 个已排好序的数据元素，采用折半查找时，最大比较次数为（ ）
2. A. 7
3. B. 10
4. C. 6
5. D. 8
6. 答案：A

7. 解析：由 $2^6 - 1 < 100 \le 2^7 - 1$ 可知，最大比较次数为 7。

8. 链表不具有的特点是（ ）

9. A. 插入删除不需要移动元素
10. B. 不必事先估计存储空间
11. C. 所需空间与线性表长度成正比
12. D. 可随机访问任一元素
13. 答案：D

14. 解析：链表元素的内存地址不连续，无法进行 $O(1)$ 的随机访问。

15. 一棵二叉树如原图所示，若采用顺序存储结构，即用一维数组元素存储该二叉树中的结点（根结点的下标为 1，若某结点的下标为 $i$，则其左孩子位于下标 $2i$ 处、右孩子位于下标 $2i+1$ 处），则该数组的最大下标至少为（ ）。

16. A. 6
17. B. 10
18. C. 15
19. D. 12
20. 答案：C

21. 解析：下标最大的结点为树中深度最大且最靠右的结点，其下标为 $((1 \times 2 + 1) \times 2 + 1) \times 2 + 1 = 15$。

22. 假设一棵二叉树的后序遍历序列为 DGJHEBIFCA，中序遍历序列为 DBGEHJACIF，则其前序遍历序列为（ ）。

23. A. ABCDEFGIIIJ
24. B. ABDEGHJCFI
25. C. ABDEGJHCFI
26. D. ABDEGHJFIC
27. 答案：B
28. 解析：通过后序确定根（A），结合中序划分左右子树递归推导得出。

NOIP2018

1. 根节点深度为 0，一棵深度为 h 的满 $k(k>1)$ 叉树，即除最后一层无任何子节点外，每一层上的所有结点都有 $k$ 个子结点的树，共有（ ）个结点。
2. A. $(k^{h+1} - 1) / (k - 1)$
3. B. $k^{h-1}$
4. C. $k^h$
5. D. $(k^{h-1}) / (k - 1)$
6. 答案：A

7. 解析：等比数列求和：$s = k^0 + k^1 + \dots + k^h = \frac{k^{h+1}-1}{k-1}$。

8. 以下排序算法中，不需要进行关键字比较操作的算法是（ ）。

9. A. 基数排序
10. B. 冒泡排序
11. C. 堆排序
12. D. 直接插入排序
13. 答案：A

14. 解析：基数排序是利用分配和收集进行排序的，不需要基于关键字的两两比较。

15. 给定一个含 N 个不相同数字的数组，在最坏情况下，找出其中最大或最小的数，至少需要 $N - 1$ 次比较操作。则最坏情况下，在该数组中同时找最大与最小的数至少需要（ ）次比较操作。

16. A. $\lceil 3N / 2 \rceil - 2$
17. B. $\lfloor 3N / 2 \rfloor - 2$
18. C. $2N - 2$
19. D. $2N - 4$
20. 答案：A

21. 解析：分组两两比较，结合奇偶性优化，同时找最大最小值最优比较次数约为 $\lceil 3N/2 \rceil - 2$。

22. 下面的故事与（ ）算法有着异曲同工之妙。“从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：‘从前有座山，山里有座庙……’”

23. A. 枚举
24. B. 递归
25. C. 贪心
26. D. 分治

27. 答案：B

28. 由四个没有区别的点构成的简单无向连通图的个数是（ ）。

29. A. 6
30. B. 7
31. C. 8
32. D. 9
33. 答案：A

34. 解析：简单无向图（无平行边无自环），4 个点构成的连通图共有 6 种同构图形。

35. 下图中所使用的数据结构是（ ）。（压入A、压入B、弹出B、压入C）

36. A. 哈希表
37. B. 栈
38. C. 队列
39. D. 二叉树
40. 答案：B
41. 解析：先进后出（LIFO）体现的是栈。

NOIP2017

1. 设 G 是有 n 个结点、m 条边（$n \le m$）的连通图，必须删去 G 的（ ）条边，才能使得 G 变成一棵树。
2. A. $m - n + 1$
3. B. $m - n$
4. C. $m + n + 1$
5. D. $n - m + 1$

6. 答案：A

7. 向一个栈顶指针为 hs 的链式栈中插入一个指针 s 指向的结点时，应执行（ ）。

8. A. hs->next = s;
9. B. s->next = hs; hs = s;
10. C. s->next = hs->next; hs->next = s;
11. D. s->next = hs; hs = hs->next;

12. 答案：B

13. 对于入栈顺序为 $a, b, c, d, e, f, g$ 的序列，下列（ ）不可能是合法的出栈序列。

14. A. $a, b, c, d, e, f, g$
15. B. $a, d, c, b, e, g, f$
16. C. $a, d, b, c, g, f, e$
17. D. $g, f, e, d, c, b, a$
18. 答案：C
19. 解析：选项 C 中 $d$ 先出栈，说明 $a,b,c,d$ 均已入栈，接着 $b$ 比 $c$ 先出栈是不可能的（因为此时 $c$ 在栈顶）。

NOIP2016

1. 以下关于字符串的判定语句中正确的是（ ）。
2. A. 字符串是一种特殊的线性表
3. B. 串的长度必须大于零
4. C. 字符串不可以用数组来表示
5. D. 空格字符组成的串就是空串

6. 答案：A

7. 一棵二叉树如原图所示，若采用顺序存储结构……则图中所有结点的最大下标为（ ）。

8. A. 6
9. B. 10
10. C. 12
11. D. 15

12. 答案：D

13. 设简单无向图 G 有 16 条边且每个顶点的度数都是 2，则图 G 有（ ）个顶点。

14. A. 10
15. B. 12
16. C. 8
17. D. 16
18. 答案：D
19. 解析：结点的度数之和等于边数的两倍：$2x = 16 \times 2 \implies x = 16$。

NOIP2015

1. 6 个顶点的连通图的最小生成树，其边数为（ ）
2. A. 6
3. B. 5
4. C. 7
5. D. 4
6. 答案：B

7. 解析：n 个顶点的生成树有 $n-1$ 条边。

8. 链表不具备的特点是（ ）

9. A. 可随机访问任何一个元素
10. B. 插入、删除操作不需要移动元素
11. C. 无需事先估计存储空间大小
12. D. 所需存储空间与存储元素个数成正比

13. 答案：A

14. 线性表若采用链表存储结构，要求内存中可用存储单元地址（ ）

15. A. 必须连续
16. B. 部分地址必须连续
17. C. 一定不连续
18. D. 连续不连续均可

19. 答案：D

20. 今有一空栈 S，对下列待进栈的数据元素序列 $a, b, c, d, e, f$ 依次进行进栈，进栈，出栈，进栈，进栈，出栈的操作，则此操作完成后，栈 S 的栈顶元素为（ ）

21. A. $f$
22. B. $c$
23. C. $a$
24. D. $b$

25. 答案：B

26. 前序遍历序列与中序遍历序列相同的二叉树为（ ）

27. A. 根结点无左子树的二叉树
28. B. 根结点无右子树的二叉树
29. C. 只有根结点的二叉树或非叶子结点只有左子树的二叉树
30. D. 只有根结点的二叉树或非叶子结点只有右子树的二叉树

31. 答案：D

32. 如果根的高度为 1，具有 61 个结点的完全二叉树的高度为（ ）

33. A. 5
34. B. 6
35. C. 7
36. D. 8
37. 答案：B
38. 解析：高度为 5 的完全二叉树最多 $2^5 - 1 = 31$ 个结点；高度为 6 时最多 $2^6 - 1 = 63$ 个结点，故 61 个结点对应高度为 6。

7.4 数学与逻辑

NOIP2019

1. 把 8 个同样的球放在 5 个同样的袋子里，允许有的袋子空着不放，问共有多少种不同的分法？
2. 答案：C (18 种)

3. 解析：整数划分类别枚举：分 1 个袋子 1 种，分 2 个袋子 4 种，分 3 个袋子 5 种，分 4 个袋子 5 种，分 5 个袋子 3 种，合计 18 种。

4. 100 以内最大的素数是（ ）。

5. A. 89
6. B. 97
7. C. 91
8. D. 93

9. 答案：B

10. 319 和 377 的最大公约数是（ ）。

11. A. 27
12. B. 33
13. C. 29
14. D. 31
15. 答案：C

16. 解析：辗转相除法：$\gcd(377, 319) = \gcd(319, 58) = \gcd(58, 29) = 29$。

17. 新学期开学了，小胖想减肥……每周最多通过跑步消耗多少千卡？

18. 答案：C (2400)

19. 解析：线性规划求解：方案一（3公里/半小时，300千卡）、方案二（5公里/1小时，600千卡），满足时间与总公里数限制下最大消耗为 2400 千卡。

20. 一副纸牌除掉大小王有 52 张牌，四种花色，每种花色 13 张。假设从这 52 张牌中随机抽取 13 张纸牌，则至少（ ）张牌的花色一致。

21. A. 4
22. B. 2
23. C. 3
24. D. 5
25. 答案：A

26. 解析：抽屉原理。若最多每种花色 3 张，则总共 $3 \times 4 = 12$ 张，抽 13 张必然有一种花色至少 4 张。

27. 一些数字可以颠倒过来看……假设某个城市的车牌只由 5 位数字组成，每一位都可以取 0 到 9。请问这个城市最多有多少个车牌倒过来恰好还是原来的车牌？

28. 答案：C (75)
29. 解析：可颠倒数字为 0, 1, 8, 6, 9。前两位的选择有 5 种（0, 1, 8, 6/9 对应确定），第 3 位只能选 0, 1, 8（共 3 种），后两位由前两位倒过来唯一确定。总数 $5 \times 5 \times 3 \times 1 \times 1 = 75$。

NOIP2018

1. 如果开始时计算机处于小写输入状态，现在有一只小老鼠反复按照 CapsLock、A、S、D、F 循环按键……第 81 个字符是（ ）。
2. 答案：A

3. 解析：周期为 8， $81 \pmod 8 = 1$，对应第一个字符 A。

4. 设含有 10 个元素的集合的全部子集数为 S，其中由 7 个元素组成的子集数为 T，则 T / S 的值为（ ）。

5. 答案：B ($15 / 128$)

6. 解析：$S = 2^{10} = 1024$，$T = C_{10}^7 = 120$，比值为 $120 / 1024 = 15 / 128$。

7. 10000 以内，与 10000 互质的正整数有（ ）个。

8. 答案：B (4000)
9. 解析：$10000 = 2^4 \times 5^4$，利用容斥原理排除被 2 或 5 整除的数：$10000 - (5000 + 2000 - 1000) = 4000$。

NOIP2017

1. 分辨率为 $800 \times 600$、16 位色的位图，存储图像信息所需的空间为（ ）。
2. 答案：A (937.5KB)

3. 解析：$\frac{16 \times 800 \times 600}{8 \times 1024} = 937.5 \text{ KB}$。

4. 2017 年 10 月 1 日是星期日，1999 年 10 月 1 日是（ ）。

5. 答案：C (星期五)

6. 甲、乙、丙三位同学选修课程，从 4 门课程中，甲选修 2 门，乙、丙各选修 3 门，则不同的选修方案共有（ ）种。

7. 答案：C (96)

8. 解析：$C_4^2 \times C_4^3 \times C_4^3 = 6 \times 4 \times 4 = 96$。

9. 对于给定的序列 ${a_k}$，我们把 $(i, j)$ 称为逆序对当且仅当 $i < j$ 且 $a_i > a_j$。序列 $1, 7, 2, 3, 5, 4$ 的逆序对数为（ ）个。

10. 答案：B (5)

11. 解析：逆序对为 (7,2), (7,3), (7,5), (7,4), (5,4)，共 5 个。

12. 若串 S = “copyright”，其子串的个数是（ ）。

13. 答案：C (46)

14. 解析：长度为 9 的字符串非空子串数为 $\frac{9 \times (9+1)}{2} = 45$，加上空串共 46 个。

15. 一家四口人，至少两个人生日属于同一月份的概率是（ ）。

16. 答案：C (41/96)
17. 解析：四个人生日各不相同的概率为 $\frac{12 \times 11 \times 10 \times 9}{12^4} = 55/96$，对立事件概率为 $1 - 55/96 = 41/96$。

NOIP2016

1. 如果 256 种颜色用二进制编码来表示，至少需要（ ）位。

2. 答案：C (8)

3. 如果开始时计算机处于小写输入状态，按 CapsLock、A、S、D 循环，第 81 个字符是（ ）。

4. 答案：C (D)

5. 解析：循环节长度为 6（含锁状态切换），具体推导第 81 个字符为 D。

6. 有 7 个一模一样的苹果，放到 3 个一样的盘子中，一共有（ ）种放法。

7. 答案：B (8)

8. Lucia 和她的朋友……不让 Jacob 看见照片，她可以向以下朋友分享该照片：

9. 答案：A (Dana, Michael, Eve)

7.5 程序设计

NOIP2019

1. 若有如下程序段……等价的赋值语句是（ ）
2. 答案：A (s = a - c;)

NOIP2018

1. 统计一个非负整数的二进制形式中 1 的个数：x &= x - 1;
2. 答案：B (x &= x - 1)

NOIP2017

1. 设 A 和 B 是两个长为 n 的有序数组……归并算法在最坏情况下至少要做（ ）次比较。
2. 答案：D ($2n - 1$)

NOIP2016

1. 循环累加 s = s + 1; c 次等价于 s = a + c;

2. 答案：B

3. 代码输出结果：2,3

4. 答案：D

5. 二分法寻找“峰顶”代码填空：

6. 答案：A (c, a, b)

NOIP2015

1. 递推关系式 $T(n) = T(n-1) + n$ 的时间复杂度为（ ）。
2. 答案：D ($O(n^2)$)

7.6 问题求解

NOIP2018

1. 逻辑推理题：周末丙去了，则甲（去了）、乙（没去）、丁（没去）、周末（没下雨）。
2. 从 1 到 2018 这 2018 个数中，共有（544）个包含数字 8 的数。

NOIP2017

1. 坐标行走问题，第 2017 轮后的坐标是：（1009, 1008）。
2. 消除 13 个格子中的数字全变为 0 至少需要（3）次操作。

NOIP2016

1. 从 $4 \times 4$ 棋盘中选取不在同一行也不在同一列的两个方格，共有（72）种方法。
2. 结点数为 2016 的二叉树最少有（1）个叶子结点；最小高度值是（11）。

NOIP2015

1. 重新排列 1234 使得每一个数字都不在原来的位置上（错排问题），一共有（9）种排法。
2. 结点数为 2015 的二叉树最多有（1008）个叶子结点。

7.7 阅读程序

NOIP2019

• 程序一（字符串特定约数位转大写）： 1) 错 2) 对 3) 错 4) 对 5) B 6) B
• 程序二（互不冲突数对模拟统计）： 1) 对 2) 错 3) 错 4) 错 5) A 6) A
• 程序三（二叉树中序遍历加权和）： 1) 错 2) 对 3) A 4) D 5) D 6) B

NOIP2018

• 程序一：输入 QuanGuoLianSai $\to$ 输出 RuanHuoMianTai
• 程序二：输入 15 $\to$ 输出 4
• 程序三：输入 5 6 $\to$ 输出 8
• 程序四：输入 10 7 1 4 3 2 5 9 8 0 6 $\to$ 输出 6

NOIP2017

• 程序一：输入 xyzxyw $\to$ 输出 z
• 程序二：输入 7 3 $\to$ 输出 8
• 程序三：输入一串 01 序列 $\to$ 输出 11
• 程序四：输入 4 3 $\to$ 输出 1 3；输入 2017 1014 $\to$ 输出 2017 1

NOIP2016

• 程序一：输入 1 2 3 4 5 6 0 7 $\to$ 输出 6,1,3
• 程序二：计算 99 到 0 之间除以 8 余 1 的数字个数 $\to$ 输出 13
• 程序三：数组前后颠倒输出 $\to$ 输出 6,5,4,3,2,1,
• 程序四：字符串大写比较 $\to$ 输出 =

NOIP2015

• 程序一：输出 3
• 程序二：输出 3,2
• 程序三：输入统计小写字母个数 $\to$ 输出 It has 18 lowercases
• 程序四：指针形参修改 $\to$ 输出 Ab

7.8 完善程序

NOIP2019

• 程序一（矩阵变幻）：
• ① C (t)
• ② D (x, y)
• ③ B (x + step, y + step)
• ④ B (n, 0)
• ⑤ B (1 << n)
• 程序二（双关键字计数排序）：
• ① ++cnt[b[i]]
• ② ord[--cnt[b[i]]] = i
• ③ ++cnt[a[i]]
• ④ res[--cnt[a[ord[i]]]] = ord[i]
• ⑤ a[res[i]], b[res[i]]

NOIP2018

• 程序一（最大公约数之和）：
• ① i * i
• ② n / i
• ③ return a
• ④ a % b
• ⑤ ans + gcd(a[i], a[j])
• 程序二（双向链表求右侧第一个更大元素）：
• ① a[x] = i
• ② i + 1
• ③ R[a[i]]
• ④ a[i]
• ⑤ R[i]

NOIP2017

• 程序一（快速幂）：
• ① 1
• ② p > 0（或 p != 0）
• ③ result * x % m
• ④ x * x % m
• ⑤ result
• 程序二（切割绳子二分）：
• ① count = count + len[i]
• ② count < m
• ③ lbound < ubound
• ④ (lbound + ubound + 1) / 2
• ⑤ count = count + len[i] / mid

NOIP2016

• 程序一（高效读入整数）：
• ① cin.get()
• ② num = c - '0'
• ③ c >= '0' && c <= '9'
• ④ num = num * 10 + c - '0'
• ⑤ num = -num
• 程序二（郊游租车二分贪心）：
• ① n - nn + 1
• ② M[i] < C[j]
• ③ count <= A
• ④ check(mid)
• ⑤ mid - 1

NOIP2015

• 程序一（打印月历）：
• ① offset = 4
• ② (offset + dayNum[i]) % 7
• ③ dayNum[m]
• ④ i
• ⑤ (offset + i) % 7
• 程序二（二分求中位数）：
• ① lbound < rbound
• ② count = 0
• ③ x[i] > mid
• ④ count++
• ⑤ rbound = mid

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com