NOIP2008年提高组初赛试题(十四届)(非常详细)

NOIP2008初赛（提高组）试题＆解析

D．应用层防火墙是在TCP/IP的“应用层”上工作，可以拦截进出某应用程序的所有数据包

【答案】ABCD

三、问题求解（共2题，每题5分，共计10分）

1．有6个城市，任何两个城市之间有一条道路连接，6个城市之间两两之间的距离如下表表示，则城市1到城市6的最短距离为____________。

城市1 城市2 城市3 城市4 城市5 城市6

城市1 0 2 3 1 12 15

城市2 2 0 2 5 3 12

城市3 3 2 0 3 6 5

城市4 1 5 3 0 7 9

城市5 12 3 6 7 0 2

城市6 15 12 5 9 2 0

【答案】7。可以用Dijkstra算法求最短路径，详细讲解见高级本P87。

2．书架上有21本书，编号从1 到 21 从中选4 本，其中每两本的编号都不相邻的选法一共有___________________种。

【答案】3060。对于不相邻的选法，可以先不考虑不相邻元素的排法，而是先将余下的元素排好，然后将需要不相邻的元素在已排好元素间插空。

为了便于理解，可以将问题转化为：将21个盒子（17个黑色、4个红色）摆成一行，要求4个红色的盒子不能相邻（注：对于每一种摆法，将书按编号依次放入，其红色盒子对应书的编号肯定就是不相邻的，即为一种解）。

计算：将17个黑色盒子摆成一行，这17个盒子间共有18个空位，在这些空位中任选

44个，即为C18?3060种。

4个不相邻元素的一种放法（18条红线表示17个盒子间的18空位）

m44【推广】n个元素中有m个元素不相邻的放法有Cn?m?1。对于本题C21?4?1?C18。

- 5 -

NOIP2008初赛（提高组）试题＆解析

四、阅读程序写结果（共4题，每题8分，共计32分）。

1．var

i,a,b,c,d:integer;

f:array[0..3] of integer; begin

for i:=0 to 3 do read(f[i]); a:=f[0]+f[1]+f[2]+f[3]; a:=a div f[0]; b:=f[0]+f[2]+f[3]; c:=(b*f[1]+a) div f[2]; d:=f[(b div c) mod 4];

if (f[(a+b+c+d) mod 4]>f[2]) then begin a:=a+b; writeln(a) end else begin c:=c+d; writeln(c); end; end.

输入： 9 19 29 39

输出：_______________________________ 【答案】 23 （信心题） 2．

procedure foo(a,b,c:integer); begin

if a>b then foo(c,a,b) else

writeln(a,',',b,',',c) end;

var a,b,c:integer; begin

readln(a,b,c); foo(a,b,c); end.

输入：2 1 3

输出：_________________ 【答案】1,3,2 (简单递归)

- 6 -

NOIP2008初赛（提高组）试题＆解析

3．

procedure f(a,b,c:integer); begin

write(a,b,c,'/');

if (a=3)and(b=2)and(c=1) then exit; if (b

if a

if a

var a,b,c:integer; begin

readln(a,b,c); f(a,b,c); end.

输入：1 3 2

输出：____________________

【答案】132/213/231/312/321/ （全排列） 4．

var

s:string;

i,j,len,k:integer; begin

readln(s); len:=length(s); for i:=1 to len do

if (ord(s[i])>=ord('A')) and (ord(s[i])<=ord('Z')) then s:=chr(ord(s[i])-ord('A')+ord('a')); for i:=1 to len do

if (ord(s[i])

while i<=len-j do begin

s[i]:=s[i+j]; i:=i+j; end; end;

- 7 -

NOIP2008初赛（提高组）试题＆解析

writeln(s); end.

输入：ABCDEFGuvwxyz

输出：________________________________ 【答案】defghijxyzabc/hfizxjaybcccc （字符串替换）

五．完善程序（前6空，每空3分，后5空，每空2分，共28分）。

1．（找第k大的数）给定一个长度为1000000的无序正整数序列，以及另一个数n(1<=n<=1000000)，接下来以类似快速排序的方法找到序列中第n大的数（关于第n大的数：例如序列{1，2，3，4，5，6}中第3大的数是4）

Var a:array[1..1000000] of integer; n,m,ans:integer;

procedure swap(var a,b:integer); var t:integer; begin

if (a<>b) then begin t:=a; a:=b; b:=t; end; end;

Function FindKth(left,right,n:integer):integer; Var tmp,value,i,j:integer; begin

if left=right then exit(left); tmp:=random(right-left)+left; swap(a[tmp],a[left]); value:=____①_____ i:=left; j:=right; while i

while (i

while (i

____④_____

if in then begin dec(j); exit(______⑥________);end;

- 8 -