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位的数表示:a1a2…an,其中,ai =1表示所需物质中必须有第i种基本 物质,ai =-1表示所需物质中必须不能有第i种基本物质,ai =0无所谓。 问题求解:当k个不同地区要求给出之后,给出一种方案,指出哪些物质被使用,哪些 物质不被使用。 程序说明:数组b[1],b[2],…,b[n]表示某种物品,a[1..k, 1..n]记录k个地区对物品的 要求,其中:a[i, j]=1表示第i个地区对第j种物品是需要的,a[i, j]=0表示第i个地区对 第j种物品是无所谓的,a[i, j]= -1表示第i个地区对第j种物品是不需要的。 【源程序】 program gxp2; var i, j, k ,n : integer; p : boolean; b : array[0..20] of 0..1; a : array[1..20, 1..10] of integer; begin readln(n, k); for i := 1 to k do begin for j := 1 to n do read(a[i, j]); readln;
9

end; for i := 0 to n do b[i] := 0; {b[i]中存放的是某一种方案} p := true; while ① p and (b[0] = 0) do begin {穷举以找出某种满足要求的方案} j := n; while b[j] := 1 do j := j – 1; {利用数组来进行穷举,以产生一种新的方案} ② b[j] := 1; for i := j + 1 to n do b[i] := 0; ③ p := false; for i := 1 to k do for j := 1 to n do if (a[i, j] = 1) and (b[j] = 0) or ④ (a[i, j] = -1) and (b[j] = 1) then p := true; {当前方案不合要求则p 置为true} end; if ⑤ p (或b[0]<>0) then writeln(‘ 找不到!’) if (b[i] = 1) then writeln(‘物质’, i, ‘需要’) else writeln(‘物质’, i, ‘不需要’); end. else for i := 1 to n do

说明: B数组中存放结果方案; P为方案找到的标志,为真表示合适的方案未找到,为假则表示找到并结束; (a[i, j]=1)and (b[j]=0) {第i个地区要求有第j个元素,可是方案中没有第j个元素} (a[i, j]=-1)and(b[j]=1) {第i个地区不能有第j个元素,可是方案中有第j个元素} 以上两行确定方案不可行,因而 p = true; b数组从后向前01穷举。 3. 存储空间的回收算法。设在内存中已经存放了若干个作业 A,B,C,D。其余的空间 为可用的(如图一中(a))。

10

此时,可用空间可用一个二维数组 dk[1..100,1..2 ]表示,(如下表一中(a)),其中: dk[i,1]对应第 i 个可用空间首址,dk[i,2]对应第 i 个可用空间长度,如上图中所示。
0 100 100 300 500 50 100 100 300 500 10000 表一(b) 0 50 100 100 0

表一(a)

现某个作业释放一个区域,其首址为 d,长度为 L,此时将释放区域加入到可用空间表 中。要求在加入时,若可用空间相邻,则必须进行合并。因此会出现下面的 4 种情况(如 上图一(b)所示): (1)下靠,即回收区域和下面可用空间相邻,例如,d=80,L=20,此时成为表二中 的(a)。 (2)上靠,例如,d=600,L=50,此时表成为表二中的(b)。 (3)上、下靠,例如,d=150,L=150,此时表成为表二中的(c)。 (4)上、下不靠,例如,d=430,L=20,此时表成为表二中的(d)。
100 80 300 500 70 100 100 100 300 500 50 100 150 100 500 300 100 300 430 500 50 100 20 100

表二(a)(下靠)

表二(b)(上靠)

表二(c)(上,下靠)

表二(d)(上,下不靠)

程序说明:对数组 dk 预置两个标志,即头和尾标志,成为表一中(b),这样可使算法简单, sp 为 dk 表末地址。 【程序清单】 program gao7_5; var i,j,sp,d,l:integer; dk :array[0..100,1..2] of integer; begin readln(sp); for i:=1 to sp do readln(dk[i,1],dk[i,2]); dk[0,1]:=0;dk[0,2]:=0; ①sp := sp + 1 ; {设置末指针} dk[sp,1]:=10000;dk[sp,2]:=0; readln(d,L); {读入新释放的空间} i:=1; while dk[i,1]<d do i:=i+1; {找到第一个大于首地址的空间编号 i——类似于插 入排序}
11

②i := i - 1 ; {新释放的空间首地址上方空间的编号} if(dk[i,1]+dk[i,2]=d)then {上靠} if(d + L = dk[i+1,1])then {下靠} begin dk[i,2]:= ③ dk[i,2]+ L + dk[i+1,2] ; {上下合并} for j:=i+1 to sp-1 do dk[j]:=dk[j+1]; {下方上移} sp:=sp-1; {空间编号少 1} end else dk[i,2]:=dk[i,2] + L {向上合并} else if(d + L = dk[i+1,1])then {下靠} begin dk[i+1,1]:= ④ d; {更新首地址} dk[i+1,2]:=dk[i+1,2] + L {向下合并} end else begin for j:=sp downto i+1 do dk[j+1]:=dk[j];{i+1 及其后的空间下移} ⑤dk[i+1,1] :=d; {i+1 处加入新空间的首地址} dk[i+1,2]:=L; {赋值新空间的长度} sp:=sp+1; {空间编号增 1} end; for i:=1 to sp-1 do writeln(dk[i,1]:4,dk[i,2]:4); readln; end.

12


推荐相关:

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

全国青少年信息学奥林匹克联赛初赛练习卷(六)答案_学科竞赛_高中教育_教育专区。...C5 ? C6 1 1 (6) 在 A 上任取一点、B 上任取两点、C 上任取一点...


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

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


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

全国青少年信息学奥林匹克联赛初赛练习卷(十四)new答案_英语考试_外语学习_教育...例如:P(x)=4x6-3x3+2x2-1 可表示为:(4,6),(-3,3),(2,2),(-1,...


第十八届全国青少年信息学奥林匹克联赛初赛试卷与答案(pascal)

第十八届全国青少年信息学奥林匹克联赛初赛试卷答案(pascal)_学科竞赛_初中教育_教育专区。noip2012普及组初赛试题和答案,第一时间上传,欢迎下载,第三和第四题还没...


1995-2012历年全国青少年信息学奥林匹克联赛初赛试题(包括答案)。

竞赛用时:2 小时) ●●全部试题答案均要求写在答卷纸上,写在试卷纸上一律...第六届全国青少年信息学(计算机)奥林匹克分区联赛初赛试题普及组参考答案 一、...


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

全国青少年信息学奥林匹克联赛初赛练习卷(八)new答案_学科竞赛_初中教育_教育专区...在微机中,通用寄存器的位数是 ( A.8 位 B.16 位 6. 在计算机中,ASCII ...


全国青少年信息学奥林匹克联赛初赛试题2009-2015

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


第十七届全国青少年信息学奥林匹克联赛初赛试题

第十七届全国青少年信息学奥林匹克联赛初赛试题 ( 普及组●● Pascal 语言 两小时完成 )●● 全部试题答案均要求写在答卷纸上,写在试卷纸上一律无效 一、 单项...


CCF NOIP2010全国青少年信息学奥林匹克联赛初赛试题

第十六届全国青少年信息学奥林匹克联赛初赛试题试题及答案 NOIP2010(Pascal 提高组...全国统一大纲、 统一试卷。初、高中或其他中等专业学校的学生可报名参加联赛。...

网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com