当前位置:首页 >> 学科竞赛 >> 全国青少年信息学奥林匹克联赛初赛练习卷(十三)new答案

全国青少年信息学奥林匹克联赛初赛练习卷(十三)new答案


全国青少年信息学奥林匹克联赛初赛练习卷 (十三) 答案 new
(普及组 PASCAL 语言 二小时完成)
●● 全部试题答案均要求写在答卷纸上,写在试卷纸上一律无效 ●●

一、单项选择题(20 题,每题 1.5 分,共计 30 分。每题有且仅有一个正确答案) 1. 给出三种排序算法:插入排序、冒泡排序和选择排序,这三种排序算法的时间代价

分别 是( ) 。 A. O(n)、O(n2) 、O(logn) C. O(n2)、O(n) 、O(logn) 2. B. O(logn)、O(n) 、O(n2) D. O(n2)、O(n2) 、O(n2)

给出一组数据:10,18,3,4,9,13,15,2,21,9,8,将它们生成一棵二叉排序树, 所需的关键码比较次数为( ) 。 A. 25 B. 24 C. 23 D. 22 ) 、控制器、存储器、输入设备和输出设备组成。 C. CPU D. ALU ) 。 D. KB TB GB

3.

从逻辑功能上讲,计算机主要由( A. ROM B. I/O

4.

在衡量存储器容量时,计量的单位由小到大的顺序是( A. KB GB TB B. TB KB GB C. TB GB KB

5.

下面( A. UNIX

)不是网络操作系统? B. NETWARE C. WINDOWS D. DOS

6.

下列(

)不属于计算机病毒的预防措施。

A. 拥有计算机病毒检测扫描器 B. 拥有实时监控程序 C. 可对未知计算机病毒进行检测 D. 对已知的计算机病毒进行杀毒 7. 汉字的区位码、国标码和机内码(又称内码)是三个不同的概念。假设某个汉字的区号 是十进制数 30,位号是十进制数 63,则在 PC 机中,它的十六进制内码是( ) 。 该汉字的区位码:306310=1E3F16 国标码:区码+3210(或者 2016)位码+3210(或者 2016) ,得到 3E5F16 机内码:将所得的两个字节的最高位都置为 1,最后得到 A. BEDF 8. B. 3E5F C. 9EBF D. B0E3 ) 。

文件夹组织是一个有层次的树状结构,其中最顶层的是( A. 我的电脑 B. 网上邻居 C. 桌面

D. 资源管理器

9.



)是用来在计算机之间进行文件传输的。利用该服务,不仅可以从远程计算机上
1

获取文件,而且还可以将文件从本地机器传送到远程计算机上。 A. DNS B. NFS C. WWW D. FTP

10. 用十六位机器码 1110001010000000 来表示定点整数 (最高位为符号位) , 当它是原码时, 表示的是十进制真值为-25216;当它是补码时,表示的是十进制真值是( ) 。 原码:对负数而言,最高位置 1,其余位不变;对正数而言,最高位为 0,其余位无变 化; 补码:仅对负数而言有所变化(对正数无变化) ,变化的规则是最高位置 1,同时其他 各位取反(即 0 变 1、1 变 0 后,最低位再加上 1) 因此,当题目中的数为补码时,原始的二进制数为:110001010000000(已经去掉了最 高位符号位)- 1 = 110001001111111,各位再取反,得:001110110000000,即 7552,再考虑 到符号位,即-7552 A. -12608 B. -7551 C. -7552 D. -25216

11. Windows 中,文件名最多可以有( A. 8 个 B. 16 个

)个字符。 D. 65536 个 )两个阶段。

C. 255 个

12. 递归算法的执行过程一般来说可先后分成递推和( A. 回溯 B. 回归 C. 返回 D. 合成

13. 堆是一种特殊的数据结构, ( A. 19,75,34,26,97,56 C. 19,56,26,97,34,75

)是一个堆。

B. 97,26,34,75,19,56 D. 19,34,26,97,56,75 ) 。 E)FFFF

14. 128KB 的存储器用十六进制表示,它的最大的地址码是( A)10000 B)EFFF C)1FFFF D)FFFFF 15. TCP/IP 协议共有( )层协议 A)3 B)4 C)5 D)6 16. 192.168.0.1 是属于() 。 A)A 类地址 B)B 类地址

E)7

C)C 类地址

D)D 类地址

E)E 类地址

17. 对给定的整数序列(54,73,21,35,67,78,63,24,89)进行从小到大的排序时,采 用快速排序的第一趟扫描的结果是( ) 。 (问题:哪一个是基准元素?) A) (24,21,35,54,67,78,63,73,89) B) (24,35,21,54,67,78,63,73,89) C) (24,21,35,54,67,63,73,78,89) D) (21,24,35,54,63,67,73,78,89) E) (24,21,35,54,67,63,73,78,89) 18. 一棵含 n 个结点的完全二叉树,其高度 h 为( ) 。 A) n/2 B) log2n C) (log2n)/2 D) [log2n]+1
2

E) 2n-1

19. 对按关键字排好序的线性表进行二分查找,该线性表适合的存储结构为( A. 顺序存储 B. 链接存储 C. 索引存储 D. 散列存储

) 。

20. 操作系统是对( A. 软件

)进行管理的系统软件。 C. 计算机资源 D. 应用程序

B. 硬件

二、问题求解(三小题,每题 4 分,共 12 分) 1. 有 5 本不同的数学书分给 5 个男同学, 有 4 本不同的英语书分给 4 个女同学, 将全部书 收回来后,再重新发给他们,那么,与原方案都不相同的方案有 1140480 种。 答:有 5 本不同的数学书分给 5 个男同学,有 5!种分法;有 4 本不同的英语书分给 4 个女 同学,有 4!种不同的分法。分书方案共有 5! * 4!种,其中每一种方案,与之都不同的方案数 由错排公式给出: 设 D(n)为 n 个数的错排方案数: D(1)=0 D(2)=1 D(n)=(n-1)(D(n-1)+D(n-2)) (n>2) 由此得出,将全部书收回后再重新分发,与原方案都不相同的方案有 5!*4!+D(5)*D(4) 种,即 1140480 种。 2. 把三角形各边分成 n 等分, 过每一分点分别做各边的平行线, 得到一些由三角形的边和 这些平行线所组成的平行四边形。 n 为已知整数, 问能组成 3*C(n+2,4) 个平行四边形。 答:设三角形为△XYZ,如下图所示。将三角形各边分成 n 等分,过每一分点分别做各边 的平行线。延长 XY 边至 Y’,延长 XZ 边至 Z’,扩充成边长为(n+1)的三角形△XY’Z’。
X A B

D Y Y’ I J

C Z Z’ K L

在原三角形中中,ABCD 是有两边分别与 XY、YZ 平行的平行四边形,将它的边 DC 映射成 Y’Z’上的线段 IJ、CB 边映射成 Y’Z’上的线段 KL。显然,I、J、K、L 四点互不重叠, 我们可以发现,这种映射是一一对应的,亦即,有两边分别平行于 XY、YZ 的平行四边形 个数与从(n+2)个元素中取 4 个的方案数一一对应。 因此, 这种平行四边形的个数为 C(n+2,4)。 其中, C(n+2,4)为从 n+2 个元素中取 4 个的方案数。 将三角形连续两次按顺时针旋转 120 度, 可以计算出其他两种类型的平行四边形的个数。因此,答案为 3*C(n+2, 4)。
3

3.

编号为 1 到 13 的纸牌按顺时针顺序排成一圈,有人从编号为 1 的牌顺时针数下去:1, 2,3,…,20,21,…,一圈又一圈,问:当数到数字 N 时,所在纸牌的编号为多少? 答:1 + (N-1) mod 13

三、阅读程序 1. program ex13_3_1; var a, b : integer; procedure pl(x: integer; var y: integer); begin x := x + y; y := x + y; end; begin a:=5; b:=8; pl(a,b); writeln(a:3, b:3); pl(b-a,b); writeln(a:3, b:3); readln end. 输出:5 21 5 58 2. program ex13_3_2; var i, j: integer; a: array[1..3, 1..3] of integer; begin for i:=1 to 3 do begin for j:=1 to 3 do begin if i=3 then a[i,j]:=a[i-1,a[i-1,j]]+1 else a[i,j]:=j; write(a[i,j]); end; writeln end; readln end. 输出:123 123
4

234 3. program ex13_3_3; const n = 10; function fn(n : integer):integer; begin if n < 1 then fn := 0 else if n=1 then fn:=1 else fn:=fn(n-1) + n; end; begin writeln(fn(n)); readln end. 输出:55 4. program ex13_3_4; const n = 7; var p : array[0..n] of integer; b : array[0..n] of integer; i, s, t : integer; begin for i:=0 to n do begin p[i]:=i+1; b[i]:=1; end; i:=0; t:=0; s:=0; while t<=n do begin s:=s+b[i]; if odd(s) and (b[i]=1) then begin write(p[i]:3); t:=t+1; b[i]:=0; end; i:=(i+1) mod (n+1); end; writeln; readln end.

5

输出:1 3 5 7 2 6 4 8 四、完善程序 1. 输出如下图形: 输入:n = 4 1 1 1 1 0 0 1 0 0 1 1 1

1 1 1 1

n = 5 1 1 1 1 1

1 0 0 0 1

1 0 1 0 1

1 0 0 0 1

1 1 1 1 1

【算法分析】 1、先完成上三角形; 2、利用对称、对调填写好整个图形。 【源程序】
program ex13_4_1; type arr = array [1..100, 1..100] of 0..1; var n, k, i, j: integer; a: arr; begin readln(n); k := (1) (n + 1)div 2 ; for i:=1 to k do for j:=i to n-i+1 do begin (2) a[i, j] (4) a[j, i] end; for i:=1 to n do begin for j:=1 to n do write(a[i, j]: 3); writeln; end; readln; := i mod 2; := a[i, j]; := a[i, j]; (3) a[n – i + 1, j]

(5) a[n – j + 1, n – i + 1] := a[i, j];

end. 2. 方阵填数 【问题描述】 在一个 N*N 的方阵中,填入 1,2,……,N*N 个数,并要求构成如下的格式:例: N=4 1 12 11 2 12 16 3 14 15 4 5 6

6

10 N=5 1 16 15 14 13 2 17 24 23 12

9

8

7

3 18 25 22 11

4 19 20 21 10

5 6 7 8 9

【算法分析】 先观察如下图形我们以 N=4,N=5 为例 N=4 1 12 11 10 N=5 1 16 15 14 13 2 17 24 23 12 3 18 25 22 11 4 19 20 21 10 5 6 7 8 9 2 12 16 9 3 14 15 8 4 5 6 7

N=4 时,共两圈,每圈有四个方向(上右下左) ,每个方向的数字分别用不同的下划线 标出,每个方向有 2*i-1 个数字(i 表示圈) 。 N=5 时,共三圈,每个方向的数字分别用不同的下划线标出,每个方向有 2*i-1 个数字 (i 表示圈) 。中心添入 N*N。 通过观察可以发现,填写时要区分 N 的奇偶性(中心的填写和每圈的数字个数不同) 。 右:行不动,列加 1; 下:行加 1,列不动; 左:行不动,列减 1; 上:行减 1,列不动。 每圈之间要调整坐标位置。 【源程序】
program ext13_4_2; var n, k, c, i, j, x, y: integer; a: array [1..100, 1..100] of integer; begin readln(n); k := (1) (n + 1)div 2 ; c := 1; for i:=1 to k do begin
7

{start place} x := i; y := i; {right} for j:=1 to n-(2*i-1) do begin a[x, y] := c; inc(c); end; {down} for j:=1 to n-(2*i-1) do begin a[x, y] := c; end; {left} for j:=1 to n-(2*i-1) do begin a[x, y] := c; inc(c); end; {up} for j:=1 to n-(2*i-1) do begin a[x, y] := c; inc(c); dec(x); end; end; if (5) odd(n) 或 n mod 2 = 1 for i:=1 to n do begin writeln; end; readln; then a[k, k] := n * n; (4) dec(y) ; (3) inc(c) ; inc(x); (2) inc(y) ;

for j:=1 to n do write(a[i, j]: 3);

end. 3. 装球 【问题描述】 设有 n 个盒子(n 足够大,可装入任何数量的球) ,分别编号 1,2,……。同时有 k 个 小球(k>0) ,今将 k 个小球装入到盒子中去。 装入规则如下: (1)第一个盒子不能为空。 (2)装入必须严格按递增顺序进行。 例如,当 k=8,n=6 时,装入方法有 1,2,5 或 1,3,4 (3)在满足上面的两个条件下,要求有球的盒子尽可能多。 (4)装完后,相邻盒子中球个数差的绝对值之和最小(未装的盒子不计) 。 如上例中: 装入法 1,2,5,则差的绝对值之和为 2-1+5-2=4 装入法 1,3,4,则差的绝对值之和为 3-1+4-3=3 【程序要求】给出 k(k 表示小球的个数)之后,求出满足上述四个条件的装入方法。 【算法描述】设计一个数组 A,用数组元素代表盒子,然后依次装入小球。 【源程序】 program ex13_4_3;

8

const n = 20; var i, j, k, L: integer; a: array[1..n] of integer; begin readln(k); ①a[0]:=0 ; j:=1; while ②k>a[j-i] begin do

a[j]:=j; ③k:=k - j ; j:=j+1 end; L := j - 1; while k>0 do begin ④a[L] := a[L] + 1 ; k := k - 1; L := L - 1; end; for i := 1 to end. ⑤ j-1 do write(a[i] : 4)

9


更多相关文档:

全国青少年信息学奥林匹克联赛初赛练习卷(八)new答案

全国青少年信息学奥林匹克联赛初赛练习卷()new答案_学科竞赛_初中教育_教育专区...12 13 14 6 10 15 16 17 9 11 18 13 16 6 8 14 15 11 11 17 …...

全国青少年信息学奥林匹克联赛初赛练习卷(十三)new答案

全国青少年信息学奥林匹克联赛初赛练习卷(十三)new答案_学科竞赛_高中教育_教育专区。全国青少年信息学奥林匹克联赛初赛练习卷 (十三) 答案 new (普及组 PASCAL 语言...

全国青少年信息学奥林匹克联赛初赛练习卷(十四)new答案

全国青少年信息学奥林匹克联赛初赛练习卷(十四)new答案_英语考试_外语学习_教育...[L]:=0; 13 for i:=1 to j do if b[i]<>0 then for L:=1 to ...

全国青少年信息学奥林匹克联赛初赛练习卷(十三)new

全国青少年信息学奥林匹克联赛初赛练习卷(十三)new_学科竞赛_高中教育_教育专区。...单项选择题(20 题,每题 1.5 分,共计 30 分。每题有且仅有一个正确答案)...

全国青少年信息学奥林匹克联赛初赛练习卷(十二)new答案

全国青少年信息学奥林匹克联赛初赛练习卷(十二)new答案_学科竞赛_高中教育_教育...(a:0:2); end. 13 1. 降序组合.给定两个自然数 n、r(n > r) ,输出...

全国青少年信息学奥林匹克联赛初赛练习卷(一)答案

全国青少年信息学奥林匹克联赛初赛练习卷()答案_学科竞赛_高中教育_教育专区。...13 2、运行结果: 7 18 21 45 61 71 83 91 本题是计算什么的问题:本题...

全国青少年信息学奥林匹克联赛初赛练习卷(九)new答案

全国青少年信息学奥林匹克联赛初赛练习卷()new答案_学科竞赛_高中教育_教育专区...91 D. 111-102-35-21 13. 因特网不属于任何个人,也不属于任何组织,其中在...

全国青少年信息学奥林匹克联赛初赛练习卷(十一)new答案

全国青少年信息学奥林匹克联赛初赛练习卷(十一)new答案_学科竞赛_高中教育_教育...两个十进制数 13 和 14,将它们进行“与”运算,结果为( A. 27 B. 12 C...

全国青少年信息学奥林匹克联赛初赛练习卷(三)答案

全国青少年信息学奥林匹克联赛初赛练习卷()答案_IT认证_资格考试/认证_教育...13 cd 编码为 14 d 编码为 15 4-1 4-2 4-3 a~b:共 2 =8(个),b...

全国青少年信息学奥林匹克联赛初赛练习卷(二)答案

全国青少年信息学奥林匹克联赛初赛练习卷()答案_其它课程_高中教育_教育专区。...t(13,350)=(350 div 13 + 1) + (350 mod 13 - 1)=27+11=38 s(...
更多相关标签:
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com