信息学初赛模拟试题五六及答案Word格式文档下载.doc
《信息学初赛模拟试题五六及答案Word格式文档下载.doc》由会员分享，可在线阅读，更多相关《信息学初赛模拟试题五六及答案Word格式文档下载.doc（31页珍藏版）》请在冰点文库上搜索。
end
=x
8.假设在程序开始执行时，数组A[1…n]是一组随机整数。
下列答案中，哪一个最好的描述了最差情况下的程序排序的时间复杂度？
（）
A.O（nlog2n）B.O（n）C.O（log2n）D.O（n2）E.O（2n）
9.假设在程序开始执行时，数组A[1…n]是按关键字非递减有序排列时，下列答案中，哪一个最好的描述了最好情况下的程序排序的时间复杂度？
10.对下列四个序列用快速排序方法进行排序，以序列的第一个元素为划分的基准，在第一趟划分过程中，元素的移动数最多的是哪一个序列（）
A.70,65,34,82,53,25,90
B.82,53,25,70,65,34,90
C.34,25,53,65,90,82,70
D.53,25,65,70,34,90,82
E.65,34,82,70,25,53,90
11.在计算机运行时，把程序和数据一样存放在内存中，这是1946年由_______所领导的研究小组正式提出并论证的。
图灵
冯·
诺依曼
布尔
赫夫曼
哈希
12.下面关于计算机的说法正确的是（）
微机内存容量的基本计量单位是字节
二进制数中右起第10位上的1相当于210
CPU每执行一个指令，就完成一步基本运算或判断
1T=1024MB
32位的计算机中的“32”指的是字长
13.为什么说PASCAL是“高级语言”，是因为它（）
必须在性能较高的机器上运行
必须经过良好培训的高水平的程序员使用
离机器的硬件较远
开发的时间较长
程序的性能较好
14.以下数据结构中，哪一个是线性结构？
A．广义表 B.二叉树 C.稀疏矩阵 D.串 E.队列
15.在下面关于计算机系统硬件的说法中不正确的是（）
没有外部设备的计算机称为祼机
当关闭计算机电源后，RAM中的程序和数据就消失了
软盘和硬盘上的数据均可由CPU直接存取
软盘和硬盘驱动器既属于输入设备又属于输出设备
CPU主要由运算器、控制器和寄存器组成
16.下面关于算法的正确说法是（）
算法必须有输出
算法必须在计算机上用某种语言实现
算法不一定有输入
算法必须在有限步执行后能结束
算法是程序的灵魂
17.以下关于结构化程序的说法中，正确的是（）
结构化程序是由单入口，单出口和循环三种结构组成
结构化程序是出顺序、单入中和单出口三种结构组成
结构化程序是由顺序、循环和GOTO语句结构组成
结构化程序是由顺序、循环和分支三种结构组成
“自顶向下，逐步求精”是结构化程序设计方法的特点
18.栈S最多能容纳4个元素。
现有6个元素按1，2，3，4，5，6的顺序进栈，问下列哪一个序列是可能的出栈序列？
5，4，3，2，1，6
3,2,5,4,1,6
2,3,5,6,1,4
1,4,6,5,2,3
4，5，3，6，2，1
19.下列排序算法中，哪些排序是不稳定的（）
A．快速排序 B.基数排序 C.希尔排序D.冒泡排序E.选择排序
20.下列说法正确的是（）
解释程序是接受参数，按照某一样板产生机器语言的计算机程序
BASIC语言程序通常需解释执行
连接程序可以把经编译程序产生的目标程序变成可执行的机器语言程序
就执行速度而言，编译程序比解释程序快
PASCAL通常是先编译后执行
二、问题求解题（每题5分，共计10分）
1.由四个结点可以构造多少种不同的二叉树.
2.下图是一个设想有11项活动的活动网。
其中有9个事件V1，V2，…V9,每个事件表示在它之前的活动已经完成，在它之后的活动可以开始。
V1表示整个工程的开始，V9表示结束，与每个活动相联系的数ax（x=1…11）是执行该活动所需的时间（单位：
天）。
问完成整项工程至少需要 天，影响工程进度的关键活动有哪些：
。
V2V7
V1V5V9
V3V8
V4V6
三、程序阅读理解题（每题8分，共计32分）
1．program
ex11_8;
var
n,i,j,k,p:
longint;
begin
write（'
N=12'
）;
i:
=2;
j:
=0;
=1;
repeat
inc（i）;
p:
=j+k;
=k;
=p;
until
i=12;
writeln（'
F（'
12,'
）='
p）;
end.
运行结果为：
2．program
example;
n:
byte;
a:
array[1..100]
of
function
f（n:
byte）:
var
i:
begin
if
a[n-1]>
0
then
=a[n-1]
else
=f（n-1）;
a[n-2]>
=i+a[n-2]
=i+f（n-2）;
a[n]:
=i;
f:
end;
fillchar（a,sizeof（a）,0）;
a[1]:
a[2]:
8,'
f（8））;
运行结果为:
3．programexample3
a[1]:
t:
fori:
=2to6do
begin
s:
forj:
=1toi-1do
s:
=s+a[j];
a[i]:
=s+1;
end;
=1to6do
t:
=t+a[i];
writeln（‘t=’,t）;
4．programexample4
vari,s,max:
integer;
fori:
=1to10doread（a[i]）;
max:
=a[1];
s:
=2to10do
ifs<
0thens:
s:
=s+a[i];
ifs>
maxthenmax:
=s;
end;
writeln（‘max=’,max）;
输入：
89–124651115–289
四、程序完善题（每题14分，共计28分）
1.n×
n方阵的每行每列都是自然数1..n的一个全排列，每行（列）无重复数字。
例：
n＝5时，
1
4
3
2
5
5
4
3
2
1
输入
n（>
＝2）和第一行数字（不检查错误）
输出
一个满足要求的方阵
因为只是要求每行（列）无重复数字，对第一行的每个数字，都四十五度斜向下写，写到行尽头就从行开头开始。
这样就不会重复。
对于经过第y行，第x列的直线，斜率k=1
设：
y=x+b
代入坐标，得出：
b=y-x
令y=1，取首行的数：
x=y-b
x从1开始，到n,如果x为0或负数，则x=x+n，取出第一行的数。
程序只用一维数组，存第一行的数字。
program
example2;
const
maxn=10000;
a:
array[1..maxn]
x,y,n:
f（x,y:
integer）:
b:
（1）
（2）
if
x<
=0
（3）
=a[x];
write（'
Enter
n:
'
readln（n）;
（n<
2）
or
（n>
maxn）
exit;
first
line:
for
x:
=1
to
n
do
read（a[x]）;
writeln（'
Output:
write（a[x]:
4）;
writeln;
y:
=2
do
write（（4）:
2．[程序说明]设有ｎ个人依次围成一圈，从第１个人开始报数，数到第ｍ个人出列，然后从出列的下一个人开始报数，数到第ｍ个人又出列，…，如此反复到所有的人全部出列为止。
设ｎ个人的编号分别为1，2，…，n，打印出出列的顺序。
本题用数组建立标志位等方法求解,用数组实现链式结构。
数组a[i]作为"
指针"
变量来使用，a[i]存放下一个结点的位置。
设立指针j指向当前结点，则移动结点过程为j:
=a[j]，当数到m时，m结点出链，则a[j]:
=a[a[j]]。
[程序]
n=14;
m=4;
var
array[1..n]
i,j,k,p:
for
n-1
a[i]:
=i+1;
a[n]:
（1）;
repeat
（2）;
=k+1;
if
k=m
write（a[j]:
=p+1;
（3）;
（4）;
end
until
p=n;
end.
信息学初赛模拟试题（六）
（PASCAL语言，两小时完成）
◆请将正确答案在答卷上填写，在本试题卷上答题无效◆◆
（本题共20小题，1—15小题为单选题，16—20小题为不定项选择题，只有选对才有分。
每题1.5分，共30分）
1．微型计算机的性能主要取决于（）。
A.内存B.中央处理器C.硬盘D.显示卡E.声音卡
2．字长为32位的计算机是指（）。
A．该计算机能够处理的最大数不超过32
B．该计算机中的CPU可以同时处理32位的二进制信息
C．该计算机的内存量为32MB
D．该计算机每秒钟所能执行的指令条数为32MIPS
E．该计算机的硬盘转速是32转
3．MS——DOS文件系统目录的组织形式属于（）。
A．关系型结构B．网络型结构C．树型结构D．直线型结构E．星型结构
4．Windows应用环境中鼠标的拖动操作不能完成的是（）。
A．当窗口不是最大时，可以移动窗口的位置
B．当窗口最大时，可以将窗口缩小成图标
C．当窗口有滚动条时可以实现窗口内容的滚动
D．可以将一个文件移动（或复制）到另一个目录中去
E．调整任务栏的大小和位置
5．下面关于PASCAL语言的几种说法中，正确的是（）。
A．它是一种高级语言B．它是一种汇编语言
C．它是一种低级语言D．它是一种机器语言E．它不是一种过程化语言
6．下列叙述中正确的是（）。
A．计算机病毒只能传染给可执行文件
B．计算机软件是指存储在软盘中的程序
C．计算机每次启动的过程之所以相同，是因为RAM中的所有信息在关机后不会丢失D．硬盘虽然装在主机箱内，但它属于外存
E．ROM是随机存储器
7．多媒体计算机系统的两大组成部分是（）。
多媒体功能卡和多媒体主机
多媒体通信软件和多媒体开发工具
C.多媒体输入设备和多媒体输出设备
D.多媒体计算机硬件系统和多媒体计算机软件系统
E.多媒体主机和多媒体信息
8．用WORD编辑文档后并存储在文件中，该文件的文件名缺省后缀名为（）
A.*.txtB.*.bmpC.*.exeD.*.docE.*.com
9．要在WINDOWS标准窗口的下拉菜单中选择命令，下列操作错误的是（）。
用鼠标单击该命令选项
用键盘上的上下方向键将高亮度条移至该命令选项后再按回车键
同时按下CTRL键与该命令选项后括号中带有下划线的字母键
直接按该命令选项后面括号中带有下划线的字母键
同时按下ALT键与该命令选项后括号中带有下划线的字母键
10．十进制数397的十六进制值为（ ）。
A.18DB.18EC.277D.361E.8
（以下为不定项选题）
11．下列电子邮件地址中正确的是（其中□表示空格）（）。
A.Malin&
B.malin@
C.Lin□Ma&
D.Lin□Ma@E.MALIN@
12．与二进制小数0.1等值的十六进制小数为（ ）。
A.0.1B.0.2C.0.4D.0.8E.7
13．关于计算机网络，正确的说法是（ ）。
A．调制解调器（Modem）是局域网络设备
B．集线器（HuB）是局域网络设备
C．网卡（NIC）是局域网络设备
D．中继器（Repeater）是局域网络设备
E．为了使用Internet网提供的服务，必须采用TCP/IP协议
14．结构化程序的结构由哪三种基本结构组成（）
A.顺序结构B.输入输出结构C.分支结构D.循环结构E.倒序结构
15．下列属于外存储器的有（）
A.硬盘B.软盘C.光盘D.MO碟E.U盘
16．在待排序文件已基本有序的前提下，下述排序方法中效率最高的是（ ）。
A.插入排序B.选择排序C.快速排序D.合并排序E.冒泡排序
17．在Excel中，数据的处理包括（）等
A．"
排序"
B．"
筛选"
C．"
分类汇总"
D．以上都正确E．以上都不正确
18．已知数组A中，每个元素A[I,J]在存贮时要占4个字节，设I从1变化到7，J从1变化到10，分配内存时是从地址S开始连续按行存贮分配的。
试问：
A[4,8]的起始地址为（ ）
A．S+148B．S+120C．S+128D．S+124E．S+144
19.某数列有1000个各不相同的单元，由低至高按序排列；
现要对该数列进行二分法检索（binarysearch），在最坏的情况下，需检视（ ）个单元
A.1000B.10C.100D.500E.250
20．设循环队列中数组的下标范围是1～m，其头尾指针分别为f和r，则其元素个数
为（）。
A．r-fB．r-f+1
C．（r-f+1）MODmD．（r-f+m）MODmE．（r-f+1） MOD m
二、问题求解：
（每题5分,共10分）
1.已知，按中序遍历二叉树的结果为：
@#$
问：
有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树。
2.有2×
n的一个长方形方格，用一个1×
2的骨牌铺满方格。
例如n=3时，为2×
3方格。
此时用一个1×
2的骨牌铺满方格，共有3种铺法
试对给出的任意一个n（n）0），求出铺法总数的递推公式。
三、写出程序的运行结果：
（每小题8分，共32分）
PROGRAMEXP1
VARI,S,MAX:
INTEGER;
A:
ARRAY[1..10]OFINTEGER;
BEGIN
FORI:
=1TO10DOREAD（A[I]）;
MAX:
=A[1];
S:
=2TO10DO
BEGIN
IFS<
0THENS:
S:
=S+A[I];
IFS>
MAXTHENMAX:
=S;
END;
WRITELN（‘MAX=’,MAX）
END.
-11624678–18-61534
输出：
第24页，共6页
2．PROGRAMEXP2
VARI,J,L,N,K,S,T:
INTEGER;
B :
ARRAY[1..10]OF0..9;
BEGIN
READLN（L,N）;
=L;
K:
T:
WHILES<
NDO
BEGINK:
=K+1;
T:
=T*L;
=S+T END;
=S-T;
N:
=N-S-1;
=1TO10DO B[I]:
J:
=11;
WHILEN>
0DO
BEGINJ:
=J-1;
B[J]:
=NMODL;
N:
=NDIVL END;
=10-K+1TO10DOWRITE（CHR（ORD（'
A'
）+B[I]））;
4 167
输出:
3．PROGRAMEXP3
VAR
I,J:
A:
ARRAY[1..12]OFINTEGER;
PROCEDURESW（I1,J1:
INTEGER）;
VARK1:
BEGIN
FORK1:
=1TO（J1-I1+1）DIV1DO
A[I1+K1-1]:
=A[I1+K1-1]+A[J1-K1+1];
A[J1-K1+1]:
=A[I1+K1-1]-A[J1-K1+1];
=A[I1-K1+1]-A[J1-K1+1];
END;
END;
=200;
FORI:
=1TO12DO
A[I]:
=I;
J:
=J-I;
END;
SW（1,4）;
SW（5,10）;
SW（11,14）;
SW（1,14）;
升级会员 