第1个回答 2008-10-18
信息学奥林匹克联赛初赛模拟试题
（普及组 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 <stdio.h>
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 <stdio.h>
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 <stdio.h>
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 <stdio.h>
#include <string.h>
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<n;i++)
for (j=0;j<n;j++) a[i][j]=' ';
for (i=0;i<=m;i++)
for (j=i;j<n-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<n;i++)
printf("%2c",a[i][j]);
printf("\n");
}
}
输入：ACEGIKM
输出：
四、完善程序（前4空每空3分，后4空，每空4分，共28分）
1、对于给定的一个正整数，从其个位数开始，每隔一位取一个数字（即取其个位、百位、万位等数字），形成一个新的整数并输出。例如：运行时若输入“14251382”，则输出的整数为“4532”。
请完善下列程序：
#include <stdio.h>
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 的有向边<i,j>。如是这样，从站点 x 至站点 y 的最少上车次数便对应图 G 中从点 x 至点 y 的最短路径长度。而程序要求的换车次数就是上车次数减 1 。
程序的输入格式：
第一行为两个整数m和n，分别表示公交线路数和公交站数。
接下来m行数据，每一行为沿第m条公交车线路前进方向的各站编号dd（0<=dd<n），每行数字以-1结束。
请完善下面的程序：
#include <stdio.h>
#define M 20
#define N 50
int a[N+1]; /*用于存放一条线路上的各站编号*/
int g[N][N]; /*存储对应的邻接矩阵*/
int dist[N]; /*存储站0到各站的最短路径*/
int m,n;
void buildG(){
int i,j,k,sc,dd;
scanf("%d%d",&m,&n);
for (i=0; i<n; i++)
for (j=0; j<n; j++) g[i][j]=0;
for (i=0; i<m; i++){
sc=0;
while (1){
scanf("%d", &dd);
if (dd==-1) break;
if (dd>=0 && dd<n) ④ ;
}
a[sc]=-1;
for (k=1; a[k]>=0; k++)
for (j=0; j<k; j++)
g ⑤ =1;
}
}
int minLen(){
int j,k;
for (j=0; j<n; j++) dist[j]=g[0][j];
dist[0]=1;
do {
for (k=-1, j=0 ; j<n; j++)
if (dist[j] > 0 && (k == -1 || dist[j] < dist[k]))
k = j;
if (k<0 || k==n-1) break;
dist[k]=-dist[k];
for (j=1; j<n; j++)
if ( ⑥ && (dist[j]==0 || -dist[k]+1<dist[j]) )
⑦ ;
} while (1);
j = dist [n-1];
return ⑧ ;
}
main ( ){
int t;
buildG();
if ((t=minLen())<0) printf("No answer!\n");
else printf("%d\n",n-1,t);
}
参考答案
一、
1、B 2、C 3、C 4、B 5、A 6、D 7、A 8、A 9、A 10、D
11、C 12、C 13、D 14、D 15、C 16、B 17、B 18、C 19、D 20、B
二、
1、41
2、
三、
1、18
2、7,1760
3、1065
2051
4、（注：每相邻的两个字符之间空1格）
M A
K K C C
I I I E E E
G G G G G G G
E E E I I I
C C K K
A M
四、
1、
①(i%2==1)
②(n%10)*k
③n=n/10
2、
④a[sc++]=dd
⑤[a[j]][a[k]]
⑥dist[j]>=0 && g[k][j]==1
⑦-dist[k]+1
⑧k<0 ? -1 : j-1
第2个回答 2008-10-18
一、选择题（每题有5个备选答案，前10个题为单选题，即每题有且只有一个正确答案，选对得分；后10题为不定项选择题，即每题有1至5个正确答案，只有全部选对才得分）。
（1） 计算机处理信息的精度决定于 （ ）
A． CPU的主频
B． 硬盘的容量
C． 系统总线的传输速率
D． CPU字长
E． 内存
（2） （101.101）2 ＝（ ）10
A． 5.625
B． 5.5
C． 6.125
D． 3.525
E． 5.4
（3） 从逻辑功能上讲，计算机主要由（ ）控制器 存储器 输入设备和输出设备组成。
A． ROM
B． I/O
C． CPU
D． ALU
E． RAM
（4） Office 2000中的“剪贴板”是 （ ）中的一块区域。
A． 硬盘
B． 内存
C． Cache
D． Office安装光盘
E． CPU
（5） 产生100至300之间的随机整数（Random），且包含100、300两个整数的表达式是（ ）
A． Random(100)+200
B． Random(200)+100
C． Random(300)
D． Random(101)+200
E． Random(201)+100
（6） 在微型计算机系统中，I/O接口位于（ ）之间。
A． CPU和内存储器
B． 外部设备和内存储器
C． 总线和输出输入设备
D． 主机和输出输入设备
E． CPU和外部设备
（7） JPG是一种（ ）的静态图像文件存储格式。
A． 有损压缩
B． 无损压缩
C． 不可压缩
D． 标准压缩
E． A,B,C,D都不正确
（8） 二叉树是重要的数据结构，5个点的不同的二叉树有（ ）个。
A． 22
B． 30
C． 40
D． 42
E． 46
（9） TCP/IP协议是指
A． 远程登陆协议/因特网互联协议
B． 文件传输协议/远程登陆协议
C． 邮件传输协议/远程登陆协议
D． 文件传输协议/邮件传输协议
E． 传输控制协议/因特网互联协议
（10） 某班有30个同学报名参加100、400、800m 3个运动项目比赛。已知有6人获100m参赛资格，8人获400m参赛资格，15人获800m参赛资格，且其中有3人获全部3项参赛资格，则至少有（ ）人没有获任何项目参赛资格。
A． 5
B． 7
C． 8
D． 9
E． 10
多项选择题（每小题有1到5个正确答案）
（1） 调制解调器又称为Modem，可用于连结计算机和电话线拨号上网。调制是指（ ）。
A． 把信息信号转换成信息信号
B． 把电信号转换成光信号
C． 把光信号转换成电信号
D． 把模拟信号转换成数字信号
E． 把数字信号转换成模拟信号
（2） 下面（ ）是网络操作系统？
A． UNIX
B． NETWARE
C． WINDOWS XP
D． DOS
E． WINDOWS 98
（3） 下列IP地址中正确的是（ ）
A． 202.300.12.4
B． 192.168.0.249
C． 100:128:35:91
D． 94.94.94.94
E． 111-102-35-21
（4） 算式（1000）10－（100）16－（10）8的结果是（ ）。
A. （890）10
B. (986)8
C. (1011100000)2
D. (2E0)16
E. (736)10
（5） 当（A>=B） and （B>=C）的取值为true时，那么表达式（A>C） or （B=C）的取值为（ ）。
A． True
B． False
C． 无法判断
D． 只有当ABC三个数都为正数时才为true
E． 只有当ABC三个数都为正数时才为false
（6） 下列排序方法那种属于稳定排序（ ）
A． 希尔排序
B． 堆排序
C． 冒泡排序
D． 快速排序
E． 插入排序
（7） 显示器是计算机必备的输出设备，它能将计算机内部的信息通过字符和图形在屏幕上表示出来。（ ）和（ ）是显示器的两个重要技术指标。
A． 分辨率
B． 对比度
C． 亮度
D． 灰度
E． 象素个数
（8） 在TCP/IP协议中，TCP和IP提供了什么服务（ ）？
A． 链路层
B． 网络层
C． 传输层
D． 会话层
E． 物理层
（9） 对于一个大小为3的栈，若输入队列为123456，则下列输出队列有可能的是（ ）
A. 123456
B. 654321
C. 432165
D. 431256
E. 321654
（10） 192.168.0.249是属于（ ）
A. A类地址
B. B类地址
C. C类地址
D. D类地址
E. E类地址
一、 问题求解
（1） 已知8个元素为（26、75、15、23、14、62、72、19），按照依次插入结点的方法生成一颗二叉排序树，则该树的深度为_____？
（2） 编号为1到13的纸牌顺时针排成一圈，有人从编号为1的牌从数字1开始顺时针数下去，1、2、3、…、20、21、…，一圈又一圈。问：当数到数字N时，所在纸牌的编号为______？
三.阅读程序写出正确的程序运行结果(4分*8=32分)
#include<stdio.h>
int n,s,d[10];
void multi (int k)
{int i,j,number;
for(i=0;i<=9;i++)
{d[k]=1;
if(k!=0)
multi(k-1);
else
{unmber=0;
for(j=n-1;j>=0;j--)
number=10*number+d[j];
s=s+number;
}
}
}
输入：5
输出：
#include<stdio.h>
int a1,z;
int sue(int x)
{int k;
z=z-x;
k=x*x;
return k;
}
main ()
{z=10;
a1=sne(10)*sne(z);
printf("%d %d\n",a1,z);
z=10;
a1=sne(z)*sne(10);
printf("%d %d\n",a1,z);
}
输出：
#include<stdio.h>
int n,m;
float x,y;
int p(float x,int n)
{if(n%2)
x=x/n;
n=n+1;
m=m-1;
}
main ()
{n=57%6;
m=35/2;
x=15.0;
y=10.0;
p(y,n);
printf("n=%d m=%d\n",n,m);
}
输出：
#include<stdio.h>
int n,a[20];
long count=0;
void sort (int a2[],int begin,int end)
{int i,j,t;
for(i=begin;i<end;i++)
for(j=i+1;j<=end;j++)
if(a2[i]>a2[j])
{t=a2[i];a2[i]=a2[j];a2[j]=t;}
}
void perm (int k)
{int j,p,t,a2[20];
if(k==n)
{count++;
for(p=1;p<=n;p++)
printf("%ld",a[p]);
printf(" ");
if(count%3==0)
printf("\n");
return ;
}
for(j=k;j<=n;j++)
{for(p=1;p<=n;p++)
a2[p]=a[p];
t=a[k];a[k]=a[j];a[j]=t;
sort(a,k+1,n);
perm(k+1);
for(p=1;p<=n;p++)
a[p]=a2[p];
}
}
main ()
{int i;
scanf("%d",&n);
for(i=1;i<=n;i++)
a[i]=i;
perm(1);
printf("\n the total=%ld\n",count);
}
输入：3
输出：
四.完善程序（前4空，每空2.5分，后6空，每空3分，共28分）
字符串匹配是对于两个字符串p和s，查找p是否是s的子序列的方法，对于两个长度分别为m和n的字符序列，当p是s的子序列时，输出p在s中首次出现的位置，否则输出“失败”信息。
#include <stdio.h>
#include <string.h>
int math(char *p,char *s)
mian ()
{int find;
char str1[]="cde";
char str2[]="abcdefg";
find=match(str1,str2);
if(find)
printf("%d\n",find);
else
printf("faliure\n");
}
int math (char *p,char *s)
{int i,j,m,n;
m=strlen(p)
n=①;
②;
do{
i++;
③;
while(j<m&&s[i+j]==p[j])
④;
if(j==m)
return i+1;
}
while(⑤);
return 0;
}
下面程序对两个整数有限集A和B进行交（*）、差（－）、和并（＋）运算，得到集合C。
#include <stdio.h>
int set(int a[],int b[],int c[],int na,int nb,char op)
int main ()
{int i,k,m,n,seta[100],setb[120],setc[220];
scanf("%d",&m);
for(i=1;i<=m;i++)
scanf("%d",&seta[i]);
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&setb[i]);
k=set(seta,setb,setc,m,n,'+');
for(i=1;i<=k;i++)
printf("%5d",setc[i]);
}
int set(int a[],int b[],int c[],int na,int nb,char op)
{int flag,nc=0,i,j;
for(i=1;i<=na;i++)
{flag=1;
①;
while(flag&&j<=nb)
{if(a[i]==b[j])
②;
j++;
}
if((flag&&(op=='-'||op=='+'))||(③&&op=='*'))
④;
}
if(⑤)
for(i=1;i<=nb;i++)
c[++nc]=b[i];
return nc;
}
答案
1．D CPU的字长是指微处理器能直接处理的二进制信息的位数，它标志着计算处理信息的精度，字长越长精度越高。
2．A（101.101）2＝（1×22＋0×21＋1×20＋1×2-1＋0×2-2＋1×2-3）10＝（5.625）10
3．D ALU是Arithmetic and Logic Unit的缩写，是指CPU中的算术逻辑部件即运算器。
4．B
5．E
6．C I/O即 Input/Output
7．A
8．D 设f（n）
代表n个点的不同
的二叉树个数，
f（5）＝42
9．E
10．B 设至少有x人没有获任何项目参赛资格。剩下30－3－x个人。其中有6－3人获100m参赛资格，8－3人获400m参赛资格，15－3人获800m参赛资格，则30－3－x＝3＋5＋12。显然x＝7。
1． DE
2． ABCE
3． BD IP地址四个十进制数在0～255之间，并且用“.”分开。
4． CDE
5． A 由（A>=B） and （B>=C）可以推出A>=C。分A>C和A=C两种情况讨论，原式都为true
6． CE
7． AD 大多数计算机的显示器都属于阴极射线管显示器（CRT），它由阴极电子枪发射电子射线束扫描屏幕表面而激发出亮光，屏幕上有多少个光点叫做分辨率，而光点亮度的深浅变化则叫做灰度，分辨率和灰度决定显示器显示的图像质量，因此，分辨率和灰度是显示器的两个重要的技术指标。
8． BC
9． AE
10． C A类（1.0.0.0～127.255.255.255）
B类（128.0.0.0～191.255.255.255）
C类（192.0.0.0～223.255.255.255）
D类（用于多点广播）
E类（为将来使用保留）
1．4
2．1＋（N－1） mod 13
三.阅读程序写出正确的程序运行结果(4分*8=32分)
1: 1111100000
2: 0 0
10000 -10
3: n=3 m=16
4: 123 132 213
231 312 321
The total=6
四.完善程序（前4空，每空2.5分，后6空，每空3分，共28分）
1： strlen(s)
2: i=-1
3: j=0
4: j++
5: i+m<n
6: j=1
7: flag=0
8: !flag
9: a[++nc]=a[i]
10: op==’+’