noip2008普及组P试题+答案（8页）(2)

2008

var

len,i:integer; begin

len := length(str); for i:=1 to len do begin

if ② then begin

str[i] := upcase(change[ord(str[i]) – ord(‘A’) + 1]); end else begin

③ end; end; end; begin

readln(str);

readln(change);

CheckChangeRule;

④ writeln(str); end.

2. (找第k大的数) 给定一个长度为1,000,000的无序正整数序列, 以及另一个数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;

6

2008

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

a[i] := a[j]; inc(i); end else break;

while (i

a[j] := a[i]; dec(j); end else break; end;

④

if in then begin dec(i); exit( ⑥ ); end; exit(i); end; var

i:integer; begin

randomize; m:=1000000; for i:=1 to m do read(a[i]); read(n);

ans:= FindKth(1,m,n); writeln(a[ans]); end.

NOIP2008年普及组（Pascal语言）参考答案与评分标准

7

2008

一、单项选择题：（每题1.5分）

1. A 2. B 3. C 4. C 5. B 6. D 7. C 8. D 9. A 10. B 11. D 12. A 13. B 14. B 15. B 16. A 17. B 18. A 19. B 20. D 二、问题求解：（共2题，每题5分，共计10分） 1．12 4 2．7(1->2->5->6)

三、阅读程序写结果（共4题，每题8分，共计32分） 1. 23 2. 2,3,1

3. 5 4 10 1 6 22 -59 -6 -11 -6 4. DBGEFCA （求树的后序遍历）

四．完善程序 (前4空，每空2.5分，后6空，每空3分，共28分)

（说明：以下各程序填空可能还有一些等价的写法，各省可请本省专家审定和上机验证，不一定上报科学委员会审查）

1. ① (change[i] >= 'A') and (change[i] <= 'Z') (只写(change[i] <= 'Z')也对)

② (str[i] >= 'A') and (str[i] <= 'Z') （只写str[i] <= 'Z'也对） ③ str[i] := change[ord(str[i]) - ord('a') +1]; ④ ChangeString; 2． ① a[left]

② a[j] < value (或a[j] <= value) ③ a[i] > value （或a[i] >= value） ④ a[i] := value; ⑤ i,right,n ⑥ FindKth(left, i, n)

8