「NOIP2017」提高组初赛试题答案及解析

第 1 题

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

A. 2020

B. 2021

C. 2022

D. 2023

本题共 1.5 分

答案

A

解析

NOIP 竞赛 2022 年起不再支持 Pascal 语言。

第 2 题

在 8 位二进制补码中，10101011 表示的数是十进制下的（ ）。

A. 43

B. -85

C. -43

D. -84

本题共 1.5 分

答案

B

解析

补码转原码：

先取反得到 11010100（注意第 1 位是符号位不要变），

再加 1 得到 11010101，

即十进制下的 -85 。

第 3 题

分辨率为 1600x900、16 位色的位图，存储图像信息所需的空间为（ ）。

A. 2812.5KB

B. 4218.75KB

C. 4320KB

D. 2880KB

本题共 1.5 分

答案

A

解析

16 位色代表一个像素的内存为 2 个字节。

因此答案为 1600 × 900 × 2 = 2880000 Byte = 2812.5 KB

第 4 题

2017 年 10 月 1 日是星期日，1949 年 10 月 1 日是（ ）。

A. 星期三

B. 星期日

C. 星期六

D. 星期二

本题共 1.5 分

答案

C

解析

1949 年 10 月 1 日 ~ 2017 年 10 月 1 日 一共有 2017 - 1949 = 68 年。

其中有 (2016 - 1952) / 4 + 1 = 17 年是闰年，所以一共有 68 × 365 + 17 = 24837 天。

24837 mod 7 = 1 。

所以答案为星期天倒退 1 天，即星期六。

第 5 题

设 G 是有 n 个结点、m 条边（n ≤ m）的连通图，必须删去 G 的（ ）条边， 才能使得 G 变成一棵树。

A. m – n + 1

B. m - n

C. m + n + 1

D. n – m + 1

本题共 1.5 分

答案

A

解析

树有 n - 1 条边，所以要删去 m - (n - 1) = m - n + 1 条边。

第 6 题

若某算法的计算时间表示为递推关系式：

$T(N) = 2T(\frac{N}{2}) + N \log N$

$T(1) = 1$

则该算法的时间复杂度为（ ）。

A. $O(N)$

B. $O(N \log N)$

C. $O(N \log^2N)$

D. $O(N^2)$

本题共 1.5 分

答案

C

解析

因为 $T(N)$ 每次都拆成 2 倍的 $T(\frac{N}{2})$ + 一个与 $N$ 有关的常数，所以我们可以画出一棵二叉树。

每个节点的值代表常数，子树和就是它的时间复杂度，所有节点的和就是答案。

显然一共有 $\log N$ 层，第 $i$ 层的和为 $N \log (\frac{N}{2^{i - 1}}) = N \log N - N (i - 1)$ 。

每一层加起来为 $\frac{N \log^2 N}{2} - N \log N$，时间复杂度忽略较小的一项，为 $O(N \log^2N)$ 。

第 7 题

表达式 a × (b + c) × d 的后缀形式是（ ）。

A. a b c d × + ×

B. a b c + × d ×

C. a × b c + × d

D. b + c × a × d

本题共 1.5 分

答案

B

解析

转化为表达式树，即每次把表达式中运算级最低的符号当做根分治下去。

求出后序遍历为 a b c + × d × 。

第 8 题

由四个不同的点构成的简单无向连通图的个数是（ ）。

A. 32

B. 35

C. 38

D. 41

本题共 1.5 分

答案

C

解析

当边数为 4,5,6 时，图一定连通，因为 4 个点最多有 6 条边，可以从 6 条边中挑选若干条，所以一共有

$\rm C_6^4 + C_6^5 + C_6^6 = 15 + 6 + 1 = 22$ 个图符合题意。

当边数为 3 时，图可能有以下两种情况：

显然第 2 种情况是不符合题意的，我们可以用总的方案数减去 ② 的方案数。

一共有 $\rm C_6^3 = 20$ 种方案，

考虑 ② 中多出来的点的编号，一共有 4 种方案。

所以答案为 22 + 20 - 4 = 38 。

第 9 题

将 7 个名额分给 4 个不同的班级，允许有的班级没有名额，有（ ）种不同的分配方案。

A. 60

B. 84

C. 96

D. 120

本题共 1.5 分

答案

D

解析

隔板法。使用隔板法的条件是每个班级至少 1 个名额。可以假设有 11 个名额，先给每个班分一个，然后在 10 个位置选 3 个插板。

答案为 ${\rm C}_{n + m - 1}^{m - 1} = {\rm C}_{10}^3 = 120$ 种。

第 10 题

若 f[0] = 0, f[1] = 1, f[n + 1] = (f[n] + f[n - 1]) / 2，则随着 i 的增大，f[i] 将接近于 ( ) 。

A. $\frac{1}{2}$

B. $\frac{2}{3}$

C. $\frac{\sqrt 5 - 1}{2}$

D. $1$

本题共 1.5 分

答案

B

解析

$f$ 的特征方程为

$x^2 = \frac{1}{2} x + \frac{1}{2}$

$(2x + 1)(x - 1) = 0$

解得 $x_1 = -\frac{1}{2},x_2 = 1$

$f_n = c_1x_1^n +c_2x_2^n$

$\because f_0 = 0, f_1 = 1$

$\therefore$ $\left\{\begin{matrix}c_1 + c_2 = 0\\\ -\frac{1}{2}c_1 + c_2 = 1\end{matrix}\right.$

解得 $\left\{\begin{matrix} c_1 = -\frac{2}{3}\\c_2 = \frac{2}{3} \end{matrix}\right.$

$f_n = -\frac{2}{3} \times \left( -\frac{1}{2} \right)^n + \frac{2}{3}$

当 $n \rightarrow \infty$ 时，$\left(-\frac{1}{2} \right)^n$ 等于 0，所以 $f_n$ 无限趋于 $\frac{2}{3}$ 。

第 11 题

设 A 和 B 是两个长为 n 的有序数组，现在需要将 A 和 B 合并成一个排好序的 数组，请问任何以元素比较作为基本运算的归并算法最坏情况下至少要做 （ ）次比较。

A. $n^2$

B. $n \log n$

C. $2n$

D. $2n - 1$

本题共 1.5 分

答案

D

解析

最坏情况下要将 A 中前 n - 1 个数和 B 中前 n - 1个数逐个比较，共 2n - 2 次，最后剩下 2 个数只要比较 1 次，所以答案为 2n - 1 次。

第 12 题

在 n（n ≥ 3）枚硬币中有一枚质量不合格的硬币（质量过轻或质量过重）,如果只有一架天平可以用来称重且称重的硬币数没有限制，下面是找出这枚不合格的硬币的算法。请把 a-c 三行代码补全到算法中。
a. A ← X ∪ Y
b. A ← Z
c. n ← |A|

算法 Coin(A, n)

1. k ← ⌊n/3⌋   
2. 将 A 中硬币分成 X，Y，Z 三个集合，使得|X| = |Y| = k,|Z| = n - 2k  
3. if W(X) ≠ W(Y)       //W(X), W(Y)分别为 X 或 Y 的重量   
4. then __________   
5. else __________   
6. _______________
7. if n>2 then goto 1   
8. if n=2 then 任取 A 中1枚硬币与拿走硬币比较，若不等，则它不合格； 若相等，则 A 中剩下的硬币不合格.    
9. if n=1 then A 中硬币不合格

正确的填空顺序是（ ）。

A. b, c, a

B. c, b, a

C. c, a, b

D. a, b, c

本题共 1.5 分

答案

D

解析

经典的质检问题。

每次把硬币分成三份（尽量平均），称量相同的两份硬币。若质量相同，则不合格的硬币在第三堆中；若质量不同，则不合格的硬币在这两堆中。由此很容易得出答案。

第 13 题

有正实数构成的数字三角形排列形式如图所示。第一行的数为 $a_{11}$；第二行的数从左到右依次为 $a_{21}$, $a_{22}$；… 第 n 行的数为 $a_{n1}$, $a_{n2}$, …, $a_{nn}$。从 $a_{11}$ 开始，每一行的数 $a_{ij}$ 只有两条边可以分别通向下一行的两个数 $a_{(i+1)1}$ 和 $a_{(i+1)(j+1)}$。用动态规划算 法找出一条从 $a_{11}$ 向下通到 $a_{n1}$, $a_{n2}$, …, $a_{nn}$ 中某个数的路径，使得该路径上的数之和达到最大。 令 C[i,j] 是从 $a_{11}$ 到 $a_{ij}$ 的路径上的数的最大和，并且 C[i,0]=C[0,j]=0, 则 C[i,j]=（ ）。

A. max{C[i-1,j-1], C[i-1,j]} + $a_{ij}$

B. C[i-1,j-1] + C[i-1,j]

C. max{C[i-1,j-1], C[i-1,j]} + 1

D. max{C[i,j-1],C[i-1,j]} + $a_{ij}$

本题共 1.5 分

答案

A

解析

经典的数塔问题。

从上一层对应的两个状态中较大的转移过来即可。

第 14 题

小明要去南美洲旅游，一共乘坐三趟航班才能到达目的地，其中第 1 个航班 准点的概率是 0.9，第 2 个航班准点的概率为 0.8, 第 3 个航班准点的概率为 0.9。如果存在第 i 个（i=1,2）航班晚点，第 i+1 个航班准点，则小明将赶不 上第 i+1 个航班，旅行失败；除了这种情况，其他情况下旅行都能成功。请问小明此次旅行成功的概率是（ ）。

A. 0.5

B. 0.648

C. 0.72

D. 0.74

本题共 1.5 分

答案

D

解析

旅行失败只有以下 4 种情况：

①：晚点 准点 准点

$P_1 = 0.1 \times 0.8 \times 0.9 = 0.072$

②：晚点 准点 晚点

$P_2 = 0.1 \times 0.8 \times 0.1 = 0.008$

③：准点 晚点 准点

$P_3 = 0.9 \times 0. 2 \times 0.9 = 0.162$

④：晚点 晚点 准点

$P_4 = 0.1 \times 0. 2 \times 0.9 = 0.018$

那么旅行失败的概率为 $P = P_1 + P_2 + P_3 + P_4 = 0.26$，

成功的概率为 $1 - P = 0.74$ 。

第 15 题

欢乐喷球：儿童游乐场有个游戏叫“欢乐喷球”，正方形场地中心能不断喷出彩色乒乓球，以场地中心为圆心还有一 个圆形轨道，轨道上有一列小火车在匀速运动，火车有六节车厢。

假设乒乓球等概率落到正方形场地的每个地点，包括火车车厢。小朋友玩这个游戏时，只能坐在同一个火车车厢里，可以在自己的车厢里捡落在该车厢内的所有乒乓球，每个人每次游戏有三分钟时间，则一个小朋友独自玩一次游戏期望可以得到（ ）个乒乓球。假设乒乓球喷出的速度为 2 个/秒，每节车厢的面积是整个场地面积的 1/20。

A. 60

B. 108

C. 18

D. 20

本题共 1.5 分

答案

C

解析

无论火车车厢在哪个位置时，接到乒乓球的概率都是 $\frac{1}{20}$，

所以答案为 $3 \times 60 \times 2 \times \frac{1}{20} = 18$ 个。

第 16 题

以下排序算法在最坏情况下时间复杂度最优的有（ ）。

A. 冒泡排序

B. 快速排序

C. 归并排序

D. 堆排

本题共 1.5 分

答案

CD

解析

冒泡排序时间复杂度稳定为 $O(n^2)$，

快速排序在最坏情况下时间复杂度为 $O(n^2)$，

归并排序和堆排序时间复杂度稳定为 $O(n \log n)$ 。

第 17 题

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

A. a, b, c, d, e, f, g

B. a, d, c, b, e, g, f

C. a, d, b, c, g, f, e

D. g, f, e, d, c, b, a

本题共 1.5 分

答案

C

解析

C 中 c 不可能在 b 的前面。

第 18 题

下列算法中，（ ）是稳定的排序算法。

A. 快速排序

B. 堆排序

C. 希尔排序

D. 插入排序

本题共 1.5 分

答案

D

解析

除了选择排序，快速排序，堆排序，希尔排序之外的排序都是稳定排序。

第 19 题

以下是面向对象的高级语言的有（ ）。

A. 汇编语言

B. C++

C. Fortran

D. Java

本题共 1.5 分

答案

BD

解析

汇编语言是不是高级语言，

Fortran 是面向过程的高级语言，

C++,Java 都是面向对象的高级语言。

第 20 题

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

A. 奥斯卡奖

B. 图灵奖

C. 诺贝尔奖

D. 王选奖

本题共 1.5 分

答案

BD

解析

图灵奖由美国计算机协会（ACM）于 1966 年设立，专门奖励那些对计算机事业作出重要贡献的个人。 其名称取自计算机科学的先驱、英国科学家艾伦·麦席森·图灵。

中国计算机学会王选奖是中国计算机学会设立的奖项，为了纪念王选院士为中国计算机事业做出的非凡贡献，学习他严谨、务实、奉献、创新、勇于超越的科研精神。

第 21 题

如下图所示，共有 13 个格子。对任何一个格子进行一次操作，会使得它自己以及与它上下左右相邻的格子中的数字改变（由 1 变 0，或由 0 变 1）。现在要使得所有的格子中的数字都变为 0，至少需要（）次操作。

本题共 5 分

答案

3

解析

第 22 题

如下图所示，A 到 B 是连通的。假设删除一条细的边的代价是 1，删除一条粗的边的代价是 2，要让 A、B 不连通，最小代价是 ( )（2 分），最小代价的不同方案数是 ( )（3 分）。（只要有一条删除的边不同，就是不同的方案）

本题共 5 分

答案

4

9

解析

对于第一问，我们可以把每条边的代价当做流量，要求的其实就是这个网络的最小割，即最大流，也可以求对偶图的最短路长度。肉眼观察就能得到答案。

对于第二问，可以把问题当做画一条线，把图分成左右两部分，且穿过的几条边代价和为 4，要细心。还有一种方法是将平面图转对偶图后跑最短路计数。

1：

2：

3：

4：

5：

6：

7：

8：

9：

平面图转对偶图：

一目了然。

第 23 题

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

输入：8 4

本题共 8 分

答案

输出：15

解析

数的划分。即求把 n 拆成 m 个自然数的和有多少种方案。

方法一：暴力枚举

1. 0 0 0 8

2. 0 0 1 7

3. 0 0 2 6

4. 0 0 3 5

5. 0 0 4 4

6. 0 1 1 6

7. 0 1 2 5

8. 0 1 3 4

9. 0 2 2 4

10. 0 2 3 3

11. 1 1 1 5

12. 1 1 2 4

13. 1 1 3 3

14. 1 2 2 3

15. 2 2 2 2

方法二：动态规划

用 $f_{i,j}$ 表示把 $i$ 分成 $j$ 个自然数和的方案数。

则 $f_{i,j} = f_{i,j - 1} + f_{i - 1, j - 1} + f_{i-j,j}$ 。

其中 $f_{i,j - 1}$ 表示划分出来第一个数是 0 的方案数，

$f_{i - 1, j - 1}$ 表示划分出来第一个数是 1 的方案数，

$f_{i-j, j}$ 表示划分出来第一个数大于 1 的方案数。

第 24 题

#include <iostream> 
using namespace std; 
int main() 
{     
    int n, i, j, x, y, nx, ny;     
    int a[40][40];     
    for (i = 0; i < 40; i++)         
        for (j = 0; j < 40; j++)             
            a[i][j] = 0;     
        cin >> n; 
        y = 0; 
        x = n - 1; 
        n = 2 * n - 1;     
        for (i = 1; i <= n * n; i++) 
        {         
            a[y][x] = i;         
            ny = (y - 1 + n) % n;         
            nx = (x + 1) % n;         
            if ((y == 0 && x == n - 1) || a[ny][nx] != 0)             
                y = y + 1;         
            else { y = ny; x = nx; 
            }     
        }     
        for (j = 0; j < n; j++)         
            cout << a[0][j] << " ";     
        cout << endl;     
        return 0; 
    }

输入：3

本题共 8 分

答案

输出：17 24 1 8 15

解析

填一个 5 阶幻方（每行，每列，每条斜线的和均相等的方阵）。

按程序模拟即可。

\	0	1	2	3	4
0	17	24	1	8	15
1	23	5	7	14	16
2	4	6	13	20	22
3	10	12	19	21	3
4	11	18	25	2	9

第 25 题

#include <iostream>
using namespace std;
int n, s, a[100005], t[100005], i;
void mergesort(int l, int r)
{
    if (l == r)
        return;
    int mid = (l + r) / 2;
    int p = l;
    int i = l;
    int j = mid + 1;
    mergesort(l, mid);
    mergesort(mid + 1, r);
    while (i <= mid && j <= r)
    {
        if (a[j] < a[i])
        {
            s += mid - i + 1;
            t[p] = a[j];
            p++;
            j++;
        }
        else
        {
            t[p] = a[i];
            p++;
            i++;
        }
    }
    while (i <= mid)
    {
        t[p] = a[i];
        p++;
        i++;
    }
    while (j <= r)
    {
        t[p] = a[j];
        p++;
        j++;
    }
    for (i = l; i <= r; i++)
        a[i] = t[i];
}
int main()
{
    cin >> n;
    for (i = 1; i <= n; i++)
        cin >> a[i];
    mergesort(1, n);
    cout << s << endl;
    return 0;
}

输入：

6
2 6 3 4 5 1

本题共 8 分

答案

输出：8

解析

归并排序求逆序对个数。

$(2,1)$

$(6,3),(6,4),(6,5),(6,1)$

$(3,1)$

$(4,1)$

$(5,1)$

第 26 题

#include <iostream>
using namespace std;
int main()
{
    int n, m;
    cin >> n >> m;
    int x = 1;
    int y = 1;
    int dx = 1;
    int dy = 1;
    int cnt = 0;
    while (cnt != 2)
    {
        cnt = 0;
        x = x + dx;
        y = y + dy;
        if (x == 1 || x == n)
        {
            ++cnt;
            dx = -dx;
        }
        if (y == 1 || y == m)
        {
            ++cnt;
            dy = -dy;
        }
    }
    cout << x << " " << y << endl;
    return 0;
}

输入 1：4 3（2 分）

输入 2：2017 1014（3 分）

输入 3：987 321（3 分）

本题共 8 分

答案

输出 1：1 3

输出 2：2017 1

输出 3：1 321

解析

第一个模拟就可以得出答案。

也很容易转化为一个模型。

从左上角（1，1）开始，向右下方射出一条光线，碰到边缘反弹，求最后会弹到哪个角。

后两个照这么做是做不出来的，考虑把 x 和 y 分开观察变化。

x 值的变化：1,2,3,…,n,n - 1,n - 2,…,1,2,3,…

y 值的变化：1,2,3,…,m,m - 1,m - 2,…,1,2,3,…

当 (x,y) 等于 (1,1),(1,m),(n,1),(n,m) 中的任意一个时结束循环。

注意到 x 从 1 开始，经过 n - 1 个数变成 n，再经过 n - 1 个数变回 1；

y 也从 1 开始，经过 m - 1 个数变成 m，再经过 m - 1 个数变回 1。

显然经过 $\rm lcm(n - 1,m - 1)$ 个数时会结束循环。

当 $\rm lcm(n - 1,m - 1)$ 是 n - 1 的奇数倍时，x = n；偶数倍时，x = 1。

当 $\rm lcm(n - 1,m - 1)$ 是 m - 1 的奇数倍时，y = m；偶数倍时，y = 1。

$\rm lcm(2016,1013) = 2016 \times 1013$（1013 是质数）

是 2016 的奇数倍，是 1013 的偶数倍。

$\rm lcm(986,320) = 157760 = 160 \times 986 = 493 \times 320$

是 986 的偶数倍，是 320 的奇数倍。

第 27 题

（大整数除法）给定两个正整数 p 和 q，其中 p 不超过10100， q 不超过100000， 求 p 除以 q 的商和余数。（第一空 2 分，其余 3 分）

​ 输入：第一行是 p 的位数 n，第二行是正整数 p，第三行是正整数 q。

​ 输出：两行，分别是 p 除以 q 的商和余数。

#include <iostream>
using namespace std;
int p[100];
int n, i, q, rest;
char c;
int main()
{
    cin >> n;
    for (i = 0; i < n; i++)
    {
        cin >> c;
        p[i] = c - '0';
    }
    cin >> q;
    rest = (1);
    i = 1;
    while ((2) && i < n)
    {
        rest = rest * 10 + p[i];
        i++;
    }
    if (rest < q)
        cout << 0 << endl;
    else
    {
        cout << (3);
        while (i < n)
        {
            rest = (4);
            i++;
            cout << rest / q;
        }
        cout << endl;
    }
    cout << (5) << endl;
    return 0;
}

本题共 14 分

答案

(1) p[0]

(2) rest < q 或 q > rest

(3) rest / q

(4) rest % q * 10 + p[i]

(5) rest % q

解析

高精度除单精度。

(1) 注意下面一行 i = 1，没有算第 0 位，所以 rest 的初值应该等于 p[0] 。

(2) 模拟除法竖式，找到最小的 k，满足前 k 位组成的数大于除数。

(3) 输出商的第 1 位。

(4) 继续模拟除法竖式，每次将当前的余数与下一位组成一个新的数。

(5) 最后输出余数，注意要对 q 取模。

第 28 题

（最长路径）给定一个有向无环图，每条边长度为 1，求图中的最长路径长度。（第五空 2 分，其余 3 分）

​ 输入：第一行是结点数 n（不超过 100）和边数 m，接下来 m 行，每行两个整数 a， b，表示从结点 a 到结点 b 有一条有向边。结点标号从 0 到 (n-1) 。

​ 输出：最长路径长度。

​ 提示：先进行拓扑排序，然后按照拓扑序计算最长路径。

#include <iostream>
using namespace std;
int n, m, i, j, a, b, head, tail, ans;
int graph[100][100]; // 用邻接矩阵存储图
int degree[100];     // 记录每个结点的入度
int len[100];        // 记录以各结点为终点的最长路径长度
int queue[100];      // 存放拓扑排序结果
int main()
{
    cin >> n >> m;
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            graph[i][j] = 0;
    for (i = 0; i < n; i++)
        degree[i] = 0;
    for (i = 0; i < m; i++)
    {
        cin >> a >> b;
        graph[a][b] = 1;
        (1);
    }
    tail = 0;
    for (i = 0; i < n; i++)
        if ((2))
        {
            queue[tail] = i;
            tail++;
        }
    head = 0;
    while (tail < n - 1)
    {
        for (i = 0; i < n; i++)
            if (graph[queue[head]][i] == 1)
            {
                (3);
                if (degree[i] == 0)
                {
                    queue[tail] = i;
                    tail++;
                }
            }
        (4);
    }
    ans = 0;
    for (i = 0; i < n; i++)
    {
        a = queue[i];
        len[a] = 1;
        for (j = 0; j < n; j++)
            if (graph[j][a] == 1 && len[j] + 1 > len[a])
                len[a] = len[j] + 1;
        if ((5))
            ans = len[a];
    }
    cout << ans << endl;
    return 0;
}

本题共 14 分

答案

(1) degree[b] = degree[b] + 1 或 degree[b]++ 或 ++degree[b]

(2) degree[i] == 0 或 !degree[i]

(3) degree[i] = degree[i] - 1 或 degree[i]-- 或 --degree[i]

(4) head = head + 1 或 head++ 或 ++head

(5) ans < len[a] 或 len[a] > ans

解析

拓扑排序 + DP

(1) 增加有向边 a -> b，节点 b 的入度 + 1。

(2) 拓扑排序时先将入度为 0 的点加入队列。

(3) 将有向边 queue[head] -> i 删除，节点 i 的入度 - 1。

(4) 把队首弹出队列。

(5) len[i] 表示到点 i 的最长路径，判断 len[i] 是否能更新答案。