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

本文格式为Word版，下载可任意编辑——全国青少年信息学奥林匹克联赛初赛练习卷（三）答案全国青少年信息学奥林匹克联赛初赛练习卷（三）

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

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

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

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

B、ObjectPascalC、C

D、SmalltalkE、Java

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

3.二叉树T，已知其前序遍历序列为1243576，中序遍历序列为4215736，其后序

遍历序列为1A、4257631

2B、42756313C、4275361

4D、472356156E、4526371

7

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

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

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

1C

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

课程课程名称先修课程C0高等数学C1程序设计语言C2离散数学C3数据结构C4编译技术C5操作系统C6普通物理C7计算机原理C6C0,C1C1,C2C3C3,C7C0请判断以下课程安排哪个是不合理的（）A、C0,C6,C7,C1,C2,C3,C4,C5B、C0,C1,C2,C3,C4,C6,C7,C5C、C0,C1,C6,C7,C2,C3,C4,C5D、C0,C1,C6,C7,C5,C2,C3,C4E、C0,C1,C2,C3,C6,C7,C5,C4

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

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

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

A）16MBB）4GB(即210*210*210*2=4GB)C）8GBD）256MB10.主机一般包括（）。(此题有问题，最正确答案应当是A+B+C)

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

A）CPUB）ROMC）RAMD）外存

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

A）100GB）100MC）100K(1024×800位=1024*100字节=100KB)D）10M

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

使用的主要协议是（）。

A）TCPB）IPC）FTPD）HTTP16.B类地址中的网络地址长度，占总地址长度的（）。

2

A）1/2B）1/4C）3/4D）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)HC）(523)DD）(101101011)B19.使用WORD进行文字处理时，伴随“输入-存储-打印〞的过程，所涉及的汉字编码分

别是（）。

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

C6单元格的内容是（）。

A）=B2+B3+B4B）=C2+C3+C4C）=$B2+$B3+$B4D）=$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在这“三个人〞中间的穿插点，有以下的状况和数量关系：1EF2G3H4当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

12345

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

2为：P4?3?9(种)

2145421554212154

4521

2415425124512541或者：

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

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

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

a:=79;b:=34;c:=57;d:=0;e:=-1;if(ac)thend:=d+eelseif(d+10writeln(str1);end.

输出：_dog-is-clever__

2.

programprogram3;var

u:array[0..3]ofinteger;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]divu[3]+8);c:=u[0]*u[1]divu[2]*u[3];x:=(a+b+2)*3-u[(c+3)mod4];

y:=(c*100-13)divadiv(u[bmod3]*5);

if((x+y)mod2=0)thenz:=(a+b+c+x+y)div2;z:=(a+b+c-x-y)*2;writeln(x+y-z);read(a);end.

输入：2574输出：_263_

3.

programprogram4;

varc:array[1..3]ofstring[200];s:array[1..10]ofinteger;m,n,i:integer;

procedurenumara;varcod:boolean;i,j,nr:integer;begin

forj:=1tondobeginnr:=0;cod:=true;

fori:=1tomdo{对输入的每一个二进制数字串进行处理}ifc[i,j]='1'thenbegin{对“1〞位的处理}ifnotcodthenbegin

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

elsebegin{对“0〞位的处理}ifcodthenbegin

nr:=1;cod:=false;

6endelseinc(nr);end;{oftheinnerforloop}ifnotcodtheninc(s[nr]);end;{oftheouterforloop}end;{ofprocedurenumara}

begin{mainprogram}

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

fori:=1tomdoreadln(c[i]);numara;

fori:=1tomdo

ifs[i]0thenwrite(i,'',s[i],'');read(i);{此句不妥}end.输入：310

111000011111000011111000000011

输出：__142133__

{程序的功能：按列统计三个数字串中，包含连续一个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种走法用递推方法求解，用集合记录坏级。{这类题应自己先行初步找出递推公式，并且能理清楚用递推法解题的大致算法思路}

programcup_5;

varx,i,n,f1,f2,f3,f4:longint;s:setof0..30;begin

readln(n);s:=①[]readln(x);{x：坏级，以0结束}while(x0)dobegin

s:=②s+[x]

7

readln(x);end;

if(1ins)thenf1:=0elsef1:=1;{设置递推公式的几个初始值}if(2ins)thenf2:=0elsef2:=③f1+1if(3ins)thenf3:=0elsef3:=1+f1+f2;ifn=1thenf4:=f1

elseifn=2thenf4:=f2

elseifn=3thenf4:=f3elsebeginfori:=4tondobeginif(iins)thenf4:=0elsef4:=④f1+f2+f3f1:=f2;f2:=f3;f3:=f4;end;end;

writeln(f4);readln;end.

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

当N=4时，得到的回形排列方阵为：12341213145111615610987当N=5时，得到的回形排列方阵为：12345161718196152425207142322218131211109输入N，输出N*N的方阵。

A：ARRAY[1..20,1..20]OFINTEGER;存放填入的数K：INTEGER;每次填入的数programcup_7;var

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

a:array[1..20,1..20]ofinteger;begin

readln(n);n1:=ndiv2;①k:=1;fori:=1ton1dobegin

forj:=iton-ido{生成四条边上的数据}begin②a[i,j]:=k;k:=k+1;end;forj:=iton-ido

8

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

begin④a[n-i+1,j]:=k;k:=k+1;end;forj:=n-i+1downtoi+1dobegina[j,i]:=k;k:=k+1;end;end;

if⑤nmod20thena[(n+1)div2,(n+1)div2]:=k;fori:=1tondobegin

forj:=1tondowrite(a[i,j]:4);writeln;end;end.

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

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

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

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

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

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