NOIP2011年普及组初赛题目及答案分析

原链接：https://longkui.blog.csdn.net/article/details/149574845 解析时间：2026-08-02T16:45:51+08:00 注：本文档已按要求转为 Markdown 格式，添加多级标题，并将图片通过 PicGo 上传至图床。对部分题目解析进行了扩写和修正，以便于阅读和理解。

一、单项选择题

（共 20 题，每题 1.5 分，共计 30 分。每题有且仅有一个正确选项。）

1、在二进制下，1101001 + （ B ） = 1110110。

A、1011 B、1101 C、1010 D、1111

【解析】 本题考查二进制加减法运算。题目相当于求 1110110 - 1101001。
  1110110
- 1101001
---------
     1101
个位 0-1 借位得 1，十位借位后 0-0=0，百位 1-0=1，千位 0-1 借位得 1。结果为 1101。答案选 B。

2、字符“0”的 ASCII 码为 48，则字符“9”的 ASCII 码为（ B ）。

A、39 B、57 C、120 D、视具体的计算机而定

【解析】 本题考查 ASCII 码基础知识。数字字符的 ASCII 码是连续递增的。因此字符 9 的 ASCII 码 = 字符 0 的 ASCII 码 + 9。即 $48 + 9 = 57$ 。答案选 B。

3、一片容量为 8GB 的 SD 卡能存储大约（ C ）张大小为 2MB 的数码照片。

A、1600 B、2000 C、4000 D、16000

【解析】 本题考查计算机存储容量的换算关系。 1 GB = 1024 MB。 8 GB = $8 \times 1024$ MB = 8192 MB。 8192 MB / 2 MB = 4096（张）。选项中最接近的是 4000 张。答案选 C。

4、摩尔定律（Moore’s law）是由英特尔创始人之一戈登·摩尔（Gordon Moore）提出来的。根据摩尔定律，在过去几十年以及在可预测的未来几年，单块集成电路的集成度大约每（ C ）个月翻一番。

A、1 B、6 C、18 D、36

【解析】 本题考查计算机发展史常识。摩尔定律的核心内容为：集成电路上可以容纳的晶体管数目，大约每经过 18 到 24 个月便会增加一倍，换言之，处理器的性能每隔两年翻一倍。答案选 C。

5、无向完全图是图中每对顶点之间都恰有一条边的简单图。已知无向完全图 G 有 7 个顶点，则它共有（ B ）条边。

A、7 B、21 C、42 D、49

【解析】 本题考查图论基础。所谓无向完全图，即任意两个不同的顶点之间都有一条且仅有一条边相连。含有 $n$ 个顶点的无向完全图的边数公式为： $n (n - 1) /2$ 。相当于从 7 个顶点中任意选 2 个顶点连线的组合数 $C_{7}^{2}$ 。代入 $n = 7$ ，边数为 $7 \times 6/2 = 21$ 。答案选 B。

6、寄存器是（ D ）的重要组成部分。

A、硬盘 B、高速缓存 C、内存 D、中央处理器（CPU）

【解析】 本题考查计算机硬件组成。寄存器（Register）是中央处理器（CPU）内部非常小、非常快的高速存储部件，用于暂存指令、数据和地址。CPU 主要由运算器、控制器和寄存器三部分组成。答案选 D。

7、如果根结点的深度记为 1，则一棵恰有 2011 个叶结点的二叉树的深度最少是（ C ）。

A、10 B、11 C、12 D、13

【解析】 本题考查满二叉树性质。要使二叉树深度最小，则必须尽量填满该二叉树，使其成为一棵完全二叉树。一棵深度为 $k$ 的满二叉树，其叶子节点数刚好为 $2^{k - 1}$ 个。

当深度 $k = 11$ 时，最多能容纳的叶子结点数为 $2^{10} = 1024$ 。这不足 2011 个叶结点。

当深度 $k = 12$ 时，最多能容纳的叶子结点数为 $2^{11} = 2048$ 。2048 大于 2011，刚好可以放下 2011 个叶子节点。因此，深度最少为 12。答案选 C。

8、体育课的铃声响了，同学们都陆续地奔向操场，按老师的要求从高到矮站成一排。每个同学按顺序来到操场时，都从排尾走向排头，找到第一个比自己高的同学，并站在他的后面。这种站队的方法类似于（ B ）算法。

A、快速排序 B、插入排序 C、冒泡排序 D、归并排序

【解析】 本题考查排序算法的模拟场景。

插入排序：核心思想是将一个新元素，插入到前面已经排好序的序列中的合适位置。题干中同学从队伍里找第一个比自己高的人并站在他后面，完美契合插入排序的思想。

冒泡排序：是相邻元素两两比较，不符合“排尾走向排头寻找位置”的特点。

快速排序：用到分治法，选基准值划分。

归并排序：分治后合并。答案选 B。

9、一个正整数在二进制下有 100 位，则它在十六进制下有（ C ）位。

A、7 B、13 C、25 D、不能确定

【解析】 本题考查不同进制间的转换关系。进制转换规律中，因为 $16 = 2^{4}$ ，所以每 4 位二进制数可以精准地转换为 1 位十六进制数。 100 位的二进制数，划分成 4 位一组： $100/4 = 25$ 。因此它在十六进制下正好是 25 位。答案选 C。

10、有人认为，在个人电脑送修前，将文件放入回收站中就是已经将其删除了。这种想法是（ C ）。

A、正确的，将文件放入回收站意味着彻底删除、无法恢复 B、不正确的，只有将回收站清空后，才意味着彻底删除、无法恢复 C、不正确的，即使将回收站清空，文件只是被标记为删除，仍可能通过恢复软件找回 D、不正确的，只要在硬盘上出现过的文件，永远不可能被彻底删除

【解析】 计算机系统中，无论是将文件移至回收站，还是清空回收站甚至格式化硬盘，由于其存储介质的物理特性，这其实只改变了文件在文件系统分配表里的逻辑地址（仅仅标记为可用空间），而文件实质的数据信息依然留存在硬盘的扇区上。只有当这些扇区被新写入的数据覆盖时，原文件才算被彻底破坏。在此之前，都可以使用专业的数据恢复软件进行找回。因此选项 C 正确。为了安全，送修前涉及隐私的区域可以使用专门的文件粉碎机进行多次覆写。

11、广度优先搜索时，需要用到的数据结构是（ B ）。

A、链表 B、队列 C、栈 D、散列表

【解析】 本题考查搜索算法对应的数据结构。

广度优先搜索 (BFS) 采取的是“一层层向外扩展”的遍历方式，遵循“先进先出”的原则，这正好契合队列（Queue）的特点。

深度优先搜索 (DFS) 采取的是“一条路走到黑然后回溯”的遍历方式，遵循“后进先出”的原则，契合栈（Stack）的特点。答案选 B。

12、在使用高级语言编写程序时，一般提到的“空间复杂度”中的“空间”是指（ A ）。

A、程序运行时理论上所占的内存空间 B、程序运行时理论上所占的数组空间 C、程序运行时理论上所占的硬盘空间 D、程序源文件理论上所占的硬盘空间

【解析】 空间复杂度 (Space Complexity) 是对一个算法在运行过程中临时占用**内存（主存）**空间大小的量度。它不包括程序源代码本身存放在硬盘上的大小，也不局限于数组占用的空间，而是理论上所需的各类变量及运行栈等总内存空间的增长趋势。答案选 A。

13、在含有 n 个元素的双向链表中查询是否存在关键字为 k 的元素，最坏情况下运行的时间复杂度是（ C ）。

A、O(1) B、O(log n) C、O(n) D、O(n log n)

【解析】 本题考查链表的查找效率。链表不支持随机访问（像数组那样的通过下标 $O (1)$ 查找），更不支持二分查找。无论是单向链表还是双向链表，要查询一个特定的值，都只能从头（或尾）节点开始挨个遍历对比。最坏的情况下，要查找的元素在链表的最后，或者根本不存在于链表中，此时必须遍历完 $n$ 个元素。因此最坏时间复杂度为 $O (n)$ 。答案选 C。

14、生物特征识别，是利用人体本身的生物特征进行身份认证的一种技术。目前，指纹识别、虹膜识别、人脸识别等技术已广泛应用于政府、银行、安全防卫等领域。以下不属于生物特征识别技术及其应用的是（ C ）。

题目14配图 (图注：A选项指纹锁、B选项人脸闸机、C选项数字密码锁、D选项虹膜/视网膜门禁)

【解析】 题目中的 A 为指纹识别，B 为人脸识别，D 为虹膜识别，均属于人体的生物物理特征。 C 选项为普通的数字密码键盘，依赖的是记忆数字而非生物特征。答案选 C。

15、现有一段文言文，要通过二进制哈夫曼编码进行压缩。简单起见，假设这段文言文只由 4 个汉字“之”、“乎”、“者”、“也”组成，它们出现的次数分别为 700、600、300、200。那么，“也”字的编码长度是（ C ）。

A、1 B、2 C、3 D、4

【解析】 本题考查哈夫曼树（Huffman Tree）的构造过程。构造规则：每次从节点集合中挑选权值（频率）最小的两个节点，将它们合并成一个新节点（权值为两节点之和），直到只剩下一个根节点。初始节点：之(700), 乎(600), 者(300), 也(200)

最小的是 者(300) 和 也(200)，合并为新节点 N1，权值为 500。现在的集合：之(700), 乎(600), N1(500)。

最小的是 乎(600) 和 N1(500)，合并为新节点 N2，权值为 1100。现在的集合：N2(1100), 之(700)。

最后合并 N2(1100) 和 之(700) 形成根节点，权值 1800。

生成的哈夫曼树如下：
graph TD;
    Root(1800) --> 之(700)
    Root --> N2(1100)
    N2 --> 乎(600)
    N2 --> N1(500)
    N1 --> 者(300)
    N1 --> 也(200)
观察树形可知：根节点向下走 1 层到达“之”；走 2 层到达“乎”；走 3 层到达“者”和“也”。哈夫曼编码的长度即节点在树中的深度（层数）。因此“也”字的编码长度是 3。答案选 C。

16、关于汇编语言，下列说法错误的是（ D ）。

A、是一种与具体硬件相关的程序设计语言 B、在编写复杂程序时，相对于高级语言而言代码量较大，且不易调试 C、可以直接访问寄存器、内存单元、以及 I/O 端口 D、随着高级语言的诞生，如今已完全被淘汰，不再使用

【解析】 汇编语言（Assembly Language）是与具体 CPU 指令集一一对应的底层语言，具有直接控制硬件、访问寄存器、执行效率极高的特点，但可读性和可移植性差。虽然目前大多数应用软件都使用高级语言开发，但在某些对性能要求极高、与底层硬件密切交互的领域（如操作系统内核、底层驱动、嵌入式单片机、破解逆向分析），汇编语言依然有着不可替代的地位，并未被淘汰。答案选 D。

17、（ A ）是一种选优搜索法，按选优条件向前搜索，以达到目标。当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择。

A、回溯法 B、枚举法 C、动态规划 D、贪心法

【解析】 本题考查常见算法思想的概念。

回溯法：按选优条件向前搜索，走不通就退回一步重新尝试，这种“试错”并“退回”的机制正是回溯的核心。

枚举法：又称暴力法，是对所有可能的情况进行一一列举，没有“选优探索”和“退回”的过程。

动态规划：将问题分解为重叠子问题，利用历史状态推导当前状态全局最优解。

贪心法：每一步总是做出在当前看来最好的选择，从而期望导致全局最优，但贪心法不回退，选定就不改了。答案选 A。

18、1956 年（ A ）授予肖克利（William Shockley）、巴丁（John Bardeen）和布拉顿（Walter Brattain），以表彰他们对半导体的研究和晶体管效应的发现。

A、诺贝尔物理学奖 B、约翰·冯·诺依曼奖 C、图灵奖 D、高德纳奖（Donald E. Knuth Prize）

【解析】 本题考查计算机相关的科技常识。对半导体及晶体管的发明属于底层物理元器件的重大突破，因此授予的是诺贝尔物理学奖。这项发明为日后计算机的微型化（取代电子管）奠定了基础。（注：图灵奖才是针对计算机科学理论贡献的最高奖项。）答案选 A。

19、对一个有向图而言，如果每个节点都存在到达其他任何节点的路径，那么就称它是强连通的。例如，右图就是一个强连通图。事实上，在删掉边（ A ）后，它依然是强连通的。

题目19配图 (图注：节点1向节点2,3,4有有向边；节点2,3,4向其它节点有有向边形成环路。) A、a B、b C、c D、d

【解析】 本题考查有向图的连通性。强连通意味着任意两个点相互之间都有通路可达。观察右图（由选项和拓扑结构推断），判断某条边删除后是否还能保证整个图存在环覆盖所有的点。我们可以逐个尝试：

边 b 可能是某个单一回路的关键路径，删除后会导致节点不可逆回。

实际上只有删掉含有多余并行通路的边 a 后，网络其余部分（如外部的大环和内部的其他回路）依然能够使各个顶点相互抵达。答案选 A。

20、从 ENIAC 到当前最先进的计算机，冯·诺依曼体系结构始终占有重要的地位。冯·诺依曼体系结构的核心内容是（ C ）。

A、采用开关电路 B、采用半导体器件 C、采用存储程序和程序控制原理 D、采用键盘输入

【解析】 冯·诺依曼体系结构的最根本标志是提出了**“存储程序”和“程序控制”**的思想。即把执行的指令序列和数据都存储在存储器中，CPU 按顺序从存储器取出指令并执行，这是现代计算机运行的基石。答案选 C。

二、问题求解

（共 2 题，每题 5 分，共计 10 分）

1、每份考卷都有一个 8 位二进制序列号。当且仅当一个序列号含有偶数个 1 时，它才是有效的。例如，00000000、01010011 都是有效的序列号，而 11111110 不是。那么，有效的序列号共有________个。

【答案】 128

【解析】 这是一个排列组合与二进制位校验的问题（类似于奇偶校验）。一共 8 位二进制数，要求里面包含的 1 的个数必须为偶数。我们可以先自由决定前 7 位的数字。前 7 位每一位都有 0 和 1 两种选择，所以前 7 位的组合共有 $2^{7} = 128$ 种可能。当这 128 种组合中的任意一种确定之后，由于整体 8 位必须有偶数个 1，这也就意味着：

如果前 7 位里含有偶数个 1，那么最后第 8 位只能填 0，以维持偶数状态。

如果前 7 位里含有奇数个 1，那么最后第 8 位只能填 1，加上这个 1 就凑成了偶数状态。

这说明，一旦前 7 位确定，第 8 位是唯一确定的，别无选择。故有效序列号的总数等同于前 7 位的可能数，即 $2^{7} = 128$ 个。

2、定义字符串的基本操作为：删除一个字符、插入一个字符和将一个字符修改成另一个字符这三种操作。将字符串 A 变成字符串 B 的最少操作步数，称为字符串 A 到字符串 B 的编辑距离。字符串”ABCDEFG”到字符串”BADECG”的编辑距离为________。

【答案】 3

【解析】 本题实际上是在求字符串的最短编辑距离（Levenshtein distance），可以通过动态规划求解，也可以通过手动观察规律：源串 A：A B C D E F G 目标 B：B A D E C G

我们可以这样手工转换以达到最少操作步数：

第一步：将 A 中的字符 A 删除，源串变为 BCDEFG。

第二步：在开头插入字符 B 以及修改？不，题目是求变成 BADECG。重新观察发现保留最大的公共子序列可以极大减少步数。长公共部分：B C D E 中含有 B D E G 等等。操作过程：源串：A B C D E F G

删除 A $\to$ B C D E F G

将 C 修改为 A $\to$ B A D E F G

将 F 修改为 C $\to$ B A D E C G

总共用时 3 步（1次删除，2次修改）。由于两字符串差异较大，不可能在 2 步内完成。所以编辑距离为 3。

三、阅读程序写结果

（共 4 题，每题 8 分，共计 32 分）

1、累加问题

#include <iostream>
using namespace std;
int main() {
    int i, n, m, ans;
    cin >> n >> m;
    i = n;
    ans = 0;
    while(i <= m) {
        ans += i;
        i++;
    }
    cout << ans << endl;
    return 0;
}

输入：10 20 输出：__________________

【答案】 165

【解析】 题目的核心逻辑是一个 while(i <= m) 循环，执行 ans += i。这其实是在计算从 $n$ 连加到 $m$ 的等差数列求和。输入 $n = 10, m = 20$ ，程序计算的是 $10 + 11 + 12 + \dots + 20$ 的和。等差数列求和公式： $S = (首项 + 末项) \times 项数 /2$ 项数 $= 20 - 10 + 1 = 11$ 项。 $S = (10 + 20) \times 11/2 = 30 \times 11/2 = 165$ 。所以输出为 165。

2、字符映射替换

#include <iostream>
#include <string>
using namespace std;
int main() {
    string map = "22233344455566677778889999";
    string tel;
    int i;
    cin>>tel;
    for(i = 0; i < tel.length(); i++)
        if((tel[i] >= '0') && (tel[i] <= '9'))
            cout << tel[i];
        else if((tel[i] >= 'A') && (tel[i] <= 'Z'))
            cout << map[tel[i] - 'A'];
    cout << endl;
    return 0;
}

输入：CCF-NOIP-2011 输出：__________________

【答案】 22366472011

【解析】 这个程序的作用是把包含大写字母的电话号码，根据传统的九宫格手机按键，将其转换为纯数字号码。

字符串 map 是字母 A 到 Z 对应的数字映射表。

for 循环遍历输入字符串 tel 的每个字符：

如果是数字 '0'-'9'，原样输出。

如果是大写字母 'A'-'Z'，将字符减去基准 'A' 得到索引（0到25），然后在 map 字符串中查表替换输出。

如果是其他符号（比如 - 减号），则忽略不输出（因为只有两个 if 条件，不满足的字符就被略过了）。

手工映射 CCF-NOIP-2011： C -> ‘C’-‘A’ = 2 -> map[2]是 '2' C -> '2' F -> ‘F’-‘A’ = 5 -> map[5]是 '3' - -> 被忽略 N -> ‘N’-‘A’ = 13 -> map[13]是 '6' O -> ‘O’-‘A’ = 14 -> map[14]是 '6' I -> ‘I’-‘A’ = 8 -> map[8]是 '4' P -> ‘P’-‘A’ = 15 -> map[15]是 '7' - -> 被忽略 2011 -> 数字原样输出 '2011'

最终拼接起来输出：22366472011。

3、计数排序与累加中值

#include <iostream>
#include <cstring>
using namespace std;
const int SIZE = 100;
int main() {
    int n, i, sum, x, a[SIZE];
    cin >> n;
    memset(a, 0, sizeof(a));
    for(i = 1; i <= n; i++) {
        cin >> x;
        a[x]++;
    }
    i = 0;
    sum = 0;
    while(sum < (n / 2 + 1)) {
        i++;
        sum += a[i];
    }
    cout << i << endl;
    return 0;
}

输入： 11 4 5 6 6 4 3 3 2 3 2 1 输出：__________________

【答案】 3

【解析】

程序的第一部分：memset 初始化数组 a 为 0。接着利用 for 循环不断读入数字 x 并执行 a[x]++。这就是典型的桶排序（计数排序），用于统计每个数字出现的频率。根据输入数据，各个数字的频率如下：

1 出现 1 次 $\Rightarrow a [1] = 1$

2 出现 2 次 $\Rightarrow a [2] = 2$

3 出现 3 次 $\Rightarrow a [3] = 3$

4 出现 2 次 $\Rightarrow a [4] = 2$

5 出现 1 次 $\Rightarrow a [5] = 1$

6 出现 2 次 $\Rightarrow a [6] = 2$

程序的第二部分：计算阈值 n / 2 + 1。本例中 $n = 11$ ，所以 $11/2 + 1 = 5 + 1 = 6$ 。

然后用 while(sum < 6) 循环从小到大累加 a[i] 的频数。这实际上是在求输入序列排序后的中位数（因为 $n = 11$ ，排序后第 6 个元素即为中位数）。

初始 sum = 0, i = 0

i = 1, sum += a[1] = 1。(sum = 1 < 6)

i = 2, sum += a[2] = 2，即 $1 + 2 = 3$ 。(sum = 3 < 6)

i = 3, sum += a[3] = 3，即 $3 + 3 = 6$ 。此时 sum = 6，条件 < 6 不再成立，循环结束。

最终输出 i，即 3。

4、组合递归问题

#include <iostream>
using namespace std;
 
int solve(int n, int m) {
    int i, sum;
    if (m == 1)
        return 1;
    sum = 0;
    for (i = 1; i < n; i++)
        sum += solve(i, m - 1);
    return sum;
}
int main() {
    int n, m;
    cin>>n>>m;
    cout<<solve(n, m)<<endl;
    return 0;
}

输入：7 4 输出：__________________

【答案】 20

【解析】 该递归函数的递推式为： $f (n, m) = \sum_{i = 1}^{n - 1} f (i, m - 1)$ ，当 $m = 1$ 时 $f (n, 1) = 1$ 。事实上，这个函数的数学背景是组合数：从 $n - 1$ 个间隙中挑出 $m - 1$ 个切割点，即求组合数 $C_{n - 1}^{m - 1}$ 。我们可以使用动态规划二维打表的形式一步步推演：

m=1 m=2 m=3 m=4
n=1 1 0 0 0
n=2 1 1 0 0
n=3 1 2 1 0
n=4 1 3 3 1
n=5 1 4 6 4
n=6 1 5 10 10
n=7 1 6 15 20

这是经典的杨辉三角变形。题目要求求 solve(7, 4) 的值。根据推导，m=4 这一列的值其实是由 m=3 这一列的累加和构成的。当 $n = 7, m = 4$ 时，结果为 20。所以输出 20。

	m=1	m=2	m=3	m=4
n=1	1	0	0	0
n=2	1	1	0	0
n=3	1	2	1	0
n=4	1	3	3	1
n=5	1	4	6	4
n=6	1	5	10	10
n=7	1	6	15	20

四、完善程序

（前 11 空，每空 2 分，后 2 空，每空 3 分，共计 28 分）

1、（子矩阵）

输入一个 n1*m1 的矩阵 a，和 n2*m2 的矩阵 b，问 a 中是否存在子矩阵和 b 相等。若存在，输出所有子矩阵左上角的坐标；若不存在输出 “There is no answer”。

#include <iostream>
using namespace std;
const int SIZE = 50;
int n1, m1, n2, m2, a[SIZE][SIZE], b[SIZE][SIZE];
 
int main() {
    int i, j, k1, k2;
    bool good, haveAns;
 
    cin >> n1 >> m1;
    for(i = 1; i <= n1; i++)
        for(j = 1; j <= m1; j++)
            cin >> a[i][j];  //输入a数组
            
    cin >> n2 >> m2;
    for(i = 1; i <= n2; i++)
        for(j = 1; j <= m2; j++)
            ____①____;
 
    haveAns = false;
    for(i = 1; i <= n1 - n2 + 1; i++)
        for(j = 1; j <= ____②____; j++) {
            ____③____;
            for(k1 = 1; k1 <= n2; k1++)
                for(k2 = 1; k2 <= ____④____; k2++) {
                    if(a[i + k1 - 1][j + k2 - 1] != b[k1][k2])
                        good = false;
                }
            if(good) {
                cout << i << ' ' << j << endl;
                ____⑤____;
            }
        }
 
    if(!haveAns)
        cout << "There is no answer" << endl;
    return 0;
}

【答案】 ① cin >> b[i][j] ② m1 - m2 + 1 ③ good = true ④ m2 ⑤ haveAns = true

【解析】 这是典型的暴力匹配二维模式串（子矩阵）的算法。

①处：观察上方输入 $a$ 矩阵的代码，此处也是双重循环嵌套，变量是针对 $n 2$ 和 $m 2$ 的。理所当然，这里是为了读入 $b$ 矩阵的元素。所以填 cin >> b[i][j]。

②处：主循环的作用是枚举 $a$ 矩阵中可能的各个“左上角坐标”。对于行 $i$ ，其起点最多只能到 $n 1 - n 2 + 1$ 否则剩余行数就不够容纳 $b$ 矩阵了。同理，对于列 $j$ ，其起点最多只能枚举到 $m 1 - m 2 + 1$ 。所以填 m1 - m2 + 1。

③处：在开始每一轮内部的子矩阵验证循环（k1, k2）之前，必须设定一个初始状态。且内部若有元素不匹配，则置 good = false。因此这里需要先假设能匹配上，即初始化 good = true。

④处：内层循环用于比对子矩阵。行是从 $k 1 = 1$ 循环到 $n 2$ 。列理应从 $k 2 = 1$ 循环到 $b$ 矩阵的列数 $m 2$ 。因此填 m2。

⑤处：一旦发现 good 仍为真，说明成功找到了相等的子矩阵，并打印坐标。为了程序末尾判断是否打印过答案，此时必须将代表有无答案的布尔变量 haveAns 标记为真。所以填 haveAns = true。

2、（大整数开方）

输入一个正整数 n（1≤n＜10

#include <iostream>
#include <string>
#include <cstring>
using namespace std;
 
const int SIZE = 200;
struct hugeint {
    int len, num[SIZE];
};
//其中 len 表示大整数的位数；num[1]表示个位、num[2]表示十位，以此类推
 
hugeint times(hugeint a, hugeint b)
//计算大整数 a 和 b 的乘积
{
    int i, j;
    hugeint ans;
    memset(ans.num, 0, sizeof(ans.num));
    for(i = 1; i <= a.len; i++)
        for(j = 1; j <= b.len; j++)
            _____①_____ +=  a.num[i]  * b.num[j];
 
    for(i = 1; i <= a.len + b.len; i++) {
        ans.num[i + 1] += ans.num[i] / 10;
        _____②_____;
    }
    if(ans.num[a.len + b.len] > 0)
        ans.len = a.len + b.len;
    else
        ans.len = a.len + b.len - 1;
    return ans;
}
 
hugeint add(hugeint a, hugeint b)
//计算大整数 a 和 b 的和
{
    int i;
    hugeint ans;
    memset(ans.num, 0, sizeof(ans.num));
    if(a.len > b.len)
        ans.len = a.len;
    else
        ans.len = b.len;
    for(i = 1; i <= ans.len; i++) {
        ans.num[i] += _____③_____;
        ans.num[i + 1] += ans.num[i] / 10;
        ans.num[i] %= 10;
    }
    if(ans.num[ans.len + 1] > 0)
        ans.len++;
    return ans;
}
 
hugeint average(hugeint a, hugeint b)
//计算大整数 a 和 b 的平均数的整数部分
{
    int i;
    hugeint ans;
    ans = add(a, b);
    for(i = ans.len; i >= 2; i--) {
        ans.num[i - 1] += (_____④_____) * 10;
        ans.num[i] /= 2;
    }
    ans.num[1] /= 2;
    if(ans.num[ans.len] == 0)
        ans.len--;
    return ans;
}
 
hugeint plustwo(hugeint a)
//计算大整数 a 加 2 后的结果
{
    int i;
    hugeint ans;
    ans = a;
    ans.num[1] += 2;
    i = 1;
    while((i <= ans.len) && (ans.num[i] >= 10)) {
        ans.num[i + 1] += ans.num[i] / 10;
        ans.num[i] %= 10;
        i++;
    }
    if(ans.num[ans.len + 1] > 0)
        _____⑤_____;
    return ans;
}
 
bool over(hugeint a, hugeint b)
//若大整数 a>b 则返回 true，否则返回 false
{
    int i;
    if(_____⑥_____)
        return false;
    if(a.len > b.len)
        return true;
    for(i = a.len; i >= 1; i--) {
        if(a.num[i] < b.num[i])
            return false;
        if(a.num[i] > b.num[i])
            return true;
    }
    return false;
}
 
int main() {
    string s;
    int i;
    hugeint target, left, middle, right;
    cin >> s;
    memset(target.num, 0, sizeof(target.num));
    target.len = s.length();
    for(i = 1; i <= target.len; i++)
        target.num[i] = s[target.len  - i] - _____⑦_____;
    
    memset(left.num, 0, sizeof(left.num));
    left.len = 1;
    left.num[1] = 1;
    right = target;
    do {
        middle = average(left, right);
        if(over(_____⑧_____))
            right = middle;
        else
            left = middle;
    } while(!over(plustwo(left), right));
 
    for(i = left.len; i >= 1; i--)
        cout << left.num[i];
    cout << endl;
    return 0;
}

【答案】 ① ans.num[i + j - 1] ② ans.num[i] %= 10 ③ a.num[i] + b.num[i] ④ ans.num[i] % 2 ⑤ ans.len++ ⑥ a.len < b.len ⑦ '0' ⑧ times(middle, middle), target

【解析】 这道题实现了一个完整的高精度算法加二分求解开平方。对于不熟悉高精度数组乘法原理的初学者稍微有一定难度，但能根据函数意图逐步推理。

①处（高精度乘法）：大整数的乘法 a * b 中，a 的第 i 位和 b 的第 j 位相乘，得到的结果应累加到答案 ans 的第 i+j-1 位上（因为个位索引为1，所以是 $i + j - 1$ 而不是 $i + j$ ）。因此填 ans.num[i + j - 1]。

②处（处理进位）：上一句执行了高位进位 ans.num[i+1] += ans.num[i] / 10;，于是当前位必须要保留向 10 取余后的数字（也就是剔除进上去的数）。故填 ans.num[i] %= 10。

③处（高精度加法）：在 add(a, b) 函数中，我们要把 a 和 b 的对应位相加累加给答案。因此填 a.num[i] + b.num[i]。

④处（高精度除以 2）：average(a,b) 里面，首先让 ans = add(a,b)。由于要求平均数，接下来要把 ans 整体除以 2。高精度除法是从高位开始往低位除的，第 i 位的数除以 2 会有余数，这个余数将做为进位留给低一位，也就是下一位 i-1 位的值要加上当前余数乘以 10。因此求当前位的余数应填 ans.num[i] % 2。

⑤处（高精度加 2 进位）：在 plustwo 加法中，如果最高位的下一位进位值大于0，说明数字位数增加了。那么此时需要将大数的长度 ans.len 增加一。因此填 ans.len++。

⑥处（高精度比较大小）：在判断 a > b 的 over 函数中，如果 a 的位数大于 b，立刻返回真。对应的，如果 a 的位数严格小于 b 的位数，说明 a 绝对比 b 小，不可能大于，因此应返回 false。填 a.len < b.len。

⑦处（字符串转整数）：在 main 函数读取时，因为输入是大整数字符串，要把字符转换为真正的数字，需要减去字符 '0' 的 ASCII 码值。填 '0'。

⑧处（二分核心判断）：题目求 n 的平方根，即寻找一个 middle 使得其平方最接近 target。二分法不断利用中间值 middle 验证：若 middle 的平方比 target 大，那么要收缩上限 right = middle；否则抬高下限 left = middle。判断条件自然是比较 middle * middle 与 target。而本程序中实现了乘法函数 times(a, b) 和比较函数 over，所以调用应为 over(times(middle, middle), target)。填 times(middle, middle), target。

教学知识库

探索

NOIP2011年普及组初赛题目及答案分析

NOIP2011年普及组初赛题目及答案分析

一、单项选择题

1、在二进制下，1101001 + （ B ） = 1110110。

2、字符“0”的 ASCII 码为 48，则字符“9”的 ASCII 码为（ B ）。

3、一片容量为 8GB 的 SD 卡能存储大约（ C ）张大小为 2MB 的数码照片。

4、摩尔定律（Moore’s law）是由英特尔创始人之一戈登·摩尔（Gordon Moore）提出来的。根据摩尔定律，在过去几十年以及在可预测的未来几年，单块集成电路的集成度大约每（ C ）个月翻一番。

5、无向完全图是图中每对顶点之间都恰有一条边的简单图。已知无向完全图 G 有 7 个顶点，则它共有（ B ）条边。

6、寄存器是（ D ）的重要组成部分。

7、如果根结点的深度记为 1，则一棵恰有 2011 个叶结点的二叉树的深度最少是（ C ）。

8、体育课的铃声响了，同学们都陆续地奔向操场，按老师的要求从高到矮站成一排。每个同学按顺序来到操场时，都从排尾走向排头，找到第一个比自己高的同学，并站在他的后面。这种站队的方法类似于（ B ）算法。

9、一个正整数在二进制下有 100 位，则它在十六进制下有（ C ）位。

10、有人认为，在个人电脑送修前，将文件放入回收站中就是已经将其删除了。这种想法是（ C ）。

11、广度优先搜索时，需要用到的数据结构是（ B ）。

12、在使用高级语言编写程序时，一般提到的“空间复杂度”中的“空间”是指（ A ）。

13、在含有 n 个元素的双向链表中查询是否存在关键字为 k 的元素，最坏情况下运行的时间复杂度是（ C ）。

14、生物特征识别，是利用人体本身的生物特征进行身份认证的一种技术。目前，指纹识别、虹膜识别、人脸识别等技术已广泛应用于政府、银行、安全防卫等领域。以下不属于生物特征识别技术及其应用的是（ C ）。

15、现有一段文言文，要通过二进制哈夫曼编码进行压缩。简单起见，假设这段文言文只由 4 个汉字“之”、“乎”、“者”、“也”组成，它们出现的次数分别为 700、600、300、200。那么，“也”字的编码长度是（ C ）。

16、关于汇编语言，下列说法错误的是（ D ）。

17、（ A ）是一种选优搜索法，按选优条件向前搜索，以达到目标。当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择。

18、1956 年（ A ）授予肖克利（William Shockley）、巴丁（John Bardeen）和布拉顿（Walter Brattain），以表彰他们对半导体的研究和晶体管效应的发现。

19、对一个有向图而言，如果每个节点都存在到达其他任何节点的路径，那么就称它是强连通的。例如，右图就是一个强连通图。事实上，在删掉边（ A ）后，它依然是强连通的。

20、从 ENIAC 到当前最先进的计算机，冯·诺依曼体系结构始终占有重要的地位。冯·诺依曼体系结构的核心内容是（ C ）。

二、问题求解

1、每份考卷都有一个 8 位二进制序列号。当且仅当一个序列号含有偶数个 1 时，它才是有效的。例如，00000000、01010011 都是有效的序列号，而 11111110 不是。那么，有效的序列号共有________个。

三、阅读程序写结果

1、累加问题

2、字符映射替换

3、计数排序与累加中值

4、组合递归问题

四、完善程序

1、（子矩阵）

2、（大整数开方）

关系图谱

目录