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

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

自由练习

模拟考试

我的成绩

第1题

在计算机内部用来传送、存贮、加工处理的数据或指令都是以（   ）形式进行的。

共 1.5 分　

第2题

下列说法正确的是（   ）。  

共 1.5 分　

第3题

与二进制小数0.1相等的十六进制数是（   ）。

共 1.5 分　

第4题

下面有四个数据组，每个组各有三个数据，其中第一个数据为八进制数，第二个数据为 十进制数，第三个数据为十六进制数。这四个数据组中三个数据相同的是（   ）。

共 1.5 分　

第5题

线性表若采用链表存储结构，要求内存中可用存储单元地址（   ）。

共 1.5 分　

第6题

今有一空栈S，对下列待进栈的数据元素序列a,b,c,d,e,f依次进行进栈，进栈，出栈， 进栈，进栈，出栈的操作，则此操作完成后，栈S的栈顶元素为（   ）。

共 1.5 分　

第7题

前序遍历序列与后序遍历序列相同的二叉树为（   ）。

共 1.5 分　

第8题

如果根的高度为1，具有61个结点的完全二叉树的高度为（   ）。

共 1.5 分　

第9题

6个顶点的连通图的最小生成树，其边数为（   ）。

共 1.5 分　

第10题

设某算法的计算时间表示为递推关系式T(n) = T(n - 1) + n（n为正整数）及T(0) = 1，则 该算法的时间复杂度为（   ）。

共 1.5 分　

第11题

具有n个顶点，e条边的图采用邻接表存储结构，进行深度优先遍历和广度优先遍历运 算的时间复杂度均为（   ）。

共 1.5 分　

第12题

在数据压缩编码的应用中，哈夫曼（Huffman）算法是一种采用了（   ）思想的算法

共 1.5 分　

第13题

双向链表中有两个指针域，llink和rlink，分别指回前驱及后继，设p指向链表中的 一个结点，q指向一待插入结点，现要求在p前插入q，则正确的插入为（   ）。

共 1.5 分　

第14题

对图G中各个结点分别指定一种颜色，使相邻结点颜色不同，则称为图G的一个正常 着色。正常着色图G所必需的最少颜色数，称为G的色数。那么下图的色数是（   ）。

共 1.5 分　

第15题

在NOI系列赛事中参赛选手必须使用由承办单位统一提供的设备。下列物品中不允许选 手自带的是（   ）。

共 1.5 分　

第16题

在NOI系列赛事中参赛选手必须使用由承办单位统一提供的设备。下列物品中不允许选 手自带的是（   ）。


共 1.5 分　

第17题

下列属于视频文件格式的有（   ）。


共 1.5 分　

第18题

下列选项不是正确的IP地址的有（   ）。


共 1.5 分　

第19题

下列有关树的叙述中，叙述正确的有（   ）。


共 1.5 分　

第20题

以下图中一定可以进行黑白染色的有（   ）。（黑白染色：为各个结点分别指定黑白 两种颜色之一，使相邻结点颜色不同。）


共 1.5 分　

第21题

在 1 和 2015 之间（包括 1 和 2015 在内）不能被 4、5、6 三个数任意一个数整除的数有_____个。

共 5 分　

第22题

结点数为 5 的不同形态的二叉树一共有_____种。（结点数为 2 的二叉树一共有 2 种：一种是根结点和左儿子，另一种是根结点和右儿子。）

共 5 分　

第23题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;
 
struct point{
    int x;
    int y;
};
 
int main()
{
    struct EX{
        int a;
        int b;
        point c;
    }e;
    e.a=1;
    e.b=2;
    e.c.x=e.a+e.b;
    e.c.y=e.a*e.b;
    cout<<e.c.x<<','<<e.c.y<<endl;
    return 0;
}

输出：（ ）

共 8 分　

第24题

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;
 
void fun(char *a,char *b)
{
    a=b;
    (*a)++;
}
 
int main()
{
    char c1,c2,*p1,*p2;
    c1='A';
    c2='a';
    p1=&c1;
    p2=&c2;
    fun(p1,p2);
    cout<<c1<<c2<<endl;
    return 0;
}

输出：（ ）

共 8 分　

第25题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;
int main()
{
    int len,maxlen;
    string s,ss;
    maxlen=0;
    do
    {
        cin>>ss;
        len=ss.length();
        if(ss[0]=='#')break;
        if(len>maxlen)
        {
            s=ss;
            maxlen=len;
        }
    }while(true);
    cout<<s<<endl;
    return 0;
}

输入：

I

am

a

citizen

of

China

#

输出：（ ）


共 8 分　

第26题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;
 
int fun(int n,int fromPos,int toPos)
{
    int t,tot;
    if(n==0)return 0;
    for(t=1;t<=3;t++)
        if(t!=fromPos && t != toPos)break;
    tot=0;
    tot+=fun(n-1,fromPos,t);
    tot++;
    tot+=fun(n-1,t,toPos);
    return tot;
}
int main()
{
    int n;
    cin>>n;
    cout<<fun(n,1,3)<<endl;
    return 0;
}

输入：5

输出：（ ）


共 8 分　

第27题

(双子序列最大和)给定一个长度为n(3≤n≤1000) 的整数序列，要求从中选出两个连续子序列，使得这两个连续子序列的序列和之和最大，最终只需输出这个最大和。一个连续子序列的序列和为该连续子序列中所有数之和。要求：每个连续子序列长度至少为 1，且两个连续子序列之间至少间隔 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
#include <iostrea m>
using namespace std;
const int MAXN = 1000;
int n, i, ans, sum;
int x[MAXN];
int lmax[MAXN];
// lmax[i] 为仅含 x[i] 及 x[i] 左侧整数的连续子序列的序列和中，最大的序列和
int rmax[MAXN];
// rmax[i] 为仅含 x[i] 及 x[i] 右侧整数的连续子序列的序列和中，最大的序列和
 
int main() {
    cin >> n;
    for (i = 0; i < n; i++) cin >> x[i];
    lmax[0] = x[0] ;
    for (i = 1; i < n; i++)
        if (lmax[i - 1] <= 0)
            lmax[i] = x[i];
        else
            lmax[i] = lmax[i - 1] + x[i];
    for (i = 1; i < n; i++)
        if (lmax[i] < lmax[i - 1])
            lmax[i] = lmax[i - 1];
    ①;
    for (i = n - 2; i >= 0; i --)
        if (rmax[i + 1] <= 0)
            ②;
        else
            ③;
    for (i = n - 2; i >= 0; i --)
        if (rmax[i] < rmax[i + 1])
            ④;
    ans = x[ 0] + x [2];
    for (i = 1; i < n - 1; i++) {
        sum = ⑤;
        if (sum > ans)
            ans = sum;
    }
    cout << ans << endl;
    return 0;
}


共 14 分　

第28题

(最短路径问题)无向连通图 G 有 n 个结点，依次编号为 0,1,2,…,(n−1)。用邻接矩阵的形式给出每条边的边长,要求输出以结点 0 为起点出发,到各结点的最短路径长度。

使用 Dijkstra 算法解决该问题：

利用 dist 数组记录当前各结点与起点的已找到的最短路径长度;

每次从未扩展的结点中选取 dist 值最小的结点 v 进行扩展，更新与 v 相邻的结点的 dist 值；

不断进行上述操作直至所有结点均被扩展，此时 dist 数据中记录的值即为各结点与起点的最短路径长度。

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
#include <iostream>
using namespace std;
const int MAXV = 100;
int n, i , j, v;
int w[MAXV][MAXV]; // 邻接矩阵，记录边长
// 其中 w[i][j] 为连接结点 i 和结点 j 的无向边长度，若无边则为 -1
int dist[MAXV];
int used[MAXV]; // 记录结点是否已扩展（0：未扩展；1：已扩展）
int main() {
    cin >> n;
    for (i = 0; i < n; i+ +)
        for (j = 0; j < n; j++)
            cin >> w[i][j];
    dist[0] = 0;
    for (i = 1; i < n; i+ +)
        dist[i] = -1;
    for (i = 0; i < n; i+ +)
        used[i] = 0;
    while (true) {
        ① ;
        for (i = 0; i < n; i++)
            if (used[i] != 1 && dist[i] != -1 && (v == -1 || ② ))
                ③ ;
        if(v == -1)
            break;
        ④ ;
        for (i = 0; i < n; i++)
            if (w[v][i] != -1 && (dist[i] == -1 || ⑤ ))
                dist[i] = dist[v] + w[v][i];
    }
    for (i = 0; i < n; i++)
        cout << dist[i] << endl;
    return 0;
}


共 14 分　

试卷信息

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