noip2011初赛试题及答案（完美Word版） 

end;

for i := a.len downto 1 do begin

if a.num[i] < b.num[i] then begin

over := false; exit; end;

if a.num[i] > b.num[i] then begin

over := true; exit; end; end;

over := false; end;’ begin readln(s);

fillchar(target.num, sizeof(target.num), 0); target.1en := 1ength(s); for i := 1 to target.1en do

target.num[i] := ord(s[target.1en – i + 1]) - ___⑦___; filichar(left.num, sizeof(1eft.num), 0); left.1en := 1; left.num[i] := 1; right := target; repeat

middle := average(1eft, right); if over(___⑧___) then right := middle else 1eft := middle;

until over(plustwo(1eft), right); for i := left.1en downto 1 do

write(1eft.num[i]); writeln; end.

11

2. （笛卡尔树）对于一个给定的两两不等的正整数序列，笛卡尔树是这样的一棵二叉树：首先，它是一个最小堆，即除了根结点外，每个结点的权值都大于父节点的权值；其次，它的中序遍历恰好就是给定的序列。例如，对于序列7、2、12、1、10、5、15、3，下图就是一棵对应的笛卡尔树。现输入序列的规模n（1≤n<100）和序列的n个元素，试求其对应的笛号尔树的深度d(根节点深度为1)，以及有多少个叶节点的深度为d。 const

SIZE = 100;

INFINITY = 1000000; var

n, maxDeep, num, i : integer; a : array[1..SIZE] of integer;

procedure solve(1eft, right, deep : integer); var

i, j, min : integer; begin

if deep > maxDeep then begin

maxDeep := deep; num := 1; end

else if deep = maxDeep then ___①___;

min := INFINITY;

for i := 1eft to right do if min > a[i] then begin

min := a[i]; ___②___; end;

if left < j then ___③___; if j < right then

12

___④___; end; begin readln(n);

for i := 1 to n do read(a[i]); maxDeep := 0; solve(1, n, 1);

writeln(maxDeep, ‘ ’, num); end.

写在后面：化了整整三个晚上，终于把这资料给整好了。从扫描、校对到排版，真想不到有如此多的错误（可能是我的扫描仪太差了），虽然很累，却很开心。以前都是我享用别人的奥赛资料，今天终于轮到我贡献一下了。分享毕竟是快乐的！感谢所有热衷于网络资料分享的人们，还有我自己。

——江郎 2011-10-25

13

CCF NOIP2011提高组（Pascal语言）参考答案与评分标准

一、单项选择题（共10题，每题1.5分，共计15分） 1 B 2 B 3 A 4 D 5 B 6 A 7 C 8 D 9 B 10 A 二、不定项选择题（共10题，每题1.5分，共计15分，多选或少选均不得分） 1 CD 2 3 4 BC 5 BC 6 ABD 7 CD 8 A 9 BCD 10 ABC ABCD AB 三、问题求解（共2题，每题5分，共计10分） 1．9 2．4

四、阅读程序写结果（共4题，每题8分，共计32分） 1．3 2．1 2 5 13 34 3．150 4．57344

五、完善程序（第1题，每空2分，第2题，每空3分，共计28分）

（说明：以下各程序填空可能还有一些等价的写法，各省可请本省专家审定和上机验证，不一定上报科学委员会审查） 1．① ans.num[i + j - 1]

② ans.num[i] := ans.num[i] mod 10; ③ ans.num[i] + a.num[i] + b.num[i]; ④ ans.num[i] mod 2 (或 ans.num[i] and 1) ⑤ inc(ans.len) （或 ans.len := ans.len + 1） ⑥ a.len < b.len ⑦ ord('0')(或48）

⑧ times(middle, middle), target 2．① inc(num) (或 num := num + 1) ② j := i

③ solve(left, j - 1, deep + 1) ④ solve(j + 1, right, deep + 1)

14