信息学竞赛初赛模拟试题16套

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

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

3、条边。任意一棵G的 生成树的总边数为（）A. 7 B. 8 C. 9 D. 10 E. 117.设有两个散列函数hl 解决冲突。探测地址的地址增量（k） =k mod 13和h2 （k） =k mod 11 +1,散列表为T0，用 二次散列法 函数hl用來计算散列地址，当发生冲突时，h2作为计算下一个 假 定某一时刻散列表的状态为：6 7 8 9101112804435下一个被插入的关键码为57,其插入的位置为（）A. 4B. 5C. 6D. 7E. 8请根据下面是一段PASCALS序,判断第8、9题。for h :二1 to nT do beg inx :=Ah+l;k :=h;while

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

5、 n)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.在计算机运行时，把程序和数据一样存放在内存中，这是1946年由 所领导的研究小组正式提岀并论证的。()A.图灵B.冯？诺依曼C.布尔D.赫夫曼E.哈希12.下面关于计算机的说法

6、正确的是()A.微机内存谷量的基本计量单位是子节B.二进制数中右起第10位上的1相当于210C.CPU每执仃个扌曰令，就兀成步基本运算或判断D.1T 二 1024MBE.32位的计算机中的“32”指的是字长13.为什么说PASCAI是“高级语言”,是因为它()A.必须在性能较咼的机器上运行B.必须经过良好培训的高水平的程序员使用C.离机器的硬件较远D.开发的时间较长E.程序的性能较好14?以下数据结构中，哪一个是线性结构？()A.广义表B.二叉树C.稀疏矩阵D.串E.队列15. 在下而关于计算机系统硬件的说法中不正确的是()A. 没有外部设备的计算机称为裸机B. 当关闭计算机电源后，RAM中的

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

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

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

10、int;begi nwrite( 5 N 二 12');i:=2;j:=O;k:=l;repeatinc(i);p:二 j+k;j: 二 k;k:二 p;until i 二 12;writeln( ，F(', 12,', p);end.运行结果为：2. program example; varn:byte;a:array1. . 100 of longint;fun cti on f (n:byte):l ongint; var i:l ongint;beginif an-l>0 the n i:=a n-Ielse i :=f (n T);if a n2>

11、0 then i:=i+a n2else i:=i+f( n-2);an :=i;f:=i;begi nfill char (a, sizeof(a) , 0 )al ：=l;a2 ：=1;writeinF (', 8,') 二' , f );end.运行结果为：3. program example3begi na1:=1;t:=0;for i:=2 to 6 dobegins:=0;for j:=1 to iT dos:=s+aj;ai:二 s+1;end;for i:=1 to 6 dot :=t+ai;write in ( 't 二',t );en

12、d.运行结果为：4. program example4var i,s,max:i nteger;begi nfor i:=1 to 10 do read (ai) max:=al; s:=al;for i:=2 to 10 dobeginif s<0 then s:二 0;s:二 s+ai;if s>max the n max:=s;end;writeln ( "max 二，,max);end.输入：8 9- 1 24 6 5 11 15 - 28 9 运行结果为：四、程序完善题(每题14分，共计28分)I. nXn方阵的每行每列都是自然数l ? .n的一个全排列，每行(

13、列)无重复数字。例:n = 5 时，1 43 2553 21442 15331 54225 431输入n 0 = 2)和笫一行数字(不检查错误)输出一个满足要求的方阵因为只是要求每行(列)无重复数字，对第一行的每个数字，都四十五度斜向下写，写到 尽头就从行开头开始。这样就不会重复。对于经过第y行，第x列的直线，斜率21设：y 二 x+b代入坐标，得出：b二y-x令y二1,取首行的数：x=y-bx从1开始，到n,如果x为0或负数，则x二x+n,取出第一行的数。 程序只用一维数组，存笫一行的数字。program examp1e2;con stmax n=10000;vara:array1 maxn

14、 of in teger;x, y, n: in teger;function f (x,y:integer ) :integer;varb:i nteger;begi nif x<=0 then(3)f：=ax;end;begi nwriteEnter n:; readln(n); if (n<2) or (n>maxn) then exit; write(，Enter first line/ );for x: = I to n do read (ax); write inO utput:');for x: = I to n dowrite(a x:4);write in;for y:=2to n dobeginfor x:=l write In;to n do write (end.2. 程序说明设有n个人依次围成一圈，从第1个人开始报数，数到第m个人出列，然后从 出列的下一个人开始报数，数到第 m个人又出列，如此反复到所有的人全部出列为止。设n个人的编号分别为1, 2,，n,打卬出111列的顺序。本题用数组建立标志位等方法求解，用数组实现链式结构。数组ai作为指针变量来使用，ai存放下一个结点的位置。设立指针j指向当前结点，则移动结点过程为 j : =aj, 当数到m