信息学初赛模拟试题五六及答案

1、信息学初赛模拟试题（五）PASCAL语言，两小时完成）一、选择题：（每题1.5分，共计30分。每题有5个选项，前10题为单选题，后10题为不定项选择题，全部选对才得分）。1. 二进制数11011011的十进制值是（ ）A. 202 B. 219 C. 193 D. 2092. 我国研制的银河型的超级计算机通过基准程序的测试，其峰值速度是（ ）A. 80亿次B. 100亿次 C. 130亿次 D. 150亿次3. 程序段如下：FOR I:=1 TO 5 DO FOR J:=2 TO I DO Writeln(*)输出*的个数是（ ）A. 5 B. 10 C. 15 D. 25 E. 304. 设

2、待排序的记录为（49，38，65，97，76， 13，27 , 49, 55, 4），经过下过程将序列排序第一趟：13, 27, 49, 55, 4, 49, 38, 65, 97, 76第二趟：13, 4, 49, 38, 27, 49, 55, 65, 97, 76第三趟：4, 13, 27, 38, 49, 49, 55, 65, 76, 97问它所用的方法是：( )A. 冒泡排序 B. 直接选择排序 C. 直接插入排序 D. 希尔排序5. 设无向树T有7片树叶，其余顶点度均为3，则T中3度顶点有多少个（ ）A. 5 B. 7 C. 9 D. 4 E. 86. 设连通图G的顶点数和边数与

3、一立方体相同，即有8个顶点和12条边。任意一棵G的生成树的总边数为（ ）A7B. 8 C. 9 D. 10E. 117. 设有两个散列函数h1(k)=k mod 13 和 h2(k)=k mod 11 +1，散列表为T012，用二次散列法解决冲突。函数h1用来计算散列地址，当发生冲突时，h2作为计算下一个探测地址的地址增量。假定某一时刻散列表的状态为： 1 2 3 4 5 6 7 8 9 10 11 12 80 44 35下一个被插入的关键码为57，其插入的位置为( )。A. 4 B. 5 C. 6 D. 7 E. 8请根据下面是一段PASCAL程序,判断第8、9题。for h :=1 to

4、n-1 do beginx :=Ah+1;k :=h;while (k>=1) and (Ak>x) do beginAk+1 :=Ak;k:=k1endAk+1 :=xend8. 假设在程序开始执行时，数组A1n是一组随机整数。下列答案中，哪一个最好的描述了最差情况下的程序排序的时间复杂度？（ ）A. O(n log2 n) B. O(n) C. O(log2n) D. O(n2) E. O(2n)9. 假设在程序开始执行时，数组A1n是按关键字非递减有序排列时，下列答案中，哪一个最好的描述了最好情况下的程序排序的时间复杂度？（ ）A. O(n log2 n) B. O(n) C

5、. O(log2n) D. O(n2) E. O(2n)10.对下列四个序列用快速排序方法进行排序，以序列的第一个元素为划分的基准，在第一趟划分过程中，元素的移动数最多的是哪一个序列（ ）A. 70 , 65 , 34 , 82 , 53 , 25 , 90B. 82 , 53 , 25 , 70 , 65 , 34 , 90C. 34 , 25 , 53 , 65 , 90 , 82 , 70D. 53 , 25 , 65 , 70 , 34 , 90 , 82E. 65 , 34 , 82 , 70 , 25 , 53 , 9011.在计算机运行时，把程序和数据一样存放在内存中，这是194

6、6年由_所领导的研究小组正式提出并论证的。（ ）图灵 冯·诺依曼布尔赫夫曼哈希12.下面关于计算机的说法正确的是（ ）微机内存容量的基本计量单位是字节二进制数中右起第10位上的1相当于210CPU每执行一个指令，就完成一步基本运算或判断1T=1024MB 32位的计算机中的“32”指的是字长13.为什么说PASCAL是“高级语言”，是因为它（ ）必须在性能较高的机器上运行必须经过良好培训的高水平的程序员使用离机器的硬件较远开发的时间较长程序的性能较好14.以下数据结构中，哪一个是线性结构？（ ）A广义表B. 二叉树C. 稀疏矩阵D. 串E. 队列15.在下面关于计算机系统硬件的说法中

7、不正确的是( )没有外部设备的计算机称为祼机当关闭计算机电源后，RAM中的程序和数据就消失了软盘和硬盘上的数据均可由 CPU直接存取软盘和硬盘驱动器既属于输入设备又属于输出设备CPU主要由运算器、控制器和寄存器组成16. 下面关于算法的正确说法是（ ）算法必须有输出算法必须在计算机上用某种语言实现算法不一定有输入算法必须在有限步执行后能结束算法是程序的灵魂17.以下关于结构化程序的说法中，正确的是（ ）结构化程序是由单入口，单出口和循环三种结构组成结构化程序是出顺序、单入中和单出口三种结构组成结构化程序是由顺序、循环和GOTO语句结构组成结构化程序是由顺序、循环和分支三种结构组成“自顶向下，逐

8、步求精”是结构化程序设计方法的特点18.栈S最多能容纳4个元素。现有6个元素按1，2，3，4，5，6的顺序进栈，问下列哪一个序列是可能的出栈序列？（ ）5，4，3，2，1，63, 2, 5, 4, 1, 62, 3, 5, 6, 1, 41, 4, 6, 5, 2, 34，5，3，6，2，119.下列排序算法中，哪些排序是不稳定的（ ）A快速排序B. 基数排序C. 希尔排序 D. 冒泡排序 E.选择排序20.下列说法正确的是（ ）解释程序是接受参数，按照某一样板产生机器语言的计算机程序BASIC语言程序通常需解释执行连接程序可以把经编译程序产生的目标程序变成可执行的机器语言程序就执行速度而言，

9、编译程序比解释程序快PASCAL通常是先编译后执行二、问题求解题（每题5分，共计10分）1. 由四个结点可以构造多少种不同的二叉树 .2. 下图是一个设想有11项活动的活动网。其中有9个事件V1，V2， V9,每个事件表示在它之前的活动已经完成，在它之后的活动可以开始。V1表示整个工程的开始，V9表示结束，与每个活动相联系的数ax(x=111)是执行该活动所需的时间（单位：天）。问完成整项工程至少需要 天，影响工程进度的关键活动有哪些： 。 V2 V7V1 V5 V9 V3 V8 V4 V6三、程序阅读理解题 （每题8分，共计32分）1program ex11_8;varn,i,j,

10、k,p:longint;beginwrite('N=12'); i:=2;j:=0;k:=1;repeatinc(i);p:=j+k;j:=k;k:=p;until i=12;writeln('F(',12,')=',p);end.运行结果为： 2program example;varn:byte;a:array1.100 of longint;function f(n:byte):longint;var i:longint;beginif an-1>0 the

11、n i:=an-1else i:=f(n-1);if an-2>0 then i:=i+an-2else i:=i+f(n-2);an:=i;f:=i;end;beginfillchar(a,sizeof(a),0);a1:=1;a2:=1;writeln('F(',8,')=',f(8);end.运行结果为: 3program example3begin a1:=1;t:=0;for i:=2 to 6 do begins:=0;for j:=1 to i-1 do s:=s+aj; ai:=s

12、+1; end;for i:=1 to 6 do t:=t+ai;writeln(t=,t);end.运行结果为： 4program example4var i,s,max:integer;begin for i:=1 to 10 do read(ai); max:=a1; s:=a1; for i:=2 to 10 dobegin if s<0 then s:=0; s:=s+ai; if s>max then max:=s;end;writeln(max=,max);end.输入：8 9 1 24 6 5 11 15 28 9运行结果为： 四、程序完善题 (每题14分，共计28

13、分)1.n×n方阵的每行每列都是自然数1.n的一个全排列，每行（列）无重复数字。例： n5时，      1 4 3 2 5      5 3 2 1 4      4 2 1 5 3      3 1 5 4

14、 2      2 5 4 3 1输入 n（>2）和第一行数字（不检查错误）输出 一个满足要求的方阵因为只是要求每行（列）无重复数字，对第一行的每个数字，都四十五度斜向下写，写到行尽头就从行开头开始。这样就不会重复。对于经过第y行，第x列的直线，斜率k=1设：y=x+b代入坐标，得出：b=y-x令y=1，取首行的数：x=y-bx从1开始，到n,如果x为0或负数，则x=x+n，取出第一行的数。程序只用一维数组，存第一行的数字。program examp

15、le2;const    maxn=10000;var     a:array1.maxn of integer;     x,y,n:integer;function f(x,y:integer):integer;var   b:integer;begin     (1)     (2)    &

16、#160;if x<=0 then  (3)     f:=ax;end;begin    write('Enter n:');  readln(n);    if (n<2) or (n>maxn) then exit;    write('Enter first 

17、line:');    for x:=1 to n do read(ax);    writeln('Output:');    for x:=1 to n do write(ax:4);    writeln;    for y:=2 to n

18、 do      begin         for x:=1 to n do write( (4) :4);         writeln;      end;end.2程序说明 设有个人依次围成一圈，从第个人开始报数，数到第个人出列，

19、然后从出列的下一个人开始报数，数到第个人又出列，如此反复到所有的人全部出列为止。设个人的编号分别为1，2，n，打印出出列的顺序。本题用数组建立标志位等方法求解,用数组实现链式结构。 数组ai作为"指针"变量来使用，ai存放下一个结点的位置。设立指针j指向当前结点，则移动结点过程为j:=aj，当数到m时，m结点出链，则aj:=aaj。程序program example;const n=14;m=4; var a:array1.n of integer;i,j,k,p:integer;beginfor i:=1

20、0;to n-1 do ai:=i+1; an:=1; (1) ;k:=1;p:=0; repeat (2) ;k:=k+1;if k=m then  beginwrite(aj:4);p:=p+1; (3) ; (4) ;enduntil p=n;end.信息学初赛模拟试题（六）（PASCAL语言，两小时完成）请将正确答案在答卷上填写，在本试题卷上答题无效一、选择题：（本题共20小题，115小题为单选题，1620小题为不定项选择题，只有选对才有分。每题1.5分，共30分）1微型计算机的性能主要取决于( )。A. 内存 B.

21、 中央处理器 C. 硬盘 D. 显示卡 E. 声音卡2字长为32位的计算机是指( )。A该计算机能够处理的最大数不超过32 B该计算机中的CPU可以同时处理32位的二进制信息C该计算机的内存量为32MBD该计算机每秒钟所能执行的指令条数为32MIPSE该计算机的硬盘转速是32转 3MSDOS文件系统目录的组织形式属于( )。 A关系型结构 B网络型结构 C树型结构 D直线型结构 E星型结构4Windows应用环境中鼠标的拖动操作不能完成的是( )。 A当窗口不是最大时，可以移动窗口的位置B当窗口最大时，可以将窗口缩小成图标C当窗口有滚动条时可以实现窗口内容的滚动D可以将一个文件移动(或复制)到

22、另一个目录中去 E调整任务栏的大小和位置5下面关于PASCAL语言的几种说法中，正确的是( )。 A它是一种高级语言 B它是一种汇编语言 C它是一种低级语言 D它是一种机器语言 E它不是一种过程化语言6下列叙述中正确的是( )。 A计算机病毒只能传染给可执行文件 B计算机软件是指存储在软盘中的程序 C计算机每次启动的过程之所以相同，是因为RAM 中的所有信息在关机后不会丢失 D硬盘虽然装在主机箱内，但它属于外存 EROM是随机存储器7多媒体计算机系统的两大组成部分是( )。多媒体功能卡和多媒体主机 多媒体通信软件和多媒体开发工具 C. 多媒体输入设备和多媒体输出设备 D. 多媒体计算机硬件系统

23、和多媒体计算机软件系统 E. 多媒体主机和多媒体信息8用WORD编辑文档后并存储在文件中，该文件的文件名缺省后缀名为( )A. *.txt B. *.bmp C. *.exe D. *.doc E. *.com9要在WINDOWS标准窗口的下拉菜单中选择命令，下列操作错误的是( )。用鼠标单击该命令选项 用键盘上的上下方向键将高亮度条移至该命令选项后再按回车键 同时按下CTRL键与该命令选项后括号中带有下划线的字母键 直接按该命令选项后面括号中带有下划线的字母键 同时按下ALT键与该命令选项后括号中带有下划线的字母键10十进制数397的十六进制值为（ ）。A. 18D B. 18E C. 27

24、7 D. 361 E.8（以下为不定项选题）11下列电子邮件地址中正确的是（其中表示空格）( )。A. Malin& B. malin C. LinMa& D. LinMa E. MALIN12与二进制小数0.1等值的十六进制小数为（ ）。A. 0.1 B. 0.2 C. 0.4 D. 0.8 E.713关于计算机网络，正确的说法是（ ）。 A调制解调器(Modem)是局域网络设备 B集线器(HuB)是局域网络设备 C网卡(NIC)是局域网络设备 D中继器（Repeater）是局域网络设备E为了使用Internet网提供的服务，必须采用TCP/IP协议14结构化程序的结构由哪三

25、种基本结构组成（ ）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中，每个元素AI,J在存贮时要占4个字节，设I从1变化到7，J从1变化到

26、10，分配内存时是从地址S开始连续按行存贮分配的。试问：A4,8的起始地址为（ ）AS+148 BS+120 CS+128 DS+124 ES+14419. 某数列有1000个各不相同的单元，由低至高按序排列；现要对该数列进行二分法检索（binary search），在最坏的情况下，需检视（ ）个单元A. 1000 B. 10 C. 100 D. 500 E.25020设循环队列中数组的下标范围是1m，其头尾指针分别为f和r，则其元素个数为 ( )。Ar-f Br-f+1 C(r-f+1) MOD m D(r-f+m) MOD m E(r-f+1)MODm二、问题求解：（每题5分,共10分）1

27、. 已知，按中序遍历二叉树的结果为：#$问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树。 2.有2×n的一个长方形方格，用一个1×2的骨牌铺满方格。例如n=3时，为2×3方格。此时用一个1×2的骨牌铺满方格，共有3种铺法 试对给出的任意一个n(n)0)，求出铺法总数的递推公式。 三、写出程序的运行结果：（每小题8分，共32分）PROGRAM EXP1VAR I,S,MAX:INTEGER; A:ARRAY1.10 OF INTEGER;BEGINFOR I:=1 TO 10 DO READ(AI);MAX:=A1;S:=A1;FOR

28、I:=2 TO 10 DO BEGIN IF S<0 THEN S:=0; S:= S+AI; IF S>MAX THEN MAX:=S; END;WRITELN(MAX=,MAX)END.输入：-1 16 24 6 7 8 18 -6 15 34输出：2PROGRAM EXP2 VAR I,J,L,N,K,S,T: INTEGER;B: ARRAY1.10 OF 0.9; BEGINREADLN(L,N);S:=L;K:=1;T:=L; WHILE S<N DO BEGIN K:=K+1;T:=T*L; S:=S+TEND;S:=S-T; N:=N-S-1;FOR I:=1

29、 TO 10 DOBI:=0; J:=11; WHILE N>0 DOBEGIN J:=J-1;BJ:=N MOD L; N:=N DIV LEND;FOR I:=10-K+1 TO 10 DO WRITE(CHR(ORD('A')+BI);END.输入：4167输出:3PROGRAM EXP3 VAR I,J:INTEGER; A:ARRAY1.12 OF INTEGER; PROCEDURE SW(I1,J1:INTEGER); VAR K1:INTEGER; BEGIN FOR K1:=1 TO(J1-I1+1) DIV 1 DO BEGIN AI1+K1-1:=A

30、I1+K1-1+AJ1-K1+1; AJ1-K1+1:=AI1+K1-1-AJ1-K1+1; AI1+K1-1:=AI1-K1+1-AJ1-K1+1; END; END;BEGIN J:=200; FOR I:=1 TO 12 DO BEGIN AI:=I; J:=J-I;END;SW(1,4);SW(5,10);SW(11,14);SW(1,14);FOR I:=1 TO 12 DO BEGIN IF J MOD I =1 THEN WRITE(AI:4); J:=J-AI; END;WRITELN; end.输出：4PROGRAM EXP4(INPUT,OUTPUT); CONST N=1

31、0; VAR S,I:INTEGER; FUNCTION CO(I1:INTEGER):INTEGER; VAR J1,S1:INTEGER; BEGIN S1:=N; FOR J1:=(N-1) DOWNTO (N-I1+1) DO S1:=S1*J1 DIV (N-J1+1); CO:=S1; END; BEGIN S:=N+1; FOR I:=2 TO N DO S:=S+CO(I); WRITELN(S=,S); END.输出：四、完善程序（共2题，每题14分，共28分） 1. 1000！尾0问题【问题描述】以下程序用于统计1000！末尾有多少个0。其中1000！=1´2&#

32、180;3´´1000。实际上我们只要统计1000！有多少个因子10。由于10=5´2，因而只需统计有多少个因子5和2。显然在11000的所有数中，5的因子个数比2的因子个数少。因此，只要统计11000的所有数中共有多少个因子5就行了。program COUNT0;var i,j,n:integer;begin n:=0; for do begin j:=i*5; while =0 do begin j:= end; end; writeln(n:4);end.2. 高精度正整数乘法问题 以下程序用于求任意2正整数的乘积。程序中用a，b表示这2个正整数，并将它们的

33、乘积存于数组ab中。根据数的乘法规则，将a的所有位与b的所有位从低位至高位两两相乘。设a的第i位与b的第j位相乘的结果为ab0，则ab0的个位应加到乘积ab的第i+j-1位上，ab0的十位应加到乘积ab的第i+j位上。在加的过程中也应注意进位。program MULTIPLY;const n=100;Type arr=array1.n of integer;var a,b:arr; ab:array1.2*nof integer; lab,la,w,lb,ab0,ab1,ab2,i,j,t:integer; procedure Init(var c:arr;var length:integer);var i,t,m:integer; ch:Char;begin length:=0; WriteLn('Input a number:'); while (not eoln) do begin length:=length+1; read(ch); clength:= end; readln; writeln(length); WriteLn('The number is '); for i:=1 to length do Write(ci:1); Writeln; m:= for i:=1 to m do begin t:=ci;