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

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

自由练习

模拟考试

我的成绩

第1题

一个 32 位整型变量占用（  ）个字节。

共 1.5 分　

第2题

二进制数 11.01 在十进制下是（ ）。

共 1.5 分　

第3题

下面的故事与（ ）法有着异曲同工之妙。
从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：从前有座山，山里有座庙，庙里有个老和尚给小和尚讲故事……

共 1.5 分　

第4题

1948 年，（ ）将热力学中的熵引入信息通信领域，标志着信息论研究的开端。

共 1.5 分　

第5题

已知一棵二叉树有 2013 个节点，则其中至多有（ ）个节点有 2 个子节点。

共 1.5 分　

第6题

在一个无向图中，如果任意两点之间都存在路径相连，则称其为连通图。下图是一个有 5 个顶点、8 条边的连通图。若要使它不再是连通图，至少要删去其中的（ ）条边。

QQ截图20210125135836.png

共 1.5 分　

第7题

斐波那契数列的定义如下： F1=1，F2=1， Fn=Fn-1+Fn-2（n≥3）。如果用下面的函数计算斐波 那契数列的第 n 项，则其时间复杂度为（  ）。

1
2
3
4
5
6
int F(int n){
    if (n <= 2)
        return 1;
    else
        return F(n - 1) + F(n - 2);
}


共 1.5 分　

第8题

二叉查找树具有如下性质：每个节点的值都大于其左子树上所有节点的值、小于其右子树 上所有节点的值。那么，二叉查找树的（  ）是一个有序序列。

共 1.5 分　

第9题

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

共 1.5 分　

第10题

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

共 1.5 分　

第11题

二分图是指能将顶点划分成两个部分，每一部分内的顶点间没有边相连的简单无向图。那 么 12 个顶点的二分图至多有（  ）条边。

共 1.5 分　

第12题

（  ）是一种通用的字符编码，它为世界上绝大部分语言设定了统一并且唯一的二进制 编码，以满足跨语言、跨平台的文本交换。目前它已经收录了超过十万个不同字符。

共 1.5 分　

第13题

把 64 位非零浮点数强制转换成 32 位浮点数后，不可能（  ）。

共 1.5 分　

第14题

对一个 n 个顶点、 m条边的带权有向简单图用 Dijkstr 算法计算单源最短路时，如果不使 用堆或其它优先队列进行优化，则其时间复杂度为（  ）。

共 1.5 分　

第15题

T(n) 表示某个算法输入规模为 n 时的运算次数。如果 T(1) 为常数，且有递归式 T(n)=2*T(n / 2)+2n ，那么 T(n) = （  ）。

共 1.5 分　

第16题

下列程序中， 正确计算 1，2，, ， 100 这 100 个自然数之和 sum（初始值为 0）的是（  ）。

Snipaste_2021-01-25_14-31-58.png


共 1.5 分　

第17题

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


共 1.5 分　

第18题

以 A0 作为起点，对下面的无向图进行深度优先遍历时（遍历的顺 序 与 顶 点 字 母 的 下 标 无 关 ）， 最 后 一 个 遍 历 到 的 顶 点 可 能 是 （  ）。

Snipaste_2021-01-25_14-33-14.png


共 1.5 分　

第19题

（ ）属于 NP 类问题。


共 1.5 分　

第20题

CCF NOIP 复赛考试结束后，因（ ）提出的申诉将不会被受理。


共 1.5 分　

第21题

某系统自称使用了一种防窃听的方式验证用户密码。密码是 n 个数 s1，s2，, ， sn，均为 0 或 1。该系统每次随机生成 n 个数 a1，a2，, ， an，均为 0 或 1，请用户回答 （s 1a1+s 2 a2+… +s n an）除以 2 的余数。如果多次的回答总是正确，即认为掌握密码。该系统认为，即使问 答的过程被泄露，也无助于破解密码——因为用户并没有直接发送密码。然而，事与愿违。 例如，当 n=4 时，有人窃听了以下 5 次问答：

Snipaste_2021-01-25_14-35-15.png

就破解出了密码 s1= _ ， s2= _ ，s3= _， s4= _。(结果之间用空格隔开即可）

共 5 分　

第22题

现有一只青蛙，初始时在 n 号荷叶上。当它某一时刻在 k 号荷叶上时，下一时刻将等概率 地随机跳到 1，2，, ， k 号荷尔蒙叶之一上，直至跳到 1 号荷叶为止。当 n=2 时，平均一 共跳 2 次；当 n=3 时，平均一共跳 2.5 次。则当 n=5 时，平均一共跳 _____次。

Snipaste_2021-01-25_14-36-59.png

共 5 分　

第23题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <string>
using namespace std;
int main() {
    string str;
    cin>>str;
    int n = str.size();
    bool isPlalindrome = true;
    for (int i = 0;i < n/2;i++) {
        if (str[i] != str[n-i-1]) isPlalindrome = false;
    }
    if (isPlalindrome)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
}

输入：

abceecba

输出：________


共 8 分　

第24题

1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
using namespace std;
int main(){
    int a, b, u, v, i, num;
    cin>>a>>b>>u>>v;
    num = 0;
    for (i = a;i <= b;i++)
        if (((i % u) == 0) || ((i % v) == 0))
            num++;
    cout<<num<<endl;
    return 0;
}

输入：

1 1000 10 15

输出：________


共 8 分　

第25题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
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;
}

输入：

8

3 2 5 11 12 7 4 10

输出：________


共 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
28
29
30
31
32
33
#include <iostream>
#include <cstring>
using namespace std;
const int SIZE = 100;
int n, m, p, a[SIZE][SIZE], count;
void colour(int x, int y){
    count++;
    a[x][y] = 1;
    if ((x > 1) && (a[x - 1][y] == 0)) colour(x - 1, y);
    if ((y > 1) && (a[x][y - 1] == 0)) colour(x, y - 1);
    if ((x < n) && (a[x + 1][y] == 0)) colour(x + 1, y);
    if ((y < m) && (a[x][y + 1] == 0)) colour(x, y + 1);
}
int main(){
    int i, j, x, y, ans;
    memset(a, 0, sizeof(a));
    cin>>n>>m>>p;
    for (i = 1;i <= p;i++) {
        cin>>x>>y;
        a[x][y] = 1;
    }
    ans = 0;
    for (i = 1;i <= n;i++)
        for (j = 1;j <= m;j++)
            if (a[i][j] == 0) {
                count = 0;
                colour(i, j);
                if (ans < count)
                    ans = count;
            }
    cout<<ans<<endl;
    return 0;
}

输入：

6 5 9

1 4

2 3

2 4

3 2

4 1

4 3

4 5

5 4

6 4

输出：________


共 8 分　

第27题

（序列重排）全局数组变量 a 定义如下： 

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。有一种朴素的算法可以实现这一需求，其时间复杂度为 O(n) 、空间复杂度为 O(n) ：

1
2
3
4
5
6
7
8
9
void swap1(int p){
int i, j, b[SIZE];
    for (i = 1;i <= p;i++)
        b[①] = a[i];
    for (i = p + 1;i <= n;i++)
        b[i - p] = a[i];
    for (i = 1;i <= n;i++)
        a[i] = b[i];
}

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

1
2
3
4
5
6
7
8
9
void swap2(int p){
    int i, j, temp;
    for (i = p + 1;i <= n;i++) {
        temp = a[i];
        for (j = i;j >=②;j--)
            a[j] = a[j - 1];
        ③ = temp;
        }
}

事实上，还有一种更好的算法，时间复杂度为O(n)、空间复杂度为O(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
void swap3(int p){
    int start1, end1, start2, end2, i, j, temp;
    start1 = 1;
    end1 = p;
    start2 = p + 1;
    end2 = n;
    while (true) {
        i = start1;
        j = start2;
        while ((i <= end1) && (j <= end2)) {
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
            i++;
            j++;
        }
        if (i <= end1)
            start1 = i;
        else if (④) {
            start1 =⑤;
            end1 =⑥;
            start2 = j;
        }else
            break;
    }
}


共 15 分　

第28题

（两元序列）试求一个整数序列中，最长的仅包含两个不同整数的连续子序列。如有多个子 序列并列最长，输出任意一个即可。例如，序列“ 1 1 2 3 2 3 2 3 3 1 1 1 3 1 ”中，有 两段满足条件的最长子序列，长度均为 7，分别用下划线和加粗斜体标出。

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
58
59
60
#include <iostream>
using namespace std;
int main(){
    const int SIZE = 100;
    int n, i, j, a[SIZE], cur1, cur2, count1, count2,
    ans_length, ans_start, ans_end;
    //cur1, cur2 分别表示当前子序列中的两个不同整数
    //count1, count2 分别表示 cur1, cur2 在当前子序列中出现的次数
    cin>>n;
    for (i = 1;i <= n;i++)
        cin>>a[i];
    i = 1;
    j = 1;
    //i, j 分别表示当前子序列的首尾，并保证其中至多有两个不同整数
    while ((j <= n) && (a[j] == a[i]))
        j++;
    cur1 = a[i];
    cur2 = a[j];
    count1 =①;
    count2 = 1;
    ans_length = j - i + 1;
    while (j < n) {
        j++;
        if (a[j] == cur1)
            count1++;
        else if (a[j] == cur2)
            count2++;
        else {
            if (a[j - 1] ==② ) {
                while (count2 > 0) {
                    if (a[i] == cur1)
                        count1--;
                    else
                        count2--;
                    i++;
                }
                cur2 = a[j];
                count2 = 1;
            }else {
                while (count1 > 0) {
                    if (a[i] == cur1)
                        ③ ;
                    else
                        ④ ;
                    i++;
                }
                ⑤ ;
                count1 = 1;
            }
        }
        if (ans_length < j - i + 1) {
            ans_length = j - i + 1;
            ans_start = i;
            ans_end = j;
        }
    }
    for (i = ans_start;i <= ans_end;i++)
        cout<<a[i]<<' ';
    return 0;
}


共 13 分　

试卷信息

题量: 28 道
总分: 100 分 
一、单项选择题（1-15 共 15 题 ）；
二、不定项选择题（15-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题