全国第十九届青少年信息学奥林匹克竞赛分区联赛初赛试题 [2013年]

1. 一个 32 位整型变量占用（ ）个字节。

2. 二进制数 11.01 在十进制下是（ ） 。

3. 下面的故事与（ ）算法有着异曲同工之妙。从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事： “从前有座山，山里有座庙，庙里有 个老和尚在给小和尚讲故事： ‘从前有座山， 山里有座庙， 庙里有个老和尚给小和尚讲故事........................’ ”

4. 逻辑表达式（ ）的值与变量 A 的真假无关。

5. 将（2, 6, 10, 17）分别存储到某个地址区间为 0~10 的哈希表中，如果哈希函数 h(x) =（ ） ，将不会 产生冲突，其中 a mod b 表示 a 除以 b 的余数。 ，其中[ X ]表示 X 下取整

6. 在十六进制表示法中，字母 A 相当于十进制中的（ ） 。

7. 下图中所使用的数据结构是（ ） 。

8. 在 Windows 资源管理器中，用鼠标右键单击一个文件时，会出现一个名为“复制”的操作选项，它 的意思是（ ） 。

9. 已知一棵二叉树有 10 个节点，则其中至多有（ ）个节点有 2 个子节点。

10. 在一个无向图中，如果任意两点之间都存在路径相连，则称其为连通图。下图是一个有 4 个顶点、6 条边的连通图。若要使它不再是连通图，至少要删去其中的（ ）条边。

11. 二叉树的（ ）第一个访问的节点是根节点。

12. 以 A0 作为起点，对下面的无向图进行深度优先遍历时，遍历顺序不可能是（ ） 。

13. IPv4 协议使用 32 位地址，随着其不断被分配，地址资源日趋枯竭。因此，它正逐渐被使用（ ） 位地址的 IPv6 协议所取代。

14. （ ）的平均时间复杂度为 O(n log n)，其中 n 是待排序的元素个数。

15. 下面是根据欧几里得算法编写的函数，它所计算的是 a 和 b 的（ ） 。function euclid(a, b : longint) : longint; begin if b = 0 then euclid := a else euclid := euclid(b, a mod b); end;

16. 通常在搜索引擎中，对某个关键词加上双引号表示（ ） 。

17. 中国的国家顶级域名是（ ） 。

18. 把 64 位非零浮点数强制转换成 32 位浮点数后，不可能（ ） 。

19. 下列程序中，正确计算 1, 2, ..., 100 这 100 个自然数之和 sum （初始值为 0） 的是（ ） 。

20. CCF NOIP 复赛全国统一评测时使用的系统软件是（ ） 。

1. 7 个同学围坐一圈，要选 2 个不相邻的作为代表，有_________种不同的选法。
答案：14

2. 某系统自称使用了一种防窃听的方式验证用户密码。密码是 n 个数 s1, s2, ..., sn，均为 0 或 1。 该系统每次随机生成 n 个数 a1, a2, ..., an， 均为 0 或 1， 请用户回答(s1a1 + s2a2 + ...+ snan)除以 2 的 余数。如果多次的回答总是正确，即认为掌握密码。该系统认为，即使问答的过程被泄露，也无助于破解 密码——因为用户并没有直接发送密码。 然而，事与愿违。例如，当 n = 4 时，有人窃听了以下 5 次问答： 就破解出了密码 s1 = _________， s2 = _________， s3 = _________， s4 = _________。
答案：0|1|1|1

1.

Var a,b: integer;
 begin readln(a, b);
writeln(a, '+', b, '=', a+b);
end. 
输入：3 5 
输出：3+5=8

2.

Var a, b, u, i, num : integer;
  begin
  readln(a,b,u);
  num := 0;
  for i:= a to b do
  begin
    if (i mod u = 0) then inc(num);
  end;
  writeln(num);
end.
输入：1 100 15
输出：6

3.

const SIZE = 100;
Var n, f, i, left, right, middle : integer;
 a:array[1..SIZE] of integer;
begin 
  readln(n, f);
  for i := 1 to n do read(a[i]);
  left := 1;
  right := n;
  repeat
  middle := (left+right) div 2;
  if (f <= a[middle]) then right := middle
                   Else left := middle+1;
until (left >= right);
writeln(left);
end.
输入：12 17
2 4 6 9 11 15 17 18 19 20 21 25 

输出：7

4.

const SIZE = 100;
Var n, ans, i, j : integer;
height, num : array[1..SIZE] of integer;
begin 
  read(n);
  for i := 1 to n do 
   begin 
      read(height[i]);
	  num[i] := 1;
	  for j := 1 to i-1 do 
	  begin
	   if ((height[j] < height[i]) and
	   (num[j] >= num[i])) then num[i] := num[j]+1;
	  end;
    end;
    ans := 0;
  for i := 1 to n do 
   begin 
    if (num[i] > ans) then ans := num[i];
   end;
   writeln(ans);
  end. 
  输入：6
  2 5 3 11 12 4 
输出：4

1. （序列重排）全局数组变量 a 定义如下：

const int SIZE = 100;
int a[SIZE], n;
它记录着一个长度为 n 的序列 a[1], a[2], ..., a[n]。
现在需要一个函数，以整数 p (1 ≤ p ≤ n)为参数，实现如下功能：将序列 a 的前 p 个数与后 n – p 个数对调，且不改变这 p 个数（或 n – p 个数）之间的相对位置。例如，长度为 5 的序列 1, 2, 3, 4, 5，当 p = 2 时重排结果为 3, 4, 5, 1, 2。
有一种朴素的算法可以实现这一需求， 其时间复杂度为 O(n)、空间复杂度为 O(n)： 
procedure swap1(p : longint);
Var i : longint;
b : array[1..SIZE] of longint;
begin for i := 1 to p do b[ n-p+i ] := a[i];//（3 分） 
for i := p + 1 to n do b[i - p] :=  n ;//（3 分） 
for i := 1 to  i-p+1 do a[i] := b[i];//（2 分）
end;
我们也可以用时间换空间，使用时间复杂度为 O(n2)、空间复杂度为 O(1)的算法： 
procedure swap2(p : longint);
Var i, j, temp : longint;
begin for i := p + 1 to n do
 begin
 temp := a[i];
 for j := i downto  i-p+1 do a[j] := a[j - 1];//（3 分）
  a[i-p] := temp;//（3 分）
 end;
end;

2. （二叉查找树） 二叉查找树具有如下性质：每个节点的值都大于其左子树上所有节点的值、小于其右 子树上所有节点的值。试判断一棵树是否为二叉查找树。
输入的第一行包含一个整数 n，表示这棵树有 n 个顶点，编号分别为 1, 2, ..., n，其中编号为 1 的 为根结点。之后的第 i 行有三个数 value, left_child, right_child，分别表示该节点关键字的值、 左子节点 的编号、右子节点的编号；如果不存在左子节点或右子节点，则用 0 代替。输出 1 表示这棵树是二叉查 找树，输出 0 则表示不是。

program Bst;
const SIZE = 100;
const INFINITE = 1000000;
type node = record
  left_child, right_child, value : longint;
end;
Var a : array[1..SIZE] of node;
   i, n : longint;
function is_bst(root, lower_bound, upper_bound : longint) : longint;
Var cur : longint;
begin
  if root = 0 then begin is_bst := 1;
  exit;
end;
cur := a[root].value;
if (cur > lower_bound) and ( cur<upper_bound ) and //（3 分） 
   (is_bst(a[root].left_child, lower_bound, cur) = 1) and 
   (is_bst( a[root].right_child , cur , upper_bound ) = 1) then is_bst := 1//（3 分，3 分，3 分） 
     Else is_bst := 0;
end;
begin readln(n);
for i := 1 to n do
  read(a[i].value, a[i].left_child, a[i].right_child);
 writeln(is_bst( 1 , -INFINITE, INFINITE));//（2 分） 
end.