noip2011初赛模拟题
- 格式：doc
- 大小：122.50 KB
- 文档页数：16
信息学奥林匹克联赛初赛模拟试题一
（普及组 C语言 二小时完成）
一、选择一个正确答案代码（A/B/C/D/E）,填入每题的括号内（每题1.5分，共30分）
1．在计算机科学领域，提出“程序=数据结构+算法”的是（ ）。
A、D.Ritchie B、N.Wirth C、Von Neumann D、Alan Turing E、B.Kernighan
2．下列哪个是最早的计算机程序设计语言（ ）。
A、C++ B、Java C、FORTRAN D、PASCAL E、COBOL
3．下列软件不是数据库处理软件的是（ ）。
A、DB2 B、FoxPro C、Foxmail D、Oracle E、Sybase
4．下列哪个公司是生产CPU（中央处理器）的主要公司（ ）。
A、 Seagate B、AMD C、KINGSTONE D、BENQ E、Sony
5．在微型计算机中，微处理器的主要功能是进行（ ）。
A、算术逻辑运算及全机的控制
B、逻辑运算
C、算术逻辑运算
D、算术运算
6．DRAM存储器的中文含义是（ ）。
A、静态随机存储器
B、动态只读存储器
C、静态只读存储器
D、动态随机存储器
7．操作系统的主要功能是（ ）。
A、控制和管理计算机系统软硬件资源
B、对汇编语言、高级语言和甚高级语言程序进行翻译
C、管理用各种语言编写的源程序
D、管理数据库文件
8．在Windows中，将某个应用程序窗口最小化之后，该应用程序（ ）。
A、仍在后台运行 B、暂时停止运行 C、完全停止运行 D、出错
9．网络互联实现在更大的范围内传输数据和共享资源，要解决两个问题：一是网络之间要有通信链路，二是提供（ ）。
A、协议转换功能 B、数据库管理功能 C、安全保密功能 D、信息传输功能
10．Internet网是目前世界上第一大互联网，它起源于美国，其雏形是（ ）。
A、NCFC B、CERNET C、GBNET D、ARPANET E、CSTNET
11．下列无符号数中，最小的是（ ）。
A、（11111010110）2 B、（3730）8 C、（2007）10 D、（7D9）16
12．已知集合A={1,2,3,4,5,6,7,8}，则A的不含2和4的非空子集的个数为（ ）。
A、255 B、127 C、63 D、31 E、15
13．C语言中，如果整型变量a=125，则执行操作a>>=2;之后，a的值是（ ）。
A、1000 B、123 C、127 D、31 E、32 14．对于栈来说，若进栈序列为1、2、3、4、5、6，进栈过程中可以出栈，则下列出栈序列中不可能的是。（ ）。
A、134256 B、243165 C、345621 D、145623 E、132465
15．一棵完全二叉树的结点总数为18，其叶结点数为（ ）。
A、7个 B、8个 C、9个 D、10个 E、11个
16．设G是一个非连通无向图，共有28条边，则该图至少有（ ）个顶点。
A、8 B、9 C、10 D、6
17．对于一个无向带权图G=（V，E），其中V={a,b,c,d,e}，E={(a,b),(a,c),(b,d),(c,d),(e,d),(c,e),
(a,d),(b,e)},E中边的权值分别为{1,4,2,5,3,1,2,3}，则其最小生成树上各边的权值之和为（ ）。
A、6 B、7 C、8 D、9
18．如右所示的有向无环图，对该图进行拓朴排序，得到
的顶点序列正确的是（ ）。
A、1,2,5,3,4,6,8,7
B、1,3,6,5,2,8,7,4
C、1,2,3,4,5,6,7,8
D、1,3,2,4,5,7,8,6
19．给出一组数据：10、18、3、4、9、13、15、2、21、9、8，将它们生成一棵二叉排序树，所需要的关键码的比较次数为（ ）。
A、25 B、24 C、23 D、22
20．对给定的整数序列（541,132,984,746,518,181,946,314,205,827）进行从小到大的排序时，采用快速排序（以中间元素518为基准）的第一趟扫描结果是（ ）。
A、（181,132,314,205,541,518,946,827,746,984）
B、（205,132,314,181,518,746,946,984,541,827）
C、（541,132,827,746,518,181,946,314,205,984）
D、（541,132,984,746,827,181,946,314,205,518）
二、问题求解（每题5分，共10分）
1．在1,2,3,4中任取2个数，同时要求这两个数不相邻，有3种选取方法：1,3；1,4；2,4。那么在1～9共9个数中，任取3个数，同时要求这4个数中没有相邻的数，它的选取方法有 种。
2．下面一个街区，纵向街道m条，横向街道n条，设A点坐标为(1,1)，则B点坐标为(m,n)，当中有一点C，其坐标为(i,j)。某人从A点走到对角B点，要求必须向上或向右走，则经过其中的C点的走法一共有 种。
三、阅读程序（每题8分，共32分）
1.#include
main(){
int a,b,c,x,y,z,u[4];
scanf("%d%d%d%d",&u[0],&u[1],&u[2],&u[3]);
a=u[0]+u[1]+u[2]+u[3]-8;
b=u[0]*(u[1]+u[2]/u[3]-a);
c=u[0]*u[1]/u[2]*u[3];
x=(a+b+c)*3-u[3*c/4];
y=(a*b*c-13)/(u[b/3]*5);
if ((x+y)%2==0) z=(a+b+c+x+y)/2;
else z=(a+b+c-x-y)/2;
printf("%d\n",x-y+z);
}
输入：2 5 7 4
2.#include
main(){
int hi,lo,m,n;
scanf("%d%d",&m,&n);
hi=0; lo=0;
do{
n--; lo+=m;
if (lo>=10000) { lo-=10000; hi++; }
} while (n!=0);
printf("%4d,%4d\n",hi,lo);
}
输入：345 208
输出：
3.#include
main(){
int i,j,p,n,q,s,a[21];
scanf("%d%d%d",&p,&n,&q);
j=21;
while (n>0){
j--; a[j]=n%10; n/=10;
}
s=0;
for (i=j;i<=20;i++)
s=s*p+a[i]; printf("%d\n",s);
j=21;
while (s>0){
j--; a[j]=s%q; s/=q;
}
for (i=j;i<=20;i++)
printf("%d",a[i]);
}
输入：7 3051 8
输出：
4.#include
#include
main(){
int n,m,i,j;
char x,st[10],a[10][10];
scanf("%s",st);
n=strlen(st);m=n/2;
for (i=0;i
for (j=0;j
for (i=0;i<=m;i++)
for (j=i;j
x=st[j];
a[i][j]=a[n-i-1][n-j-1]=x;
}
for (j=n-1;j>=0;j--){
for (i=0;i
printf("%2c",a[i][j]);
printf("\n");
}
}
输入：ACEGIKM
输出：
四、完善程序（前4空每空3分，后4空，每空4分，共28分）
1、对于给定的一个正整数，从其个位数开始，每隔一位取一个数字（即取其个位、百位、万位等数字），形成一个新的整数并输出。例如：运行时若输入“14251382”，则输出的整数为“4532”。
请完善下列程序：
#include
main(){
long n,num; int i,k;
scanf(“%d”,&n);
k=1; num=0;
for (i=1;n>0;i++){
if ①
{
num=num+ ② ;
k=k*10;
}
③ ;
}
printf(“%d\n”,num);
}
2、设某城市有 n 个车站，并有 m 条公交线路连接这些车站，设这些公交车都是单向的，这 n 个车站被顺序编号为0 至 n-1 。本程序，输入该城市的公交线路数、车站个数， 以及各公交线路上的各站编号，求得从站0出发乘公交 车至站 n-1 的最少换车次数。
程序利用输入信息构建一张有向图 G (用邻接矩阵 g 表示)，有向图的顶点是车站，若有某条公交线路经 i 站能到达 j 站，就在顶点 i 到顶点 j 之间设置一条权为 1 的有向边。如是这样，从站点 x 至站点 y 的最少上车次数便对应图 G 中从点 x 至点 y 的最短路径长度。而程序要求的换车次数就是上车次数减 1 。
程序的输入格式：
第一行为两个整数m和n，分别表示公交线路数和公交站数。
接下来m行数据，每一行为沿第m条公交车线路前进方向的各站编号dd（0<=dd
