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 i - 8 -
相关推荐：
loading