Dotcpp  >  试卷列表  >  NOIP第二十三届全国青少年信息学奥林匹克联赛初赛试题[2017提高组]

NOIP第二十三届全国青少年信息学奥林匹克联赛初赛试题[2017提高组]

自由练习

模拟考试

我的成绩

第1题

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

共 1.5 分　

第2题

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

共 1.5 分　

第3题

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

共 1.5 分　

第4题

2017年10月1日是星期日，1949年10月1日是( )。

共 1.5 分　

第5题

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

共 1.5 分　

第6题

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

T(N)=2T(N/2)+NlogN

T(1)=1

则该算法的时间复杂度为( )。

共 1.5 分　

第7题

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

共 1.5 分　

第8题

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

共 1.5 分　

第9题

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

共 1.5 分　

第10题

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

共 1.5 分　

第11题

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

共 1.5 分　

第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 中硬币不合格

正确的填空顺序是 ( ) 。


共 1.5 分　

第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]=( )。

共 1.5 分　

第14题

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

共 1.5 分　

第15题

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

共 1.5 分　

第16题

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


共 1.5 分　

第17题

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

共 1.5 分　

第18题

下列算法中，( )是稳定的排序算法。

共 1.5 分　

第19题

以下是面向对象的高级语言的是( )。


共 1.5 分　

第20题

以下和计算机领域密切相关的奖项是( )。


共 1.5 分　

第21题

一个人站在坐标（0，0）处，面朝 x 轴正方向。第一轮，他向前走 1 单位距离，然后右转；第二轮，他向前走 2 单位距离，然后右转；第三轮，他向前走 3 单位距离，然后右转……他一直这么走下去。请问第 2017 轮后，他的坐标是：（___ , ___）。

Snipaste_2021-01-27_21-49-31.png

共 5 分　

第22题

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

Snipaste_2021-01-27_21-50-28.png

共 5 分　

第23题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <cstring>
using namespace std;
int main()
{
    int t[256];
    char s[10];
    int i;
    scanf("%s", s);
    for(i = 0; i < 256; i++) t[i] = 0;
    for(i = 0; i < strlen(s); i++) t[s[i]]++;
    for(i = 0; i < strlen(s); i++)
        if(t[s[i]] == 1) {
            cout << s[i] << endl;
            return 0;
        }
    cout << "no" << endl;
    return 0;
}

输入：

xyzxyw

输出：（ ）


共 8 分　

第24题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>
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;
    scanf("%d%d", &m, &n);
    printf("%d
", g(m, n, 0));
    return  0;
}

输入：

7 3

输出：（ ）

共 8 分　

第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
#include <iostream>
#include <string>
using namespace std;
int main()
{
    string ch;
    int a[200];
    int b[200];
    int n, i, t, res;
    cin >> ch;
    n = ch.length();
    for(i = 0; i < 200; i++) b[i] = 0;
    for(i = 1; i <= n ; i++) {
        a[i] = ch[i-1] - '0';
        b[i] = b[i-1] + a[i];
    }
    res = b[n];
    t = 0;
    for(i = n; i > 0; i--) {
        if(a[i] == 0) t++;
        if(b[i-1] + t < res) res = b[i-1] + t;
    }
    cout << res << endl;
    return 0;
}

输入：

1001101011001101101011110001

输出：（ ）


共 8 分　

第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
#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）输入：

2017 1014

输出：（ ）


共 8 分　

第27题

（快速幂）请完善下面的程序，该程序使用分治法求 xp mod m 的值。

输入：三个不超过 10000 的正整数 x, p, m。

输出：xp mod m 的值。

提示：若 p 为偶数，xp = (x2)p/2；若 p 为奇数，xp = x  (x2)(p-1)/2。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
using namespace std;
int x, p, m, i, result;
int main()
{
    cin >> x >> p >> m;
    result = ①;
    while(②)
    {
        if(p % 2 == 1)
            result = ③;
        p /= 2;
        x = ④;
    }
    cout << ⑤ << endl;
    return  0 ;
}


共 14 分　

第28题

（切割绳子）有 n 条绳子，每条绳子的长度已知且均为正整数。绳子可以以任意正整数长度切割，但不可以连接。现在要从这些绳子中切割出m条长度相同的绳段，求绳段的最大长度是多少。

输入：第一行是一个不超过 100 的正整数 n，第二行是 n 个不超过 10^6的正整数，表示每条绳子的长度，第三行是一个不超过 10^8 的正整数 m。

输出 ：绳段的最大长度，若无法切割，输出 Failed。

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
#include <iostream>
using namespace std;
int n, m, i, lbound, ubound, mid, count;
int  len[100]; //绳子长度
int main()
{
    cin >> n;
    count = 0;
    for (i = 0; i < n; i++) {
        cin >> len[i];
        ①;
    }
    cin >> m;
    if (②) {
        cout << "Failed" << endl;
        return 0;
    }
    lbound = 1 ;
    ubound = 1000000 ;
    while (③) {
        mid = ④;
        count =0 ;
        for (i = 0; i < n; i++ )
            ⑤;
        if (count < m)
            ubound = mid - 1 ;
        else
            lbound = mid ;
    }
    cout << lbound << endl;
    return 0;
}


共 14 分　

试卷信息

题量: 28 道
总分: 100 分 
一、单项选择题（1-15 共 15 题 ）；
二、不定项选择题（16-20 共 5 题）；
三、问题求解（21-22 共 2 题）；
四、阅读程序写结果（23-26 共 4 题）；
五、完善程序（27-28 共2题）。
第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题