N O I P2000普及组初赛
试题答案
https://www.sodocs.net/doc/833469083.html,work Information Technology Company.2020YEAR
第六届全国青少年信息学(计算机)奥林匹克分区联赛试题
(普及组 PASCAL语言二小时完成)
●●全部试题答案均要求写在答卷纸上,写在试卷纸上一律无效●●
一、选择一个正确答案代码(A/B/C/D),填入每题的括号内(每题1.5分,多选无
分,共30分)
1.下列无符号数中,最小的数是().
A.(11011001)2 B.(75)10 C.(37)8 D.(2A)16
2.在外部设备中,绘图仪属于().
A.输入设备 B.输出设备 C.辅(外)存储器 D.主(内)存储器
3.GB2312-80 规定了一级汉字3755个,二级汉字3008个,其中二级汉字字库中的汉字是以()为序排列的.
A.以笔划多少 B.以部首 C.以ASCII码 D.以机内码
4.算法是指().
A.为解决问题而编制的计算机程序 B.为解决问题而采取的方法与步骤C.为解决问题而需要采用的计算机语言 D.为解决问题而采用的计算方法
5.RAM 中的信息是().
A.生产厂家预先写入的 B.计算机工作时随机写入的
C.防止计算机病毒侵入所使用的 D.专门用于计算机开机时自检用的
6.计算机主机是由CPU 与()构成的.
A.控制器 B.运算器 C.输入、输出设备 D.内存储器
7.计算机病毒的特点是().
A.传播性、潜伏性、易读性与隐蔽性 B.破坏性、传播性、潜伏性与安全性 C.传播性、潜伏性、破坏性与隐蔽性 D.传播性、潜伏性、破坏性与易读性
8.设循环队列中数组的下标范围是1–n,其头尾指针分别为f和r,则其元素个数为().
A.r- f B.r- f +1
C.(r- f ) MOD n+1 D.(r- f + n) MOD n
9.在待排序的数据表已经为有序时,下列排序算法中花费时间反而多的是().
A 堆排序
B 希尔排序
C 冒泡排序
D 快速排序
10.Internet 的规范译名应为().
A.英特尔网 B.因特网 C.万维网 D.以太网
11.WINDOWS 9X 是一种()操作系统.
A.单任务字符方式 B.单任务图形方式
C.多任务字符方式 D.多任务图形方式
12.某种计算机的内存容量是640K, 这里的640K 容量是指( ) 个字节.A.640 B. 640*1000 C. 640 * 1024 D.640*1024*1024
13.在Windows 9X中,菜单项后带有符号“…”,表示该菜单项( ) .A.可以进行开关选择 B.执行时有对话框
C.有若干子命令 D.不能执行
14.某数列有1000个各不相同的单元,由低至高按序排列;现要对该数列进行二分法检索(binary search),在最坏的情況下,需检视( )个单元.
A.1000 B. 10 C. 100 D. 500
15.已知数组A中,每个元素A[I,J]在存贮时要占3个字节,设I从1变化到8,J 从1变化到10,分配内存时是从地址SA开始连续按行存贮分配的。
试问:A[5,8]的起始地址为().
A.SA+141 B.SA+180 C.SA+222 D.SA+225
16.大家知道,不同类型的存储器组成了多层次结构的存储器体系,按存取速度从快到慢的排列是().
A.快存 / 辅存 / 主存 B.外存 / 主存 / 辅存
C.快存 / 主存 / 辅存 D.主存 / 辅存 / 外存
17.线性表若采用链表存贮结构,要求内存中可用存贮单元地址().A.必须连续 B.部分地址必须连续
C.一定不连续 D.连续不连续均可
18.下列叙述中,正确的是().
A.线性表的线性存贮结构优于链表存贮结构
B.队列的操作方式是先进后出
C.栈的操作方式是先进先出
D.二维数组是指它的每个数据元素为一个线性表的线性表
19.电线上停着两种鸟(A,B),可以看出两只相邻的鸟就将电线分为了一个线段。这些线段可分为两类:一类是两端的小鸟相同;另一类则是两端的小鸟不相同.
已知:电线两个顶点上正好停着相同的小鸟,试问两端为不同小鸟的线段数目一定是( ).
A .奇数
B .偶数
C .可奇可偶
D .数目固定
20.请仔細閱读下列程序段:
PASCAL 语言 BASIC 语言
上列程序段的正确輸出是( ).
A .-1
B .-2
C .-3
D .-4
二、问题解答(每题7分,共14分)
1.已知,按中序遍历二叉树的结果为:abc
问:有多少种不同形态的二叉树可以得到这一遍历结果,并画出这些二叉树。
2.有2×n 的一个长方形方格,用一个1×2的骨牌铺满方格。例如n=3时,为2×3方格。 此时用一个1×2的骨牌铺满方格,共有3种铺法:
试对给出的任意一个n
(n>0),求出铺法总数的递推公式。
三、阅读程序,并写出程序正确的运行结果(
10+16分,共26分) 1.PROGRAM NOI_002;
VAR I, J, L, N, K, S, T : INTEGER; B : ARRAY[1..10] OF 0..9; BEGIN
READLN(L,N); S:=L; K:=1; T:=L;
WHILE S BEGIN K:=K+1; T:=T*L; S:=S+T END; S:=S-T; N:=N-S-1; FOR I:=1 TO 10 DO B[I]:=0; J:=11; WHILE N>0 DO BEGIN J:=J-1; B[J]:=N MOD L; N:=N DIV L END; FOR I:=10-K+1 TO 10 DO WRITE(CHR(ORD('A')+B[I])); END. 输入: 4 167 输出: 2.PROGRAM NOI_004; VAR I, J, J1, J2, P, Q : INTEGER; P1 : BOOLEAN; B,C : ARRAY[1..100] OF INTEGER; BEGIN READLN(Q,P); J:=1; P1:=TRUE; B[J]:=Q; J1:=0; WHILE (Q>0) AND P1 DO BEGIN J1:=J1+1; C[J1]:=Q*10 DIV P; Q:=Q*10-C[J1]*P; IF Q>0 THEN BEGIN J2:=1; WHILE (B[J2]<>Q) AND (J2<=J) DO J2:=J2+1; IF B[J2]=Q THEN BEGIN P1:=FALSE; WRITE('0.'); FOR I:=1 TO J2-1 DO WRITE(C[I]:1); WRITE('{'); FOR I:=J2 TO J1 DO WRITE(C[I]:1); WRITELN('}') END ELSE BEGIN J:=J+1; B[J]:=Q END END END; IF Q=0 THEN BEGIN WRITE('0.'); FOR I:=1 TO J1 DO WRITE(C[I]:1); WRITELN END; READLN END. 输入① 1 8输出 输入② 2 7输出 四、完善程序(每题15分,共30分) 1.将2n个0和2n个1,排成一圈。从任一个位置开始,每次按逆时针的方向以长度为n+1的 单位进行数二进制数。 要求给出一种排法,用上面的方法产生出来的2n+1个二进制数都不相同。 例如,当n=2时, 即22个0 和22个1 排成如下一圈: 比如,从A位置开始,逆时针方向取三个数000,然后再从B位置上开始取三个数001,接着从C开始取三个数010,...可以得到000,001,010,101,011,111,110,100共8个二进制数且都不相同。 程序说明 以n=4为例,即有16个0,16个1, 数组a用以记录32个0,1的排法, 数组b统计二进制数是否已出现过。 程序清单 PROGRAM NOI00; VAR A : ARRAY[1..36] OF 0..1; B :ARRAY[0..31] OF INTEGER; I, J, K, S, P : INTEGER; BEGIN FOR I:=1 TO 36 DO A[I]:=0; FOR I:=28 TO 32 DO A[I]:=1; P:=1; A[6]:=1; WHILE (P=1) DO BEGIN J:=27; FOR I:=1 TO 32 DO S:=0; FOR I:=1 TO 32 DO FOR J:=I TO I+4 DO WRITE(A[J]); WRITELN END. 2.多项式的乘法。 例如有如下多项式: