NOIP 2014 提高组初赛试题

第 1 题
以下哪个是面向对象的高级语言( ).
A.汇编语言
B.C++
C.FORTRAN
D.Basic
正确答案： B
本题共 1.5 分

第 2 题
1TB代表的字节数量是( ).
A.2的10次方
B.2的20次方
C.2的30次方
D.2的40次方
正确答案： D
本题共 1.5 分

第 3 题
二进制数00100100和00010101的和是( ).
A.00101000
B.001010100
C.01000101
D.00111001
正确答案： D
本题共 1.5 分

第 4 题
TCP协议属于哪一层协议( ).
A.应用层
B.传输层
C.网络层
D.数据链路层
正确答案： B
本题共 1.5 分

第 5 题
下列几个32位IP地址中，书写错误的是( ).
A.162.105.128.27
B.192.168.0.1
C.256.256.129.1
D.10.0.0.1
正确答案： C
本题共 1.5 分

第 6 题
在无向图中，所有定点的度数之和是边数的( )倍.
A.0.5
B.1
C.2
D.4
正确答案： C
本题共 1.5 分

第 7 题
对长度位n的有序单链表，若检索每个元素的概率相等，则顺序检索到表中任一元素的平均检索长度为( ).
A.n/2
B.(n+1)/2
C.(n-1)/2
D.n/4
正确答案： B
本题共 1.5 分

第 8 题
编译器的主要功能是( ).
A.将一种高级语言翻译成另一种高级语言
B.将源程序翻译成指令
C.将低级语言翻译成高级语言
D.将源程序重新组合
正确答案： B
本题共 1.5 分

第 9 题
二进制数111.101所对应的十进制数是( ).
A.5.625
B.5.5
C.6.125
D.7.625
正确答案： D
本题共 1.5 分

第 10 题
若有变量 int a, float x, y, 且 a=7, x=2.5, y=4.7, 则表达式 x+a%3*(int)(x+y)%2/4的值大约是( ).
A.2.500000
B.2.750000
C.3.500000
D.0.000000
正确答案： A
本题共 1.5 分

第 11 题
有以下结构体说明和变量定义，如图所示，指针p、q、r分别指向一个链表中的三个续结点。

struct node {
int data;
struct node *next;
} *p,*q,*r;
现要将q和r所指结点的先后位置交换，同时要保持链表的连续，以下程序段中错误的是( )
A.q->next = r->next; p-> next = r; r->next = q;
B.p->next = r; q->next = r->next; r->next = q;
C.q->next = r->next; r->next = q; p->next = r;
D.r->next = q; q->next = r->next; p->next = r;
正确答案： D
本题共 1.5 分

第 12 题
同时查找2n 个数中的最大值和最小值，最少比较次数为( ).
A.3(n-2)/2
B.4n-2
C.3n-2
D.2n-2
正确答案： C
本题共 1.5 分

第 13 题
设G是有6个结点的完全图，要得到一颗生成树，需要从G中删去( )条边.
A.6
B.9
C.10
D.15
正确答案： C
本题共 1.5 分

第 14 题
以下时间复杂度不是O(n2)的排序方法是( ).
A.插入排序
B.归并排序
C.冒泡排序
D.选择排序
正确答案： B
本题共 1.5 分

第 15 题
以下程序实现了找第二小元素的算法。输入时n个不等的数构成的数组S，输出S中第二小的数SecondMin。在最坏的情况下，该算法需要做( )次比较。

if ( S[1] < S[2] )

{

FirstMin = S[1];

SecondMin = S[2];

} else {

FirstMin = S[2];

SecondMin = S[1];

}

for ( i = 3; i <= n; i++ )

if ( S[i] < SecondMin )

if ( S[i] < FirstMin )

{

SecondMin = FirstMin;

FirstMin = S[i];

} else {

SecondMin = S[i];

}

A.2n
B.n-1
C.2n-3
D.2n-2
正确答案： C
本题共 1.5 分

第 16 题
若逻辑变量A、C为真，B、D为假，以下逻辑运算表达式真的有( ).
A.(B∨C∨D)∨D∧A
B.((- A∧B)∨C)∧-B
C.(A∧B)∨(C∧D∨-A)
D.A∧(D∨-C)∧B
正确答案： AB
本题共 1.5 分

第 17 题
下列( )软件属于操作系统软件。
A.Microsoft Word
B.Windows XP
C.Android
D.Mac OS X
E.Oracle
正确答案： BCD
本题共 1.5 分

第 18 题
在NOI比赛中，对于程序设计题，选手提交的答案不得包含下列哪些内容( ).
A.试图访问网络
B.打开或创建题目规定的输入/输出文件之外的其他文件
C.运行其他程序
D.改变文件系统的访问权限
E.读写文件系统的管理信息
正确答案： ABCDE
本题共 1.5 分

第 19 题
以下哪些结构可以用来存储图( ).
A.邻接矩阵
B.栈
C.邻接表
D.二叉树
正确答案： AC
本题共 1.5 分

第 20 题
下列各无符号十进制整数中，能用八位二进制表示的数有( ).
A.296
B.133
C.256
D.199
正确答案： BD
本题共 1.5 分

第 21 题
有数字1,1,2,4,8,8所组成的不同的四位数的个数是_____.
正确答案： 102
本题共 5 分

第 22 题
如图所示，图中每条边上的数字表示该边的长度，则从A到E的最短距离是_____.

正确答案： 15
本题共 5 分

第 23 题

#include <stdio.h>

int main()

{

int a, b, i, tot, c1, c2;

scanf( "%d%d", &a, &b );

tot = 0;

for ( i = a; i <= b; i++ )

{

c1 = i / 10;

c2 = i % 10;

if ( (c1 + c2) % 3 == 0 )

tot++;

}

printf( "%d\n", tot );

return(0);

}

输入：7 31
输出：_________
正确答案： 8
本题共 8 分

第 24 题

#include <stdio.h>

int fun( int n, int minNum, int maxNum )

{

int tot, i;

if ( n == 0 )

return(1);

tot = 0;

for ( i = minNum; i <= maxNum; i++ )

tot += fun( n - 1, i + 1, maxNum );

return(tot);

}

int main()

{

int n, m;

scanf( "%d%d ", &n, &m );

printf( "%d\n", fun( m, 1, n ) );

return(0);

}

输入： 6 3
输出：________
正确答案： 20
本题共 8 分

第 25 题

#include <stdio.h>

#include <string.h>

const int SIZE = 100;

const int LENGTH = 25;

* strcmp(a,b) <0:a的字典序小于b

* strcmp(a,b) =0:a和b一样

* strcmp(a,b) >0:a的字典序大于b

int main()

{

char dict[SIZE][LENGTH + 1];

int rank[SIZE];

int ind[SIZE];

int i, j, n, tmp;

scanf( "%d", &n );

for ( i = 1; i <= n; i++ )

{

rank [i] = i;

ind[i] = i;

scanf( "%s", dict[i] );

}

for ( i = 1; i < n; i++ )

for ( j = 1; j <= n - i; j++ )

if ( strcmp( dict[ind[j]], dict[ind[j + 1]] ) > 0 )

{

tmp = ind[j];

ind[j] = ind[j + 1];

ind[j + 1] = tmp;

}

for ( i = 1; i <= n; i++ )

rank[ind[i]] = i;

for ( i = 1; i <= n; i++ )

printf( "%d ", rank[i] );

printf( "\n" );

return(0);

}

输入：
7
aaa
aba
bbb
aaa
aaa
ccc
aa
输出：______
正确答案： 2 5 6 3 4 7 1
本题共 8 分

第 26 题

#include <cstdio>

const int SIZE = 100;

int alive[SIZE];

int n;

int next( int num )

{

num++;

if ( num > n )

num = 1;

}

while ( alive[num] == 0 );

return(num);

}

int main()

{

int m, i, j, num;

scanf( "%d%d", &n, &m );

for ( i = 1; i <= n; i++ )

alive[i] = 1;

num = 1;

for ( i = 1; i <= n; i++ )

{

for ( j = 1; j < m; j++ )

num = next( num );

printf( "%d ", num );

alive[num] = 0;

if ( i < n )

num = next( num );

}

printf( "\n" );

return(0);

}

输入： 11 3
输出：_________
正确答案： 3 6 9 1 5 10 4 11 8 2 7
本题共 8 分

第 27 题
（双栈模拟数组）　只使用两个栈结构stack1和stack2，模拟对数组的随机读取。作为栈结构，stack1和stack2只能访问栈顶（最后一个有效元素）。栈顶指针top1和top2均指向栈顶元素的下一个位置。输入第一行包含的两个整数，分别是数组长度n和访问次数m，中间用单个空格隔开。第二行包含n个整数，一次给出数组各项（数组下标从0到a-1）。第三行包含m个整数，需要访问的数组下标。对于每次访问，输出对应的数组元素。

#include <stdio.h>

const int SIZE = 100;

int stack1[SIZE], stack2[SIZE];

int top1, top2;

int n, m, i, j;

void clearStack()

{

int i;

for ( i = top1; i < SIZE; i++ )

stack[i] = 0;

for ( i = top2; i < SIZE; i++ )

stack[i] = 0;

}

int main()

{

scanf( "%d,%d", &n, &m );

for ( i = 0; i < n; i++ )

scanf( "%d", &stack1[i] );

top1 = ______ （1）______;

top2 = ______ （2）______;

for ( j = 0; j < m; j++ )

{

scanf( "%d", &i );

while ( i < top1 - 1 )

{

top1--;

______( 3 ) ______;

top2++;

}

while ( i > top1 - 1 )

{

top2--;

______( 4 ) ______;

top1++;

}

clearstack();

printf( "%d\n", stack1[______( 5 ) ______] );

}

return(0);

}

1.正确答案： n
2.正确答案： 0
3.正确答案： stack2[top2]=stack1[top1]
4.正确答案： stack1[top1]=stack2[top2]
5.正确答案： top1-1

本题共 13 分

第 28 题
2.(最大矩阵和)给出M行N列的整数矩阵，就最大的子矩阵和（子矩阵不能为空）。输入第一行包含两个整数M和N,即矩阵的行数和列数。之后M行，每行N个整数，描述整个矩阵。程序最终输出最大的子矩阵和。（第一空2分，其余3分，共14分）

#include <stdio.h>

const int SIZE=100;

int matrix[SIZE+1][SIZE+1];

int rowsum[SIZE+1][SIZE+1]; //rowsum[i][j]记录第i行前j个数的和

int m,n,i,j,first,last,area,ans;

int main(){

scanf(“%d %d”,&m,&n);

for(i=1;i<=m;i++)

for(j=1;j<=n;j++)

scanf(“%d”,&matrix[i][j]);

ans=matrix (1) ;

for(i=1;i<=m;i++)

(2) ;

for(i=1;i<=m;i++)

for(j=1;j<=n;j++)

rowsum[i][j]= (3) ;

for(first=1;first<=n;first++)

for(last=first;last<=n;last++){

(4) ;

for(i=1;i<=m;i++){

area+= (5) ;

if(area>ans)

ans=area;

if(area<0)

area=0;

}

printf(“%d\n”,ans);

return 0;

}

1.正确答案： [1][1]
2.正确答案： rowsum[i][0]=0
3.正确答案： rowsum[i][j-1] + matrix[i][j]
4.正确答案： area=0
5.正确答案： rowsum[i][last]-rowsum[i][first-1]

本题共 14 分

相关文章: