nbhkdz.com冰点文库

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


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

一、单项选择题(20 题,每题 1.5 分,共计 30 分。每题有且仅有一个正确答案) 1. 在网络上,若某台电脑的设备及数据可由其他电脑共享,这台电脑称为( A. 主机 2.

B. 服务器 C. 副机 D. 个人计算机 )地址,该地址共含( )个字节, ) 。为了避免使用数字,人们经常使 ) 。

连接到 Internet 上的每台计算机都必须有一个( 前面若干字节表示( ) ,后面若干字节表示( 用字母代替,这些名字称为( ) 。 A. IP、四、网络地址、计算机地址、网名 B. 网络、四、IP 地址、网内计算机地址、域名 C. 网络、不超过十、网页、网址、网名 D. IP、四、网络地址、网内计算机地址、域名

3.

产生 100 至 300 之间的随机整数(包含 100、300)的表达式是( A. Random(100)+200 C. Random(201)+100 B. Random(200)+100 D. Random(300) ) 。 C. 物理层

) 。

4.

OSI 七层协议中,最底层的协议是( A. 会话层 B. 数据链路层

D. 网络层

5.

设 x 为值大于零的实型变量,在 Pascal 中,计算 x8 的表达式为( ) 。 A. ln(8*(exp(x)) B. exp(8*(lnx)) ) 。 C. 10110011 D. 00011001 ) 。 C. x^8 D. sqr(sqr(sqr(x)))*x

6.

十进制数-103 的补码是( A. 10011001

B. 11100111

7.

为了区分汉字与 ASCII 码,计算机中汉字编码的最高位为( A. 0 B. 1 C. 2 D. 4 )之间。

8.

在微型计算机系统中,I/O 接口位于( A. CPU 和内存储器 C. 总线与输入输出设备

B. 外部设备与内存储器 D. 主机和输入输出设备 )码实现十进制数与二进制数之间的自动转换。 C. 海明码 D. 机内码

9.

在微型计算机中,常用( A. BCD 码

B. ASCII 码

1

10. 下列关于排序算法的说法中,正确的是( A. 快速排序就是最快的排序 C. 选择排序比插入排序好 11. 含 5 个结点的不同的二叉树有( A. 22 12. JPG 是一种( A. 有损压缩 B. 30 C. 40

) 。

B. 归并排序是稳定的排序 D. 无论如何,排序的时间复杂度不小于(NlogN) )种。 D. 42

)的静态图像文件存储格式。 B. 无损压缩 C. 不可压缩 D. 以上都正确

13. 插入排序是一种简单实用的排序算法,在对数据进行排序时,我们可能用二分查找,对 要插入的元素快速找到在已经排好的元素序列中的位置。 下面的描述中正确的是 ( ) 。 A. 二分查找的时间复杂度为 O(lgN),因此排序的时间复杂度为 O(N*lgN) B. 二分查找的时间复杂度为 O(N),因此排序的时间复杂度为 O(N*lgN) C. 二分查找的时间复杂度为 O(lgN),排序的时间复杂度不变,为 O(N*N) D. 二分查找的时间复杂度为 O(N),排序的时间复杂度不变,为 O(N*N) 二分查找的时间复杂度为 O(lgN),排序的时间复杂度为 O(N2),故答案为 C。 14. 某班有 30 个同学报名参加 100、400、800 米三个运动项目的比赛。已知有 6 人获 100 米参赛资格,8 人获 400 米参赛资格,15 人获 800 米参赛资格,且其中有 3 人获全部三 项参赛资格,则至少有( )人没有获任何项目参赛资格。 A. 5 B. 7 C. 9 D. 10

设至少有 x 人没有获任何项目的参赛资格。剩下的 30-3-x 个人必须参加 100、400、800 米,其中有 6-3 人获 100 米的参赛资格,8-3 人获 400 米的参赛资格,15-3 人获 800 米的参 赛资格,即 30-3-x=3+5+12。显然,x=7。答案:B。 15. 如下的叙述中,哪一个是关于数据类型的正确描述?( A. 是一组值的集合 B. 不包含子结构的信息 C. 一条信息或是其值属于某个类型的一条记录 D. 指一组值的集合以及定义在该集合上的一组操作 16. 通信时, 模拟信号也可以用数字信道来传输, 实现模拟信号与数字信号之间转换功能的 是( ) 。 A. D/A B. A/D C. Modem D. Codec )

通常, 模拟信号要转换成数字信号才能在数字传输系统上进行传输, 模拟信号转换成数 字信号要使用脉码调制技术,即 PCM,经过对模拟信号采样、量化、编码三个步骤,使之 变换成数字信号。

2

在接收方,收到数字信号后,再将它还原为原来的模拟信号。这种在发送方将模拟信号 变换为数字信号的装置称为编码器 (Coder) ,在接收方将数字信号变换为模拟信号的装置称 为解码器(Decoder) 。通常进行的双向通信使用既能编码又能解码的装置,称为编码解码器 (Codec) 。 17. 在 TCP/IP 协议中,TCP 和 IP 分别提供什么服务?( A. 传输层、网络层 C. 传输层、会话层 B. 链路层、网络层 D. 物理层、链路层 ) 。 )

18. 逻辑代数式 f=AB+ABC+AB(C+D),则 f 的简化式子为( A. AB B. A+B C. ABC D. ABCD

19. 设有一个十阶的对称矩阵, 采用压缩的存储方式, 以行序为主存储, a11 为第一个元素, 其存储地址为 1,每个元素占 1 个地址空间,则 a85 的的地址为( ) 。 A. 13 B. 33 C. 18 D. 50 ) 。

20. 当用一个带符号的字节来表示整数(可正可负)时,最小的二进制数是( A. 10000000 B. 11111111 C. 01111111 D. 00000000

二、问题求解(三小题,每题 4 分,共 12 分) 1. 某校有学号分别为 1,2,3,…,n 的 n 位学生要去音乐厅听音乐,音乐老师手里有座 位号分别为 1,2,3,…,n 的票要分给学生,希望每个学生的座位号与自己的学号都 不相同,请问老师有多少种不同的方案来分配这些票?例如,当 n=2 时,只有一种方 案,n=3 时,有 2 种方案。现对任意的 n>1,记 F(n)为不同的方案数,请写出 F(n)的递 归关系式。 答:本题是“错排”问题。利用容斥原理,可知错排的方案数为: f(n)=n!(1-1/1!+1/2!-1/3!+…+(-1)^n1/n!) 其对应的递归/递推公式为: f(n) = (n-1) * (f(n-1) + f(n-2)) f(1)=0 f(2)=1 2. 以正 2n+1(n>0)边形的顶点为顶点的三角形的集合记为 Mn。求: Mn 中有多少个锐角三角形? 当 N=10 时,Mn 中有多少个两两不全等的三角形。 答: (1)设锐角三角形的某个顶点为 V。连接 V 与 O(O 为圆心) ,将剩下的 2n 个点分作两半。 左边的点从上到下依次是 A1、A2、…、An,右边的点从上到下依次是 B1、B2、…、Bn。
V A1 O An-1 An 3 Bn Bn-1 B1

记 A={A1, A2, …, An},B={B1, B2, …, Bn}。以 V 为顶点的锐角三角形的另外两个顶 点不能同属于 A,若不然,设为 Ai,Aj (I<j),则∠AjAiV 为钝角。同理,不能同属于 B。 于是,可以设这个三角形为△VAiBj。∠AiBjV 和∠BjAiV 必然都是锐角,因此,只要 ∠AiVBj 为锐角即可。 如果 i=1,稍加分析可以发现,j 的取值范围是{n}; 如果 i=2,j 的取值范围是{n-1, n}; …… 如果 I=n,j 的取值范围是{1,2,3,…,n}。 因此, (i, j)总共有 1+2+3+…+n= n(n+1)/2 种不同的取法。 V 是任意的,有 2n+1 种取法。每个锐角三角形被重复算了 3 次,故而此问题的答案就 是: n(n+1)/2*(2n+1) / 3 = n(n+1)(2n+1)/6。 (2)Mn 中有 a 个等边三角形、b 个等腰三角形、c 个不等边三角形,那么,a+b+c 就 是我们要求的答案。从 2n+1 个点中任取 3 个点有 C(2n+1, 3)种取法。考察这 C(2n+1, 3)种取 法: a)分析等边三角形。在 2n+1 个点中,任意确定一个点 V,那么就能唯一确定一个以 V 为顶点的等边三角形;按照这样计算,位于一个固定位置的等边三角形会计算 3 次。所以, 在 C(2n+1, 3)种取法中,同一个等边三角形会被计算(2n+1)/3 次。 b)分析等腰非等边三角形。在 2n+1 个点中,任意确定一个点 V,那么,就能唯一确 定一个以 V 为顶点的等腰非等边三角形。所以,在 C(2n+1, 3)种取法中,同一个等边三角形 会被计算(2n+1)次。 c)同理,一个不等边三角形会被计算 2(2n+1)次。 总的来说,就是(2n+1)/3*a+(2n+1)*b+2(2n+1)*c=C(2n+1, 3) (*) 然后分分两种情况讨论。 1、 (2n+1)是 3 的倍数。此时,a=1,b=n-1,通过(*)式解出 c=(n2-2n+1)/3,所以 a+b+c=( n2+n+1)/3; 2、 (2n+1)不是 3 的倍数。 此时, a=0, b=n, 通过 (*) 式解出 c=( n2-2n)/3, 故 a+b+c=( n2+n)/3; 综 合 起 来 , 就 是 [( n2+n+1)/3] ( [ ] 表 示 高 斯 函 数 ) 。 具 体 到 此 题 , n=10 就 是 [(10*10+10+1)/3]=37。 答案:37。 3. 将 n 个不同颜色的球放入 k 个无标号的盒子中(n>=k,且盒子不允许为空)的方案数 为 S(n, k)。 例如, 当 n=4, k=3 时, S(n, k)=6。 当 n=6, k=3 时, S(n, k) = 90 。 答:将 n 个不同颜色的球放到 k 个无标号的盒子中的方案数可以分为以下两种情况来 讨论: (1)第 n 个球单独成堆,此时有 S(n-1, k-1)种方案; (2)第 n 个球不单独成堆,而是和其他若干个球合成一堆。此时,我们先将前(n-1)个 球分成 k 堆,然后将第 n 个球插入某一堆中。对于每一种将前(n-1)个球分成 k 堆的方案, 我们都有 k 种插法,所以此时有 k*S(n-1, k)种方案。 综上所述,S(n, k)的递推式为: (注意此处采用了递推方法) S(1, 1) = 1 S(n, k) = 0 (n < k) S(n, k) = S(n-1, k-1) + k * S(n-1, k) (n >=k)
4

利用递推式,我们可以比较方便地计算出结果。 K N 1 2 3 4 5 6 1 1 1 1 1 1 1 2 0 1 3 7 15 31 3 0 0 1 6 25 90

三、阅读程序(共 4 题,每题 7 分,共计 28 分) 1. program ex12_3_1; var m, n: byte; procedure fen(I, j: byte; s: string); var k: byte; s1: string; begin if j = 1 then writeln(m, ‘=’, s, i); else for k := 1 to I – j + 1 do begin str(k, s1); fen(I-k, j-1, s+s1+’+’); end; end; begin readln(m, n); fen(m, n, ‘ ‘); end. 输入:6 3 输出:6 = 1 + 1 + 4 6=1+2+3 6=1+3+2 6=1+4+1 6=2+1+3 6=2+2+2 6=2+3+1 6=3+1+2
5

6=3+2+1 6=4+1+1 【分析】 fen(m, n)是一个递归过程,其功能是将 m 拆成 n 个数相加的形式,而 fen(m-k, n-1)是从 m 中拆分出 k。 2. program ex12_3_2; var a: array[2..6] of integer; i, j, m: integer; begin for i := 2 to 6 do a[i] := i + 1; repeat m := 2; for i := 3 to 6 do if a[m] > a[i] then m := i; a[m] := a[m] + m; m := 1; for i := 2 to 5 do for j := i+1 to 6 do if a[i] < a[j] then m:=0; until m <> 0; write(a[2]:6); end. 输出:61 3. program ex12_3_3; const n = 200; var si, pr: set of 2..n; x, j, m: integer; begin writeln(‘Please input m: ‘); readln(m); si := [2..m]; pr := []; x := 2; repeat while not(x in si) do x := succ(x); pr := pr + [x]; j := x; while j <= m do

6

begin si := si – [j]; j := j + x; end; until si = []; j := 0; for x := 2 to m do if x in pr then begin write(x:5); inc(j); if j mod 10 = 0 then writeln; end; writeln end. 输入:m=30 输出: 2 3 5 7 11 13 17 19

23

29

4. (此题有问题,不完整) program ex12_3_4; var link: array[1..13] of integer; count, I, pre, next: integer; begin for I := 1 to 13 do link[i] := I + 1; link[13] : = 1; pre := 13; next := 1; count := 0; repeat until count = 13; writeln(‘Last pice: ’, next); for I := 1 to 13 do write(link[i]:4); end.

四、完善程序(19 个空,共 30 分) 1. OIM 地形 题目描述: 二维离散世界有一种地形叫 OIM(OI Mountain) ,这种山的坡度只能上升(’/’)或下降 (’\’) ,而且两边的山脚都与地平线等高,山上所有地方都不低于地平线。例如: ∧ ∧ / ∨\是一座 OIM; 而 / \ 不是 ∨ 这个世界的地理学家们为了方便记录,给 OIM 所有可能的形状用正整数编号,而且每
7

个正整数恰好对应一种山形。他们规定,若两座山的宽度不同,则较宽的编号较大;若宽度 相同,则比较从左边开始第 1 个坡度不同的地方,坡度上升的编号较大。以下 3 座 OIM 的 编号由小到大递增: ∧ ∧ ∧ ∧ / ∨\ / ∨∨\ / ∨ \。 显然∧的编号为 1,但是地理学家在整理记录时发觉,查找编号与山形的对应关系不 是很方便。他们希望能快速地从编号得到山的形状。你自告奋勇答应他们写一个程序,输入 编号,能马上输出山形。 【输入】一个编号(编号大小不超过 600,000,000) 【输出】 输入编号所对应的山形, 一座山所占行数恰为它的高度, 即山顶上不能有多余空行。 【输入样例】15 {问题:从手工角度来看,本问题的本质是什么?} 【输出样例】 ∧ ∧ {已知和求解的各是什么?该如何下手来分析?} / ∨ \ 【源程序】 program program2; const L: integer = 19; sz: integer = 50; up: char = ‘/’; dn: char = ‘\’; var i, nth, x, y, h, e, f: integer; m: array[0..1, 0..38, 0..19] of integer; {m[]数组的作用是什么?} pic: array[0..49, 0..49] of char; {pic[]数组的作用是什么?} procedure init; var k, s, a, b, c: integer; begin for a := 0 to 1 do for b := 0 to 2 * L do for c := 0 to L do m[a,b,c] := 0; m[0,0,0] := 1; for k := 0 to 2 * L – 1 do begin for s := 1 to L do begin m[0,k+1,s] := m[0,k,s+1] + m[1,k,s+1]; m[1,k+1,s] := end; m[0,k+1,0] := m[0,k,1] + m[1,k,1]; end;
8

① m[0,k,s-1] + m[1,k,s-1];

end; {of procedure init} procedure draw(k, s, nth: integer); begin if (k=0) then exit; if ((nth - m[1,k,s]) >= 0) then begin nth := nth - m[1,k,s]; if (y > h) then ② h := y; {y 是行,x 是列} pic[y,x] := up; y := y + 1; x := x + 1; draw( ③ k - 1, s + 1, nth ); end else begin y := y – 1; pic[y, x] := dn; x := x + 1; draw(k-1, s – 1, nth); end; end; begin init; read(nth); {读入编号} for e := 0 to sz – 1 do for f := 0 to sz – 1 do pic[e, f] := ‘ ‘; x := 0; y := 0; h := 0; i := 0; while ((nth – m[0,2*i,0]) >= 0) do begin nth := nth - m[0,2*i,0]; ④ i := i + 1; end; draw( ⑤ 2 * i, 0, nth ); for i := h downto x – 1 do begin for e := 0 to x – 1 do write(pic[i, e]); writeln(‘ ‘); end; end. {x 是源点/左下角的横坐标} {y 是源点/左下角的纵坐标} {h 是山的高度} {main program}

9

2. 表的操作 【问题描述】 设有一个表,记为 L=(a1, a2, … , an) ,其中: L:表名; a1, a2, …, an 为表中的元素; 当 ai 为 0~9 数字时,表示元素;ai 为大写字母时, 表示是另一个表,但不能循环定义。 例如,下列表的定义是合法的(约定 L 是第一个表的表名) : L = (1, 3, K, 8, 0, 4) K = (3, P, 4, H, 7) P = (2, 3) H = (4, 0, 5, 3) 【程序要求】 当全部表给出之后,求出表中所有元素的最大元素,以及表中全部元素的和。 【算法及数据结构简要说明】 表用记录类型定义,该记录包含以下两个域: 长度(LENGTH) ; 表体(是元素为字符类型的数组 ELEMENT) ; 队列用数组 BASE 表示,队列指针用整型变量 FRONT 与 REAR 表示。 设计一个字符入队的过程 inqueue,一个出队的函数 outqueue。表中最大元素及元素 求和均采用递归计算。 【程序清单】 const maxlen = 100; type list = record length : integer; element: array[1..maxlen] of char; var max : integer; tabno: char; q : array[] procedure inqueue(q,c); {过程需要二个参数,q 为记录类型,c 字符类型} q.rear := ① __; q.base[q.rear] := c; end; function outqueue(q); {q 为记录类型} q.front := ② ; outqueue := q.base[q.front] end; function maxnumber(c: char): char; var m: char; begin
10

max := chr(0); for i := 1 to t[c].length do begin ch := t[c].element[i]; if __③ if end; __④_ end;

_ then m := maxnumber(ch) else m := ch; max < m then max := m _

function total (c: char): integer; var k, i , m : integer; begin k := 0; for i:= 1 to t[c].length do begin ch := t[c].elelment[i]; if __⑤_ k := k + m end; total := k; end;

_ then m := total (ch); else m := ord (ch) – ord ( '0' );

begin {main program} max := 36; for tabno := 'a' to 'z' do t[tabno].length := 0; q.front := 0; q.rear := 0; inqueue(q, 'L' ); while (q.front <>q .rear ) do begin tabno := outqueue(q); write(tabno, ‘=' ); readln ( s ); i := 1; while s[i] <> ' ( ' do i := i+ 1; while s[i] <> ' ) ' do begin if (s[i]>='a') and (s[i]<='z') then begin s[i]:=chr(ord(s[i])+ord('a')-ord('a')); if (s[i]>='a') and (s[i]<='z') then begin
11

inc(t[tabno].length); t[tabno].element[t[tabno].length] := s[i]; inqueue(q, s[i]); end; end else if (s[i]>='0') andn (s[i]<='9') then begin inc(t[tabno].length); t[tabno].element[t[tabno].length] := s[i] end; inc(i) end; edn; write('the max number in table L is:', maxnumber('L')); write('total is:', total('L')) end. 3. 最小修路费用 【问题描述】 现在政府计划在某个区域内的城市间架设高速公路, 以使任意两个城市间能够直接或间 接到达。现在问怎样修路,才能使得费用最小。 【输入文件】 第一行一个整数 n(n <= 100) ,表示城市的数目; 第二行至第 n+1 行每行两个数 xi、yi(0 <= xi, yi <= 100) ,表示第 i 个城市的坐标(单 位:千米) 。 【输出】 最小费用(每千米一个单位价格) 。 【程序清单】 program ex12_4_3; const maxn=100; type tcity = record x, y: real end; var c : array[1..maxn] of tcity; d : array[1..maxn,1..maxn] of real; p : array[1..maxn] of integer; n, i, j, k : integer; a , min : real; begin readln(n); for i:=1 to n do readln(c[i].x,c[i].y);

12

for i:=1 to n do {求出任意两点间的距离} for j:=1 to n do d[i,j]:=sqrt(sqr(c[i].x-c[j].x)+sqr(c[i].y-c[j].y)); p[1]:=0; {p[]数组何用?p[1]=0 什么意思?} for i:=2 to n do (4) p[i] := 1; for i:=1 to n-1 do begin {算法执行 n-1 轮、挑选出 n-1 条边即可}

min:=1e10; {即 10000000000} for j:=1 to n do if (5) min < d[p[j],j] begin min:=d[p[j],j]; (6) k := j end;

then

a := a + d[p[k],k]; {将当前挑选出来的最短边累加起来} p[k]:=0; {结点 k 又成为当前的最新前趋结点,并根据 k 来修改其他结点的边 的权值} for j:=1 to n do if (7) d[p[j],j] < d[k,j] then p[j]:=k; end; writeln(a:0:2); end.

13

1.

降序组合.给定两个自然数 n、r(n > r) ,输出从数 1 到 n 中按降序顺序取 r 个自然数的 所有组合。例如,n=5、r=3 时,有如下组合: 543 542 541 532 531 521 432 431 421 321 程序如下 program t4_1; var n, r, i, j : integer; a : array[1..20] of integer; begin write('n, r = '); repeat readln(n,r); until n>r; i := 1; a[1] := n; writeln('result:'); repeat if i<>r then if a[i]>r-i then begin ___(1)_ __; i:=i+1; end else begin ___(2)_ __; a[i] := a[i]-1 end else begin for j := 1 to r do write(a[j]:3); writeln; if a[r]=1 then begin i := i - 1;
14

a[i] := a[i] - 1; end else ___(3)_ __ end; until a[1]=r - 1; end.

15


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

全国青少年信息学奥林匹克联赛初赛练习卷()new答案_学科竞赛_初中教育_教育专区...12. 数字图像文件可以用下列哪个(些)软件来编辑( )。 A) 画笔(Paintbrush) ...

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

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

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

全国青少年信息学奥林匹克联赛初赛练习卷(十四)new答案_英语考试_外语学习_教育...我们给需 要用到的斜线编号,以 5 阶方阵为例: 11 16 20 23 25 7 12 ...

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

全国青少年信息学奥林匹克联赛初赛练习卷(十三)new答案_学科竞赛_高中教育_教育...,N*N 个数,并要求构成如下的格式:例: N=4 1 12 11 2 12 16 3 14 ...

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

全国青少年信息学奥林匹克联赛初赛练习卷()new答案_学科竞赛_高中教育_教育专区...最后有: 34 26 15 44 12 +) 23 46 4 0 18 23 46 4 0 18 34 26 ...

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

全国青少年信息学奥林匹克联赛初赛练习卷()答案_学科竞赛_高中教育_教育专区。...(5 题,每题 7 分,共 35 分) 1、运行结果:4 8 12 1 6 11 2 9 15...

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

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

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

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

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

全国青少年信息学奥林匹克联赛初赛练习卷()答案_其它课程_高中教育_教育专区。...E 12. 美籍匈牙利数学家 冯·诺依曼 对计算机科学发展所做出的贡献是: () A...

第十二届全国青少年信息学奥林匹克联赛初赛试题及答案(普及组、C语言

十二全国青少年信息学奥林匹克联赛初赛试题及答案(普及组、C 语言)普及组 C 语言 二小时完成) 一、单项选择题(共 20 题,每题 1.5 分,共计 30 分。每...