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

全国青少年信息学奥林匹克联赛初赛练习卷（三）

(普及组PASCAL语言 二小时完成)

●● 全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效 ●●

一、单项选择题（20题，每题1.5分，共30分）

1. 下列哪个程序设计语言不支持面向对象的程序设计方法（ ） A、C++

B、Object Pascal C、C

D、Smalltalk E、Java

2. 由3个a，1个b和2个c构成的所有字符串中，包含子串“abc”的共有（ ）个 A、20 B、8 C、16 D、12 E、24

3. 二叉树T，已知其前序遍历序列为1 2 4 3 5 7 6，中序遍历序列为4 2 1 5 7 3 6，其后序

遍历序列为 1 A、4 2 5 7 6 3 1

2 B、4 2 7 5 6 3 1 3 C、4 2 7 5 3 6 1

4 D、4 7 2 3 5 6 1 5 6 E、4 5 2 6 3 7 1

7

4. 满二叉树的叶节点数为N，则它的节点总数为（ ）。 A、N B、2N C、2N-1 D、2N+1 E、2^N-1

5. （2004）10 +（32）16的结果是（ ） A、（2036）10 B、（2054）16 C、（4006）10 D、（100000000110）2 E、（2036）16

6. 在下图，从端点（ ）出发存在一条路径可以遍历图中的每条边一次，而且仅遍历一次 A B

1 C

A、A点 B、B点 C、C点 D、D点 E、E点 7. 某大学计算机专业的必修课及其先修课程如下表所示：

课程 代号 课程 名称 先修 课程 C0 高等 数学 C1 程序 设计 语言 C2 离散 数学 C3 数据 结构 C4 编译 技术 C5 操作 系统 C6 普通 物理 C7 计算 机原 理 C6 C0,C1 C1,C2 C3 C3,C7 C0 请判断下列课程安排哪个是不合理的（ ） A、C0,C6,C7,C1,C2,C3,C4,C5 B、C0,C1,C2,C3,C4,C6,C7,C5 C、C0,C1,C6,C7,C2,C3,C4,C5 D、C0,C1,C6,C7,C5,C2,C3,C4 E、C0,C1,C2,C3,C6,C7,C5,C4

8. 8位无符号二进制数能够表示的最大十进制数是（ ）。

A）255 B）256 C）64 D）63

9. 假设一台PC机使用32位的地址线来管理内存，则内存的最大容量可达到（ ）。

A）16MB B）4GB(即210*210*210*2=4GB) C）8GB D）256MB 10. 主机一般包括（ ）。(此题有问题，最佳答案应该是A+B+C)

A）CPU、内存 B）CPU、外存储器 C）主板、CPU D）存储器、寄存器 11. 用计算机进行图形制作时，正在绘制的图形是存放在（ ）中的。

A）CPU B）ROM C）RAM D）外存

14. 至少需要多大存储容量才能存放一幅分辨率为1024×800的黑白图像（不压缩）（ ）。

A）100G B）100M C）100K (1024×800位=1024*100字节=100KB) D）10M

15. 计算机网络协议是指通信双方为了正确的通信而预先规定的一组协定。上网浏览信息时

使用的主要协议是（ ）。

A）TCP B）IP C）FTP D）HTTP 16. B类地址中的网络地址长度，占总地址长度的（ ）。

2

A）1/2 B）1/4 C）3/4 D）1

17. 在资源管理器中，用鼠标选中非连续多个文件的方法是（ ）。

A）单击文件 B）SHIFT+单击文件 C）CTRL+单击文件 D）ALT+单击文件 18. 已知A=（72E）H(H表示16进制)，B=（1315）D(D表示10进制)，则A-B的结果是

（ ）。

A）(674)O(O表示8进制) B）(1AD)H C）(523)D D）(101101011)B 19. 使用WORD进行文字处理时，伴随“输入-存储-打印”的过程，所涉及的汉字编码分

别是（ ）。

A）输入码、机内码、字型码 B）拼音、机内码、交换码 C）拼音、ASCII码、字型码 D）输入码、机内码、打印码 20. Excel中B6单元格的内容是“=B2+B3+B4”，通过填充句柄向右拖拉至C6单元格，则

C6单元格的内容是（ ）。

A）= B2+B3+B4 B）= C2+C3+C4 C）= $B2+$B3+$B4 D）=$C2+$C3+$C4 二、问题求解（请在空格处填上答案，每空5分，共10分）

1. 某班8人，排成一纵队，正、副班长A和B必须一个在队首、一个在队尾，战士C和D

不能相邻，而E和F必须相邻，问有多少种排法？ 答：

【分析及解法一】

假设该班的人员编号为A、B、C、D、E、F、G、H，根据题意可知，必须将他们排成如下模式：

考虑A在头、B在尾的情况（B在头、A在尾的情况是对称的）：

因E、F必须相邻，因而，从E、F的位置来考虑，共有5个位置可选；

4一旦E、F确定下来后，其他四个人的位置的排列方法可有P4种，其中C、D相邻的排

列有如下情形：

A、E、F、C、D、*、*、B，此时，C+D相邻排列有3种位置，考虑到E和F、C和D、G和H之间的全排列，应该有2*3*2*2=24种情况

A、*、E、F、*、*、*、B，C+D相邻排列有2种位置，E和F、C和D、G和H之间的全排列，应该有2*2*2*2=16种情况

A、*、*、E、F、*、*、B，此时，C+D相邻排列有2种位置，E和F、C和D、G和H之间的全排列，应该有2*2*2*2=16种情况

A、*、*、*、E、F、*、B，此时，C+D相邻排列有2种位置，E和F、C和D、G和H之间的全排列，应该有2*2*2*2=16种情况

A、*、*、*、*、E、F、B，此时，C+D相邻排列有3种位置，E和F、C和D、G和H之间的全排列，应该有2*3*2*2=24种情况 因此：

4全部排列的总数=2*5*2*P4=480

C、D相邻的排列数目=24*2+16*3=96

因此，满足条件的排列总数=480 – 96 - 96 = 288

3

【分析及解法二】

先不考虑A、B，也不考虑C、D，并将E、F当作一个整体来考虑，这样，只要考虑DF、G、H三者的全排列数目即可，即有：3！=6种，这时，再考察一下C、D在这“三个人”中间的穿插点，有以下的情况和数量关系： 1 EF 2 G 3 H 4 当C插在1号位置时，D有三种插法；当C插在2号位置时，D有两种插法；当C插在3号位置时，D有1种插法。因为C、D是可以对调的，因此，有以下的数量关系：

EF、G、H三者的全排列数：6 * 2 = 12种（乘2是因为EF可以对调） C、D的穿插方法：（3+2+1）*2=12

再加上A、B可以对调，则共有：12*12*2=288（种）

【分析及解法三】

AB、CD、EF、GH都是两两可以对调的（共2*2*2*2=16种），那么，当确定A、B在首尾后，仔细区分EF所在的各种情况，有：

情况：A （EF）_ _ _ _ B，则C、D不相邻的放法： 3*16种； 情况：A _ （EF） _ _ _ B，则C、D不相邻的放法： 4*16种； 情况：A _ _ （EF） _ _ B，则C、D不相邻的放法：4*16种； 情况：A _ _ _（EF） _ B，则C、D不相邻的放法： 4*16种； 情况：A _ _ _ _（EF）B，则C、D不相邻的放法： 3*16种；

共：18*16=288（种）

【分析及解法四】

或者，也可以将C、D当作一个整体来考虑：

不考虑A、B，则C、D、DF、G、H（相当于共5个人）的排列数目为：5！ 再考虑将其中CD相邻的情况排除掉。CD相邻后，相当于有4个人，则共有排列数：4！*2（C、D可以对调）

那么，考虑到A与B、E与F都可以对调，则共有排列数： (5! – 4!*2)*2*2 = (120 - 48) * 4 = 72 * 4 = 288

2. 无向图G有16条边，有3个4度顶点、4个3度顶点，其余顶点的度均小于3，则G

至少有 11 个顶点。

答：4*3=12（条），3*4=12（条），16*2 – 12 – 12 = 8（条），因其他顶点的度数小于3，又问至少有几个顶点，故其他结点的度数应该为2，因此，其他结点的数目为：8/2=4（个），（至少）共11个顶点。

3. 如下图，有一个无穷大的的栈S，在栈的右边排列着1、2、3、4、5共五个车厢，其

中每个车厢可以向左行走，也可以进入栈S，让后面的车厢通过。现已知第一个到达出口的是3号车厢，请写出所有可能的到达出口的车厢排列总数(不必给出每种排列)。

出口←

← S↓ 4

1 2 3 4 5

答：第一个到达出口的是3号车厢，可知1、2是先进了栈的；因此，可能的排列数目

2为：P4?3?9(种)

2145 4215 5421 2154

4521

2415 4251 2451 2541 或者：

按照计算“出栈序列”的Catalan数的思想与方法来做：设元素进栈为0，元素出栈为1，则根据题意，本题的排列格局为：0001XXXXX1 ，中间五个元素应包含两个与三个1（这样总共五个0、五个1），组合数为C（5，2）共10种，再减去中间为“11100”这种不合理的情况（这种情况会导致栈下溢），共9种。

三、阅读程序（共4题，每题8分，共计32分） program program1; var

a,b,c,d,e:integer; begin

a:=79 ; b:=34; c:=57;d:=0 ; e:=-1; if (ac) then d:=d+e else if (d+10

输出：__-80____

1.

program program2; var

i,j:integer;

str1,str2:string; begin

str1:='pig-is-stupid'; str2:='clever';

str1[1]:='d'; str1[2]:='o'; i:=8;

for j:=1 to 6 do begin

str1[i]:=str2[j];inc(i); end;

5

writeln(str1); end.

输出：_dog-is-clever__

2.

program program3; var

u:array[0..3] of integer; a,b,c,x,y,z:integer; begin

read(u[0],u[1],u[2],u[3]); a:=u[0]+u[1]+u[2]+u[3]-5;

b:=u[0]*(u[1]-u[2] div u[3]+8); c:=u[0]*u[1] div u[2] * u[3]; x:=(a+b+2)*3-u[(c+3) mod 4];

y:=(c*100-13) div a div (u[b mod 3]*5);

if ((x+y) mod 2=0) then z:=(a+b+c+x+y) div 2; z:=(a+b+c-x-y)*2; writeln(x+y-z); read(a); end.

输入：2 5 7 4 输出：_263_

3.

program program4;

var c:array[1..3] of string[200]; s:array[1..10] of integer; m,n,i:integer ;

procedure numara; var cod: boolean; i, j, nr: integer; begin

for j:=1 to n do begin nr:=0; cod:=true;

for i:=1 to m do {对输入的每一个二进制数字串进行处理} if c[i,j]='1' then begin {对“1”位的处理} if not cod then begin

cod:=true;inc(s[nr]);nr:=0; end end

else begin {对“0”位的处理} if cod then begin

nr:=1;cod:=false ;

6

end

else inc(nr); end; {of the inner for loop} if not cod then inc(s[nr]); end; {of the outer for loop} end; {of procedure numara}

begin {main program}

readln(m,n); {m=3, n=10}

for i:=1 to m do readln(c[i]); numara;

for i:=1 to m do

if s[i] <>0 then write(i,' ',s[i],' '); read(i); {此句不妥} end. 输入： 3 10

1110000111 1100001111 1000000011

输出：__1 4 2 1 3 3__

{程序的功能：按列统计三个数字串中，包含连续一个0的列的数目、连续两个0的列的数目、连续3个0的列的数目，分别将这三个数目放在s[1]、s[2]、s[3]中} 四、完善程序 ( 前8个空每空3分，最后一个空4分，共28分）

1. 上楼梯（4个空，每空1.5分，共6分）

【问题描述】设有一个n级的楼梯（1≤n≤12），编号从下到上依次为1至n，其中有若干级为坏的。有一个人上楼梯时一步可走1级、或2级、或3级（坏级只能跨过而不能踏上，但级数照算）。问：这个人从楼下走到第n级，共有多少种不同的走法？

例如：当n=1时（无坏级情况下）， 仅有1种走法 n=2时（无坏级情况下），有：1级+1级或2级 共2种走法 n=3时（第二级为坏级情况下），有：1级+2级，直接3级，共2种走法 【程序说明】用递推方法求解，用集合记录坏级。{这类题应自己先行初步找出递推公式，并且能理清楚用递推法解题的大致算法思路}

【程序清单】 program cup_5;

var x, i, n, f1, f2, f3, f4: longint; s: set of 0..30; begin

readln(n); s:= ① [] readln(x); {x：坏级，以0结束} while (x <> 0) do begin

s:= ② s+[x]

7

readln(x); end;

if (1 in s) then f1:=0 else f1:=1; {设置递推公式的几个初始值} if (2 in s) then f2:=0 else f2:= ③ f1+1 if (3 in s) then f3:=0 else f3:=1+f1+f2; if n=1 then f4:=f1

else if n=2 then f4:=f2

else if n=3 then f4:=f3 else begin

for i:=4 to n do begin

if (i in s) then f4:=0 else f4:= ④f1+f2+f3 f1:=f2; f2:=f3; f3:=f4; end; end;

writeln(f4); readln; end.

2. 回形排列（5个空，每空3分，共15分） 【问题描述】给出一个N（1≤N≤20），得到一个N*N的回形排列方阵。 例如：

当N=4时，得到的回形排列方阵为： 1 2 3 4 12 13 14 5 11 16 15 6 10 9 8 7 当N=5时，得到的回形排列方阵为： 1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9 输入N，输出N*N的方阵。

【程序说明】A：ARRAY[1..20,1..20] OF INTEGER; 存放填入的数 K：INTEGER; 每次填入的数 【程序清单】 program cup_7; var

i, j, k, n, n1: integer;

a: array[1..20,1..20] of integer; begin

readln(n); n1:=n div 2; ① k:=1; for i:=1 to n1 do begin

for j:=i to n-i do {生成四条边上的数据} begin ② a[i,j]:=k; k:=k+1; end; for j:=i to n-i do

8

begin ③a[j,n-i+1]:=k; k:=k+1; end; for j:=n-i+1 downto i+1 do

begin ④a[n-i+1,j]:=k; k:=k+1; end; for j:=n-i+1 downto i+1 do begin a[j,i]:=k; k:=k+1;end; end;

if ⑤n mod 2<> 0 then a[(n+1) div 2,(n+1) div 2]:=k; for i:=1 to n do begin

for j:=1 to n do write(a[i,j]:4); writeln; end; end.

3. 单词编码（三个空，每空4分，共12分）

【问题描述】单词由小写的英文字母表组成，n为字母表的长度，例如， n=1，表示由小写字母a组成单词，仅有一个a，编码为1 n=2，表示由[a,b]组成单词，其单词编码有：

a 编码为1 ab 编码为2 b 编码为3

n=3，表示由[a,b,c]组成单词，其单词编码如下：

a 编码为1 ab 编码为2 abc 编码为3 ac 编码为4

b 编码为5 bc 编码为6 c 编码为7

n=4，表示由[a,b,c,d]组成单词，其单词编码如下：{先透过例子找出单词编码的规律}

a 编码为1 ab 编码为2 abc 编码为3 abcd 编码为4 abd 编码为5 ac 编码为6 acd 编码为7 ad 编码为8 b 编码为9 bc 编码为10 bcd 编码为11 bd 编码为12 c 编码为13 cd 编码为14 d 编码为15

4-14-24-3

a~b：共2=8(个)，b~c：共2=4(个)，c~d：共2=2(个)

问题：输入n与一个单词（$为单词结束标志，不是单词的组成部分），输出单词的编码。 例如：输入：4 bcd$

输出：11

【程序说明】n : 整数 str ： 存放单词 【程序清单】 program cup_6;

var str: string; i, n, j, s, k: integer; dalta: array[1..20] of integer; begin

readln(n); readln(str); dalta[n+1]:=1;

9

for i:=n downto 2 do

dalta[i]:= ① exp((n–(i-1))*ln2) 或dalta[i+1] * 2; dalta[1]:=0; s:=0; j:=1; while str[j]<>’$’ do begin

s:=s+1; k:=ord(str[j]) – 96; j:=j+1; for i:=1 to k do s:= ②s+dalta[i]; for i:=2 to k+1 do ③ dalta[i]:=dalta[i-1]; 或dalta[i]:=0; end;

writeln(s); readln; end. 10

本文来源：https://www.bwwdw.com/article/wkg8.html