1 NOIP2010年普及组初赛题目及答案解析
原链接：https://longkui.blog.csdn.net/article/details/149573769 解析时间：2026-08-02T17:51:39+08:00 注：本文档已按要求转为 Markdown 格式，添加多级标题，并将图片通过 PicGo 上传至图床。对部分题目解析进行了扩写和修正，以便于阅读和理解。
1.1 一、单项选择题
（共20题，每题1.5分，共计30分。每题有且仅有一个正确答案。）
1.1.1 2E+03 表示（ D ）
A. 2.03 B. 5 C. 8 D. 2000
【解析】 本题考查科学计数法。
E(或e) 代表 10 的次幂。2E+03也就是 ，即 2000。 答案选 D。
1.1.2 一个字节（ byte ）由（ A ）个二进制位组成
A. 8 B. 16 C. 32 D. 以上都有可能
【解析】 本题考查计算机存储单位的基础知识。 1 字节（Byte）固定等于 8 个二进制位（Bit）。这是计算机中最基础的容量单位。 答案选 A。
1.1.3 以下逻辑表达式的值恒为真的是（ A ）
A. P∨(┐P ∧Q) ∨(┐P∧┐Q) B. Q∨ (┐P∧Q) ∨(P∧┐Q) C. P∨Q∨(P∧┐Q) ∨(┐P ∧Q) D. P∨ ┐Q∨(P ∧┐Q) ∨(┐P∧┐Q)
【解析】 本题考查布尔逻辑代数的化简。题目中均为析取（或，
∨），只要整个表达式中有一部分能化简为恒真（True），则整个表达式恒为真。我们利用逻辑代数法则化简 A项：
P ∨ (┐P ∧ Q) ∨ (┐P ∧ ┐Q)提取后两项的公因子┐P：= P ∨ [┐P ∧ (Q ∨ ┐Q)]因为Q ∨ ┐Q恒为真 (True)：= P ∨ [┐P ∧ True]= P ∨ ┐P显然，P ∨ ┐P的结果也恒为真。对比其他项（可通过赋值反例排除）： B项：若 Q 为假，P 为假，则整个表达式为假。 C项：若 P 为假，Q 为假，则整个表达式为假。 D项：若 P 为假，Q 为真，则整个表达式为假。
综上，只有 A 恒为真。答案选 A。
1.1.4 Linux 下可执行文件的默认扩展名为（ D ）
A. exe B. com C. dll D. 以上都不是
【解析】 本题考查操作系统的基础知识。
- A项：
.exe是 Windows 环境下可执行程序的后缀。- B项：
.com早期在 DOS/Windows 下也是可执行文件后缀，现在常见为网站顶级域名。- C项：
.dll是 Windows 环境下的动态链接库（Dynamic Link Library）。- D项：Linux 系统与 Windows 不同，Linux 下的文件不需要扩展名，依靠文件的属性权限来区分。在 Linux 中“一切皆文件”。要知道文件是否为可执行文件，一般通过
ls -l命令查看文件属性，若包含执行权限（x），即可被执行。答案选 D。
1.1.5 如果树根算第 1 层，那么一棵 n 层的二叉树最多有（ A ）个结点
A. B. C. D.
【解析】 本题考查二叉树的基本性质。
- 性质1：在二叉树的第 层，最多有 个结点（）。
- 性质2：深度为 （即有 层）的二叉树，至多有 个结点。
题目问的是 层二叉树最多的节点数，直接套用性质2即可得出答案为 。答案选 A。
1.1.6 提出“存储程序”的计算机工作原理的是（ D ）
A. 克劳德·香农 B. 戈登·摩尔 C. 查尔斯·巴比奇 D. 冯·诺依曼
【解析】
- A项：克劳德·香农（Claude Shannon），提出“熵”的概念，是信息论的开创者。
- B项：戈登·摩尔（Gordon Moore），Intel 公司创始人之一，提出了著名的摩尔定律。
- C项：查尔斯·巴比奇（Charles Babbage），提出了差分机与分析机的设计概念，被称为现代计算机的鼻祖。
- D项：约翰·冯·诺依曼（John von Neumann），被誉为**“现代计算机之父”。他最早提出了“存储程序和程序控制”**的计算机体系结构（即冯·诺依曼架构），是目前绝大多数计算机的基础。
答案选 D。
1.1.7 设 X、Y、Z 分别代表三进制下的一位数字，若等式 XY + ZX = XYX 在三进制下成立，那么同样在三进制下，等式 XY * ZX = （ B ）也成立。
A. YXZ B. ZXY C. XYZ D. XZY
【解析】 三进制的三个数字分别为 0，1，2。我们通过列竖式来推理 的值：
X Y + Z X ------ X Y X这是一道两位数加两位数等于三位数的加法题，必然产生了进位。
- 在三进制下，两个单数相加最大只能进 1，所以百位上的 X 必然等于 1。
- 再看个位： （或 但两数都小于3不可能进位）。因为 ，即 ，得出 Y = 0。
- 再看十位：。代入已知 ，即 （因为向百位进了1，所以和是3）。由此得出 Z = 2。
结论：。 接下来计算 ： 代表三进制数 （即十进制的3）， 代表三进制数 （即十进制的7）。 两者相乘：。 对照字母：2 是 Z，1 是 X，0 是 Y。所以结果表示为 ZXY。 答案选 B。
1.1.8 Pascal 语言、 C 语言和 C++ 语言都属于（ D ）
A. 面向对象语言 B. 脚本语言 C. 解释性语言 D. 编译性语言
【解析】
- 面向对象语言：Java, C++, C#, Python 等。C 语言是面向过程的，因此 A 错误。
- 脚本语言：通常是不需要编译、直接解释执行的语言，如 PHP, JavaScript, Python 等。
- 解释性语言：程序在运行时才通过解释器动态翻译成机器语言（每执行一次翻译一次），如 JavaScript, Python, MATLAB 等。
- 编译性语言：程序在执行前需要专门的编译过程，由编译器将源代码一次性翻译为底层的机器语言（例如 .exe 或 可执行的二进制文件），运行时直接执行，效率较高。C/C++、Pascal 均属于此类。
答案选 D。
1.1.9 前缀表达式“ + 3 * 2 + 5 12 ”的值是（ C ）
A. 23 B. 25 C. 37 D. 65
【解析】 前缀表达式（波兰表达式）转换为中缀表达式或直接计算，最稳妥的方法是从右向左扫描。 具体步骤（堆栈法）：
- 从右往左读，遇到数字就压入栈中。遇到操作符，就从栈中弹出两个数字（先弹出的作为左操作数，后弹出的作为右操作数），进行计算，然后把结果压回栈中。
- 对于
+ 3 * 2 + 5 12：
- 压入 12
- 压入 5
- 遇到
+，弹出 5 和 12，计算 ，将 17 压栈。- 压入 2
- 遇到
*，弹出 2 和 17，计算 ，将 34 压栈。- 压入 3
- 遇到
+，弹出 3 和 34，计算 ，将 37 压栈。最终栈内剩余结果为 37。答案选 C。
1.1.10 主存储器的存取速度比中央处理器（ CPU）的工作速度慢得多， 从而使得后者的效率受到影响。 而根据局部性原理， CPU所访问的存储单元通常都趋于聚集在一个较小的连续区域中。于是，为了提高系统整体的执行效率，在 CPU 中引入了（ B ）。
A. 寄存器 B. 高速缓存 C. 闪存 D. 外存
【解析】
- A项 寄存器 (Register)：CPU 内部存储数据的小元件，速度最快，但容量极小，主要用于存储当前正在执行的指令和数据。
- B项 高速缓存 (Cache)：介于 CPU 寄存器和主内存之间的高速小容量存储器。利用局部性原理（时间局部性和空间局部性），将主存中近期频繁访问的数据块复制到 Cache 中，大大缩短 CPU 获取数据的等待时间，提高执行效率。
- C项 闪存 (Flash Memory)：一种非易失性存储器（如 U盘、固态硬盘），断电后数据不丢失，属于外部存储，速度慢于主存。
- D项 外存：包括硬盘、光盘等，容量大但速度最慢。
答案选 B。
1.1.11 一个字长为 8 位的整数的补码是 11111001 ，则它的原码是（ D ）
A. 00000111 B. 01111001 C. 11111001 D. 10000111
【解析】 本题考查原码、反码、补码的转换规律。
- 正数的原码、反码、补码均相同。
- 负数的补码 = 其原码保留符号位，其余各位取反，最后加 1。
- 已知负数补码求原码的捷径：补码的符号位不变，其余各位取反，再加 1（即对补码再求一次补码，即可得到原码）。
题中给出的补码首位（符号位）为
1，说明是负数。 补码：1111 1001符号位不变，其余取反：1000 0110末位加 1：1000 0111这就是该负数的原码（对应的十进制为 -7）。答案选 D。
1.1.12 基于比较的排序时间复杂度的下限是（ B ），其中 n 表示待排序的元素个数。
A. O(n) B. O(n log n) C. O(log n) D. O(n²)
【解析】 本题考查排序算法的理论下界。 对于基于比较的排序（如冒泡、快排、归并、堆排等），可以将整个排序过程抽象为一棵决策树。 个待排序元素的全排列共有 种可能，这意味着决策树必须至少有 个叶子节点，才能涵盖所有正确的排序结果。 一棵高度为 的二叉树最多有 个叶子节点。因此必须满足： 两边取对数得到： 根据**斯特林公式（Stirling’s formula）**近似得出 。 因此，比较的次数（即树的高度 ）至少是 级别。 答案选 B。（注：非比较排序如桶排序、基数排序可突破此下限）
1.1.13 一个自然数在十进制下有 n 位，则它在二进制下的位数与（ B ）最接近。
A. 5n B. nlog₂10 C. 10log₂n D. 10^n log₂n
【解析】 假设该自然数为 。既然它在十进制下有 位，说明它的数量级在 到 之间，即 。 设它在二进制下有 位，那么同理，它的数量级满足 。 令 ，两边同时取以 2 为底的对数： 因为 ，所以一个 位的十进制数，大约对应 位的二进制数。 答案选 B。
1.1.14 在下列 HTML 语句中，可以正确产生一个指向 NOI 官方网站的超链接的是（ B ）
A. <a url="http://www.noi.cn">欢迎访问NOI网站</a>
B. <a href="http://www.noi.cn">欢迎访问NOI网站</a>
C. <a> http://www.noi.cn</a>
D. <a name="http://www.noi.cn">欢迎访问NOI网站</a>
【解析】 在 HTML 中，创建超链接必须使用
<a>标签（锚点标签）。 其指定链接目标地址的关键属性是href（Hypertext REFerence），而不是url或name。 基本语法为：<a href="链接地址">显示的文本</a>。 答案选 B。
1.1.15 元素 R1、R2、R3、R4、R5 入栈的顺序为 R1、R2、R3、R4、R5。如果第 1 个出栈的是 R3，那么第 5 个出栈的不可能是（ B ）。
A. R1 B. R2 C. R4 D. R5
【解析】 本题考查栈的特性（后进先出 LIFO）。 既然第一个出栈的是 R3，这意味着入栈操作至少进行到了 R3：
- R1 进栈，R2 进栈，R3 进栈。此时栈内从底到顶是
R1, R2, R3。- R3 马上出栈。
- 此时栈中剩余
R1, R2(R2在栈顶，R1在栈底)。接下来不论 R4、R5 如何进出栈，由于 R2 在 R1 的上面，R2 必然比 R1 先出栈。 因此，R1 可能是最后一个（第5个）出栈的，R4、R5 也可能在 R2 出栈后入栈再最后出栈，但 R2 绝对不可能是最后一个出栈的元素（因为只要 R2 不出，R1 就出不来，R1 一定在 R2 后面）。 答案选 B。
1.1.16 双向链表中有两个指针域 llink 和 rlink ，分别指向该结点的前驱及后继。 设 p 指向链表中的一个结点，它的左右结点均非空。现要求删除结点 p ，则下面语句序列中错误的是 （ A ）。
A. p->rlink->llink = p->rlink; p->llink->rlink = p->llink; delete p;
B. p->llink->rlink = p->rlink; p->rlink->llink = p->llink; delete p;
C. p->rlink->llink = p->llink; p->rlink->llink->rlink = p->rlink; delete p;
D. p->llink->rlink = p->rlink; p->llink->rlink->llink = p->llink; delete p;
【解析】 要在双向链表中删除节点 p，核心思路是将其前驱节点和后继节点“绕过” p 直接相连：
- 让 p 的前驱节点的右指针指向 p 的后继：
p->llink->rlink = p->rlink;- 让 p 的后继节点的左指针指向 p 的前驱：
p->rlink->llink = p->llink;（这两步顺序可以互换，对应了正确的 B 选项）。分析 A 选项的错误：
p->rlink->llink = p->rlink;这句话的意思是，让 p 的后继节点的左指针，指向 p 的后继节点自己！这造成了链表彻底断裂，无法连上 p 的前驱节点了。 答案选 A。
1.1.17 一棵二叉树的前序遍历序列是 ABCDEFG，后序遍历序列是 CBFEGDA，则根结点的左子树的结点个数可能是（ A ）。
A. 2 B. 3 C. 4 D. 5
【解析】
- 前序遍历（根-左-右）：首节点必是整棵树的根。可见
A是根。- 后序遍历（左-右-根）：尾节点必是根。验证
A为根。剔除根节点 A，剩下：
- 前序剩余：
B C D E F G- 后序剩余：
C B F E G D在前序剩余中，
B紧挨着A，所以B是根节点某个子树（可能是左，也可能是右）的根。 如果B是右子树的根，那么在后序遍历中B也应该是最后访问的节点之一（紧挨着A，即最后倒数第二位），但后序剩余是C B F E G D，倒数第二位是D而不是B。这说明整棵树既有左子树又有右子树，B必然是左子树的根。既然
B是左子树的根，再观察后序序列C B ...，由于后序遍历是“左右根”，说明在B节点子树下访问完所有子孙后才访问B，而B前面只有一个C。这表示以B为根的左子树，只包含了C和B自己这两个节点。因此，根节点 A 的左子树包含
B和C，节点个数为 2。答案选 A。
1.1.18 关于拓扑排序，下面说法正确的是（ D ）。
A. 所有连通的有向图都可以实现拓扑排序 B. 对同一个图而言，拓扑排序的结果是唯一的 C. 拓扑排序中入度为 0 的结点总会排在入度大于 0 的结点的前面 D. 拓扑排序结果序列中的第一个结点一定是入度为 0 的点
【解析】 拓扑排序是将有向无环图（DAG）的顶点排成线性序列的算法，若存在边
<u,v>，则u必须排在v之前。
- A错误：拓扑排序的前提是“无环”。如果有向连通图包含环，则无法进行拓扑排序。
- B错误：如果图中存在多个入度为 0 的点，或者排布层级有并列的顶点，那么拓扑排序结果往往不是唯一的。
- C错误：不一定总排在前面。比如有独立的一条链
1->2和一个孤立点3（入度为0）。合法序列可以是1, 2, 3，此时入度为 0 的3排在了入度大于 0 的2后面。- D正确：根据拓扑排序算法流程（每次剥离入度为 0 的节点），输出的第一步必须是没有前置依赖的点，即入度为 0 的点。
1.1.19 完全二叉树的顺序存储方案，是指将完全二叉树的结点从上至下、从左至右依次存放到一个顺序结构的数组中。假定根结点存放在数组的 1 号位置，则第 k 号结点的父结点如果存在的话，应当存放在数组的（ C ）号位置。
A. 2k B. 2k+1 C. ⌊k/2⌋ D. ⌊(k+1)/2⌋
【解析】 这是完全二叉树顺序存储的基础性质。
- 若节点编号为 (且 )，它的父节点编号一定为 (即 向下取整)。
- 它的左孩子（若存在）编号为 。
- 它的右孩子（若存在）编号为 。
比如节点 2 和节点 3，他们的父节点都是 1 (2/2 = 1, 3/2 = 1)。答案选 C。
1.1.20 全国青少年信息学奥林匹克系列活动的主办单位是（ D ）。
A. 教育部 B. 科技部 C. 共青团中央 D. 中国计算机学会
【解析】 常识题。NOI（全国青少年信息学奥林匹克）系列活动（包括 NOIP、CSP-J/S 等）均由**中国计算机学会（CCF）**主办。答案选 D。
1.2 二、问题求解
（共 2 题，每题 5 分，共计 10 分）
1.2.1 LZW 编码
LZW 编码是一种自适应词典编码。在编码的过程中，开始时只有一部基础构造元素的编码词典， 如果在编码的过程中遇到一个新的词条，则该词条及一个新的编码会被追加到词典中，并用于后继信息的编码。
举例说明，考虑一个待编码的信息串：“xyx yy yy xyx” 。初始词典只有 3 个条目， 第一个为 x，编码为 1；第二个为 y，编码为 2 ；第三个为空格，编码为 3；于是串 “xyx” 的编码为 1-2-1 （其中 - 为编码分隔符） ，加上后面的一个空格就是 1-2-1-3 。但由于有了一个空格， 我们就知道前面的 “xyx” 是一个单词， 而由于该单词没有在词典中， 我们就可以自适应的把这个词条添加到词典里，编码为 4 ，然后按照新的词典对后继信息进行编码，以此类推。于是，最后得到编码： 1-2-1-3-2-2-3-5-3-4 。
现在已知初始词典的 3 个条目如上述，则信息串 “yyxy xx yyxy xyx xx xyx” 的 编码是 ________________________。
【答案】 2-2-1-2-3-1-1-3-4-3-1-2-1-3-5-3-6 或 22123113431213536
【解析】 LZW 是一种基于字典的压缩编码。其基本原理是：如果发现之前没见过的单词（以空格为界），就按顺序给它编一个新号并放入字典中；如果是出现过的单词，在后续可以直接使用它的编号。
题目信息串为
yyxy xx yyxy xyx xx xyx。已知字典初始有：x:1,y:2,空格:3。 我们逐个处理单词：
- 第一个单词 yyxy：此时字典里只有单个字符，所以拆解编码为
y, y, x, y，即2-2-1-2，后接一个空格3。同时，因为遇到空格，这个新单词yyxy被加入字典，编号为 4。目前结果：2-2-1-2-3。- 第二个单词 xx：字典里只有单个字符和
yyxy，所以拆解编码为x, x，即1-1，后接一个空格3。遇到空格后，新单词xx加入字典，编号为 5。目前结果：2-2-1-2-3-1-1-3。- 第三个单词 yyxy：这个单词我们已经在字典里了，它的编号是 4！所以直接输出
4，后接空格3。但是，这里注意，LZW 编码的题目在给出的样例中：“xyx yy yy xyx” 最后变成了 1-2-1-3-2-2-3-5-3-4。样例在第二个 yy 的时候，直接输出了 5。这说明，一旦单词整体放入词典，下次遇到就可以直接作为整体输出编号。所以yyxy整体编码为 4。目前结果：...-4-3。- 第四个单词 xyx：不在字典中，按字符拆分
x, y, x，即1-2-1，后接空格3。遇到空格后，把新单词xyx加入字典，编号为 6。目前结果：...-1-2-1-3。- 第五个单词 xx：在字典中，编号为 5，直接输出
5，后接空格3。目前结果：...-5-3。- 第六个单词 xyx：在字典中，编号为 6，直接输出
6。由于是最后一个单词，后面没有空格了。目前结果：...-6。综上拼接起来：
2-2-1-2-3-1-1-3-4-3-1-2-1-3-5-3-6。
1.2.2 队列快照
队列快照是指在某一时刻队列中的元素组成的有序序列。例如，当元素 1 、2 、3 入队， 元素 1 出队后， 此刻的队列快照是 “2 3” 。当元素 2、3 也出队后，队列快照是 “” ，即为空。
现有 3 个正整数元素依次入队、出队。已知它们的和为 8，则共有 _________ 种可能的不 同的队列快照（不同队列的相同快照只计一次）。例如， “5 1” 、”4 2 2” 、”” 都是可能 的队列快照；而 “7” 不是可能的队列快照，因为剩下的 2 个正整数的和不可能是 1。
【答案】 49
【解析】 题意：有三个正整数依次入队、出队，设它们分别为 。已知 且 。
任何一个序列 都会经历以下快照状态：
空(初始状态)[x](x入队)[x, y](y入队)[x, y, z](z入队)[y, z](x出队)[z](y出队)空(z出队，回归空)题目要求求所有不同的队列快照数量。我们按快照包含的元素个数进行分类统计：
长度为 3 的快照：
[x, y, z]等价于求方程 的正整数解的个数。利用插板法，7 个空隙中插入 2 个板： 种。 所以长度为 3 的快照有 21 种。长度为 2 的快照：
[x, y]和[y, z]这相当于任意两个正整数的组合 ，由于是由总和为 8 的三个正数截取的一段，必定有 (因为另一个数至少为 1)。 所以所有的合法二元组 满足：。 我们统计满足此条件的组合数： 若 ，有 1 种 (1,1) 若 ，有 2 种 (1,2), (2,1) 若 ，有 3 种 … … 若 ，有 6 种 总计： 种。 所以长度为 2 的快照有 21 种。长度为 1 的快照：
[x]和[z]单元素快照的值，必须严格小于 8 且大于 0。由于三个正数和为8，最大的单数可能是 6（即 6+1+1=8）。 所以单元素可以是 中的任意一个。 所以长度为 1 的快照有 6 种。长度为 0 的快照：
空显然只有 1 种。总计不同的快照数： 种。
1.3 三、阅读程序写结果
（共 4 题，每题 8 分，其中第 4 题（ 1）、（2）各 4 分，共计 32 分）
1.3.1 变量交换与比较
#include<iostream>
using namespace std;
void swap(int & a, int & b) {
int t;
t = a;
a = b;
b = t;
}
int main() {
int a1, a2, a3, x;
cin>>a1>>a2>>a3;
if (a1 > a2)
swap(a1, a2);
if (a2 > a3)
swap(a2, a3);
if (a1 > a2)
swap(a1, a2);
cin>>x;
if (x < a2)
if (x < a1)
cout<<x<<' '<<a1<<' '<<a2<<' '<<a3<<endl;
else
cout<<a1<<' '<<x<<' '<<a2<<' '<<a3<<endl;
else if (x < a3)
cout<<a1<<' '<<a2<<' '<<x<<' '<<a3<<endl;
else
cout<<a1<<' '<<a2<<' '<<a3<<' '<<x<<endl;
return 0;
}输入： 91 2 20 77 输出： ________________
【答案】 2 20 77 91
【解析】 本程序的目的是将输入的 4 个数进行升序排序。 第一步，读入
a1=91, a2=2, a3=20。 接下来的三个if和swap语句实现的是典型的三个数的冒泡排序。swap函数中的参数&a和&b是引用传递，因此会对main中的变量直接修改。
a1(91) > a2(2)，交换，变成2, 91, 20a2(91) > a3(20)，交换，变成2, 20, 91a1(2) > a2(20)，不成立。 此时a1, a2, a3的值已经变为2, 20, 91。第二步，读入
x=77。 后面的if...else语句逻辑是将x插入到已经排好序的a1, a2, a3中。
x(77) < a2(20)：不成立。- 进入
else if (x < a3(91))：成立。- 执行
cout << a1 << ' ' << a2 << ' ' << x << ' ' << a3 << endl;因此，最终打印输出的结果是：
2 20 77 91。
1.3.2 回文数查找
#include<iostream>
using namespace std;
int rSum(int j) {
int sum = 0;
while (j != 0) {
sum = sum * 10 + (j % 10);
j = j / 10;
}
return sum;
}
int main() {
int n, m, i;
cin>>n>>m;
for (i = n; i < m; i++)
if (i == rSum(i))
cout<<i<<' ';
return 0;
}输入： 90 120 输出： ________________
【答案】 99 101 111
【解析】
- 分析
rSum函数的功能： 这个函数通过不断取模 (j % 10) 得到数字的最低位，然后把它累加到sum中，同时sum乘 10 以提升数量级，j除以 10 以去掉最低位。 这个过程的效果是将一个整数的各个位反转。例如输入123，rSum就会返回321。- 分析
main函数的功能： 遍历区间[n, m)，判断i == rSum(i)是否成立。这意味着寻找反转后等于自身的数，即回文数。- 执行过程： 输入区间
[90, 120)，我们要找出 90 到 119 之间的所有回文数。 显然，满足条件的两位数只有 99，三位数只有 101 和 111。所以程序输出为
99 101 111（中间有空格）。
1.3.3 寻找最大与次大字符
#include<iostream>
using namespace std;
int main() {
string s;
char m1, m2;
int i;
getline(cin, s);
m1 = ' ';
m2 = ' ';
for (i = 0; i < s.length(); i++)
if (s[i] > m1) {
m2 = m1;
m1 = s[i];
} else if (s[i] > m2)
m2 = s[i];
cout<<int(m1)<<' '<<int(m2)<<endl;
return 0;
}输入： Expo 2010 Shanghai China 输出： ________________ (附提示：空格 ASCII 32，‘0’ ASCII 48，‘A’ ASCII 65，‘a’ ASCII 97)
【答案】 120 112
【解析】 观察循环中的
if逻辑：if (s[i] > m1) { m2 = m1; m1 = s[i]; } else if (s[i] > m2) { m2 = s[i]; }这段代码维护了字符串中 ASCII 码最大的两个字符。其中：
m1存储出现过的最大字符。m2存储出现过的第二大字符。字符串为
"Expo 2010 Shanghai China"。 小写字母的 ASCII 码值最大，我们找字符串中最大的两个小写字母：
- 字母 ‘x’：ASCII 码为 。
- 字母 ‘p’：ASCII 码为 。
- 字母 ‘o’：ASCII 码为 。
- 字母 ‘n’ 等等…
最大字符为
'x'，次大字符为'p'。 程序最后输出强转为int，因此输出的是它们的 ASCII 码。 结果为120 112。
1.3.4 递归函数
#include<iostream>
using namespace std;
const int NUM = 5;
int r(int n) {
int i;
if (n <= NUM)
return n;
for (i = 1; i <= NUM; i++)
if (r(n - i) < 0)
return i;
return -1;
}
int main() {
int n;
cin>>n;
cout<<r(n)<<endl;
return 0;
}（1） 输入： 7 输出： _________ （4 分） （2） 输入： 16 输出： _________ （4 分）
【答案】 （1）1 （2）4
【解析】 我们使用递推的方式，手工计算 较小情况下的 的值：
- 根据
if (n <= 5) return n;可知： 都是大于 0 的。- 计算 ： 执行 for 循环，当 到 时，调用的 分别是 到 ，它们均大于 0，无法满足
< 0的条件。 所以循环走完，最后执行return -1;，即 。- 计算 ： 当 时，调用 。因为 成立，函数直接
return i;即return 1。所以 。- 计算 ： ，，不成立。 ， 成立，返回 2。所以 。
- 按照这种规律，我们可以列出 的值列表：
由此可见，数列以 6 为周期循环。
- n = 1~5 :
- n = 6 :
- n = 7~11 :
- n = 12 :
- n = 13~17 :
- 对于 ，周期循环中的相对位置为 1，所以输出 1。
- 对于 ，计算 ，周期循环中的相对位置为 4，所以输出 4。
1.4 四、完善程序
（前 4 空，每空 2.5 分，后 6 空，每空 3 分，共计 28 分）
1.4.1 哥德巴赫猜想
哥德巴赫猜想是指，任一大于 2 的偶数都可写成两个质数之和。迄今为止，这仍然是一个著名的世界难题，被誉为数学王冠上的明珠。 试编写程序，验证任一大于 2 且不超过 n 的偶数都能写成两个质数之和。
#include<iostream>
using namespace std;
int main() {
const int SIZE = 1000;
int n, r, p[SIZE], i, j, k, ans;
bool tmp;
cin>>n;
r = 1;
p[1] = 2;
for (i = 3; i <= n; i++) {
① ________;
for (j = 1; j <= r; j++)
if (i % ② ________) {
tmp = false;
break;
}
if (tmp) {
r++;
③ ________;
}
}
ans = 0;
for (i = 2; i <= n / 2; i++) { // i=n/2 表示缩小范围，排除重复情况。
tmp = false;
for (j = 1; j <= r; j++)
for (k = j; k <= r; k++)
if (i + i == ④ ________) {
tmp = true;
break;
}
if (tmp)
ans++;
}
cout<<ans<<endl;
return 0;
}若输入 n 为 2010 ，则输出 ⑤ ________ 时表示验证成功，即大于 2 且不超过 2010 的偶数都满足哥德巴赫猜想。
【答案】 ① tmp = true ② p[j] == 0 ③ p[r] = i ④ p[j] + p[k] ⑤ 1004
【解析】
- 第一段（筛质数）： 该段的主要功能是找出不超过 n 的所有质数，并依次存放在数组
p中。p的初始状态p[1] = 2，r记录已找到的质数个数。
- 在外层循环
for(i=3; i<=n; i++)中，要判断i是否为质数。判断方法是让i对已知的质数序列取余。- ① 处：在每次内层循环前，我们需要设定一个假设：默认
i是质数，所以填tmp = true。- ② 处：在内层循环中，如果发现
i能够整除某个已知的质数p[j]，则说明i不是质数。因此此处判断条件应填p[j] == 0（原博主给出的答案直接写p[j]是错误的，C++ 中i % p[j]若不为0则为真，不符合逻辑，应判断其余数是否为0）。- ③ 处：如果经过验证
tmp仍为真，说明i是质数，需要将i加入到质数数组p的末尾。此时质数计数r++，接下来要赋值。填p[r] = i。- 第二段（验证哥德巴赫猜想）：
- 外层循环
for(i=2; i<=n/2; i++)，这里实际上是遍历大于2的所有偶数（步长体现在偶数为 ）。即偶数范围是从 到 。- ④ 处：代码试图判断偶数（即
i+i）是否能表示为两个质数之和。这里遍历了所有已知的质数组合p[j]和p[k]，所以条件应填p[j] + p[k]。- 第五处（求成功验证的数量）：
- 循环的范围是从
i=2到i = n / 2。- 当输入
n = 2010时，n / 2 = 1005。i的范围是从 2 变化到 1005，一共验证了 个偶数。- 因此最终如果完全成功，
ans的值为 1004。填 1004。
1.4.2 过河问题
在一个月黑风高的夜晚，有一群人在河的右岸，想通过唯一的一根独木桥走到河的左岸。在这伸手不见五指的黑夜里，过桥时必须借助灯光来照明，很不幸的是，他们只有一盏灯。另外，独木桥上最多承受两个人同时经过，否则将会坍塌。每个人单独过桥都需要一定的时间，不同的人需要的时间可能不同。两个人一起过桥时，由于只有一盏灯，所以需要的时间是较慢的那个人单独过桥时所花的时间。现输入 n（2≤n≤100）和这 n 个人单独过桥时需要的时间，请计算总共最少需要多少时间，他们才能全部到达河的左岸。
例如，有 3 个人甲、乙、丙，他们单独过桥的时间分别为 1、 2、4，则总共最少需要的时间为 7 。具体方法是：甲、乙一起过桥到河的左岸，甲单独回到河的右岸将灯带回，然后甲、丙再一起过桥到河的左岸，总时间为 2+1+4=7。
#include<iostream>
using namespace std;
const int SIZE = 100;
const int INFINITY = 10000;
const bool LEFT = true;
const bool RIGHT = false;
const bool LEFT_TO_RIGHT = true;
const bool RIGHT_TO_LEFT = false;
int n, hour[SIZE]; //存放每个人的过河时间
bool pos[SIZE];
int max(int a, int b) {
if (a > b) return a;
else return b;
}
int go(bool stage) {
int i, j, num, tmp, ans;
if (stage == RIGHT_TO_LEFT) {
num = 0;
ans = 0;
for (i = 1; i <= n; i++)
if (pos[i] == RIGHT) {
num++; //人数加1
if (hour[i] > ans)
ans = hour[i]; //ans保留了最长的过桥时间
}
if ( ① __________ )
return ans;
ans = INFINITY;
for (i = 1; i <= n - 1; i++)
if (pos[i] == RIGHT) //如果这个人在右侧
for (j = i + 1; j <= n; j++)
if (pos[j] == RIGHT) {
pos[i] = LEFT;
pos[j] = LEFT;
tmp = max(hour[i], hour[j]) + ② __________ ;
if (tmp < ans)
ans = tmp;
pos[i] = RIGHT;
pos[j] = RIGHT;
}
return ans;
}
if (stage == LEFT_TO_RIGHT) {
ans = INFINITY;
for (i = 1; i <= n; i++)
if ( ③_________ ) {
pos[i] = RIGHT;
tmp = ④ _________;
if (tmp < ans)
ans = tmp;
⑤__________ ;
}
return ans;
}
return 0;
}
int main() {
int i;
cin>>n;
for (i = 1; i <=n; i++) {
cin>>hour[i];
pos[i] = RIGHT; //pos是记录每个元素所处的位置。
}
cout<<go(RIGHT_TO_LEFT)<<endl; //初始状态RIGHT_TO_LEFT
return 0;
}(本小题中， LEFT 可用 true 代替， LEFT_TO_RIGHT 可用 true 代替， RIGHT_TO_LEFT 可用 false 代替)
【答案】 ① num <= 2 ② go(LEFT_TO_RIGHT) ③ pos[i] == LEFT ④ hour[i] + go(RIGHT_TO_LEFT) ⑤ pos[i] = LEFT
【解析】 本题使用**回溯法（暴力搜索）**来枚举所有可能的过河方案，并取其中时间最少的方案。
go(stage)函数用来递归计算剩余过河过程所需的最短时间。stage表示当前的行动方向（从右往左，或是从左往右返回送灯）。- 第一段（从右向左过河
RIGHT_TO_LEFT）：
- 这意味着要有两个人一起过桥。首先统计目前在右岸（
RIGHT）的人数num，并找出他们之中过桥时间最长的一个记入ans。- ① 处：判断递归的结束条件。如果留在右岸的人数小于或等于 2 个人，那么他们可以一次性直接过桥，此时花费的时间正是刚才算出的最大时间
ans。所以填num <= 2。- 然后程序通过两层循环遍历所有可能一起过河的 2 个人组合（
i和j）。- 将选中的两人过河，即
pos[i]和pos[j]改为LEFT。- ② 处：此时计算总时间。本次过桥花费的时间是
max(hour[i], hour[j])，因为灯到了左岸，接下来必须有人送回来，所以要加上进入下一次LEFT_TO_RIGHT状态的后续花费，即填go(LEFT_TO_RIGHT)（或者写go(true)也可以）。- 第二段（从左向右送灯
LEFT_TO_RIGHT）：
- 因为只需一个人送灯即可，所以用单层循环遍历所有可以送灯的人。
- ③ 处：判断谁能送灯。这个人必须在左岸，所以条件是
pos[i] == LEFT。- 将选中的这个人送回右岸，即
pos[i] = RIGHT。- ④ 处：计算本次送灯到结束的总时间。本次花费的时间是
hour[i]，然后状态转回从右岸向左过河。填hour[i] + go(RIGHT_TO_LEFT)。- ⑤ 处：回溯的恢复现场操作。上面尝试了将人送回右岸（
pos[i]=RIGHT），试完之后要恢复为原来在左岸的状态，所以填pos[i] = LEFT。