解题报告-NOIP2017提高组初赛

NOIP 2017 提高组初赛试题 完全解读！

第 1 题

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

A. 2020 B. 2021 C. 2022 D. 2023

送命题。

第 2 题

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

A. 43 B. -85 C. -43 D. -84

	原码	补码	反码
正数	符号(0)+数值表示法	原码	原码
负数	符号(1)+数值表示法	符号位之外各位取反	符号位之外各位取反，最低位加1

$$
[x]_{补}=10101011
$$

$$
[x]_{反}=10101010
$$

$$
[x]_{原}=11010101
$$

$$
x=-85
$$

第 3 题

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

A. 2812.5KB B. 4218.75KB C. 4320KB D. 2880KB

$$
8 \ \text{bit}= 1\ \text{byte(B)}\
1024\ \text{B}=1\ \text{KB}\
1024\ \text{KB}=1\ \text{MB}\
1024\ \text{MB}=1\ \text{GB}
$$

第 4 题

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

A. 星期三 B. 星期日 C. 星期六 D. 星期二

2017->2016：星期日->星期六

2016->2015：星期六->星期四

2015->2014：星期四->星期三

……

1950->1949：星期日->星期六

第 5 题

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

A. m – n + 1 B. m - n C. m + n + 1 D. n – m + 1

树有 n - 1 条边

第 6 题

若某算法的计算时间表示为递推关系式：
T(N) = 2T(N / 2) + N log N
T(1) = 1
则该算法的时间复杂度为（ ）。

A. O(N) B. O(NlogN) C. O(Nlog^2N) D. O(N^2)

$T$ 共有 $\log N$ 次递归调用，每次复杂度为 $O(N\log N)$

第 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

普通表达式为中序遍历，后缀表达式为可能的后序遍历

第 8 题

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

A. 32 B. 35 C. 38 D. 41

由四个点构成的简单无向连通图，它们之间只可能有 6 条不同的边。将四个点按序排列，这 6 条边可分为纵横向及斜向两种边。

1. 纵横边有 1 条

   该情况下，无向图有 4 种摆放位置。要使得图连通，斜向边只有 1 种摆法。

   ans += 4 * 1

2. 纵横边有 2 条

   • 两纵/两横

     ans += 2 * 3

   • 一纵一横

     ans += 4 * 2

3. 纵横边有 3 条

   ans += 4 * 4

4. 纵横边有 4 条

   ans += 1 * 4

第 9 题

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

A. 60 B. 84 C. 96 D. 120

| 0 | 0 | 0 | 0 | 0 | 0 | 0 |

插板法。考虑在七个名额间插入 3 个板子，将它们隔成 4 份。插板的方案数即为分配方案数。
$$
C_{8+3-1}^{3}=120
$$

第 10 题

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

A. 1/2 B. 2/3 C. (√5 − 1)/2 D. 1

还是不会

第 11 题

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

A. n^2 B. nlogn C. 2n D. 2n-1

构造 A、B 分别为 [1,3,5,7…] [2,4,6,8,…] 此时需要 2n-1 次比较

第 12 题

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

1
2
3
4
5
6
7
8
9
10

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

正确的填空顺序是（ ）。

A. b, c, a B. c, b, a C. c, a, b D. a, b, c

如果 X 和 Y 重量不等，则不合格的硬币在 X ∪ Y 中；否则在 Z 中。

第 13 题

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

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

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]} + aij

数字三角形动态规划。

$f[i][j]=max(f[i-1][j],f[i-1][j-1])+a[i][j]$

第 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	航班2	航班3
准点	0.9	0.8	0.9
晚点	0.1	0.2	0.1

枚举。共 8 种情况。

第 15 题

欢乐喷球：儿童游乐场有个游戏叫“欢乐喷球”，正方形场地中心能不断喷出彩色乒乓球，以场地中心为圆心还有一 个圆形轨道，轨道上有一列小火车在匀速运动，火车有六节车厢。假设乒乓球等概率落到正方形场地的每个地点，包括火车车厢。小朋友玩这个游戏时，只能坐在同一个火车车厢里，可以在自己的车厢里捡落在该车厢内的所有乒乓球，每个人每次游戏有三分钟时间，则一个小朋友独自玩一次游戏期望可以得到（ ）个乒乓球。假设乒乓球喷出的速度为 2 个/秒，每节车厢的面积是整个场地面积的 1/20。

A. 60 B. 108 C. 18 D. 20

$$
2360/20=18
$$

第 16 题

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

A. 冒泡排序 B. 快速排序 C. 归并排序 D. 堆排

	期望复杂度	最劣复杂度	最优复杂度	是否稳定
冒泡排序	/	$O(n^2)$	$O(n^2)$	稳定
插入排序	/	$O(n^2)$	$O(n)$	稳定
选择排序	/	$O(n^2)$	$O(n^2)$	不稳定
快速排序	$O(n\log n)$	$O(n^2)$	/	不稳定
归并排序	/	$O(n\log n)$	$O(n\log n)$	稳定
堆排序	/	$O(n\log n)$	$O(n\log n)$	不稳定
基数排序	/	$O(nd)$	$O(nd)$	稳定
希尔排序	/	$O(n\log^2 n)$	$O(n^{3/2})$	不稳定

第 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

略

第 18 题

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

A. 快速排序 B. 堆排序 C. 希尔排序 D. 插入排序

见 第 16 题

第 19 题

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

A. 汇编语言 B. C++ C. Fortran D. Java

面向对象语言：simula 67, Smalltalk, EIFFEL, C++, Java, C# 等

第 20 题

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

A. 奥斯卡奖 B. 图灵奖 C. 诺贝尔奖 D. 王选奖

图灵奖（英语：ACM A.M. Turing Award），又译杜林奖、A.M.图灵奖，是计算机协会（ACM）于1966年设立的奖项，专门奖励对计算机事业作出重要贡献的个人。其名称取自世界计算机科学的先驱、英国科学家、曼彻斯特大学教授艾伦·图灵（A.M. Turing），这个奖设立目的之一是纪念这位现代计算机科学的奠基者。获奖者必须是在计算机领域具有持久而重大的先进性的技术贡献。大多数获奖者是计算机科学家。是计算机界最负盛名的奖项，有“计算机界诺贝尔奖”之称。——中文维基百科

中国计算机学会王选奖 是中国计算机学会于2005年起设立的奖项。该奖项最初名为中国计算机学会创新奖，2006年起更为现名，以纪念著名计算机科学家王选。——中文维基百科

第 21 题

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

模拟即可。略

第 22 题

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

最小割=最大流，易得最大流为 4。

模拟，共 9 种不同的方案。

第 23 题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

#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
输出：_____

大 模 拟

推出来 15

第 24 题

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

#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
输出：____

小套路题。构造数字幻方，并输出最上方一行。

第 25 题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

#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
输出：_____

小套路题。归并排序求逆序对。

第 26 题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#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
输出 1：（2 分）
输入 2：2017 1014
输出 2：（3 分）
输入 3：987 321
输出 3：____（3 分）

样例 1：构造两个数列 [1,2,3,4,3,2,1,2,3,4,3,2,1,…], [1,2,3,2,1,2,3,2,1,…]。求这两个数列最靠前的位置，使得 $a_i=1,b_i=1$或$a_i=x,b_i=1$或$a_i=1,b_i=x$或$a_i=x,b_i=y$。

第 27 题

（大整数除法）给定两个正整数p和q，其中p不超过10100， q不超过100000， 求 p 除以 q 的商和余数。（第一空 2 分，其余 3 分） 输入：第一行是 p 的位数 n，第二行是正整数 p，第三行是正整数 q。 输出：两行，分别是 p 除以 q 的商和余数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

#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;
}

​

第 28 题

（最长路径）给定一个有向无环图，每条边长度为 1，求图中的最长路径长度。（第五空 2 分，其余 3 分） 输入：第一行是结点数 n（不超过 100）和边数 m，接下来 m 行，每行两个整数 a， b，表示从结点 a 到结点 b 有一条有向边。结点标号从 0 到(n-1)。 输出：最长路径长度。 提示：先进行拓扑排序，然后按照拓扑序计算最长路径。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

#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;
}

DAG 上的动态规划。
$$
\text{len[u]}=\max{\text{len[v]}+1},(v,u)\in E
$$