nbhkdz.com冰点文库

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


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

一、单项选择题(20 题,每题 1.5 分,共计 30 分。每题有且仅有一个正确答案) 1. 计算机系统由硬件系统和软件系统组成, 平常我们所说的计算机软件是由程序和 ( 组成。

A. 软盘 2. B. 文档 C. 操作平台 D. 相关软件工具 ) 。 )

下面有关数制的式子中,正确的是(

A. (A2B.C5)16 = (101000101011.01011100)2 B. 在八进制中,2*6=14 C. (110010)2+(16)10=(1000100)2 D. (01000)2=(8)8 3. 汉字输入方法实质上是对汉字进行编码。下面( )不是汉字输入方法的编码方式 。 A. 音码 4. B. 形码 C. 音形码 D. ASCII 码

Windows 是一种多任务的操作系统,各个 Windows 应用程序之间可以非常方便地通过 ( )来交换数据。 A. 复制 B. 读/写文件 C. 剪贴板 D. 剪切

5.

因特网(Internet)给我们提供了资源共享、浏览、检索信息和远程登录等多种服务。 下面几个选项中,用于远程登录的是( ) 。 A. Telnet B. E-mail C. TCP/IP ) 。 B. 非顺序存储的线性表结构 D. 顺序存储的非线性表结构 D. WWW

6.

在数据结构中,链表是( A. 顺序存储的线性表结构

C. 非顺序存储的非线性表结构 7.

如果一棵 M 度树中有 N1 个度为 1 的顶点,N2 个度为 2 的顶点,……,Nm 个度为 M 的顶点,则该树中的叶子顶点个数为( ) 。 A. N1 B. M-N1-N2 C. N1+2N2+…+(m-1)Nm-1+1 D. N2+2N3+…+(m-1)Nm+1 ) 。

8.

设有 1024 个数据,利用二分法进行查找时,最坏情况下的比较次数为( A. 11 B. 10 C. 9 D. 8

9.

设数组 X[10..40, 20..50]以行优先的方式存储,每个元素占 4 个字节,且已知 x[10,20] 的地址为 1000,则 x[30,30]的地址为( ) 。

1

A. 2280

B. 2980 C. 2240

D. 2284 ) 。

10. 在各种排序算法中,其平均算法复杂度为 O(nlog2n)的是( A. 快速排序 B. 冒泡排序 C. 归并排序

D. 直接插入排序

冒泡排序和直接插入排序的时间复杂度均为 O(n2),归并排序的时间复杂度为 O(n+m), 其中 n、m 分别为两个归并排序的长度。快速排序是冒泡排序的一种改进,在最坏情况下其 执行时间为 O(n2),平均执行时间为 O(nlog2n)。 11. 已知一棵二叉树的前序遍历序列为 ABDEGCFH,中序遍历序列为 DBGEACHF,则该 二叉树的层次序列为( ) 。 A. GEDHFBCA B. DGEBHFCA C. ABCDEFGH D. ACBFEDHG

12. 对 于 一 个 无 向 带 权 图 G= ( V , E ) , 其 中 V={a,b,c,d,e} , E={(a,b),(a,c),(b,d),(c,d),(e,d),(c,e),(a,d),(b,e)},E 中边的权值分别为{1,4,2,5,3,1,2,3},现 寻找 E 的一个子集 E1,使得 V 中任意两个顶点之间均存在至少一条路径,且子集 E1 中边的权值之和最小,则最小权值是( ) 。 A. 5 B. 7 C. 6 D. 8

根据图的最小生成树算法, 边集 E 的一个子集 E1={(q, b), (b, d), (e, d), (c, e)}为满足条件 的一个子集,其最小权值和为 7。 13. 给定一个正整数 N=8934632178,现决定依次删除其中 6 个数位上的数字(每次删除一 个数位上的数字) ,每次删除后按原来的次序组成一个新数,每次得到的新数 M 的值均 是当前状态下的最小数,则第 4 次应该删除的数字是( ) 。 A. 6 B. 8 C. 7 D. 4

此题可以推出一个贪心标准:每次从最高位起寻找递减区间,若存在递减区间,则递减 区间的最高位数字, 否则, 删除最末位数字。 根据这一贪心标准, 要删除 6 个数位上的数字, 使得每次删除后组成的新数最小,应依次删除数字 9、8、6、4、3、3。 14. 下列不属于冯。诺伊曼计算机模型的核心思想的是( A. 采用二进制形式表示数据和指令 B. 采用“存储程序”工作方式 C. 计算机硬件由五大部件(运算器、控制器、存储器、输入和输出设备)组成 D. 结构化程序设计方法 15. 不属于结构化程序设计基本特点的是( ) 。 A. 程序是由三种基本结构组成 B. 一个程序可以分解为多个不同的模块 C. 采用“自顶向下、逐步求精”的设计方法 D. 程序是由各种不同的对象组成的 ) 。

2

16. 对一般的数组 G 而言,当( I]的地址相同。 A. G 的列数与行数相同

)时,其按行存储的 G[I,J]的地址与按列存储的 G[J,

B. G 的列的上界与 G 的行的上界相同 C. G 的列的下界与行的下界相同 D. G 的列下界与行的下界相同 设 G 数组有 n 行、m 列。Aij 为 G[I,J]的地址,元素的长度为 L。按行存储时,有: aij=a11+(i-1)*m+(j-1))*L aji=a11+((i-1)*n+(j-1))*L 若 aij=aji,则 m=n,故答案为 C。 17. 在 Windows 操作系统中,当硬盘空间不足时,一般情况下,可最先考虑删除( 录下的文件来释放空间。 A. My Documents B. Temp C. Program Files D. Fonts )MB。 )目

18. 分辨率为 1280*1024 真彩色(16 位)的 17 英寸显示器的显存容量至少应为( A. 1 B. 2 C. 4 D. 8

1280*1024*16/(8*1024*1024)=2621440(B)=2.5(MB) ,故答案为 C。 19. IE 是目前流行的浏览器软件,它的工作基础是解释执行用( A. VC B. C++ C. HTML D. HTTP ) 。 D. 程序设计语言 )语言书写的文件。

20. 计算机之所以能自动工作,主要是因为采用了( A. 二进制数制

B. 高速电子元件 C. 存储程序控制

二、问题求解(三小题,每题 4 分,共 12 分) 第1题 已知 8 个数据元素为(26,75,15,23,14,62,72,19) ,按照依次插入结点的方法 生成一棵二叉排序树,则该树的深度为 4 。 (假设树根结点为第 1 层) 第2题 假设按先根次序遍历某棵树的顶点顺序为 SACEFBDGHIJK,后根次序遍历该树的顶点 顺序为 CFEABHGIKJDS,请画出这棵树。 答:以广义表形式给出这棵树: S(A(C) ,B(,E(F) ) ,D(G(H) ,I,J(K) ) ) ,或者: S(A(C) ,B(,E(,F) ) ,D(G(,H) ,I,J(,K) ) )

3

3.

如下形状的三角形中,字母 a~i 分别表示数字 1、2、3、…、9: a b c d e f g h i 字母 a~i 同时满足下列条件: (1)a<f<i; (2)b<d,g<h,c<e (3)a+b+d+f = f+g+h+i = i+e+c+a=19 试求出满足条件的三角形的个数。 答 : 因 为 a … I 为 1 … 9 , 且 a+b+d+f=f+g+h+I=I+e+c+a=19 , 所 以 a+b+d+f+ f+g+h+I+I+e+c+a=57,而 a+b+c+d+e+f+g+h+I=45,综合上述两式得 a+f+I=12,即这个数字 三角形 3 个顶点的数和为 12,只要经过全面仔细计算,采用穷举法即可得出如下 4 个三角 形,它们满足所有条件: 1 1 2 2 6 2 5 3 5 4 6 1 8 9 9 8 9 6 8 9 4 3 5 7 4 2 6 7 3 1 8 7 3 4 5 7 (这其实是一个穷举法问题的手工计算和推导过程) 三、阅读程序(共 4 题,每题 7 分,共计 28 分) 1. var c, i, k, j, a: integer; m: array[1..100, 1..100] of integer; begin readln(a); c := a * a; i := 1; k := (a+1) div 2; for j := 1 to c do begin m[i, k] := j; if j mod a = 0 then begin if i = a then i := i + 1 else i := 1; end {of then} else begin if I = 1 then I := a else I := I- 1;
4

if k = a then k := 1 else k := k + 1; end; {else} end; {for} for I := 1 to a do begin for j := 1 to a do write(m[I, j]:5); writeln; end; {for} end. {of main} 输入:5 输出: 11 6 1 21 16 10 5 25 20 15 4 24 19 14 9 23 18 13 8 3 17 12 7 2 22 由以上的输出可以看出,数组中的每个元素都互不相同,且每行每列及对角线的数和

(a 2 ? 1) ? a 为 。 2
2. program LM_31; var d, p: integer; begin p := 1; d := 11; while d > 1 do begin p := 2 * (p+1); d := d - 1; end; writeln(p); end. 输出: 3070 本题的功能是递推的方法求 p 的值:

?1 i ? 11 ? ?2 ? ( p ? 1) 1 ? i ? 11
分析程序流程,d 循环 11 次,p 值的变化如下: p:1,4,10,22,46,94,190,382,766,1534,3070 d:11,10,9,8,7,6,5,4,3,2,1
5

3. program LM_32; var g: ingeter; k, t: real; m: ingeter; begin k:=0; g:=0; for m := 1 to 49 do begin g := g + 1; k := k +1 / (g * (g + 1)) end; writeln(k:10:2) end. 输出: 0.98 本题是求

1 1 1 1 1 1 ? ??? ? ? 的和。因为 ,所以, 1* 2 2 * 3 49 * 50 i * (i ? 1) i i ? 1

k ? 1?

1 1 1 1 1 1 ? ? ??? ? ? 1? ? 0.98 2 2 3 49 50 50

4. program lm_33; var n, I, tem, t: longint; s: string; begin write(‘input n:’); readln(n); s := ‘1’; repeat i := length(s); while s[i] = ‘1’ do begin s[i] := ‘0’; dec(i); end; if i > 0 then s[i] := ‘1’ else s := ‘1’ + s; val(s, t, tem); until t mod n = 0;
6

writeln(n, ‘*’, t div n, ‘=’, s); end. 输入:6 输出: 6*185=1110 本题是输入一个正整数 n,求一个最小正整数 m,使得 n*m 的各位数字非 0 即 1。 四、完善程序(19 个空,共 30 分) 1. 单源最短路径 给定带权有向图 G=(V,E),源点 v1∈V,求从 v1 到 V 中其余各顶点的最短路径。 算法: 1、 数据结构 cost[i,j] 表示带权有向图的邻接矩阵 d[j] 表示从 v1 到 vj 的最短路径的长度 path[j] 表示从 v1 到 vj 的最短路径 2、 实现方法 设集合 s 中存放了已求得的最短路径的终点。初始状态下,s 中只有一个顶点 v1,以后 每求得一条最短路径(v1,v2,…,vk) ,就将 vk 加入 s 中。D[j]存放了从 v1 起,中间经过 s 中 的顶点到达 s 以外的顶点 vj 的当前最短路径的长度。D[j]的值随着 s 中的顶点的增加而不断 地修正。若 s=v,则 d[j]的值是从 v1 到 vj 的最短路径长度。 程序: program test41; const n = 5; type gr = array[1..n, 1..n] of real; dt = array[1..n] of real; jh = set of 1..n; pt = array[1..n] of jh; var s: jh; i, j, k: integer; mm: real; begin for i := 1 to n do for j := 1 to n do read(cost[i,j]); s := [1]; for i := 2 to n do begin d[i] := cost[1.i]; if d[i] < maxnum then path[i] := [1] + [i]; else path[i] := ①[ ]

;
7

end; for i := 1 to n-1 do begin mm := maxnum; for j := 2 to n do if ②mm > d[j] then begin mm := d[j]; k := j; end; s := ③s + [k] ; for j := 2 to n do if not(j in s) and (cost[k,j]<maxnum) then if ④ d[j] > d[k] + cost[k,j] then begin d[j] := d[k] + cost[k,j]; path[j] := ⑤ path[k] + [j] ; end; end; writeln; for i := 2 to n do begin writeln(‘v1->’, ‘v’,i,’:’,d[i]); write(‘v1’); for j := 2 to n do if j in path[i] then write(‘->’, ‘v’, j); writeln; end; end. 2. 程序中的过程 perm(n,s)是用字符集合 s 中的字符,生成由 n 个字符组成的所有排列。 其中 s 中的字符在每种字符排列中最多出现一次。 程序中假定可放入 s 中的序号最小的 字 符 为 小 写 字 母 a , n 不 大 于 10 , 且 不 大 于 s 中 的 元 素 数 目 。 例 如 , 对 于 s={‘a’, ’b’, ’c’} , n=2 , 则 所 有 字 符 排 列 有:’ba’, ’ca’, ’ab’, ’cb’, ’ac’,’bc’。 program test42; const n = 10; type letter = set of char; words = packed array[1..n] of char; var w: words; procedure perm(n: integer; s: letter);

8

var s1: letter; x: char; begin if ①n = 0 then write(w:10) else begin s1 := s; while (② s1 <> [] ) do begin x := ‘a’; while ③not (x in s1) s1 := ④ s1 – [x] w[n] := ⑤ x ; perm(n-1, s-[x]); end; end; end; begin w := ‘ ’; perm(2, [‘a’,’b’,’c’]); writeln; end.

do x := succ(x); ;

3. 问题描述:倒蛇形矩阵填数。任给一个正整数 N(N≤20) ,将 1 至 N*N 的数分别填入矩 阵,在显示器上输出如下格式的矩阵。例如: N=3,输出矩阵为: N=5,输出矩阵为: 9 7 6 25 23 22 16 15 8 5 2 24 21 17 14 7 4 3 1 20 18 13 8 6 19 12 9 5 2 11 10 4 3 1 算法分析: 由于图案是正方形,所以只需把矩阵分割成两部分,即左上角部分和右下角部分。对于 左上角部分,将其斜向分割,可以把它看作一个三角形,即第 I 行有 I 个元素。当行数 I 为奇数时,J 的变化为 I…1;为偶数时,J 的变化为 1…I。每个元素在矩阵中的坐标位置也 容易得到。对右下角部分,情况恰好相反,可以类似地解决。 将(1)与(2)合在一起,就得到问题的解。 程序: program ex5; var t: array[1..20, 1..20] of integer; k, n, i, j: integer;

9

begin fillchar(t, sizeof(t), 0); writeln(‘Please input n:’); readln(n); if (n<1) or (n>20) then begin writeln(‘Input data error!’); halt; end; k := n * n; for i := 1 to n do if not od(i) then for j := 1 to i do begin ①t[i-j+1,j]:=k ; dec(k) end; else for j := i downto 1 do begin ②t[i-j+1,j]:=k ; dec(k); end; k := 1; for i := 1 to n –1 do if not odd(i) then for j := 1 to i do begin ③t[n-i+j,n-j+1]:=k inc(k); end else for j := i downto 1 do begin ④t[n-i+j,n-j+1]:=k ; inc(k); end; for i := 1 to n do begin for j := 1 to n do write(t[i,j]:4); ⑤ writeln ; end; end.

;

10


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

全国青少年信息学奥林匹克联赛初赛练习卷()new答案_学科竞赛_初中教育_教育专区...白球 6 个, 现任取两个球, 取出的球全是绿球的比例是 10:105 (即 2 :...

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

全国青少年信息学奥林匹克联赛初赛练习卷(十四)new答案_英语考试_外语学习_教育...下列关于十进制数 100 的正确说法是( )。 A) 原码为 01100100B B) 反码为...

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

全国青少年信息学奥林匹克联赛初赛练习卷()new答案_学科竞赛_高中教育_教育专区...)的名字 10. 按照网络覆盖范围和计算机之间相距的远近,计算机网络可以分为( A....

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

全国青少年信息学奥林匹克联赛初赛练习卷(十一)new答案_学科竞赛_高中教育_教育...计算机的主存容量达到 1GB 时,其地址的表示至少需要使用( A. 10 位 2. B....

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

全国青少年信息学奥林匹克联赛初赛练习卷(十二)new答案_学科竞赛_高中教育_教育...{算法执行 n-1 轮、挑选出 n-1 条边即可} min:=1e10; {即 10000000000...

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

全国青少年信息学奥林匹克联赛初赛练习卷()答案_学科竞赛_高中教育_教育专区。...4 8 12 1 6 11 2 9 15 10 5 3 7 14 the number is :13 2、运行...

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

全国青少年信息学奥林匹克联赛初赛练习卷(十三)new答案_学科竞赛_高中教育_教育...O(n2)、O(n2) 、O(n2) 给出一组数据:10,18,3,4,9,13,15,2,21,9...

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

全国青少年信息学奥林匹克联赛初赛练习卷()答案_学科竞赛_高中教育_教育专区。...y=0 if x<0 then y=5 else if x<10 then y=10 if x<100 then y=...

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

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

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

全国青少年信息学奥林匹克联赛初赛练习卷()答案_IT认证_资格考试/认证_教育...已知 A=(72E)H(H 表示 16 进制),B=(1315)D(D 表示 10 进制),则 A-...