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

SIZE= 100; var

n. m, r， i ： integer;

value, heap, pos, home, opt : array[l..SIZEl of integer; //heap [i]表示用顺序数组存储的堆heap中第i个元素的值

//pos [i]表示opt [i]在堆heap中的位置，即heap lpos [i]] =opt [i] //home [i]表示heap [i]在序列opt中的位置，即opt [home [i]] =heap [i] procedure swap (i, j : integer)j ／／交换堆中的第i个和第j个元素 var

tmp ： integer; begin

pos [home [i]] ：=j； pos [home[j]] ：=i； tmp ：=heap [i]；

heap [i] ：=heap [j]； heap [j] ：=tmp; tmp ：=home [i];

home [i] ：=home[j]; home [j] := tmp; end;

procedure add (k : integer) ; ／／在堆中插入opt[k] var

i ： integer; begin

inc (r) ;

heap [r] := ①

pos [k] := r; ②

while (i > 1) and (heap[i] < heap[i div _2]) do begin

swap (i, i div 2); i := i div 2; end; end;

procedure remove (k : integer) ; ／／在堆中删除opt[k] var

i, j : integer; begin

i := pos [k] ; swap (i, r) ; dec (r) ;

if i = r + 1 then exit;

while (i > 1) and (heap [i] < heap[i div 2]) do begin

swap (i, i div 2); i := i div 2; end;

while i + i <= r do begin

if (i + i + 1 <= r) and (heap[i + i + 1] < heap[i + i]) then j:=i+i+l else

③

if heap [i] > heap [j] then begin

④

i: = j end else

break; end; end; begin

readln (n, m) ; for i := 1 to n do read (value [i] ) ; r := 0;

for i := 1 to m do begin

opt [il := value [i] ; add (i) ; end;

for i := m + 1 to n do begin

opt[i] := ⑤ remove ( ⑥ ) add (i) ; end;

writeln (heap [1] ) ; end.

第十五届全国青少年信息学奥林匹克联赛初赛试题

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

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

一． 单项选择题 （共10题，每题1.5分，共计15分。每题有且仅有一个正确答案。）

1、关于图灵机下面的说法哪个是正确的：

A) 图灵机是世界上最早的电子计算机。

B) 由于大量使用磁带操作，图灵机运行速度很慢。 C) 图灵机只是一个理论上的计算模型。

D) 图灵机是英国人图灵发明的，在二战中为破译德军的密码发挥了重要作用。

2、关于BIOS下面的说法哪个是正确的：

A) BIOS是计算机基本输入输出系统软件的简称。

B) BIOS里包含了键盘、鼠标、声卡、图形界面显器等常用输入输出设备的驱动程序。 C) BIOS一般由操作系统厂商来开发完成。

D) BIOS能提供各种文件拷贝、复制、删除以及目录维护等文件管理功能。

3、已知大写字母A的ASCII编码为65（十进制），则大写字母J的 十六进制 ASCII编码为：

A) 48 B) 49 C) 50 D) 以上都不是

4、在字长为16位的系统环境下，一个16位带符号整数的二进制补码为1111111111101101。其对应的十进制整数应该是：

A) 19 B) -19 C) 18 D) -18

5、一个包含n个分支结点（非叶结点）的非空满k叉树，k>=1，它的叶结点数目为：

A) nk + 1 B) nk-1 C) (k+1)n-1 D. (k-1)n+1

6. 表达式a*(b+c)-d的后缀表达式是：

A) abcd*+- B) abc+*d- C) abc*+d- D) -+*abcd

7、最优前缀编码，也称Huffman编码。这种编码组合的特点是对于较频繁使用的元素给与较短的唯一编码，

以提高通讯的效率。下面编码组合哪一组不是合法的前缀编码。 A)（00，01，10，11） B)（0，1，00，11） C)（0，10，110，111） D)（1，01，000，001）

8、快速排序平均情况和最坏情况下的算法时间复杂度分别为：

A) 平均情况 O(nlog2n)，最坏情况O(n2) B) 平均情况 O(n)， 最坏情况O(n2)

C) 平均情况 O(n)， 最坏情况O(nlog2n) D) 平均情况 O(log2n)， 最坏情况O(n2)

9、左图给出了一个加权无向图，从顶点V0开始用prim算法求最小生成树。则依次加入最小生成树的顶点集合的顶点序列为：

A) V0, V1, V2, V3, V5, V4 B) V0, V1, V5, V4, V3, V3 C) V1, V2, V3, V0, V5, V4 D) V1, V2, V3, V0, V4, V5

10、全国信息学奥林匹克的官方网站为参与信息学竞赛的老师同学们提供相关的信息和资源，请问全国信

息学奥林匹克官方网站的网址是： A) http://www.noi.com/ C) http://www.noi.cn/

二． 不定项选择题 （共10题，每题1.5分，共计15分。每题正确答案的个数不少于1。多选或少选均不得分）。

1、关于CPU下面哪些说法是正确的：

A) B) C) D)

2、关于计算机内存下面的说法哪些是正确的：

A) 的。 B) C) D)

一般的个人计算机在同一时刻只能存/取一个特定的内存单元。

计算机内存严格说来包括主存（memory）、高速缓存（cache）和寄存器（register）三个部分。 1MB内存通常是指1024*1024字节大小的内存。

随机存储器（RAM）的意思是当程序运行时，每次具体分配给程序的内存位置是随机而不确定CPU全称为中央处理器（或中央处理单元）。 CPU能直接运行机器语言。 CPU最早是由Intel公司发明的。

同样主频下，32位的CPU比16位的CPU运行速度快一倍。

B) http://www.noi.org/ D) http://www.xinxixue.com/

3、关于操作系统下面说法哪些是正确的：