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

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

自由练习

模拟考试

我的成绩

第1题

目前计算机芯片（集成电路）制造的主要原料是（ ），它是一种可以在沙子中提炼出的物质。

共 1.5 分　

第2题

（    ）是主要用于显示网页服务器或者文件系统的HTML文件的内容，并让用户与这些文件交互的一种软件。

共 1.5 分　

第3题

目前个人电脑的（     ）市场占有率最靠前的厂商包括Intel、AMD等公司。

共 1.5 分　

第4题

无论是TCP/IP模型还是OSI模型，都可以视为网络的分层模型，每个网络协议都会被归入某一层中。如果用现实生活中的例子来比喻这些“层”，以下最恰当的是（    ）。

中国公司的经理与波兰公司的经理交互商业文件

国际会议中，每个人都与他国地位对等的人直接进行会谈

军队发布命令

体育比赛中，每一级比赛的优胜者晋级上一级比赛


共 1.5 分　

第5题

如果不在快速排序中引入随机化，有可能导致的后果是（    ）。

共 1.5 分　

第6题

1946年诞生于美国宾夕法尼亚大学的ENIAC属于（    ）计算机。  

共 1.5 分　

第7题

在程序运行过程中，如果递归调用的层数过多，会因为（ ）引发错误。

共 1.5 分　

第8题

地址总线的位数决定了CPU可直接寻址的内存空间大小，例如地址总线为16位，其最大的可寻址空间为64KB。如果地址总线是32位，则理论上最大可寻址的内存空间为（      ）。 

共 1.5 分　

第9题

以下不属于3G（第三代移动通信技术）标准的是（     ）。

共 1.5 分　

第10题

仿生学的问世开辟了独特的科学技术发展道路。人们研究生物体的结构、功能和工作原理，并将这些原理移植于新兴的工程技术中。以下关于仿生学的叙述，错误的是（    ）

共 1.5 分　

第11题

如果对于所有规模为n的输入，一个算法均恰好进行（     ）次运算，我们可以说该算法的时间复杂度为O（2^n） 。 


共 1.5 分　

第12题

从顶点A0出发，对有向图（    ）进行广度优先搜索（BFS）时，一种可能的遍历顺序是A0，A1,A2，A3，A4 。

QQ截图20210124192246.png


共 1.5 分　

第13题

如果一个栈初始时为空，且当前栈中的元素从栈顶到栈底依次为a，b，c（如右图所示），另有元素d已经出栈，则可能的入栈顺序是（     ）。

QQ截图20210121143933.png


共 1.5 分　

第14题

在计算机显示器所使用的RGB颜色模型中，（    ）属于三原色之一。


共 1.5 分　

第15题

一棵二叉树一共有19个节点，其叶子节点可能有（    ）个。 


共 1.5 分　

第16题

已知带权有向图G上的所有权值均为正整数，记顶点u到顶点v的最短路径的权值为d(u,v)。若v1v2v3v4v5 是图G上的顶点，且它们之间两两都存路径可达，则以下说法正确的有（   ）。


共 1.5 分　

第17题

逻辑异或⊕是一种二元运算，其真值表如下所示。 

QQ截图20210124193035.png

以下关于逻辑异或的性质，正确的有（     ）。 



共 1.5 分　

第18题

十进制下的无限循环小数（不包括循环节内的数字均为0成均为9的平凡情况），在二进制下有可能是（    ）。 


共 1.5 分　

第19题

（     ）是目前互联网上常用的E-mail服务协议。


共 1.5 分　

第20题

以下关于计算复杂度的说法中，正确的有（    ）。


共 1.5 分　

第21题

本题中，我们约定布尔表达式只能包含 p, q, r三个布尔变量，以及“与”(∧)、“或”(∨)、“非”(¬)三种布尔运算。如果无论 p,q,r如何取值，两个布尔表达式的值总是相同，则称它们等价。

例如，(p∨q)∨r 和 p∨(q∨r) 等价，p∨¬p 和 q∨¬q 也等价；而 p∨q 和 p∧q 不等价。那么，两两不等价的布尔表达式最多有____个。


共 5 分　

第22题

对于一棵二叉树，独立集是指两两互不相邻的节点构成的集合。例如，图 1 有 5 个不同的独立集（1 个双点集合、3 个单点集合、1 个空集），图 2 有 14 个不同的独立集。那么，图 3 有____个不同的独立集。

QQ截图20210124193912.png

共 5 分　

第23题

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>
using namespace std;
int n, i, temp, sum, a[100];
int main(){
    cin>>n;
    for (i = 1;i <= n;i++)
        cin>>a[i];
    for (i = 1;i <= n - 1;i++)
        if (a[i] > a[i + 1]) {
            temp = a[i];
            a[i] = a[i + 1];
            a[i + 1] = temp;
        }
    for (i = n;i >= 2;i--)
        if (a[i] < a[i - 1]) {
            temp = a[i];
            a[i] = a[i - 1];
            a[i - 1] = temp;
        }
    sum = 0;
    for (i = 2;i <= n - 1;i++)
        sum += a[i];
    cout<<sum / (n - 2)<<endl;
    return 0;
}

输入：

8

40 70 50 70 20 40 10 30

输出：____

共 8 分　

第24题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
using namespace std;
int n, i, ans;
int gcd(int a, int b){
    if (a % b == 0)
        return b;
    else
        return gcd(b, a%b);
}
int main(){
    cin>>n;
    ans = 0;
    for (i = 1;i <= n;i++)
        if (gcd(n,i) == i)ans++;
    cout<<ans<<endl;
}

输入：120

输出：____

共 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
#include <iostream>
using namespace std;
const int SIZE = 20;
int data[SIZE];
int n, i, h, ans;
void merge(){
    data[h-1] = data[h-1] + data[h];
    h--;
    ans++;
}
int main(){
    cin>>n;
    h = 1;
    data[h] = 1;
    ans = 0;
    for (i = 2;i <= n;i++){
        h++;
        data[h] = 1;
        while (h > 1 && data[h] == data[h-1])
            merge();
    }
    cout << ans << endl;
}

1、输入：8

输出：____

2、输入：2012

输出：____

共 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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <string>
using namespace std;
int lefts[20], rights[20], father[20];
string s1, s2, s3;
int n, ans;
void calc(int x, int dep){
    ans = ans + dep*(s1[x] - 'A' + 1);
    if (lefts[x] >= 0) calc(lefts[x], dep+1);
    if (rights[x] >= 0) calc(rights[x], dep+1);
}
void check(int x){
    if (lefts[x] >= 0) check(lefts[x]);
    s3 = s3 + s1[x];
    if (rights[x] >= 0) check(rights[x]);
}
void dfs(int x, int th){
    if (th == n){
        s3 = "";
        check(0);
        if (s3 == s2){
            ans = 0;
            calc(0, 1);
            cout<<ans<<endl;
        }
        return;
    }
    if (lefts[x] == -1 && rights[x] == -1){
        lefts[x] = th;
        father[th] = x;
        dfs(th, th+1);
        father[th] = -1;
        lefts[x] = -1;
    }
    if (rights[x] == -1){
        rights[x] = th;
        father[th] = x;
        dfs(th, th+1);
        father[th] = -1;
        rights[x] = -1;
    }
    if (father[x] >= 0)dfs(father[x], th);
}
int main(){
    cin>>s1;
    cin>>s2;
    n = s1.size();
    memset(lefts, -1, sizeof(lefts));
    memset(rights, -1, sizeof(rights));
    memset(father, -1, sizeof(father));
    dfs(0, 1);
}

输入：

ABCDEF

BCAEDF

输出：____

共 8 分　

第27题

（排列数）输入两个正整数 n,m(1≤n≤20,1≤m≤n)，在 1~n 中任取 m 个数，按字典序从小到大输出所有这样的排列。

例如输入：

3 2

输出：

1  2

1  3

2  1

2  3

3  1

3  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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<iostream>
#include<cstring>
using namespace std;
const int SIZE = 25;
bool used[SIZE];
int data[SIZE];
int n, m, i, j, k;
bool flag;
int main(){
    cin>>n>>m;
    memset(used, false, sizeof(used));
    for (i = 1; i <= m; i++){
        data[i] = i;
        used[i] = true;
    }
    flag = true;
    while (flag){
        for (i = 1; i <= m-1; i++)cout<<data[i]<<"";
        cout << data[m] << endl;
        flag =①;
        for (i = m; i >= 1; i--){
            ②;
            for (j = data[i]+1; j <= n; j++)
                if (!used[j]){
                    used[j] = true;
                    data[i] =③;
                    flag = true;
                    break;
                }
            if (flag){
                for (k = i+1; k <= m; k++)
                    for (j = 1; j <=④; j++)
                        if (!used[j]){
                            data[k] = j;
                            used[j] = true;
                            break;
                        }
                ⑤;
            }
        }
    }
}


共 13 分　

第28题

（壳栈）小 Z 设计了一种新的数据结构“新壳栈”。首先，它和传统的栈一样支持压入、弹出操作。此外，其栈顶的前 c 个元素是它的壳，支持翻转操作。其中，c > 2 是一个固定的正整数，表示壳的厚度。小 Z 还希望，每次操作，无论是压入、弹出还是翻转，都仅用与 c 无关的常数时间完成。聪明的你能帮助她编程实现“新壳栈”吗？

程序期望的实现效果如以下两表所示。其中，输入的第一行是正整数 c，之后每行输入都是一条指令。另外，如遇弹出操作时栈为空，或翻转操作时栈中元素不足 c 个，应当输出相应的错误信息。

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
using namespace std;
const int NSIZE = 100000,CSIZE = 1000;
int n, c, r, tail, head, s[NSIZE], q[CSIZE];
//数组 s 模拟一个栈，n 为栈的元素个数
//数组 q 模拟一个循环队列，tail 为队尾的下标，head 为队头的下标
bool direction, empty;
int previous(int k){
    if (direction)
        return ((k + c - 2) % c) + 1;
    else
        return (k % c) + 1;
}
int next(int k){
    if (direction)
        ①;
    else
        return ((k + c - 2) % c) + 1;
}
void push(){
    int element;
    cin>>element;
    if (next(head) == tail) {
        n++;
        ②;
        tail = next(tail);
    }
    if (empty)
        empty = false;
    else
        head = next(head);
    ③= element;
}
void pop(){
    if (empty) {
        cout<<"Error: the stack is empty!"<<endl;
        return;
    }
    cout<<④<<endl;
    if (tail == head)
        empty = true;
    else {
        head = previous(head);
        if (n > 0) {
            tail = previous(tail);
            ⑤= s[n];
            n--;
        }
    }
}
void reverse(){
    int temp;
    if (⑥== tail) {
        direction = !direction;
        temp = head;
        head = tail;
        tail = temp;
    }else
        cout<<"Error: less than "<<c<<" elements in the stack!"<<endl;
}
int main(){
    cin>>c;
    n = 0;
    tail = 1;
    head = 1;
    empty = true;
    direction = true;
    do{
        cin>>r;
        switch (r) {
            case 1: push();break;
            case 2: pop();break;
            case 3: reverse();break;
        }
    } while (r != 0);
    return 0;
}


共 15 分　

试卷信息

题量: 28 道
总分: 100 分 
一、单项选择题（1-10 共 10 题 ）；
二、不定项选择题（11-20 共 10 题）；
三、问题求解（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题