NOIP提高组初赛试题答案Word下载.docx
《NOIP提高组初赛试题答案Word下载.docx》由会员分享,可在线阅读,更多相关《NOIP提高组初赛试题答案Word下载.docx(11页珍藏版)》请在冰点文库上搜索。
A)(2048)10B)(2049)10C)(3746)8D)(1AF7)16
12、TCP/IP协议共有()层协议
A)3B)4C)5D)6
13、若已知一个栈的入栈顺序是1,2,3,…,n,其输出序列为P1,P2,P3,…,Pn,若
P1是n,贝UPi是()
A)iB)n-1C)n-i+1D)不确定
14、计算机病毒是()
A)通过计算机传播的危害人体健康的一种病毒
B)人为制造的能够侵入计算机系统并给计算机带来故障的程序或指令集合
C)一种由于计算机元器件老化而产生的对生态环境有害的物质
D)利用计算机的海量高速运算能力而研制出来的用于疾病预防的新型病毒
15、下面关于算法的错误说法是()
A)算法必须有输出B)算法必须在计算机上用某种语言实现
C)算法不一定有输入D)算法必须在有限步执行后能结束
16.
[x]补码=10011000,其原码为()
二、问题求解(5+7=12分)
1.已知一棵二叉树的结点名为大写英文字母,其中序与后序遍历的顺序分别为:
CBGEAFHDIJ与
CGEBHFJIDA则该二叉树的先序遍历的顺序为:
2.平面上有三条平行直线,每条直线上分别有7,5,6个点,且不同直线上三个点都不在同一条直线上。
问用这些点为顶点,能组成多少个不同四边形?
三、阅读程序,写出程序正确的运行结果(4+7+8+9=28分)
1.PROGRAMGAO7_1
FUNCTIONACK(M,N:
INTEGER):
INTEGER;
BEGIN
IFM=0THENACK:
=N+1
ELSEIFN=0THENACK:
=ACK(M-1,1)
ELSEACK:
=ACK(M-1,ACK(M,N-1))
END;
BEGINWRITELN(ACK(3,4));
READLN;
END.
输出
2.PROGRAMGAO7_2;
VARP,Q,S,T:
READLN(P);
FORQ:
=P+1TO2*PDO
T:
=0;
S:
=(P*Q)MOD(Q-P);
IFS=0THENBEGINT:
=P+Q+(P*Q)DIV(Q-P);
WRITE(T:
4);
END;
3.PR0GRAMGAO7_3;
VARI,J,H,M,N,K:
INTEGER;
B:
ARRAY[1..10]OFINTEGER;
READLN(N);
FORl:
=1TO10DO
M:
=N;
J:
=11;
WHILEM>
0DO
BEGINJ:
=J-1;
B[J]:
=MMOD10;
M:
=MDIV10END;
FORH:
=JTO10DON:
=N+B[H];
END;
WRITELN(N);
END.
输入1234输出:
4.PROGRAMGAO7_4;
VARX,Y1,Y2,Y3:
READLN(X);
Y1:
=0;
Y2:
=1;
Y3:
WHILEY2<
=XDO
Y1:
=Y1+1;
=Y3+2;
=Y2+Y3
WRITELN(Y1);
输入:
23420输出:
四、完善程序(每空3分,共30分)
1.
(如图
存储空间的回收算法。
设在内存中已经存放了若干个作业A,B,C,D。
其余的空间为可用的
一中(司)。
第i个可用空间首址,dk[i,2]对应第i个可用空间长度如上图中,dk:
现某个作业释放一个区域,其首址为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)。
表二(a)(下靠)表二(b)(上靠)表二(c)(上,下靠)表二(d)(上,下不靠)
程序说明:
对数组dk预置2个标志,即头和尾标志,成为表二中(b),这样可使算法简单,sp为dk表末地址。
程序清单:
var
i,j,sp,d,l:
integer;
dk:
array[0..100,1..2]ofinteger;
begin
readln(sp);
fori:
=1tospdo
readln(dk[i,1],dk[i,2]);
dk[0,1]:
=0;
dk[0,2]:
_①
dk[sp,1]:
=10000;
dk[sp,2]:
readln(d,l);
i:
=1;
whiledk[i,1]<
ddoi:
=i+1;
—②—;
if(dk[i,1]+dk[i,2]=d)then
if(d+l=dk[i+1,1])thenbegin
dk[i,2]:
=_③_;
forj:
=i+1tosp-1dodk[j]:
=dk[j+1];
end
elsedk[i,2]:
=dk[i,2]+l〃l不是1
else
dk[i+1,1]:
=④;
dk[i+1,2]:
=dk[i+1,2]+l
elsebegin
=spdowntoi+1dodk[j+1]:
=dk[j];
⑤:
=d;
=l;
sp:
=sp+1;
end;
=1tosp-1dowriteln(dk[i,1]:
4,dk[i,2]:
4);
readln;
end.
2.求关键路径
设有一个工程网络如下图表示(无环路的有向图):
其中,顶点表示活动,①表示工程开始,⑤表示工程结束(可变,用N表示),边上的数字表示活动延
续的时间。
如上图中,活动①开始5天后活动②才能开始工作,而活动③则要等①、②完成之后才能开始,即最早也要7天后才能工作。
在工程网络中,延续时间最长的路径称为关键路径。
上图中的关键路径为:
①一②一③一④一⑤共18
天完成。
关键路径的算法如下:
1.数据结构:
R[1..N,1..N]OFINTEGER;
表示活动的延续时间,若无连线,则用-1表示;
EET[1..N]表示活动最早可以开始的时间
ET[1..N]表示活动最迟应该开始的时间
关键路径通过点J,具有如下的性质:
EET[J]=ET[J]
2.约定:
结点的排列已经过拓扑排序,即序号前面的结点会影响序号后面结点的活动。
i,j,n,max,min,w,x,y:
integer;
r:
array[1..20,1..20]ofinteger;
eet,et:
array[1..20]ofinteger;
begin
readln(n);
=1tondo
r[i,j]:
=-1;
readln(x,y,w);
whilex<
>
0dobegin
r[x,y]:
=w;
eet[1]:
=2tondobeginmax:
ifr[j,i]<
-1then
if②thenmax:
=r[j,i]+eet[j];
eet[i]:
=max;
=n-1downto1dobeginmin:
=1000;
ifr[i,j]<
if④thenmin:
=et[j]-r[i,j];
et[i]:
=min;
writeIn(eet[n]);
=1ton-1do
if⑤thenwrite(i,'
—'
);
writeln(n);
readln;
第七届全国青少年信息学(计算机)奥林匹克分区联赛
初赛试题
(普及组参考答案)
一、选择一个正确答案代码(A/B/C/D),填入每题的括号内(每题1.5分,多选无分,共30分)
题号
1
2
3
4
5
6
7
8
9
10
选择
C
D
B
A
11
12
13
14
15
16
17
18
19
20
二、问题解答(5+7分,两题共12分)
1.答:
在a,b,c,d,e,f六件物品中,按条件能选出的物品是:
a,b,c,f
2.答:
用这些点为顶点,能组成751个不同三角形
三、阅读程序,并写出程序的正确运行结果:
(5+8+9+9分,共31分)
(1)程序的运行结果是:
⑵程序的运行结果是:
1361012021504036
⑶程序的运行结果是:
181110877666626160
(4)程序的运行结果是:
6734
四、根据题意,将程序补充完整(每个点3分,共30分)
题一
1B[X]+1;
2K:
3B[I]>
4I:
5KMOD8=0
题二
1B[0]=0
2S+D[I,B[I]];
3B[J]=D[J,O]
④S:
=S+G[I]