NOIP-2013-普及组初赛试题及解析

0.1 NOIP 2013 普及组初赛试题及解析

原创 已于2025-04-23 20:12:57 修改 1.4k 阅读 · 白 6 · 代 0GEO检测

NOIP 2013 普及组初赛试题及解析

一. 单项选择题(共20题，每题1.5分，共计30分。每题有且仅有一个正确答案.)。

二. 问题求解 (共2题，每题5分，共计10分; 每题全部答对得5分，没有部分分)

三. 阅读程序写结果 (共4题，每题8分，共计32分)

四. 完善程序 (共 2 题, 每题 14 分, 共计 28 分)

0.2 一. 单项选择题(共20题，每题1.5分，共计30分。每题有且仅有一个正确答案.)。

0.3 1、一个32 位整型变量占用( )个字节

cpp AI写代码

A. 4

B. 8

C. 32

D. 128

正确答案:A

一个32位整型变量占用的字节数是4个字节。

因为在大多数现代计算机系统中:

一个字节 (byte) = 8位 (bit)

所以，32位 (bit) 等于4字节 (byte) 。

0.4 2、二进制数 11.01 在十进制下是( )

cpp

A. 3.25

B.4.125

C. 6.25

D. 11.125

正确答案:A

整数部分:

11 在二进制下转换为十进制是 $1\ast 2^1+1\ast 2^0=2+1=3$

小数部分:

01 在二进制下转换为十进制是 $0\ast 2^{-1}+1\ast 2^{-2}=0+0.25=0.25$

将整数部分和小数部分相加，得到 11.01(二进制)等于 3.25(十进制)。

3、下面的故事与( )算法有着异曲同工之妙。 从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事:“从前有座山，山里有座庙，庙里有个给小和尚讲故事:‘从前有座山，山里有座庙，庙里有个老和尚给小和尚讲故事……’”

cpp AI写代码

A. 枚举

B. 递归

C. 贪心

D. 分治

NOIP 2013 普及组初赛试题及解析

正确答案:B

这个故事描述了一个无限递归的情景。老和尚不断给小和尚讲述同一个故事，而这个故事本身又包含了老和尚给小和尚讲故事的部分，形成了嵌套与递归算法的概念相似，递归算法是指函数调用自身来解决问题，通常用于解决可以分解为更小规模的相同问题的场景。因此，这个故事与递归算曲同工之妙。

递归算法的特点是有一个明确的终止条件，否则递归将无限进行下去。在这个故事中，如果老和尚永远不停下来，故事就会无限重复。然而，在实法中，必须确保存在一个终止条件来避免无限递归。

0.5 4、逻辑表达式( )的值与变量 A 的真假无关

cpp

A. $\left(A\vee B\right)\wedge \to A$

B. $\left(A\vee B\right)\wedge \neg B$

C. $\left(A\wedge B\right)\vee \left(\neg A\wedge B\right)$

D. $\left(A\vee B\right)\wedge =A\wedge B$

正确答案:C

A选项: $\left(A\vee B\right)\wedge \neg A$

如果A为真，那么A v B也为真，但¬A为假。所以整个表达式为假。

如果A为假，那么A、B的值取决于B，而¬A为真。因此，整个表达式的值也取决于B。

B选项: $\left(A\vee B\right)\wedge \neg B$

如果A为真，那么A v B也为真，但¬B的值取决于B。因此，整个表达式的值取决于B。

如果A为假，那么A v B的值取决于B，而¬B为假。所以整个表达式为假。

C选项: $\left(A\wedge B\right)\vee \left(\neg A\wedge B\right)$

无论A是真还是假，只要B为真，整个表达式就为真。如果B为假，则整个表达式为假。这个表达式的值完全取决于B，而与A无关。

D选项: $\left(A\vee B\right)\wedge \neg A\wedge B$

这个表达式包含 $\neg A$ 和 $B$ ，因此它的值取决于A和B的值。

5、将{2,6,10,17}分别存储到某个地址区间为0~10的哈希表中，如果哈希函数h(x)=( ),将不会产生冲突，其中a mod b 表示a除以b的余数

A.xmod11

B. $x^2\mathrm{mod}11$

C. $\left(2x\right)\mathrm{mod}11$

D. $\lfloor \sqrt{}x\rfloor \mathrm{mod}11$ ，其中 $\lfloor \sqrt{}x\rfloor$ 表示 $\sqrt{}x$ 下取整

正确答案:D

首先，我们来分析每个选项:

A. $\mathrm{x}$ mod 11

对于 $2,h\left(2\right)=2\mathrm{mod}11=2$

对于 $6,h\left(6\right)=6\mathrm{mod}11=6$

对于10, h(10) = 10 mod 11 = 10

对于17, h(17) = 17 mod 11 = 6 (冲突，因为6已经映射到地址6)

由于17和6映射到相同的地址6，所以选项A不正确。

B. $x^{\wedge }2\mathrm{mod}11$

对于 $2,h\left(2\right)=2^{\wedge }2\mathrm{mod}11=4$

对于 $6,h\left(6\right)=6^{\wedge }2\mathrm{mod}11=36\mathrm{mod}11=3$

对于10, h(10) = 10^2 mod 11 = 100 mod 11 = 10

对于17, h(17) = 17^2 mod 11 = 289 mod 11 = 10 (冲突，因为10已经映射到地址10)

由于17和10映射到相同的地址10，所以选项B不正确。

C. (2x) mod 11

对于2, h(2) = (22) mod 11 = 4

对于6, h(6) = (26) mod 11 = 12 mod 11 = 1

对于10, h(10) = (210) mod 11 = 20 mod 11 = 9

对于17, $h\left(17\right)=\left(217\right)\mathrm{mod}11=34\mathrm{mod}11=1$ (冲突,因为6已经映射到地址1)

由于17和6映射到相同的地址1，所以选项C不正确。

D. $\left|\sqrt{x}\right|\mathrm{mod}11$

对于 $2,h\left(2\right)=\left[\sqrt{2}\right]\mathrm{mod}11=1\mathrm{mod}11=1$

对于 $6,h\left(6\right)=\lfloor \sqrt{6}\rfloor \mathrm{mod}11=2\mathrm{mod}11=2$

对于10, $h\left(10\right)=\lfloor \sqrt{}10\rfloor \mathrm{mod}11=3\mathrm{mod}11=3$

对于 17, $h\left(17\right)=\lfloor \sqrt{17}\rfloor \mathrm{mod}11=4\mathrm{mod}11=4$

在这种情况下，每个元素都映射到一个唯一的地址，所以选项D是正确的。

6、在十六进制表示法中，字母 A 相当于十进制中的 ( )

cpp

A. 9

B. 10

C. 15

D. 16

正确答案:B

在十六进制(hexadecimal)表示法中，字母A到F用来表示10到15的十进制数值。具体来说，A代表10，B代表11，C代表12，D代表13，E代表1 表15。

0.6 7、下图中所使用的数据结构是()

cpp

A. 哈希表

B. 栈

C. 队列

D. 二叉树

正确答案:B

A选项: 是一种使用哈希函数组织数据的数据结构，它提供快速的插入、删除和查找操作。

B选项: 是一种后进先出(LIFO)的数据结构，它只允许在栈顶进行插入和删除操作。

C选项: 是一种先进先出 (FIFO) 的数据结构，它允许在队列的开头插入元素，在队列的末尾删除元素。

D选项: 是一种树形数据结构，其中每个节点最多有两个子节点。

8、在 Windows 资源管理器中，用鼠标右键单击一个文件时，会出现一个名为“复制”的操作选项，它的意思是( )

cpp

A. 用剪切板中的文件替换该文件

B. 在该文件所在文件夹中, 将该文件克隆一份

C. 将该文件复制到剪切板，并保留原文件

D. 将该文件复制到剪切板，并删除原文件

正确答案:C

复制的意思是将该文件的内容复制到剪贴板中，但不删除或移动原文件。这意味着原文件保持不变，只是在剪贴板中创建了一个该文件的副本。 A选项: 这实际上是“粘贴”操作的效果，不是“复制”。

B选项: 这实际上是创建了文件的一个副本，但“复制”操作并不直接在当前文件夹中创建副本。

C选项: 这正是“复制”操作的意思。

D选项: 这是“剪切”或“移动”操作的效果，不是“复制”。

0.7 9、已知一棵二叉树有 10 个节点，则其中至多有( )个节点有2 个子节点

cpp	AI写代码
A. 4
B. 5
C. 6
D. 7

正确答案:A

在二叉树中，每个节点最多有两个子节点:左子节点和右子节点。但是，不是每个节点都必须有两个子节点。一个节点可以是叶节点(没有子节点以是只有一个子节点的节点。

考虑一个满二叉树的情况，即每个节点都有两个子节点，这样的二叉树会有 2^n - 1 个节点，其中 n 是树的层数。为了得到一个有 10 个节点的二

about:blank

2026/8/2 18:44 NOIP 2013 普及组初赛试题及解析

不可能是一个满二叉树，因为最接近 10 的 2 的幂次方减 1 是 7 (即 $2^{\wedge }3-1=7$ )。

现在，考虑一个只有 4 层(从根开始计数)的二叉树，其最大节点数为 2^4 - 1 = 15。如果我们从这样一个满二叉树中移除尽可能多的叶节点和只节点的节点，以便让更多的节点有两个子节点，我们可以这样做:

移除底层的所有叶节点，直到只剩下 10 个节点。

在这些剩下的节点中，尽可能让节点有两个子节点。

由于我们是从一个满二叉树开始的，移除叶节点和只有一个子节点的节点后，剩下的每个节点都将有两个子节点。因此，在一个有 10 个节点的二至多有 4 个节点有两个子节点。

10、在一个无向图中，如果任意两点之间都存在路径相连，则称其为连通图。下图是一个有 4 个顶点、6 条边的连通图。若要使它不再是连通图，至中的( )条边

CSDN @青岛少儿编程-王老师

cpp

A. 1

B. 2

C. 3

D. 4

正确答案:C

这是一个无向图，每个点都能到达其他任意一个点，则要使它不是连通图，则需要把一个点孤立在外，就需要删除3条边即可，故选C

0.8 11、二叉树的()第一个访问的节点是根节点

cpp

A. 先序遍历

B. 中序遍历

C. 后序遍历

D. 以上都是

正确答案:A

先根/序 (Preorder Traversal) 遍历:根结点、左子树、右子树。

中根/序 (Inorder Traversal) 遍历:左子树，根结点，右子树。

后跟/序 (Postorder Traversal) 遍历:左子树，右子树，根结点。

12、以A0作为起点，对下面的无向图进行深度优先遍历时，遍历顺序不可能是( )

cpp

A.A0, A1, A2, A3

B.A0, A1, A3, A2

C.A0, A2, A1, A3

D.A0, A3, A1, A2

正确答案:A

既然是深度优先遍历，就要一直访问到一个节点最后一层，则A是错的，A为广搜

0.9 13、IPv4 协议使用 32 位地址，随着其不断被分配，地址资源日趋枯竭。因此，它正逐渐被使用 ( ) 位地址的 IPv6 协议所取代

cpp

A. 40

B. 48

C. 64

D. 128

正确答案:D

IPv4(Internet Protocol version 4)确实使用32位地址，这提供了大约43亿个唯一地址。然而，随着互联网的爆炸性增长和物联网(IoT)的快速； 些地址已经变得非常稀缺。

IPv6(Internet Protocol version 6)是为了解决IPv4地址耗尽的问题而设计的。IPv6使用128位地址，这提供了大约3.4 $\times {10}^{38}$ 个唯一地址，从而展了地址空间，满足了未来互联网发展的需求。

0.10 ()的平均时间复杂度为 O(nlogn)，其中 n 是待排序的元素个数

cpp AI写代码

A. 快速排序

B. 插入排序

C. 冒泡排序

D. 基数排序

正确答案:A

在各种经典排序算法中，平均时间复杂度为 O(nlogn) 的算法是:

A. 快速排序 (Quick Sort)

快速排序是一种分而治之的排序算法，它通过一个分割操作将数组分为两个子数组，然后对这两个子数组递归地进行排序。在平均情况下，快速排复杂度为 O(nlogn)，其中 n 是待排序的元素个数。然而，在最坏情况下，当输入数组已经有序或逆序时，快速排序的时间复杂度会退化到 O(n^2) B. 插入排序 (Insertion Sort)

about:blank

2026/8/2 18:44 NOIP 2013 普及组初赛试题及解析

插入排序的时间复杂度在最坏和平均情况下都是 O(n^2)。它逐个将元素插入到已排序的部分中，因此其性能不如快速排序等 O(nlogn) 的算法。 C. 冒泡排序 (Bubble Sort)

‘冒泡排序的时间复杂度在最坏和平均情况下也是 O(n^2)。它重复地遍历待排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过3 数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

D. 基数排序 (Radix Sort)

基数排序的时间复杂度通常是 O(nk)，其中 n 是待排序的元素个数，k 是元素的最大位数。虽然基数排序在某些情况下可以非常高效，但它的时间不是 O(nlogn)。

15、下面是根据欧几里得算法编写的函数，它所计算的是a 和 b的()

cpp

int euclid(int a, int b){

if (b == 0)

return a;

return euclid(b, a % b);

}

cpp

A. 最大公共质因子

B. 最小公共质因子

C. 最大公约数

D. 最小公倍数

正确答案:C

欧几里得算法(也称为辗转相除法)是一个用于计算两个整数的最大公约数(GCD)的经典算法。给定的函数 euclid 正是根据这个算法编写的。 这个算法的基本思想是:对于给定的两个整数 a 和 b，其中 a > b，GCD(a, b) 等于 GCD(b, a mod b)。算法会持续进行，直到其中一个数变为0。 一个数就是两个输入数的最大公约数。

在您提供的函数 euclid 中，当 b 为0时，函数返回 a，这意味着 a 和 b 的最大公约数就是 a。

因此，这个函数计算的是两个整数 a 和 b 的最大公约数。

0.11 16、通常在搜索引擎中，对某个关键词加上双引号表示( )

cpp

A. 排除关键词, 不显示任何包含该关键词的结果

B. 将关键词分解, 在搜索结果中必须包含其中的一部分

C. 精确搜索, 只显示包含整个关键词的结果

D. 站内搜索, 只显示关键词所指向网站的内容

正确答案:C

A选项: 是不正确的，因为排除关键词通常使用减号(-)而不是双引号。

B选项: 也不正确，因为双引号的作用不是分解关键词，而是要求整个关键词的精确匹配。

C选项: 在搜索引擎中，对某个关键词加上双引号通常表示精确搜索，即只显示包含整个关键词的结果。这意味着搜索引擎会寻找与引号内完全匹配或词汇，而不是分散的单词。

D选项: 同样是错误的，因为双引号并不表示站内搜索，而是精确搜索。

0.12 17、中国的国家顶级域名是( )

cpp

A. .cn

B. .ch

C. .chn

D. .china

正确答案:A

A选项: 中国的国家顶级域名是 .cn。这个域名后缀用于标识与中国相关的网站或组织。

B选项:.ch 是瑞士的国家顶级域名。

C和D选项:.chn 和 .China 都不是标准的顶级域名后缀。虽然 .China 可能在某些情境下被用作域名，但它并不是官方承认的顶级域名。

18、把 64 位非零浮点数强制转换成 32 位浮点数后，不可能()

A. 大于原数

B. 小于原数

C. 等于原数

D. 与原数符号相反

正确答案:D

当我们把一个 64 位(通常是双精度浮点数，如 IEEE 754 标准中的 double)转换为 32 位(通常是单精度浮点数，如 IEEE 754 标准中的 float)F 会发生精度损失或舍入错误。这是因为 32 位浮点数表示的数值范围和精度都小于 64 位浮点数。

A选项:当 64 位浮点数的值在 32 位浮点数的可表示范围内，但由于舍入而向上调整时，32 位浮点数可能大于 64 位浮点数。例如，如果 64 位浮 3.14159(一个超过 32 位浮点数精度的值)，它可能被舍入为 3.15(一个更大的 32 位浮点数)。

B选项: 当 64 位浮点数的值在 32 位浮点数的可表示范围内，但由于舍入而向下调整时，32 位浮点数可能小于 64 位浮点数。例如，如果 64 位浮点 3.14159(一个超过 32 位浮点数精度的值)，它可能被舍入为 3.14(一个更小的 32 位浮点数)。

C选项: 如果 64 位浮点数的值正好在 32 位浮点数的可表示范围内，并且没有舍入错误，那么 32 位浮点数可能等于 64 位浮点数。

D选项: 强制类型转换不会改变数值的符号。无论 64 位浮点数是正数还是负数，转换后的 32 位浮点数的符号将与原数相同。因此，这是不可能的

19、下列程序中，正确计算1,2,…,100这100个自然数之和sum{初始值为0}的是( )

cpp

A. $i=1$ do{sum+=i;i++; }while(i<=100);

B. i = 1; do{sum++=i; i++; }while(i > 100);

C. i = 1; while(i < 100){ sum+=i; i++; }

D. i = 1; while(i >= 100){ sum+=i; i++; }

正确答案:A

A选项:

初始化i = 1 。

进入 do…while 循环，其中 sum += i; 将 i 加到 sum 上，然后 i++ 将 i 的值增加 1 。

检查 while(i<=100)，如果 i 小于或等于 100，则继续循环。

循环继续直到 i 大于 100，此时退出循环。

这个选项会计算从 1 到 100 的所有自然数之和。

B选项:

初始化i = 1 。

进入 do…while 循环，但条件 i > 100 在第一次迭代时就为 false，因此循环体不会执行。

循环不会执行，所以不会计算任何数的和。

这个选项不会计算从 1 到 100 的所有自然数之和。

C选项:

初始化i = 1 。

进入 while 循环，其中 sum+=i; 将 i 加到 sum 上，然后 i++ 将 i 的值增加 1 。

循环继续直到 i 不小于 100，即 i 等于 100 时退出循环。

这个选项只会计算从 1 到 99 的所有自然数之和，不包括 100。

D选项:

初始化 i = 1 。

进入 while 循环，但条件 i >= 100 在第一次迭代时就为 false，因此循环体不会执行。

循环不会执行，所以不会计算任何数的和。

这个选项不会计算从 1 到 100 的所有自然数之和。

0.13 20、CCF NOIP 复赛全国统一评测时使用的系统软件是( )

cpp

A. NOI Windows

B. NOI Linux

C. NOI Mac OS

D. NOI DOS

正确答案:B

CCF NOIP(全国青少年信息学奥林匹克竞赛)复赛全国统一评测时使用的系统软件是NOI Linux。NOI Linux是专门为信息学竞赛设计的Linux发行

about:blank

提供了竞赛所需的各种编程环境和工具，确保了评测环境的一致性，避免因为操作系统不同导致的评测结果差异。

0.14 二. 问题求解 (共2题，每题5分，共计10分; 每题全部答对得5分，没有部分分)

0.15 1、7 个同学围坐一圈，要选 2 个不相邻的作为代表，有___种不同的选法

正确答案:14

可以把这七个人想象成为一个七边形，问题变为了“求七边形有多少条对角线”，这样就可以运用公式求出共有x个选法(x条对角线)=n(n-3)/2=14

2、某系统自称使用了一种防窃听的方式验证用户密码。密码是 n 个数s1, s2,…, sn，均为0 或1。该系统每次随机生成n 个数a1, a2,…, an ，均为0 或1 答(s1a1+s2a2+…+snan) 除以2 的余数。如果多次的回答总是正确，即认为掌握密码。该系统认为，即使问答的过程被泄露，也无助于破解密码—— 没有直接发送密码。

然而，事与愿违。例如，当 n=4 时，有人窃听了以下5 次问答:

问答编号	系统生成的 $\mathrm{n}$ 个数				掌握密码的用户的回答
	a1	a2	a3	a4
1	1	1	0	0	1
2	0	0	1	1	0
3	0	1	1	0	0
4	1	1	1	0	0
5	1	0	0	0	0

就破解出了密码s1=，s2=，s3=，s4=。

答案格式为:纯数字用,连接

---

正确答案:0,1,1,1

根据用户的回答，代入a1、a2、a3、a4，可以倒推出有关S1，S2，S3，S4的关系式:

														(S1+S2) %2=1① (S1+S2+S3) %2=0④

															(S3+S4) %2=0② (S1) %2=0⑤

														(S2+S3) %2=0③

根据上面五个式子中的⑤式，可以推出S1=0，将S1代入①式，得出S2=1，将S2代入③式，得出S3=1，将S3代入②式，得出S4=1

---

0.16 三. 阅读程序写结果 (共4题，每题8分，共计32分)

0.17 1、阅读程序写结果:

cpp

---

include

using namespace std;

int main(){

int a, b;

cin >> a >> b;

cout << a << "+" << b << "=" << a + b << endl;

}

---

输入:35

输出:___

正确答案: $3+5=8$

签到题

这段C++代码是一个简单的加法程序。程序首先声明了两个整型变量a和b，然后通过cin从标准输入(通常是键盘)读取这两个变量的值。接着， cout将这两个变量的和输出到标准输出(通常是屏幕)。

当输入为“3 5”时，程序将这两个数字分别赋值给变量a和b，然后计算它们的和(即8)，最后输出“3+5=8”。

0.18 2、阅读程序写结果:

cpp AI 写代码

---

include

using namespace std;

int main(){

int a, b, u, i, num;

cin >> a >> b >> u;

---

about:blank

2026/8/2 18:44 NOIP 2013 普及组初赛试题及解析

num = 0;

for $\left(i=a;i<=b;i++\right)$

if ((i % и) == 0)

num++;

cout<<num << endl;

return 0;

}

输入: 1100 15

输出:___

正确答案: 6

这段C++代码用于计算在一个给定的整数范围内(从a到b，包括a和b)，有多少个数是给定数u的倍数。

$a=1,b=100,num=0,u=15$

$\mathbf{i}$	i <= b	(i % u) == 0	num++
1	true	false
2	true	false
3	true	false
$\ldots$
15	true	true	1
16	true	false
$\ldots$
30	true	true	2
$\ldots$
45	true	true	3
$\ldots$
60	true	true	4
$\ldots$
75	true	true	5
$\ldots$
90	true	true	6
$\ldots$
100	true	false
101	false

在1到100之间，15的倍数有:15,30,45,60,75,90。共有6个。

0.19 3、阅读程序写结果:

cpp

---

include

using namespace std;

int main(){

const int SIZE = 100;

int n, f, i, left, right, middle, a[SIZE];

cin >> n >> f;

---

2026/8/2 18:44 NOIP 2013 普及组初赛试题及解析

---

	for $\left( {i = 1;i <  = n;i +  + }\right)$

		cin >> a[i];

	left = 1;

	right $= n$

	do \{

		middle = (left + right) / 2;

		if (f <= a[middle])

				right = middle;

		else

				left = middle + 1;

	\} while (left < right);

	cout << left << endl;

	return 0;

\}

输入:

12 17

24691115171819202125

输出:___

---

正确答案:7

这段代码是一个实现二分查找(Binary Search)算法的程序，用于在一个已排序的数组中查找一个特定的值。程序首先读取一个整数n，表示数组然后读取一个整数f，表示要查找的目标值。接下来，程序读取n个整数，并将它们存储在数组a中。

二分查找算法的工作原理是不断将搜索范围缩小一半，直到找到目标值或搜索范围为空。在这个程序中，left和right变量分别表示当前搜索范围的2 (初始时，left = 1, right = n)，而middle变量则表示当前搜索范围的中间位置。

在每次循环中，程序检查目标值f是否小于等于中间位置的值a[middle]。如果是，说明目标值可能在左半部分，因此将right更新为middle；否则，[ 能在右半部分，因此将left更新为middle + 1。循环继续直到left和right相等，此时搜索范围缩小到一个点，即目标值的位置(如果存在的话)。

$n=12,f=17,$ lift $=1,$ right $=12$

middle = (left + right) / 2	f <= a[middle]	right = middle	left = middle + 1	left :
6	${17} < = {15}$		7	tI
9	${17} < = {19}$	9		tI
8	${17} < = {18}$	8		tI
7	${17} < = {17}$	7		fa

0.20 4、阅读程序写结果:

cpp

---

include

using namespace std;

int main(){

const int SIZE = 100;

int height[SIZE], num[SIZE], n, ans;

cin >> n;

for (int i = 0; i < n; i++)\{

		cin >> height[i];

		num[i] = 1;

		for (int j = 0; j < i; j++)\{

			if ((height[j] < height[i]) && (num[j] >= num[i]))

				num[i] = num[j]+1;

	\}

\}

ans $= 0$ ;

for (int i = 0; i < n; i++)\{

		if (num[i] > ans) ans = num[i];

\}

cout<<ans << endl;

}

---

2026/8/2 18:44 NOIP 2013 普及组初赛试题及解析

输入:

6

25311124

输出:___

正确答案: 4

这段C++代码实现了计算最长递增子序列(Longest Increasing Subsequence, LIS)的长度。给定一个整数数组，该算法找出数组中最长的子序列序列中的元素从左到右递增。

代码的主要逻辑如下:

声明两个大小为SIZE的整数数组height和num，以及两个整数n和ans。height数组用于存储输入的整数，num数组用于存储以当前元素结尾的最长列的长度。

从标准输入读取一个整数n，表示数组的大小。

使用一个for循环读取n个整数，并存储在height数组中。同时，初始化num数组，使得每个元素的初始值为1(因为任何单独的元素都可以被视为长递增子序列)。

使用嵌套for循环计算num数组的值。外层循环遍历height数组中的每个元素，内层循环则检查当前元素之前的所有元素。如果找到一个比当前元素 height[j]，并且以height[j]结尾的递增子序列的长度num[j]大于或等于以当前元素结尾的递增子序列的长度num[j]，则更新num[i]为num[j] + 1。

使用另一个for循环遍历num数组，找到其最大值，即为最长递增子序列的长度，存储在ans中。

输出ans的值。

对于给定的输入:

6

25311124

最长递增子序列是2,3,11,12，它的长度为4。因此，程序的输出将是4。

height[] = {2, 5, 3, 11, 12, 4}, n = 6

i	i < n	num	j	j < l	(height[j] < height[i]) && (num[j] >= num[i])	num[i] = num[j]+1	n
0	true	1	0	false
1	true	1,1	0	true	true	num[1] = 2
			1	false
2	true	1, 2, 1	0	true	true	num[2] = 2	1
			1	true	false
			2	false
3	true	1, 2, 2, 1	0	true	true	num[3] = 2	1,2
			1	true	true	num[3] = 3	1,1
			2	true	false
			3	false
4	true	1, 2, 2, 3, 1	0	true	true	num[4] = 2	1, 2
			1	true	true	num[4] = 3	1, 2
			2	true	false
			3	true	true	num[4] = 4	1, 2
			4	false
5	true	1, 2, 2, 3, 4, 1	0	true	true	num[5] = 2	1,2,1
			1	true	false
			2	true	true	num[5] = 3	1,2,3
			3	true	false
			4	true	false
			5	false
6	false

i	i < n	num[i] > ans	ans = num[i]
0	true	true	1
1	true	true	2
2	true	false
3	true	true	3
4	true	true	4
5	true	false
6	false

0.21 四. 完善程序 (共 2 题, 每题 14 分, 共计 28 分)

0.22 1、(序列重排)

全局数组变量 a 定义如下:

cpp AI写代码

---

const int SIZE = 100;

int a[SIZE], n;

---

它记录着一个长度为 n 的序列 a[1], a[2], …, a[n]。

现在需要一个函数，以整数 p (1≤p≤n)为参数，实现如下功能:将序列 a 的前 p

个数与后 $n-p$ 个数对调，且不改变这 p 个数 (或 $n-p$ 个数) 之间的相对位置。例如，

长度为 5 的序列1,2,3,4,5，当 $p=2$ 时重排结果为3,4,5,1,2。

有一种朴素的算法 可以实现这一需求，其时间复杂度为 $\mathrm{O}\left(\mathrm{n}\right)$ 、空间复杂度为 $\mathrm{O}\left(\mathrm{n}\right)$ :

cpp AI写代码

---

void swap1(int p){

int i, j, b[SIZE];

for (i = 1; i <= p; i++)

	$\mathrm{b}\left\lbrack  \text{ ① }\right\rbrack   = \mathrm{a}\left\lbrack  \mathrm{i}\right\rbrack$ ； // (3分)

for $\left( {i = p + 1;i <  = n;i +  + }\right)$

	b[i - p] = ②; // (3分)

for $\left( {i = 1;i <  = 3;i +  + }\right) //$ (2分)

	$\mathrm{a}\left\lbrack  \mathrm{i}\right\rbrack   = \mathrm{b}\left\lbrack  \mathrm{i}\right\rbrack  ;$

}

---

我们也可以用时间换空间，使用时间复杂度 为 $O\left(n^2\right)$ 、空间复杂度为 $O\left(1\right)$ 的算法:

cpp

---

void swap2(int p)\{

	int i, j, temp;

	for $\left( {i = p + 1;i <  = n;i +  + }\right) \{$

			temp = a[i];

			for (j = i; j >= 0; j--) // (3 分)

				a[j] = a[j - 1];

			⑤ = temp; // (3 分)

	\}

\}

正确答案:

1. $n-p+i$

2.a[i]

3.n

4.i-p + 1

5.a[i-p]

---

2026/8/2 18:44 NOIP 2013 普及组初赛试题及解析

该题目包含两个函数swap1和swap2，分别用于重排数组a。swap1使用额外的数组b来辅助完成重排，时间复杂度为O(n)，空间复杂度为O(n)。sv 用原地交换的方式，不使用额外空间，时间复杂度为 $O\left(n^2\right)$ ，空间复杂度为O(1)。

对于swap1函数:

第一个空应该填入n - p + i，这是因为我们需要将a数组的前p个数复制到b数组中，b数组的索引需要从1开始，所以b数组的索引应该是n - p + i。 第二个空应该填入a[i]，这是因为我们需要将a数组的后n - p个数复制到b数组中，从p + 1开始复制，保持原数组的顺序不变。

第三个空应该填入n，这是因为我们需要将b数组中的所有元素复制回a数组，从1开始复制到n。

对于swap2函数:

第四个空应该填入i - p + 1，这是因为我们需要将a[i]之前的p个数向右移动一位，所以需要从i - p + 1开始向前移动。

第五个空应该填入a[i - p]，这是因为经过前面i - p次的右移后，a[i - p]的位置将会是空的，我们需要将temp(即原来的a[i])放入这个空位置。

综上所述，我们完成了对swap1和swap2两个函数的详细分析，并给出了正确的填空答案。swap1函数使用额外的空间换取了时间效率，而swap2 过原地交换的方式，虽然时间复杂度较高，但节省了空间。根据具体的需求和性能考虑，可以选择合适的函数来实现序列重排。

2、(二叉查找树)二叉查找树具有如下性质:每个节点的值都大于其左子树上所有节点的值、小于其右子树上所有节点的值。试判断一棵树是否为树。

输入的第一行包含一个整数 n，表示这棵树有n 个顶点，编号分别为 1,2,…, n，其中编号为 1 的为根结点。之后的第 i 行有三个数 value, left_child, r ，分别表示该节点关键字的值、左子节点的编号、右子节点的编号；如果不存在左子节点或右子节点，则用 0 代替。输出 1 表示这棵树是二叉查找树表示不是。

cpp

---

#include <iostream>

using namespace std;

const int SIZE = 100;

const int INFINITE = 1000000;

struct node\{

	int left_child, right_child, value;

\}; node a[SIZE];

int is_bst(int root, int lower_bound, int upper_bound)\{

	int cur;

	if (root == 0)

		return(1);

	cur = a[root].value;

	if ((cur > lower_bound) && ( ① && (is_bst(a[root].left_child, lower_bound, cur) == 1) && (is_bst( ②, ③, ④ ) == 1))

		return(1);

	return(0);

\}

int in, n;

	int i, n;

	cin >> n;

	for $\left( {i = 1;i <  = n;i +  + }\right)$

		cin >> a[i].value >> a[i].left_child >> a[i].right_child;

	cout << is_bst(), -INFINITE, INFINITE) << endl;

	return(0);

\}

正确答案:

1.cur < upper_bound

2.a[root].right_child

3.cur

4.upper_bound

5.1

---

AI 写代码

这段代码的目的是检查给定的树是否是一个二叉查找树(BST)。在BST中，对于每个节点，其值必须大于或等于其左子树中所有节点的值，并且于其右子树中所有节点的值。

cpp

include

using namespace std;

const int SIZE = 100; // 定义最大节点数

const int INFINITE = 1000000; // 定义一个足够大的数，用于表示无穷大

about:blank

NOIP 2013 普及组初赛试题及解析

---

struct node\{ // 定义树节点的结构

	int left_child, right_child, value; // 左孩子、右孩子和节点的值

\};

node a [SIZE]; // 定义节点数组

// is_bst函数检查以root为根的子树是否是BST, lower_bound和upper_bound分别是该子树中所有节点值的下界和上界

int is_bst(int root, int lower_bound, int upper_bound)\{

	int cur;

	if (root == 0) // 如果节点为空，则它是BST

		return(1);

	cur = a[root].value; // 当前节点的值

	// 检查当前节点的值是否在指定的上下界之间

	if ((cur > lower_bound) && (cur < upper_bound) &&

		(is_bst(a[root].left_child, lower_bound, cur) == 1) && // 递归检查左子树

		(is_bst(a[root].right_child, cur, upper_bound) == 1)) // 递归检查右子树

		return(1);

	return(0); // 如果不满足BST的条件，返回0

\}

int main()\{

	int i, n;

	cin >> n; // 输入节点数

	for (i = 1; i <= n; i++) // 输入每个节点的信息

		cin >> a[i].value >> a[i].left_child >> a[i].right_child;

	// 检查整棵树是否是BST，从根节点1开始，初始上下界为-INF和INF

	cout << is_bst(1, -INFINITE, INFINITE) << endl;

	return(0);

\}

cur < upper_bound:检查当前节点的值是否小于上界。

a[root].right_child:递归检查右子树时，应传入右子节点的编号。

cur:在递归检查右子树时，右子树的所有节点值应该大于或等于当前节点的值cur。

upper_bound:在递归检查右子树时，右子树的所有节点值应该小于或等于上界upper_bound。

1:从根节点1开始检查整棵树是否是BST。

---