2007-2011年noip初赛提高组试题及答案(2)

end;

if ans.num[ans.len] = 0 then dec(ans.len); average := ans; end;

function plustwo(a : hugeint) : hugeint; var

i : integer; ans : hugeint; begin ans := a;

ans.num[1] := ans.num[1] + 2; i := 1;

while(i <= ans.len) and (ans.num[i] >= 10) do begin

ans.num[i + 1] := ans.num[i + 1] + ans.num[i] div 10; ans.num[i] := ans.num[i] mod 10; inc(i); end;

if ans.num[ans.len + 1] > 0 then___⑤___; plustwo := ans; end;

function over(a, b : hugeint) : boolean; var

i : integer; begin

if(___⑥___)then begin

over := false; exit; end;

if a.1en > b.1en then begin

over := true; exit;

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.

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

___④___; end; begin

readln(n);

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

writeln(maxDeep, end.

’, num); ‘

第十六届（2010年）全国青少年信息学奥林匹克联赛初赛

试题

（ 提高组 Pascal语言 二小时完成 ）

●● 全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效 ●●

一、单项选择题

1.与16进制数 A1.2等值的10进制数是 （ ）A.101.2

D.177.25

A.8

B.16

C.32

D.以上都有

B.111.4

C.161.125

2.一个字节（byte）由（ ）个二进制组成。 可能

3.以下逻辑表达式的值恒为真的是（ ）。 A.P∨（┓P∧Q）∨(┓P∧┓Q) C.P∨Q∨（P∧┓Q）∨（┓P∧Q）

B.Q∨（┓P∧Q）∨（P∧┓Q） D.P∨┓Q∨（P∧┓Q）∨(┓P∧┓Q)

B. com

C. dll

D.

4.Linux下可执行文件的默认扩展名是( )。 A. exe 以上都不是

5.如果在某个进制下等式7*7=41成立，那么在该进制下等式12*12=（ ）也成立。 A. 100

B. 144

C. 164

D. 196

6.提出“存储程序”的计算机工作原理的是（ ）。 A. 克劳德 香农 B.戈登 摩尔

C.查尔斯 巴比奇

D.冯 诺依曼

B. 25

C. 37

7.前缀表达式“+ 3 * 2 + 5 12 ” 的值是（ ）。A. 23

D. 65

8.主存储器的存取速度比中央处理器(CPU)的工作速度慢的多，从而使得后者的效率受到影响。而根据局部性原理，CPU所访问的存储单元通常都趋于一个较小的连续区域中。于是，为了提高系统整体的执行效率，在CPU中引入了( )。A.寄存器

D.外存

B.高速缓存

C.闪存

9.完全二叉树的顺序存储方案，是指将完全二叉树的结点从上到下、从左到右依次存放到一个顺序结构的数组中。假定根结点存放在数组的1号位置上，则第k号结点的父结点如果存在的话，应当存放在数组中的（ ）号位置。 A. 2k (k+1)/2

10.以下竞赛活动中历史最悠久的是（ ）。A. NOIP 二、不定项选择题

1.元素R1、R2、R3、R4、R5入栈的顺序为R1、R2、R3、R4、R5。如果第1个出栈的是R3，那么第5个出栈的可能是( )。A.R1 B.R2 C.R4 D.R5

2. Pascal语言，C语言和C++语言都属于( )。A.高级语言 B.自然语言 C.解释性语言 D.编译性语言

B.NOI

C. IOI D. APIO

B. 2k+1

C. k/2下取整

D.