tceic.com
简单学习网 让学习变简单
相关标签
当前位置:首页 >> 学科竞赛 >>

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


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

一、单项选择题(20 题,每题 1.5 分,共 30 分)

1.

小张用十六进制,八进制和十进制写了如下一个等式: 52 – 19 =

33 式中三个数是各不相同进位制的数,试问 52、19、33,分别为___________. (A)八进制,十进制,十六进制 (B)十进制,十六进制,八进制 (C)八进制,十六进制,十进制 (D)十进制,八进制,十六进制

2.

下列 if 语句中,endif 表示相应 if 的结束: y=0 if x<0 then y=5 else if x<10 then y=10 if x<100 then y=100 endif else y=200 endif endif 试指出:当x=80时,运行的结果为__E__,当x=5时结果为__D_。 A、y=9 B、y=5 C、y=10 D、y=100 E、y=200

3.

下列哪个网络上常用的名字缩写是错误的( ) 。 A. WWW(World Wide Web) B. URL(Uniform Resource Locator) C. HTTP(Hypertext Transfer Protocol) D. FTP(Fast Transfer Protocol) {应该是“File Transfer Protocol”} E. TCP(Transfer Control Protocol) 。

4. 不能在Linux 上使用的网页浏览器是( )。 A. Internet Explorer B. Netscape C. Opera D. Firefox E. Mozilla

5. 一位艺术史学家有20000 幅1024 * 768 的真彩色图像, 如果将这些图像以位图形式保存 在CD 光盘上(一张CD 光盘的容量按600M计算),大约需要( )张CD光盘。 A. 1 B. 10 C. 100 D. 1000 E. 10000

(1024*768*32*20000)/ (8*1024*1024*600) =100张
1

6.

由 3 个 a,5 个 b 和 2 个 c 构成的所有字符串中,包含子串“abc”的共有( )个。 A. 40320 B. 39600 C. 840 D. 780 E. 60 (8*7!)/(2!*4!) – (5+4+3+2+1)*4 = 780 亦即,考虑”abc”的摆放位置,共有 8 种,余下的 7 个字符的全排列有 7!种。但是, 在这 7!种全排列中,a 的重复摆放共有 2!种,b 的重复摆放有 4!种。此外,在余下的 7 个字符中,仍有可能出现“abc”的排列,这与前面考虑的 8 种“abc”的摆放是重复的, 也要去掉。这时,根据头一个“abc”的摆放起点位置,后一个“abc”分别有 5、4、3、 2、1 种可能的摆放位置,而一旦第二个“abc”摆放好后,余下的一个 a 和三个 b 的摆
1 放位置有 C4 种可能,因而得上式。

7.

第一个给计算机写程序的人是( )。 A) Alan Mathison Turing D) John Mc-Carthy B) Ada Lovelace E) Edsger Wybe Dijkstra ) 。 C) 1 34 +5*56 7/C) John von Neumann

8.

表达式(1 + 34) * 5 – 56 / 7的后缀表达式为( A) 1+34*5-56/7 D) 1 34 5*+56 7/B) -*+1 34 5/56 7 E) 1 34+5 56 7-*/

9. 中央处理器(CPU)能访问的最大存储器容量取决于( A. 地址总线 B. 数据总线 C. 控制总线 )2。

)。

D. 实际内存容量

10. 已知x=(0.1011010 )2,则[x/2]补=( A. 0.1011101 B. 11110110

C. 0.0101101

D. 0.100110 )。

11. 在磁盘上建立子目录有许多优点,下列描述中不属于建立子目录优点的是( A. 便于文件管理 C. 加快文件查找速度 B. 解决根目录中目录项个数有限的问题 D. 节省磁盘使用空间

12. 在使用E-mail前,需要对Outlook进行设置,其中ISP接收电子邮件的服务器称为( 服务器。 A. POP3 B. SMTP C. DNS D. FTP )。



13. 已知A=35H,则A∧05H∨A∧30H的结果是( A. 30H 110101 000101 B. 05H C. 35H 110101 110000
2

D. 53H

———— 000101 110000 ———— 110101 (即35H)

———— 110000

14. 按照二叉树的定义,具有3个结点的二叉树有( A. 3 B. 4 C. 5 D. 6

)种。

15. 64KB 的存储器用十六进制表示,它的最大的地址码是( )。 A) 10000 B) FFFF C) 1FFFF D) EFFFF

16. TCP/IP 协议共有( A) 3 B) 4

)层协议。 C) 5 D) 6 TCP/IP 应用层(各种应用协议,如 TELNET,FTP,SMTP 等) 传输层 TCP,UDP 网际网层/网络层(IP 等) 网络接口层/数据链路层

OSI 7 6 5 4 3 2 1 应用层 表示层 会话层 传输层 网络层 数据链路层 物理层 )。 C) 11100110

17. [x]补码=10011000,其原码为( A) 011001111 B) 11101000

D) 01100101

[x]反码 = 0011000 – 1 = 0010111 [x]原码 = 对 0010111 的各位取反 = 1101000 最后,再拼上最高位“1”(表示是负数)即可。 二、问题求解(请在空格处填上答案,每空 5 分,共 10 分) 1. 设有一棵k叉树,其中只有度为0和k的两种结点,设n0、nk分别表示度为0和度为k的结 点数,试求出n0、nk之间的关系(n0=数学表达式,数学表达式仅含nk、k和数字)。 答:n0 + nk = nk * k + 1

因此,n0 = nk * k – (nk - 1) = nk*(k - 1) + 1
3

另外,也可以参见“树与二叉树”第一次作业第一题的解答部分。 2. 平面上有三条平行直线,每条直线上分别有 7,5,6 个点,且不同直线上三个点都不 在同一条直线上。问用这些点为顶点,能组成多少个不同四边形? 答:2250 个。 分析:
2 (1) 在 A 上任取两点、在 B 上任取两点构成四边形,这样的四边形数目为 C7 ? C52 ; 2 2 (2) 在 A 上任取两点、在 C 上任取两点构成四边形,这样的四边形数目为 C7 ; ? C6 2 2 (3) 在 B 上任取两点、在 C 上任取两点构成四边形,这样的四边形数目为 C5 ; ? C6

(4) 因为不同直线上 3 个点都不在同一条直线上,所以两条线上任意一点和另一条 线上任取两点也可以构成四边形;
1 1 2 (5) 在 A 上任取一点、B 上任取一点、C 上任取两点构成四边形,有 C7 ; ? C5 ? C6 1 1 (6) 在 A 上任取一点、B 上任取两点、C 上任取一点构成四边形,有 C7 ; ? C52 ? C6 2 1 1 (7) 在 A 上任取两点、B 上任取一点、C 上任取一点构成四边形,有 C7 ; ? C5 ? C6

以上各项相加的结果即为所求:
2 2 2 2 2 1 1 2 1 1 2 1 1 + C5 + C7 + C7 + C7 =2250 C7 ? C52 + C7 ? C6 ? C6 ? C5 ? C6 ? C52 ? C6 ? C5 ? C6

或者: “做减法”
4 3 3 3 4 4 4 C18 ? C7 *11? C6 *12 ? C5 *13 ? C7 ? C6 ? C5

三、阅读程序(共 4 题,每题 8 分,共计 32 分) 1. program exp1; var i, j, k, n, L0, L1, LK:Integer; a : array [0..20] of integer; begin readln(n,k); for i:=0 to n-1 do a[i]:=i+1; a[n]:=a[n-1]; L0:=n-1; for i:=1 to n-1 do begin L1:=L0-k; if (L1<0) then L1:=L1+n; if (L1=Lk) then begin A[L0]:=a[n]; Lk:=Lk-1; a[n]:=a[Lk]; L0:=LK
4

Lk:=n-1;

end; else begin a[L0]:=a[L1]; end; end; {of for loop} a[L0]:=a[n]; for i:=0 to n-1 do write(a[I]:4); writeln; end. 输入:10 输出: 4 7 8 9 10 1 2 3 4 5 6 L0:=L1;

1. program exp2; var i, n,jr,jw,jb:integer; ch1:char; ch:array[1..20] of char; begin readln(n); for i:=1 to n do read(ch[i]); jr:=1;jw:=n;jb:=n; while (jr<=jw) do begin if(ch[jw]='R') then begin ch1:=Ch[jr];Ch[jr]:=ch[jw];ch[jw]:=ch1;jr:=jr+1 end else if ch[jw]='W' then jw:=jw-1 else begin ch1:=ch[jw];ch[jw]:=ch[jb];ch[jb]:=ch1;jw:=jw-1;jb:=jb-1; end end; {of while} for i:=1 to n do write(ch[i]); writeln;

5

end. 输入:10 RBRBWWRBBR 输出:RRRRWWBBBB 2. program exp3; var I,j,p,n,q,s:integer; a :array[1..20]of integer; begin readln(p,n,q);j :=21; while (n>0)do begin j:=j-1;a[j]:=n mod 10;n:=n div 10; end; s:=0; for i:=j to 20 do s:=s*p+a[i]; writeln(s); j :=21; while (s>0) do begin j:=j-1;a[j]:=s mod q;s:=s div q;end; for i:=j to 20 do write(a[i]);readln; end. 输入:7 3051 8 输出:1065 2051 3. program chu7_3; var p,q,s,t:integer; begin readln(p); for q:=p+1 to 2*p do begin t:=0; s:=(p*q) mod (q-p); if s=0 then begin t:=p+q+(p*q) div (q-p); write(t:4); end; end;
6

readln end. 输入:12 输出:181 110 87 76 66 62 61 60

四、完善程序(10 个空,前 7 个空每空 2.5 分,后三个空每空 3 分,共 28 分) 1. 逻辑游戏 题目描述: 一个同学给了我一个逻辑游戏。他给了我图 1,在这个图上,每一段边界都已经进行了 编号。 我的任务是在图中画一条连续的曲线, 使得这条曲线穿过每一个边界一次且仅穿过一 次,而且曲线的起点和终点都在这整个区域的外面。这条曲线是容许自交的。 对于图 1,我的同学告诉我画出这样的一条曲线(图 2)是不可能的,但是对于有的图 形(比如图 3) ,画出这样一条曲线是可行的。对于给定的一个图,我想知道是否可以画出 满足要求的曲线。

图1

图2

图3

图4

输入: 输入的图形用一个n×n的矩阵表示的。矩阵的每一个单元里有一个0到255之间(包括0 和255)的整数。处于同一个区域的单元里的数相同,相邻区域的数不同(但是不相邻的区 域里的数可能相同) 。 输入的第一行是n(0<n<100) 。以下的n行每行包括n个整数,分别给出对应的单元里的 整数(这n个整数之间用空格分开) 。图4给出了输入样例对应的图形。
7

输出: 当可以画出满足题意的曲线的时候,输出“YES” ;否则,输出“NO” 。 输入样例: 3 112 122 112 输出样例: YES 程序: program program2; const d: array[0..7] of integer = (1, 0, -1, 0, 0, 1, 数组有什么作用?} var orig, n, i, j, ns: integer; a: array[0..101, 0..101] of integer; bun: boolean; procedure plimba(x, y: integer); var i, x1, y1: integer; begin a[x, y] := -a[x, y]; if (abs(a[x - 1, y]) <> orig) and (( y]) or (abs(a[x, y - 1]) <> orig)) then inc(ns); if (abs(a[x + 1, y]) <> orig) and ((a[x + 1, y - 1] <> a[x + 1,y]) or (abs(a[x, y - 1]) <> orig)) then inc(ns); if (abs(a[x, y - 1]) <> orig) and (( 1]) or (abs(a[x - 1, y]) <> orig)) then inc(ns); if (abs(a[x, y + 1]) <> orig) and ((a[x - 1, y + 1] <> a[x,y + 1]) or (abs(a[x - 1, y]) <> orig)) then inc(ns); for i := 0 to 3 do begin x1 := x + d[2 * i];y1:=y+ ④d[2*i+1] ; if (x1 >= 1) and (x1 <= n) and (y1 >= 1) and (y1 <= n) and ( ⑤a[x1,y1]=orig (或者 orig=a[x1,y1]) y1); end; end; {end of procedure} begin {main program} bun := true; read(n); ) then plimba(x1, ③a[x-1,y-1] <> a[x, y ②a[x-1,y-1] <> a[x - 1, ① 0,-1 ); {d[]

{a[]是表示图形的矩阵}

8

for i := 0 to n+1 do for j := 0 to n+1 do a[i, j] := 0; a[0, 0] := -1; a[n + 1, 0] := -1; a[0, n + 1] := -1; a[n + 1, n + 1] := -1; for i := 1 to n do for j := 1 to n do read(a[i, j]); for i := 1 to n do {穷举起点的坐标} for j := 1 to n do if a[i, j] > -1 then begin ns := 0; ⑥orig:=a[i,j] ; plimba(i, j); if ns mod 2 = 1 then bun := false; end; if bun then writeln('YES'); if not bun then writeln('NO'); end.

2. 问题描述:有n种基本物质(n≤10),分别记为P1,P2,…,Pn,用n种基本物质构 造物品,这些物品使用在k个不同地区(k≤20),每个地区对物品提出自己的要求。 这些要求用一个n位的数