《信息学竞赛普及组初赛模拟试题》由会员分享，可在线阅读，更多相关《信息学竞赛普及组初赛模拟试题（45页珍藏版）》请在金锄头文库上搜索。
1、信息学竞赛普及组初赛模拟试题（五）一、选择题：（每题 1.5 分，共计 30 分。每题有5 个选项，前 10题为单选题， 后 10 题为不定项选择题，全部选对才得分）。1. 二进制数11011011 的十进制值是（ ）A. 202 B. 219 C. 193 D. 2092. 我国研制的银河III型的超级计算机通过基准程序的测试，其峰值速度是（）A. 80 亿次 B. 100 亿次 C. 130 亿次 D. 150 亿次3. 程序段如下：FOR I:=1 TO 5 DOFOR J:=2 TO I DOWriteln（ * ）输出*的个数是（ ）A. 5 B. 10 C. 15 D. 25 E.
2、 304. 设待排序的记录为（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. 设连通
3、图G的顶点数和边数与一立方体相同，即有8个顶点和12条边。任意 一棵G的生成树的总边数为（）A7B. 8 C. 9 D. 10 E. 117. 设有两个散列函数 h1（k）=k mod 13 和 h2（k）=k mod 11 +1，散列表为 T012， 用二次散列法解决冲突。函数hl用来计算散列地址，当发生冲突时，h2作为计 算下一个探测地址的地址增量。假定某一时刻散列表的状态为：0 1 2 3 4 5 6 7 8 9 10 11 1280 4435下一个被插入的关键码为 57，其插入的位置为( 。A. 4B. 5C. 6 D. 7 E. 8请根据下面是一段PASCAL程序,判断第8、9题。f
4、or h :=1 to n-1 do beginx :=Ah+1; k :=h;while (k=1) and (Akx) do beginAk+1 :=Ak;k:=k - 1endAk+1 :=xend8假设在程序开始执行时，数组Aln是一组随机整数。下列答案中，哪一个 最好的描述了最差情况下的程序排序的时间复杂度？( )A. O(n log2 n) B. 0(n) C. O(log2n) D. 0(n2) E. 0(2n)9假设在程序开始执行时，数组A1n是按关键字非递减有序排列时，下列答 案中，哪一个最好的描述了最好情况下的程序排序的时间复杂度？( )A. O(n log2 n) B.
5、O(n) C. 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. 在计算机运行时，把程序和数据一样存放在
6、内存中，这是1946年由所领导的研究小组正式提出并论证的。( )A. 图灵B. 冯诺依曼C. 布尔D. 赫夫曼E. 哈希12. 下面关于计算机的说法正确的是（ ）A. 微机内存容量的基本计量单位是字节B. 二进制数中右起第 10 位上的 1 相当于 210C. CPU 每执行一个指令，就完成一步基本运算或判断D. 1T=1024MBE. 32 位的计算机中的“32”指的是字长13. 为什么说 PASCAL 是“高级语言”，是因为它（ ）A. 必须在性能较高的机器上运行B. 必须经过良好培训的高水平的程序员使用C. 离机器的硬件较远D. 开发的时间较长E. 程序的性能较好14. 以下数据结构中，
7、哪一个是线性结构？（ ）E. 队列A. 广义表B.二叉树 C.稀疏矩阵D.串15. 在下面关于计算机系统硬件的说法中不正确的是（口A. 没有外部设备的计算机称为祼机B. 当关闭计算机电源后，RAM中的程序和数据就消失了C. 软盘和硬盘上的数据均可由 CPU 直接存取D. 软盘和硬盘驱动器既属于输入设备又属于输出设备E. CPU 主要由运算器、控制器和寄存器组成16. 下面关于算法的正确说法是（ ）A. 算法必须有输出B. 算法必须在计算机上用某种语言实现C. 算法不一定有输入D. 算法必须在有限步执行后能结束E. 算法是程序的灵魂17. 以下关于结构化程序的说法中，正确的是（ ）A. 结构化程
8、序是由单入口，单出口和循环三种结构组成B. 结构化程序是出顺序、单入中和单出口三种结构组成C. 结构化程序是由顺序、循环和 GOTO 语句结构组成D. 结构化程序是由顺序、循环和分支三种结构组成E. “自顶向下，逐步求精”是结构化程序设计方法的特点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, 3E. 4，5，3，6，2，119. 下列排序算法中，哪些排序是不稳定的（
9、）A.快速排序B.基数排序C.希尔排序D.冒泡排序 E.选择排序20. 下列说法正确的是（ ）A. 解释程序是接受参数，按照某一样板产生机器语言的计算机程序B. BASIC 语言程序通常需解释执行C. 连接程序可以把经编译程序产生的目标程序变成可执行的机器语言程序D. 就执行速度而言，编译程序比解释程序快E. PASCAL 通常是先编译后执行二、问题求解题（每题 5 分，共计 10 分）1. 由四个结点可以构造多少种不同的二叉树 .2. 下图是一个设想有11项活动的活动网。其中有9个事件VI, V2,V9,每个 事件表示在它之前的活动已经完成，在它之后的活动可以开始。 V1 表示整个工 程的开
10、始，V9表示结束，与每个活动相联系的数ax（x=lll）是执行该活动所需 的时间（单位：天）。问完成整项工程至少需要 天,影响工程进度的关 键活动有哪些：。V2 V7V1V5V9V3 V8V6V4三、程序阅读理解题 （每题8 分，共计32 分）1program ex11_8;varn,i,j,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.10
11、0 of longint;function f(n:byte):longint;var i:longint;beginif an-10 then i:=an-1else i:=f(n-1);if an-20 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 example3 begina1:=1;t:=0;for i:=2 to 6 dobegins:=0;for j:=1 to i-1 do
12、s:=s+aj;ai:=s+1;end;for i:=1 to 6 dot:=t+ai; writeln(t=,t); end.运行结果为： 4program example4 var i,s,max:integer;beginfor i:=1 to 10 do read(ai);max:=a1; s:=a1;for i:=2 to 10 dobeginif smax then max:=s;end;writeln（max=,max）;end.输入：8 9 - 1 24 6 5 11 15 -28 9 运行结果为：四、程序完善题 （每题14分，共计28分）l. nXn方阵的每行每列都是自然数l
13、.n的一个全排列，每行（列）无重复数字。 例：n = 5 时，1 4 3 2 55 3 2 1 44 2 1 5 33 1 5 4 22 5 4 3 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
14、;const maxn=10000;vara:array1.maxn of integer;x,y,n:integer;function f（x,y:integer）:integer;varb:integer;begin(1)(2)if x=0 then (3)f:=ax;end;beginwrite(Enter n:); readln(n);if (nmaxn) then exit;write(Enter first 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 dobeginfor x:=1 to n do write( (4) :4);writeln;end;end.2. 程序说明设有n个人依次围成一圈，从第1个人开始报数，数到第m个人 出列，然后从出列的下一个人开始报数，数到第m个人又出列，如此反复到 所有的人全部出列为止。设n个人的编号分别为1, 2，n，打印出出列的顺 序
