第十六届全国青少年信息学奥林匹克联赛初赛试题及答案(提高组)

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

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

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

1.与十六进制数A1. 2等值的十进制数是（   ）。

A．101.2      B. 111.4      C. 161.125      D. 177.25

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

A.8     B. 16     C. 32      D. 以上都有可能

3.以下逻辑表达式的值恒为真的是（   ）。

A.  P∨(﹁P∧Q) ∨(﹁P∧﹁Q)       B. Q∨(﹁P∧Q) ∨(P∧﹁Q)

C.  P∨Q∨(P∧﹁Q) ∨(﹁P∧Q)      D. P∨﹁Q∨(P∧﹁Q) ∨(﹁P∧﹁Q)

4.Linux下可执行文件的默认扩展名为（       ）。

A. exe     B. com     C. dll      D. 以上都不是

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

A. 100     B. 144     C. 1      D. 196

6.提出“存储程序”的计算机工作原理的是（     ）。

A. 克劳德·香农     B. 戈登·摩尔     C. 查尔斯·巴比奇     D. 冯·诺伊曼

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

A. 23     B. 25     C. 37      D. 65

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

A. 寄存器     B. 高速缓存     C. 闪存      D. 外存

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

A. 2k     B. 2k+1     C. k/2下取整      D. (k+1)/2下取整

10.以下竞赛活动中历史最悠久的是（      ）。

A. 全国青少年信息学奥林匹克联赛（NOIP）

B. 全国青少年信息学奥林匹克竞赛（NOI）

C. 国际信息学奥林匹克竞赛（IOI）

D. 亚太地区信息学奥林匹克竞赛（APIO）

二、不定项选择题（共 10 题，每题 1.5 分，共计 15 分。每题有一个或多个正确选项。多选或少选均不得分）

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. 编译性语言

3.原地排序是指在排序过程中（除了存储待排序元素以外的）辅助空间的大小与数据规模无关的排序算法。以下属于原地排序的有（    ）。

A. 冒泡排序     B. 插入排序     C. 基数排序      D. 选择排序

4.在整数的补码表示法中，以下说法正确的是（    ）。

A. 只有负整数的编码最高位为1

B. 在编码的位数确定后，所能表示的最小整数和最大整数的绝对值相同

C. 整数0只有唯一的一个编码

D. 两个用补码表示的数相加时，如果在最高位产生进位，则表示运算溢出

5.一棵二叉树的前序遍历序列是ABCDEFG，后序遍历序列是CBFEGDA，则根结点的左子树的结点个数可能是（    ）。

A. 0     B. 2     C. 4      D. 6

6.在下列HTML语句中，可以正确产生一个指向NOI官方网站的超链接的是（    ）。

A. 欢迎访问NOI网站

B. 欢迎访问NOI网站

C.  http://www.noi.cn

D. 欢迎访问NOI网站

7.关于拓扑排序，下面说法正确的是（      ）。

A. 所有连通的有向图都可以实现拓扑排序

B. 对同一个图而言，拓扑排序的结果是唯一的

C. 拓扑排序中入度为0的结点总会排在入度大于0的结点的前面

D. 拓扑排序结果序列中的第一个结点一定是入度为0的点

8.一个平面的法线是指与该平面垂直的直线。过点(1,1,1)、(0,3,0)、(2,0,0)的平面的法线是（     ）。

A. 过点(1,1,1)、(2,3,3)的直线

B. 过点(1,1,1)、(3,2,1)的直线

C. 过点(0,3,0)、(-3,1,1)的直线

D. 过点(2,0,0)、(5,2,1)的直线

9.双向链表中有两个指针域llink和rlink，分别指向该结点的前驱和后继。设p指向链表中的一个结点，它的左右结点均非空。现要求删除结点p，则下面语句序列中正确的是（    ）。

A.  p^.rlink^.llink := p^.rlink;    p^.llink^.rlink := p^.llink;        dispose(p);

B.  p^.llink^.rlink := p^.rlink;    p^.rlink^.llink := p^.llink;        dispose(p);

C.  p^.rlink^.llink := p^.llink;    p^.rlink^.llink^.rlink := p^.rlink;   dispose(p);

D.  p^.llink^.rlink := p^.rlink;    p^.llink^.rlink^.llink := p^.llink;   dispose(p);

10.今年（2010年）发生的事件有（     ）。

A. 惠普实验室研究员Vinay Deolalikar自称证明了P≠NP

B. 英特尔公司收购了计算机安全软件公司迈克菲（McAfee）

C. 苹果公司发布了iPhone 4手机

D. 微软公司发布了Windows 7操作系统

三、问题求解（共3题，每题5分，共计15分）

1.LZW是一种自适应的词典编码。在编码的过程中，开始时只有一部基础构造元素的编码词典，如果在编码的过程中遇到一个新的词条，则该词条及一个新的编码会被追加到词典中，并用于后继信息的编码。

举例说明，考虑一个待编码的信息串：“xyx yy yy xyx”。初始时词典中只有3个条目，第一个为x，编码为1；第二个为y，编码为2；第三个为空格，编码为3。于是，串“xyx”的编码为1-2-1（其中“-”为编码分隔符），加上后面的一个空格就是1-2-1-3。但由于有了一个空格，我们就知道前面的“xyx”是一个单词，而由于该单词没有出现在词典中，我们就可以自适应地把这个词条添加到词典里，编码为4。然后，按照新的词典，对后继信息进行编码，依此类推。于是，最后得到编码：1-2-1-3-2-2-3-5-3-4。

我们可以看到，信息被压缩了。压缩好的信息传递到接收方，接收方也只要根据基础词典，就可以完成对该序列的完全恢复。解码过程是编码过程的逆操作。现在，已知初始词典的3个条目如上述，接收端收到的编码信息为2-2-1-2-3-1-1-3-4-3-1-2-1-3-5-3-6，则解码后的信息串是“                       ” 。

2.无向图G有7个顶点，若不存在由奇数条边构成的简单回路，则它至多有          边。

3.记T为一个队列，初始时为空。现有n个总和不超过32的正整数依次入队。如果无论这些数具体为何值，都能找到一种出队的方式，使得存在某个时刻队列T中的数之和恰好为9，那么n的最小值是          。

四、阅读程序写结果（共4题，每题7分，共计28分）

1

const

SIZE = 10;

var

   i, j, cnt, n, m: integer;

   data: array[1..SIZE] of integer;

begin

   readln(n, m);

   for i := 1 to n do

      read(data[i]);

   for i := 1 to n do

   begin

      cnt := 0;

      for j:= 1 to n do

if (data[i]            inc(cnt);

      if cnt = m then

         writeln(data[i]);

   end;

end.

输入：

5  2

96  -8  0  16  87

输出：

2、

const

   SIZE = 100;

var

   na, nb, i, j, k: integer;

   a, b: array[1..SIZE] of integer;

begin

   readln(na);

   for i := 1 to na do

      read(a[i]);

   readln(nb);

for i := 1 to nb do

      read(b[i]);

   i := 1;     j := 1;

while (i<=na) and (j<=nb) do

   begin

if a[i] <= b[j] then

         begin

            write(a[i], ‘ ‘);

            inc(i);

         end

      else

         begin

            write(b[j], ‘ ‘);

            inc(j);

         end;

   end;

if i <= na then

      for k := i to na do

         write(a[k], ‘ ‘);

if j <= nb then

      for k := j to nb do

         write(b[k], ‘ ‘);

end.

输入：

5

1  3  5  7  9

4

2  6  10  14

输出：

3、

const

   NUM = 5;

var

   n: integer;

function r(n: integer): integer;

var i: integer;

begin

if n <= NUM then

   begin

      r := n;

      exit;

   end;

   for i := 1 to NUM do

if r(n-i) < 0 then

      begin

         r := i;

         exit;

      end;

   r := -1;

end;

begin

   readln(n);

   writeln(r(n));

end.

输入：16    输出：

4、

const SIZE = 100;

var

   n, m, x, y, i: integer;

   r: array[1..SIZE] of integer;

   map: array[1..SIZE, 1..SIZE] of boolean;

   found: boolean;

function successful: boolean;

var i: integer;

begin

   for i:= 1 to n do

if not map[r[i]][r[i mod n+1]] then

      begin

         successful := false;

         exit;

      end;

   successful := true;

end;

procedure swap(var a, b: integer);

var t: integer;

begin

   t:=a;    a:=b;    b:=t;

end;

procedure perm(left, right: integer);

var i: integer;

begin

   if found then  exit;

if left > right then

   begin

      if successful then

      begin

         for i := 1 to n do

            write(r[i], ‘ ‘);

         found := true;

      end;

      exit;

   end;

   for i := left to right do

   begin

      swap(r[left], r[i]);

      perm(left+1, right);

      swap(r[left], r[i]);

   end;

end;

begin

   readln(n, m);

   fillchar(map, sizeof(map), false);

   for i := 1 to m do

   begin

      readln(x, y);

      map[x][y] := true;

      map[y][x] := true;

   end;

   for i := 1 to n do

      r[i] := i;

   found := false;

   perm(1,n);

   if not found then

      writeln(‘No solution!’);

end.

输入：

9  12

1  2

2  3

3  4

4  5

5  6

6  1

1  7

2  7

3  8

4  8

5  9

6  9

输出：

四、完善程序（第1空2分，其余10空，每空2.5分，共计27分）

1、（过河问题）在一个月黑风高的夜晚，有一群人在河的右岸，想通地唯一的一根独木桥走到河的左岸。在这伸手不见五指的黑夜里，过桥时必须借助灯光来照明。不幸的是，他们只有一盏灯。另外，独木桥上最多承受两个人同时经过，否则就会坍塌。每个人单独过桥都需要一定的时间，不同的人需要的时间可能不同。两个人一起过桥时，由于只有一盏灯，所有需要的时间是较慢的那个人单独过桥时所花的时间。现输入n（2<=n<100）和这n个人单独过桥时需要的时间，请计算总共最少需要多少时间，他们才能全部到达河的左岸。

例如，有3个人甲、乙、丙，他们单独过桥的时间分别为1、2、4，则总共最少需要的时间为7。具体方法是：甲、乙一起过桥到河的左岸，甲单独回到河的右岸并将灯带回，然后甲、丙再一起过桥到河的左岸，总时间为2+1+4=7。

const

   SIZE = 100;

   INFINITY = 10000;

   LEFT = true;

   RIGHT = false;

   LEFT_TO_RIGHT = true;

   RIGHT_TO_LEFT = false;

var

   n, i: integer;

   time: array[1..SIZE] of integer;

   pos: array[1..SIZE] of boolean;

function max(a, b: integer): integer;

begin

if a > b then

      max := a

   else

      max := b;

end;

function go(stage: boolean): integer;

var i, j, num, tmp, ans: integer;

begin

   if (stage=RIGHT_TO_LEFT) then

      begin

         num := 0;

         ans := 0;

         for i := 1 to n do

            if pos[i] = RIGHT then

            begin

               inc(num);

if time[i] > ans then ans := time[i];

            end;

         if   ①              then

         begin

            go := ans;

            exit;

         end;    

         ans := INFINITY;

         for i := 1 to n-1 do

            if pos[i]=RIGHT then

               for j := i+1 to n then

                  if pos[j]=RIGHT then

                  begin

                     pos[i] := LEFT;

                     pos[j] := LEFT;

                     tmp:=max(time[i],time[j])+  ②            ;

if tmp < ans then ans := tmp;

                     pos[i] := RIGHT;

                     pos[j] := RIGHT;

                  end;

         go := ans;

      end

   else 

if (stage=LEFT_TO_RIGHT) then

   begin

      ans := INFINITY;

      for i := 1 to n do

         if  ③           then

         begin

            pos[i] := RIGHT;

            tmp :=   ④             ;

if tmp < ans then ans := tmp;

              ⑤              ;

         end;

      go := ans;

   end

else

   go := 0;

end;

begin

   readln(n);

   for i := 1 to n do

   begin

      read(time[i]);

      pos[i] := RIGHT;

   end;

   writeln(go(RIGHT_TO_LEFT));

end.

2、（峰火传递）烽火台又称烽燧，是重要的军事防御措施，一般建在险要处或交通要道上。一旦有敌情发生，白天燃烧柴草，通过浓烟表达信息；夜晚燃烧干柴，以火光传递军情。在某两座城市之间有n个烽火台，每个烽火台发出信号都有一定的代价。为了使情报准确地传递，在连续m个烽火台中，至少要有一个发出信号。现输入n、m和每个烽火台发出信号的代价，请计算总共最少花费多少代价，才能使敌军来袭之时，情报能在这两座城市之间准确传递。

例如，有5个烽火台，它们发出信号的代价依次为1、2、5、6、2，且m为3，则总共最少花费的代价为4，即由第2个和第5个烽火台发出信号。

const

   SIZE = 100;

var

   n, m, r, i: integer;

   value, heap, pos, home, opt: array[1..SIZE] of integer;

   //heap[i]表示用顺序数组存储的堆heap中第i个元素的值

   //pos[i]表示opt[i]在堆heap中的位置，即heap[pos[i]]=opt[i]

   //home[i]表示heap[i]在序列opt中的位置，即opt[home[i]]=heap[i]

procedure swap(i, j: integer);

//交换堆中的第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;

     ②              ;

   i := 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]   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]         j := i + i + 1

      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[i] := value[i];

      add(i);

   end;

   for i := m+1 to n do

   begin

      opt[i] :=   ⑤                ;

      remove(  ⑥                     );

      add(i);

   end;

   writeln(heap[1]);

end.

第十六届全国青少年信息学奥林匹克联赛初赛答题纸（提高组）答案

姓名                     成绩

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

4.答：yyxy xx yyxy xyx xx xyx

5.答：12

6.答：18

四、阅读程序写结果（共4题，每题7分，共计28分）

1、输出：16

2、输出：1 2 3 5 6 7 9 10 14

3、输出：4

4、输出：1 6 9 5 4 8 3 2 7

四、完善程序（前4空每空2.5分，后6空每空3分，共计28分）

1、①num<=2(或num<3或num=2)    ②  go(LEFT_TO_RIGHT)   ③pos[i]=LEFT

   ④time[i]+go(RIGHT_TO_LEFT)   ⑤pos[i] := LEFT 

2、① opt[k]              ② home[r] := k        ③ j:=r+r

 ④ swap(i,j)          ⑤ value[i]+heap[1]   ⑥ i - m