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

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

自由练习

模拟考试

我的成绩

第1题

与 16 进制数 A1.2 等值的 10 进制数是（  ）

共 1.5 分　

第2题

一个字节（ byte ）由（ ）个二进制位组成。

共 1.5 分　

第3题

一下逻辑表达式的值恒为真的是（ ）

共 1.5 分　

第4题

Linux 下可执行文件的默认扩展名为（ ）

共 1.5 分　

第5题

如果在某个进制下等式 7*7=41 成立，那么在该进制下等式 12*12= （ ）也成立。

共 1.5 分　

第6题

提出 “存储程序 ”的计算机工作原理的是（ ）。

共 1.5 分　

第7题

前缀表达式 “+3*2+5 12 的值是（ ）

共 1.5 分　

第8题

主存储器的存取速度比中央处理器 （CPU ）的工作速度慢很多， 从而使得后者的效率受到 影响。而根据局部性原理， CPU 所访问的存储单元通常都趋于聚集在一个较小的连续区域 中。于是，为了提高系统整体的执行效率，在 CPU 中引入了（ ）

共 1.5 分　

第9题

完全二叉树的顺序存储方案， 是指将完全二叉树的结点从上至下、 从左至右一次存放到一 个顺序结构的数组中。假定根结点存放在数组的 1 号位置，则第 K 号结点的父结点如果存 在的话，应当存放在数组的（ ）号位置。

共 1.5 分　

第10题

以下竞赛活动中历史最悠久的是（ ）

共 1.5 分　

第11题

元素 R1、R2 、R3 、R4、R5 入栈的顺序为 R1 、R2、R3 、R4 、R5。如果第一个出栈的 是 R3，那么第五个出栈的可能是（ ）。


共 1.5 分　

第12题

Pascal 语言、 C 语言、和 C++ 语言都属于（ ）


共 1.5 分　

第13题

原地排序是指在排序过程中 （除了存储待排序元素以外的） 付诸空间的大小与数据规模无 关的排序算法。一下属于原地排序的有（ ）


共 1.5 分　

第14题

在整数的补码表示法中，以下说法正确的是（ ）


共 1.5 分　

第15题

一颗二叉树的前序遍历序列是 ABCDEFG ，后序遍历序列是 CBFEGDA ，则根结点的左子 树的结点个数可能是（ ）


共 1.5 分　

第16题

在下列 HTML 语句中，可以正确产生一个指向 NOI 官方网站的超链接的是（ ）


共 1.5 分　

第17题

关于拓扑排序，下面说法正确的是（ ）


共 1.5 分　

第18题

一个平面的法线是指与该平面垂直的直线。过点（ 1,1,1 ）、（ 0,3,0 ）、（ 2,0,0 ）的平面 的法线是（ ）


共 1.5 分　

第19题

双向链表中有两个指针域 llink 和 rlink ，分别指向该结点的前驱及后继。设 p 指向链表中 的一个结点，它的左右结点均非空。现要求删除结点 P,则下面语句序列中正确的是（ ）


共 1.5 分　

第20题

今年（ 2010 ）发生的事件有（ ）


共 1.5 分　

第21题

LZW 编码是一种自适应词典编码。在编码的过程中，开始时只有一部基础构造元素的编 码词典， 如果在编码的过程中遇到一个新的词条， 则该词条及一个新的编码会被追加到词典 中，并用于后继信息的编码。 举例说明，考虑一个待编码的信息串：“ xyx yy yy xyx ”。初始词典只有 3 个条目， 第一个为 x,编码为 1；第二个为 y，编码为 2；第三个为空格，编码为 3；于是串“ xyx”的 编码为 1-2-1 （其中 -为编码分隔符），加上后面的一个空格就是 1-2-1-3 。但由于有了一个 空格，我们就知道前面的“ xyx”是一个单词，而由于该单词没有在词典中，我们就可以自 适应的把这个词条添加到词典里，编码为 4，然后按照新的词典对后继信息进行编码，以此 类推。于是，最后得到编码： 1-2-1-3-2-2-3-5-3-4 。 我们可以看到，信息被压缩了。压缩好的信息传递到接受方，接收方也只要根据基础 词典就可以完成对该序列的完全恢复。 解码过程是编码过程的逆操作。 现在已知初始词典的 3 个条目如上述，接收端收到的编码信息为 2-2-1-2-3-1-1-3-4-3-1-2-1-3-5-3-6 ，则解码 后的信息串是” ______________________________________________________________ ”。

共 5 分　

第22题

无向图 G 有 7 个顶点，若不存在奇数条边构成的简单回路，则它至多有 __________ 条 边。

共 5 分　

第23题

记 T 为一队列初始为空现有 n 个总和不超过 32 的正整数依次入队如果无论这些数具 体为何值都能找到一种出队的方式使得存在某个时刻队列 T 中的数之和恰好为 9 那么 n 的最小值是 ________________。

共 5 分　

第24题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdio.h>
#define SIZE 10
int main() 
{
    int data[SIZE], i, j, cnt, n, m;// 定义 // 
    scanf("%d %d\n", &n, &m);// 输入 n 和 m，此处我们输入的是 5 和 2//
    for(i = 1; i <= n; i++)
        scanf("%d", &data[i]);// 再次输入 i 个数 data[1] =96 data[2]=-8 data[3]=0 data[4]=16 data[5]=87//
    for(i = 1; i <= n; i++) 
    { //n=5//
        cnt = 0;
        for(j = 1; j<= n; j++)//n=5 ，data[1] =96 data[2]=-8 data[3]=0 data[4]= 16
        data[5]=87//
        if ((data[i] < data[j]) || (data[j] == data[i] && j< i))// 如果说 data[i]<data[j] ，或者说{data[j] 等于 data[i] ，同时 j 小于 i
        cnt++;//cnt 的数目加 1// 
        if(cnt == m)// 如果说 cnt 等于 m 等于 2，因为 cnt=2 ，即整个程序运行了两遍，也运行两遍，换句话说，只有恰好运行两遍的数字才能满足题意。假设， data[1]=96 ，与
        data[2]=-8 data[3]=0 data[4]= 16 data[5]=87 //比较大小时， 显然为最大， 不能比其他的数小，不满足条件 data[i] < data[j] ，同样， data[2]=-8 ，比它大的数有 3 个也不满足题意，
        data[3]=0 //比它大的数有 4 个，不合题意 data[4]= 16 ，比它大的数恰恰只有两个，满足题意，为所输出 //
        printf("%d\n", data[i]);// 输出 data[i]//
    }
    getch(); //（此语句在 windows 2000 以上系统用 winTC 编译 C 时需要加入，用以暂停查看屏幕）
    return 0;
}

输入： 5 2 

 96 -8 0 16 87 

输出： ______

共 7 分　

第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
#include <stdio.h>
#define SIZE 100
int main()
{
    int na, nb, a[SIZE], b[SIZE], i, j, k;// 定义 //
    scanf("%d\n", &na);// 输入 5,即 na=5//
    for (i = 1; i <= na; i++)
        scanf("%d", &a[i]);// 输入数字， a[1]=1. a[2]=3 a[3]=5 a[4]=7 a[5]=9//
    scanf("%d\n", &nb);// 输入数字 4//
    for (i = 1; i <= nb; i++)
        scanf("%d", &b[i]);// 同理，输入数字 b[1] =2 b[2] =6 b[3] =10 b[4] =14//
    i=1;
    j=1;
    while ((i <= na) && (j <= nb)) 
    {// 当 i 小于等于 na 时，并且 j 小于等于 nb 时候 //
        if (a[i] <= b[j]) 
        {// 如果说 a[i]大于 b[j]//
            printf("%d ", a[i]);// 输出 a[i]//
            i++;//i 增加 1//
        }
        else {
        printf("%d ", b[j]);// 否则输出 b[j]//
        j++;
        }
    }
    if (i <= na)// 如果 i 小于等于 na//
    for (k = i; k<= na; k++)// 循环 //
    printf("%d ", a[k]); //按照上面的循环条件输出数字 //
    if (j <= nb)
    for (k = j; k<= nb; k++)// 同理 //
    printf ("%d ", b[k]); 
    getch();
    return 0;
}

输入： 5

 1 3 5 7 9 

4 

2 6 10 14 

输出：______

共 7 分　

第26题

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;
const int NUM=5;
int r(int n)
{
     int i;
     if(n<=NUM)
     return 0;
     for(i=1;i<=NUM;i++)
     if( r(n-i)<0)
     return i;
     return -1;
}
int main()
{
     int n; 
     cin>>n;
     cout<<r(n)<<endl;
     return 0;
}

输入： 16 

输出： ______________ 

共 7 分　

第27题

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
#include<iostream>
#include<cstring>
using namespace std;
const int SIZE=100;
int n,m,r[SIZE];
bool map[SIZE][SIZE],found;
bool successful()
{
 int i;
 for(i=1;i<=n;i++)
 if(!map[r[i]][r[i%n+1]])
 return false;
 return true;
}
void swap(int *a,int *b)
{
 int t;
 t=*a;
 *a=*b;
 *b=t;
}
void perm(int left,int right)
{
 int i;
 if(found)
 return ;
 if(left>right)
 { 
 if(successful())
 {
 for(i=1;i<=n;i++)
 cout<<r[i]<<' ';
 found=true;
 }
 return ; 
 }
 for(i=left;i<=right;i++)
 {
 swap(r+left,r+i);
 perm(left+1,right);
 swap(r+left,r+i);
 }
}
int main()
{
 int x,y,i;
 cin>>n>>m;
 memset(map,false,sizeof(map));
 for(i=1;i<=m;i++)
 {
 cin>>x>>y;
 map[x][y]=true;
 map[y][x]=true;
 }
 for(i=1;i<=n;i++)
 r[i]=i;
 found=false;
 perm(1,n);
 if(!found)
 cout<<"No solution!"<<endl; 
 return 0;
}

输入： 9 12 

1 2 

2 3 

3 4 

4 5

5 6

6 1 

1 7

2 7

3 8 

4 8 

5 9 

6 9 

输出： _________

共 7 分　

第28题

( 过河问题 ) 在一个月黑风高的夜晚 , 有一群人在河的右岸 , 想通过唯一的一根独木桥走到 河的左岸 . 在伸手不见五指的黑夜里 , 过桥时必须借照灯光来照明 , 不幸的是 , 他们只有一盏灯 . 另外, 独木桥上最多能承受两个人同时经过 , 否则将会坍塌 . 每个人单独过独木桥都需要一定 的时间 , 不同的人要的时间可能不同 . 两个人一起过独木桥时 , 由于只有一盏灯 , 所以需要的时 间是较慢的那个人单独过桥所花费的时间 . 现在输入 N(2<=N<1000)和这 N 个人单独过桥需要 的时间 , 请计算总共最少需要多少时间 , 他们才能全部到达河左岸 . 

例如, 有 3 个人甲、乙、丙 , 他们单独过桥的时间分别为 1、2、4, 则总共最少需要的时 间为 7. 具体方法是 : 甲、乙一起过桥到河的左岸 , 甲单独回到河的右岸将灯带回 , 然后甲、丙 在一起过桥到河的左岸 , 总时间为 2+1+4=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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<iostream>
#include<cstring>
using namespace std;
const int SIZE=100;
const int INFINITY = 10000;
const bool LEFT=true;
const bool RIGHT =false; 
const bool LEFT_TO_RIGHT=true;
const bool RIGHT_TO_LEFT=false;
int n,hour[SIZE];
bool pos[SIZE];
int max(int a,int b)
{
 if(a>b)
 return a;
 else
 return b;
} 
int go(bool stage)
{
 int i,j,num,tmp,ans;
 if(stage==RIGHT_TO_LEFT)
 {
 num=0;
 ans=0;
 for(i=1;i<=n;i++)
 if(pos[i]==RIGHT)
 {
 num++;
 if( hour[i]>ans)
 ans=hour[i];
 }
 if( ① ) 
 return ans;
 ans=INFINITY;
 for(i=1;i<=n-1;i++)
 if(pos[i]==RIGHT) 
 for(j=i+1;j<=n;j++)
 if(pos[j]==RIGHT)
 {
 pos[i]=LEFT;
 pos[j]=LEFT;
 tmp=max(hour[i],hour[j])+ ② ;
 if(tmp<ans)
 ans=tmp;
 pos[i]=RIGHT;
 pos[j]=RIGHT;
 }
 return ans;
 }
 if(stage==LEFT_TO_RIGHT)
 {
 ans=INFINITY;
 for(i=1;i<=n;i++)
 if( ③ )
 {
 pos[i]=RIGHT;
 tmp= ④ ;
 if(tmp<ans)
 ans=tmp;
⑤ ;
 }
 return ans;
 }
 return 0;
}
int main() 
{
 int i;
 cin>>n;
 for(i=1;i<=n;i++)
 {
 cin>>hour[i];
 pos[i]=RIGHT;
 }
 cout<<go[RIGHT_TO_LEFT)<<endl;
 return 0;
}


共 12 分　

第29题

（烽火传递） 烽火台又称烽燧，是重要的军事防御设施，一般建在险要处或交通要道上。 一旦有敌情发生，白天燃烧柴草，通过浓烟表达信息；夜晚燃烧干柴，以火光传递军情。在 某两座城市之间有 n 个烽火台，每个烽火台发出信号都有一定的代价。为了使情报准确地传 递，在连续的 m个烽火台中至少要有一个发出信号。现输入 n、m和每个烽火台发出信号的代 价，请计算总共最少花费多少代价，才能使敌军来袭之时，情报能在这两座城市之间准确传 递。 

例如，有 5 个烽火台，他们发出信号的代价依次为 1，2，5，6，2，，且 m为 3，则总共最少 花费代价为 4，即由第 2 个和第 5 个烽火台发出信号。

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
78
79
80
81
82
83
84
#include<iostream>
#include<cstring>
using namespace std;
const int SIZE=100;
int n,m,r,value[SIZE],heap[SIZE],
 pos[SIZE],home[SIZE],opt[SIZE];
 //hep[i] 表示用顺序数组储存的堆 heap 中第 i 个元素的值
 //pos[i] 表示 opt[i] 在堆 heap中的位置，即 heap[pos[i]]=opt[i]
 //home[i] 表示 heap[i] 在序列 opt 中的位置，即 opt[home[i]]=heap[i]
void swap(int i,int j)// 交换堆中的第 i 个和第 j 个元素
{
 int tmp;
 pos[home[i]]=j;
 pos[home[j]]=i; 
 tmp=heap[i];
 head[i]=head[j];
 heap[j]=tmp;
 tmp=home[i];
 home[i]=home[j];
 home[j]=tmp; 
}
void add(int k)// 在堆中插入 opt[k]
{
 int i;
 r++;
 heap[r]= ① ;
 pos[k]=r;
② ;
 i=r;
 while( (i>1) && (heap[i]<heap[i/2]) )
 {
 swap(i,i/2);
 i/=2;
 }
}
void remove(int k)// 在堆中删除 opt[k]
{
 int i,j;
 i=pos[k];
 swap(i,r);;
 r--;
 if(i==r+1)
 return ;
 while( (i>1)&&(heap[i]<heap[i/2]) )
 {
 swap(i,i/2); 
 i/=2;
 }
 while(i+i<=r)
 {
 if( (i+i+1<=r) && (heap[i+i+1]<heap[i+i]) )
 j=i+i+1;
 else
③ ;
 if(hea[i]>heap[j])
 {
④ ;
 i=j;
 }
 else
 break;
 }
} 
int main()
{
 int i;
 cin>>n>>m;
 for(i=1;i<=n;i+++)
 cin>>value[i];
 r=0;
 for(i=1;i<=m;i++)
 {
 opt[i]=value[i];
 add(i);
 }
 for(i=m+1;i<=n;i++)
 { 
 opt[i]= ⑤ ;
 remove( ⑥ );
 add(i);
 } 
 cout<<heap[1]<<endl;
 return 0;
}


共 15 分　

试卷信息

题量: 29 道
总分: 100 分 
一.单项选择题（1-10 共 10 题）；
二.不定项选择题（11-20 共 10 题）；
三、问题求解（21-23 共 3 题）；
四.阅读程序写结果（23-27 共 4 题）；
五、完善程序（28-29 共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题