kl800.com省心范文网

第五届全国青少年信息学奥林匹克联赛初赛试题及答案(提高组PASCAL)

第五届全国青少年信息学奥林匹克联赛初赛试题
●● ( 提高组 Pascal 语言 二小时完成 ) Pascal 全部试题答案均要求写在答卷纸上,写在试卷纸上一律无效 ●●

多选无分, 一.选择一个正确答案代码,填入每题的话号内(每题 1.5 分,多选无分,共 30 分) 选择一个正确答案代码,填入每题的话号内( 1. 微机内存储器的地址是按( )编址的。 A. 二进制位 B. 字长 C.字节 D. 微处理器的型号 2. 下列诸因素中,对微机工作影响最小的是( ) A.尘土 B. 噪声 C. 温度 D. 湿度 3.在 24*24 点阵的“字库”中,汉字“一”与“编”的字模占用字节数分别是( ) A.32,32 B.32,72 C.72,72 D.72,32 4.将 DOS 系统盘插入 A 驱动器启动机器,随后使用一批应用软件,在此过程中,DOS 系 统盘( ) A. 必须始终插入在 A 驱动器中 B. 不必再用 B. C.可能有时要插入 A 驱动器中 D.可能有时要插入 B 驱动中 5.以下 DOS 命令中,有可能在磁盘上建立子目录的是( ) . A.type B. dir C.xcopy D.cd 6.在 config.sys 文件中,装入特定的可安装设备驱动程序的命令是( ) . A.buffer B.files C.driver D.device 7.计算机能直接执行的指令包括两部分,它们是( ) . A.源操作数与目标操作数 B.操作码与操作数 C.ASCII 码与汉字代码 字符 8、在微机中;通用寄存器的位数是( ) . A 8 位 B.16 位 C.计算机字长 D.32 位 9.在计算机中,字符编码通常采用( ) A.原码 B.反码 C.ASCII 码 D.补码 10. 计算机的软件系统通常分为( ) A 系统软件与应用软件 B 高级软件与一般软件 C 军用软件与民用软件 D 管理软件与控制软件

D.数字与

11. 执行 DOS 命令:C>ATTRIB A:*.*的功能是( ) A.查看 A 盘上所有文件属性 B.查看 A 盘上当前目录中所有文件属性 C.查看 A 盘上所有系统文件属性 D.删去 A 盘上所有隐含文件的属性 12.执件下列 DOS 命令,效果等价的是( )组. A. copy *.for 与 copy *.for con B. copy A: *.* B: 与 xcopy A:*.* B: C. copy fole1.txt + file2.txt 与 copy flle2.txt + file1.txt D. xcopy A:*.* B:/S 与 diskcopy A:B: 13.已知小写字母‘m’的十六进制的 ASCll 码值是 6D,则小写字母‘c’的十六进制的 ASCll 码值是( ) A.98 B.62 C.99 D.63 14、计算机中的数有浮点数与定点数两种,其中用浮点数表示的数,通常由( )两部分 组成。 A.指数与基数 B. 尾数与小数 C. 阶码与尾数 D.整数与小数 15.下列文件名中,属于 DOS 中的保留设备名的为( ) A.AUX B.COM C.CON1 D.PRNL 16 启动计算机引导 DOS 是将操作系统( ) A. 从磁盘调入中央处理器 B. 从内存储器调入高速缓冲存储器 C. 从软盘调入硬盘 D. 从系统盘调入内存储器 17. 十进制算术表达式:3*512+7*64+4*8+5 的运算结果,用二进制表示为( ) . A. 10111100101 B.11111100101 C.1111l0100101 D.11111101101 l8.组成’教授’ (jiao shou )’副教授’ (fu jiao shou )与’讲师’ jiang shi)这三个词 ( 的汉字,在 GB2312-80 字符集中都是一级汉字.对这三个词排序的结果是( ) . A 教授,副教授,讲师 B.副教授,教授,讲师 C 讲师,副教授,教授 D.副教授,讲师,教授 19.不同的计算机,其指令系统也不同,这主要取决于( ) . A 所用的操作系统 B. 系统的总体结构 C.所用的 CPU

D.所用的程序设计语言

20.对具有隐含属性(H)的当前目录下的文件 ab. txt,能成功执行的 DOS 命令是( ) A. TYPE ab.txt B.COPY ab. txt xy. txt C. DIR ab.txt D. REN ab. txt xy. Txt

二.回答问题: (10 分) 回答问题: 将 Ln 定义为求在一个平面中用 n 条直线所能确定的最大区域数目, 例如: n=1 时, 当 L1=2,进一步考虑,用 n 条折成角的直线(角度任意) ,放在平面上能确定的最大区域数 目 Zn 是多少?例如当 n=1 时,Z1=2(如下图所示) :

1 2

当给出 n 后,请写出以下的表达式: Ln=_______________________ Zn=_______________________

(每题 三.阅读程序,并写出程序的正确运行结果: 每题 15 分,共 30 分) 阅读程序,并写出程序的正确运行结果: ( 1、 program exgp1; var i,j,k:integer; a:array[0..100] of integer; begin for i:=0 to 100 do a[i]:=i; for k:=5 downto 2 do begin for i:=1 to 100 do if (i mod k)=0 then a[i]:=0; for i:=1 to 99 do for j:=1 to 100-i do if a[j]>a[i+1] then begin a[j]:=a[j+1]; a[j+1]:=a[j]-a[j+1]; a[j]:=a[j]-a[j+1]; end; end; j:=1; while (a[j]=0) and (j<100) do j:=j+1; for i:=j to 100 do a[0]:=a[0]+a[i]; writeln(a[0]); end. 本题的运行结果是: 2、 设数组 A[1],A[2],…A[N],已存入了数据,调用不同的排序程序,则数据比较的次 数将会不同,试计算出分别调用下列不同的排序程序的比较运算的次数。其中 SWAP (I,J)表示 A[I]与 A[J]进行交换。 ⑴ PROCEDURE SORT1(N:INTEGER) ; var I,j:integer; begin

for I:=1 to n-1 do for j:=1 to n do if a[j]<a[I] then swap(I,j) end; 调用该过程的语句为 SORT1(N) ,比较运算的次数为: ⑵ PROCEDURE SORT2(I,N:INTEGER) ; var j:integer; begin if I=n then write(a[n]); else for j:=I+1 to n do if a[j]<a[I] then swap(I,j) write(a[I]); sort2(I+1,n) end; 调用该过程的语句为 SORT2(N) ,比较运算的次数为: ⑶ PROCEDURE SORT3(I,J:INTEGER) ; var m:integer; begin if I<>j then begin m:=(I+j) div 2; sort3(I,m);sort3(m+1,j); merge;{假设合并的元素分别为 P,G 个,需要比较 P+G 次}; end; end; 调用该过程的语句为 SORT3(N) ,比较运算的次数为: 四、根据题意,将以下程序填写完整(共 30 分) 根据题意,将以下程序填写完整( 1.[问题描述]求一棵树的深度与宽度; (15 分) 树可用数组 TREE:ARRAY[1..N,1..5] OF INTEGER; 其中:TREE[I,1]表示结点号;TREE[1,2]-------TREE[1,5]所属结点 1 2 5 6 11 7 12 3 8 9 4 10

13

如上图可表示为: 1 2 3 4 5 6 7 8 9 10 11 12 13 2 5 8 9 0 0 11 0 0 0 0 13 0 3 6 0 10 0 0 12 0 0 0 0 0 0 4 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

在求解过程中,用到数组 G:ARRAY[1..N,1..7] OF INTEGER; 其中:G[I,1]表示父结点,G[I,2]表示层次,G[I,3]表示本结点号,G[I,4]-----G[I,7]表示子女结点;同时,设 2 个指针 SP1(取数指针) ,SP2(存数指针) [程序清单] program exgp3; const n=13; var I,j,k,sp1,sp2,n1,n2,jmax,p:integer; tree:array[1..n,1..5] of integer; g:array[1..n,1..7] of integer; begin for I:=1 to n do begin tree[I,1]:=I; for j:=2 to 5 do read(tree[I,j]); readln; end; sp1:=1;sp2:=1;g[1,1]:=0;g[1,2]:=1;g[1,3]:=1; for I:=4 to 7 do g[1,I]:=tree[1,I-2]; while 1 do begin p:=g[sp1,2];n2:=g[sp1,3]; 2 ; j:=4; while 3 do begin n1:=g[sp1,j]; j:=j+1; 4 ; g[sp2,1]:=n2;g[sp2,2]:=p;g[sp2,3]:=n1;

for I:=1 to 4 do g[sp2,I+3]:=tree[n1,I+1]; end; 5 ; end; writeln(‘maxd=’,g[sp2,2]); j:=1; k:=g[1,2]; jmax:=0; for I:=2 to sp2 do if 6 then j:=j+1 else begin if j>jmax then jmax:=j; 7 ; k:=g[I,2]; end; if j>jmax then jmax:=j; writeln(‘maxl=’,jmax); end. 2.[问题描述] 用生成法求出 1,2,………,r 的全排列(r<=8) (15 分) [算法过程] 用数组 a:array[1..r] of integer;表示全排列; 初始化时,a[i]:=i,(i=1,2,….,r),设中间的某个排列为 a[1],a[2],….a[r], 则求出下一个排列的算法为: (1) 从后面向前找,直到找到一个顺序为止 (设下标为 j-1,则 a[j-1]<a[j]) (2) 从 a[j]……..a[r]中,找出一个 a[k]比 a[j-1]大的最小元素 (3) 将 a[j-1]与 a[k]交换 (4) 将 a[j],a[j+1],….,a[r]由小到大排序 [程序清单] program exg4; const r=7; var n,I,s,k,j,i1,t:integer; a:array[1..r] of integer; procedure print1; var ik:integer; begin for ik:=1 to r do write(a[ik]:8); writeln; end; begin for I:=1 to r do 1 ; print1; s:=1;

for I:=2 to r do s:=s*I; s:=s-1; for I:= 2 do begin j:=r; while 3 do j:=j-1; k:=j; for i1:=j+1 to r do if 4 then k:=i1; t:=a[j-1]; a[j-1]:=a[k]; a[k]:=t; for i1:=j to r-1 do for k:=i1+1 to r do if 5 then begin t:=a[i1]; a[i1]:=a[k]; a[k]:=t; end; print1; end; end.

第五届)提高组( 语言) NOIP1999 年(第五届)提高组(Pascal 语言)参考答案 一、单项选择题 1. C 2. B 3. C 4. C 5. C 6. D 7. B 8. C 9. C 10.A 11. D 12. B 13. A 14. C 15. B 16. A 17. D 18. D 19. B 20. B 二、问题求解 Ln=n(n+1)/2+1(n≥0) Zn=L2n-2n=2n2-n+1 三、阅读程序,并写出正确的程序运行结果 1.程序运行的结果:970 2. (1)调用该过程的语句为 SORT1(N) ;比较运算的次数为:n(n-1) (2)调用该过程的语句为 SORT2(N) ;比较运算的次数为:n(n-1)/2 (3)调用该过程的语句为 SORT3(N) ;比较运算的次数为:nlog2n+c 四、根据题意,将以下程序填写完善 (1)共 15 分(2+2+3+2+2+2+2=15 分) ① sp1<=sp2 ② p:=p+1 ③ g[sp1,j]<>0 ④ sp2:=sp2+1; ⑤ sp1:=sp1+1 ⑥ k=g[i,2] ⑦ j:=1; (2)共 15 分(每个点 3 分) ① a[i]:=i; ② 1 to s ③ a[j-1]>a[j] ④ (a[i1]>a[j-1]) and (a[i1]<a[k]) ⑤ a[i1]>a[k]