当前位置:首页 >> 学科竞赛 >>

NOIP普及组初赛模拟试题(五)

信息学竞赛普及组初赛模拟试题(五)
一、选择题: (每题 1.5 分,共计 30 分。每题有 5 个选项,前 10 题为单选题,后 10 题为不 定项选择题,全部选对才得分) 。 1.二进制数 11011011 的十进制值是( A. 202 A. 80 亿次 B. 219 C. 193 ) D. 209 ) C. 130 亿次 ) D. 150 亿次

2.我国研制的银河Ⅲ型的超级计算机通过基准程序的测试,其峰值速度是( B. 100 亿次 3.程序段如下,输出’*’的个数是( FOR I:=1 TO 5 DO FOR J:=2 TO I DO Writeln(‘*’) A. 5 B. 10 C. 15 D. 25 E. 30

4.设待排序的记录为(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. 冒泡排序 A. 5 ) C. 直接插入排序 D. 4 D. 希尔排序 ) E. 8 B. 直接选择排序 B. 7 C. 9

5.设无向树 T 有 7 片树叶,其余顶点度均为 3,则 T 中 3 度顶点有多少个(

6.设连通图 G 的顶点数和边数与一立方体相同,即有 8 个顶点和 12 条边。任意一棵 G 的生成 树的总边数为( ) A.7 B. 8 C. 9 D. 10 E. 11 7.设有两个散列函数 h1(k)=k mod 13 和 h2(k)=k mod 11 +1,散列表为 T[0?12],用二次 散列法解决冲突。函数 h1 用来计算散列地址,当发生冲突时,h2 作为计算下一个探测地址 的地址增量。假定某一时刻散列表的状态为: 0 1 2 80 A. 4 B. 5 3 4 5 44 C. 6 6 7 8 9 35 )。 E. 8 D. 7 10 11 12

下一个被插入的关键码为 57,其插入的位置为(

请根据下面一段 PASCAL 程序,判断第 8、9 题。 for h :=1 to n-1 do begin x :=A[h+1]; k :=h; while (k>=1) and (A[k]>x) do begin A[k+1] :=A[k]; k:=k–1 end A[k+1] :=x End 8.假设在程序开始执行时,数组 A[1?n]是一组随机整数。下列答案中,哪一个最好的描述 了最差情况下的程序排序的时间复杂度?( A. O(n log2 )
n


n

B. O(n)

C. O(log2 )

D. O(n )

2

E. O(2n)

9. 假设在程序开始执行时,数组 A[1?n]是按关键字非递减有序排列时,下列答案中,哪一 个最好的描述了最好情况下的程序排序的时间复杂度?( A. O(n log2 )
n


2

B. O(n)

C. O(log2 )

n

D. O(n )

E. O(2n)

10.对下列四个序列用快速排序方法进行排序,以序列的第一个元素为划分的基准,在第一趟 划分过程中,元素的移动数最多的是哪一个序列( A. 70 , 65 , 34 , 82 , 53 , 25 , 90 C. 34 , 25 , 53 , 65 , 90 , 82 , 70 E. 65 , 34 , 82 , 70 , 25 , 53 , 90 11.在计算机运行时,把程序和数据一样存放在内存中,这是 1946 年由_______所领导的研究 小组正式提出并论证的。 ( A. 图灵 ) C. 布尔 ) B. 二进制数中右起第 10 位上的 1 相当于 2
10



B. 82 , 53 , 25 , 70 , 65 , 34 , 90 D. 53 , 25 , 65 , 70 , 34 , 90 , 82

B. 冯·诺依曼

D. 赫夫曼

E. 哈希

12.下面关于计算机的说法正确的是(

A. 微机内存容量的基本计量单位是字节

C. CPU 每执行一个指令,就完成一步基本运算或判断 D. 1TB=1024MB A. 必须在性能较高的机器上运行 E. 32 位的计算机中的“32”指的是字长 ) B. 必须经过良好培训的高水平的程序员使用 13.为什么说 PASCAL 是“高级语言” ,是因为它(

C. 离机器的硬件较远 A.广义表 B. 二叉树

D. 开发的时间较长 ) C. 稀疏矩阵 )

E. 程序的性能较好 D. 串 E. 队列

14.以下数据结构中,哪一个是线性结构?(

15.在下面关于计算机系统硬件的说法中不正确的是( A. 没有外部设备的计算机称为祼机

B. 当关闭计算机电源后,RAM 中的程序和数据就消失了 C. 软盘和硬盘上的数据均可由 CPU 直接存取 D. 软盘和硬盘驱动器既属于输入设备又属于输出设备 E. CPU 主要由运算器、控制器和寄存器组成 16. 下面关于算法的正确说法是( A. 算法必须有输出 ) C. 算法不一定有输入 E. 算法是程序的灵魂 ) B. 算法必须在计算机上用某种语言实现

D. 算法必须在有限步执行后能结束 17.以下关于结构化程序的说法中,正确的是( A. 结构化程序是由单入口,单出口和循环三种结构组成 B. 结构化程序是出顺序、单入中和单出口三种结构组成 C. 结构化程序是由顺序、循环和 GOTO 语句结构组成 D. 结构化程序是由顺序、循环和分支三种结构组成 E.“自顶向下,逐步求精”是结构化程序设计方法的特点

18.栈 S 最多能容纳 4 个元素。现有 6 个元素按 1,2,3,4,5,6 的顺序进栈,问下列哪一 个序列是可能的出栈序列?( b ) A. 5,4,3,2,1,6 D. 1, 4, 6, 5, 2, 3 A.快速排序 B. 3, 2, 5, 4, 1, 6 E. 4,5,3,6,2,1 ) D. 冒泡排序 E.选择排序 C. 希尔排序 C. 2, 3, 5, 6, 1, 4

19.下列排序算法中,哪些排序是不稳定的( B. 基数排序 ) 20.下列说法正确的是(

A. 解释程序是接受参数,按照某一样板产生机器语言的计算机程序 B. BASIC 语言程序通常需解释执行 C. 连接程序可以把经编译程序产生的目标程序变成可执行的机器语言程序 D. 就执行速度而言,编译程序比解释程序快 E. PASCAL 通常是先编译后执行 二、问题求解题(每题 5 分,共计 10 分) 1. 由四个结点可以构造多少种不同的二叉树 。 2. 下图是一个设想有 5 项活动的活动网。其中有 6 个事件 V1,V2,? V5,每个事件表示在 它之前的活动已经完成,在它之后的活动可以开始。V1 表示整个工程的开始,V2 表示结束,

与每个活动相联系的数 ax(x=1?6)是执行该活动所需的时间(单位:天) 。问完成整项工程 至少需要 天,影响工程进度的关键活动有哪些: 。

三、程序阅读理解题 (每题 8 分,共计 32 分) 1.program ex11_8; var n,i,j,k,p:longint; begin write('N=12'); i:=2;j:=0;k:=1; repeat inc(i);p:=j+k;j:=k;k:=p; until i=12; writeln('F(',12,')=',p); end. 运行结果为: 2.program example; Var n:byte; a:array[1..100] of longint; function f(n:byte):longint; var i:longint; begin if a[n-1]>0 then i:=a[n-1] else i:=f(n-1); if a[n-2]>0 then i:=i+a[n-2] else i:=i+f(n-2); a[n]:=i;f:=i; end; begin fillchar(a,sizeof(a),0); a[1]:=1;a[2]:=1; writeln('F(',8,')=',f(8));

end. 运行结果为: 3.program example3 Begin a[1]:=1;t:=0; for i:=2 to 6 do begin s:=0; for j:=1 to i-1 do s:=s+a[j]; a[i]:=s+1; end; for i:=1 to 6 do t:=t+a[i]; writeln(‘t=’,t); end. 运行结果为: 4.program example4 var i,s,max:integer; begin for i:=1 to 10 do read(a[i]); max:=a[1]; s:=a[1]; for i:=2 to 10 do begin if s<0 then s:=0; s:=s+a[i]; if s>max then max:=s; end; writeln(‘max=’,max); end. 输入:8 9 –1 24 6 5 11 15 –28 9 运行结果为: 。 。 。

四、程序完善题 (每题 14 分,共计 28 分) 1、n×n 方阵的每行每列都是自然数 1..n 的一个全排列,每行(列)无重复数字。例:n=5 时, 1 4 3 2 5 5 3 2 1 4 4 2 1 5 3 3 1 5 4 2 2 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 example1; const maxn=10000; var a:array[1..maxn] of integer; x,y,n:integer; function f(x,y:integer):integer; var b:integer; begin (1) (2) if x<=0 then f:=a[x]; end; begin write('Enter n:'); readln(n); if (n<2) or (n>maxn) then exit; write('Enter first line:'); for x:=1 to n do read(a[x]); (3)

writeln('Output:'); for x:=1 to n do write(a[x]:4); writeln; for y:=2 to n do begin for x:=1 to n do write( writeln; end; end. 2.[程序说明] 设有n个人依次围成一圈,从第 1 个人开始报数,数到第m个人出列,然后 从出列的下一个人开始报数,数到第m个人又出列,?,如此反复到所有的人全部出列为止。 设n个人的编号分别为 1,2,?,n,打印出出列的顺序。 本题用数组建立标志位等方法求解,用数组实现链式结构。数组 a[i]作为"指针"变量来 使用,a[i]存放下一个结点的位置。设立指针 j 指向当前结点,则移动结点过程为 j:=a[j], 当数到 m 时,m 结点出链,则 a[j]:=a[a[j]]。 [程序] program example; const n=14;m=4; var a:array[1..n] of integer; i,j,k,p:integer; begin for i:=1 to n-1 do a[i]:=i+1; a[n]:=1; (1) ; k:=1; p:=0; repeat (2) ; k:=k+1; if k=m then begin write(a[j]:4); p:=p+1; (4) :4);

(3) (4) End until p=n; end. 参考答案

; ;

一、选择题: (每题 1.5 分,共计 30 分。每题有 5 个选项,前 10 题为单选题,后 10 题为不 定项选择题,全部选对才得分) 。 1 2 3 4 5 6 7 8 9 10

B
11

C
12

B
13

D
14

A
15

A
16

E
17

D
18

B
19

E
20

B

ACE

C

DE

AC

ABCDE

DE

BE

AC

BCDE

二、问题求解题(每题 5 分,共计 10 分) ) 1、 14 2、 15 (2 分) a1,a4,a3,a2 (3 分)

三、程序阅读理解题 (每题 8 分,共计 32 分) 1、F(12)=89 2、F(8)=21 3、 t=63 4、max=77

四、程序完善题 (每题 14 分,共计 28 分) 1、① 2、① b:=y-x; j:=n ; ② ② x:=1-b; j:=a[j]; ③ ③ x:=x+n ; a[j]:=a[a[j]]; ④ ④ f(x,y) k:=1;


相关文章:
NOIP普及组初赛模拟试题(五).doc
NOIP普及组初赛模拟试题(五) - 信息学竞赛普及组初赛模拟试题(五) 一、选
noip普及组初赛模拟试卷(附答案).doc
noip普及组初赛模拟试卷(附答案) - 选择一个正确答案代码 (A/B/C/D) ,填入每题的括号内 (每题 1.5 分,多选无分, 共 30 分) 题号 1 2 3 4 5 6 ...
noip普及组初赛模拟试卷(附答案)分析.doc
noip普及组初赛模拟试卷(附答案)分析 - 选择一个正确答案代码 (A/B/C/D) ,填入每题的括号内 (每题 1.5 分,多选无分, 共 30 分) 题号 1 2 3 4 5...
noip普及组初赛模拟试卷(附答案)考前模拟.doc
noip普及组初赛模拟试卷(附答案)考前模拟_学科竞赛_初中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档noip普及组初赛模拟试卷(附答案)考前模拟_学科竞赛_初中...
noip普及组初赛模拟试卷.doc
noip普及组初赛模拟试卷 - 学校 姓名 年级 1.选择一个正确答案代码(A/B/C/D),填入每题的括号内 (每题 1.5 分,多选无分, 共 30 分) 题号 选择 题号 ...
noip普及组初赛模拟试卷1(附答案).doc
noip普及组初赛模拟试卷1(附答案) - 1. 计算机中的数有浮点数与定点数两
NOIP普及组初赛历年试题及答案选择题篇.doc
NOIP普及组初赛历年试题及答案选择题篇 - NOIP 普及组初赛历年试题及答案
noip普及组初赛模拟试卷6(附答案).doc
noip普及组初赛模拟试卷6(附答案) - 选择题 1.大家知道, 不同类型的存
NOIP普及组初赛历年试题及答案阅读题篇.doc
NOIP 普及组初赛历年试题及答案阅读题篇阅读程序写结果(共 4 题,每题 8
noip普及组初赛模拟试卷8(附答案).doc
noip普及组初赛模拟试卷8(附答案) - 选择题 1.光盘根据基制造材料和记录
NOIP普及组初赛历年试题及答案求解题篇.pdf
NOIP普及组初赛历年试题及答案求解题篇 - NOIP 普及组初赛历年试题及答案
noip普及组初赛模拟试卷11(附答案).pdf
noip普及组初赛模拟试卷11(附答案) - 上课时间安排 9/5 9/12 1
noip普及组初赛模拟试卷15(附答案).doc
noip普及组初赛模拟试卷15(附答案) - 1. 在磁盘上建立子目录有许多优点
noip普及组初赛模拟试卷23(附答案).doc
noip普及组初赛模拟试卷23(附答案) - 选择题 1. 以下不属于信息的是_
noip普及组初赛模拟试卷9(附答案).doc
noip普及组初赛模拟试卷9(附答案) - 选择题 1. C 语言解释程序属于_
noip普及组初赛模拟试卷1(附答案).pdf
noip普及组初赛模拟试卷1(附答案) - 1. 计算机中的数有浮点数与定点数两
NOIP普及组初赛历年试题及答案选择题篇.doc
NOIP普及组初赛历年试题及答案选择题篇 - NOIP 普及组初赛历年试题及答案
noip普及组初赛模拟试卷.doc
noip普及组初赛模拟试卷 - 学校 姓名 年级 1.选择一个正确答案代码(A/B/C/D),填入每题的括号内 (每题 1.5 分,多选无分, 共 30 分) 题号 选择 题号 ...
noip普及组初赛模拟试卷17(附答案).doc
noip普及组初赛模拟试卷17(附答案) - 选择题 1.计算机的特点是处理速度
NOIP2013普及组初赛模拟试题1(含答案).doc
NOIP2013普及组初赛模拟试题1(含答案)_财会/金融考试_资格考试/认证_教育专区。NOIP普及组C语言模拟试题 含答案 NOIP 2013 模拟试题 资料④ NOIP 2013 初赛模拟题...
更多相关标签: