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

1. 以下哪个是面向对象的高级语言( )。

2. 1TB代表的字节数量是( )。

3. 二进制数00100100和00010101的和是( )。

4. TCP协议属于哪一层协议( )。

5. 下列几个32位IP地址中，书写错误的是( ).

6. 在无向图中，所有顶点的度数之和是边数的( )倍。

7. 对长度为n的有序单链表，若检索每个元素的概率相等，则顺序检索到表中任一元素的平均检索长度为( )。

8. 编译器的主要功能是( )。

9. 二进制数111.101所对应的十进制数是( )。

10. 若有变量var a:integer；x，y:real；，且a:=7，x:=2.5，y:=4.7，则表达式x + a mod 3 * trunc(x + y) mod 2 div 4的值大约是( )。

11. 有以下结构体说明和变量定义，如图所示，指针p、q、r分别指向一个链表中的三个连续结点。 type ptr=^node; node=record data:integer; next:ptr; end; var p,q,r:ptr; data next data next data next 现要将q和r所指结点的先后位置交换，同时要保持链表的连续，以下程序段中错误的是( )。

12. 同时查找2n个数中的最大值和最小值，最少比较次数为( )。

13. 设G是有6个结点的完全图要得到一棵生成树，需要从G中删去( )条边。

14. 以下时间复杂度不是O(n2)的排序方法是( )。

15. 以下程序段实现了找第二小元素的算法。输入是n个不等的数构成的数组S，输出S中第二小的数SecondMin。在最坏情况下，该算法需要做( )次比较。 if S[1]

1. 若逻辑变量A、C为真，B、D为假，以下逻辑运算表达式为真的有( )。

2. 下列( )软件属于操作系统软件。

3. 在NOI比赛中，对于程序设计题，选手提交的答案不得包含下列哪些内容 ( )。

4. 以下哪些结构可以用来存储图( )。

5. 下列各无符号十进制整数中，能用八位二进制表示的数有( )。

1. 由数字1,1,2,4,8,8所组成的不同的四位数的个数是_________。
答案：102

2. 如图所示，图中每条边上的数字表示该边的长度，则从A到E的最短距离是________。
答案：15

1.

var
  a, b, i, tot, c1, c2: integer;
begin
  readln(a, b);
  tot := 0;
  for i := a to b do
  begin
    c1 := i div 10;
    c2 := i mod 10;
    if (c1 + c2) mod 3 = 0 then
      inc(tot);
  end;
  writeln(tot);
end.

输入：7 31
输出：8

2.

var
  n, m: integer;
function fun(n, minNum, maxNum: integer): integer;
var tot, i: integer;
begin
if n = 0 then
  exit(1);
    tot := 0;
    for i := minNum to maxNum do
        tot := tot + fun(n - 1, i + 1, maxNum);
    exit(tot);
end;

begin
  readln(n, m);
  writeln(fun(m, 1, n));
end.
输入：6 3
输出：20

3.

const
  SIZE = 100;
var
  dict: array [1..SIZE] of string;
  rank, ind: array [1..SIZE] of integer;
  i, j, n, tmp: integer;

begin
  readln(n);
  for i := 1 to n do
  begin
    rank[i] := i;
    ind[i] := i;
    readln(dict[i]);
  end;
  for i := 1 to n - 1 do
    for j := 1 to n - i do
      if dict[ind[j]] > dict[ind[j + 1]] then
      begin
        tmp := ind[j];
        ind[j] := ind[j + 1];
        ind[j + 1] := tmp;
      end;
  for i := 1 to n do
    rank[ind[i]] := i;
  for i := 1 to n do
    write(rank[i], ' ');
  writeln;
end.

输入：
7
aaa
aba
bbb
aaa
aaa
ccc
aa
输出：2 5 6 3 4 7 1

4.

const
  SIZE = 100;
var
  alive: array [1..SIZE] of integer;
  n, m, num, i, j: integer;

function next(num: integer): integer;
begin
    repeat
        inc(num);
        if num > n then
            num := 1;
    until alive[num] <> 0;
    exit(num);
end;

begin
  read(n, m);
  for i := 1 to n do
    alive[i] := 1;
  num := 1;
  for i := 1 to n do
    begin
        for j := 1 to m - 1 do
            num := next(num);
        write(num, ' ');
        alive[num] := 0;
        if i < n then
            num := next(num);
end;
writeln;
end.
输入：11 3
输出：3 6 9 1 5 10 4 11 8 2 7

1. （双栈模拟数组）只使用两个栈结构 stack1和 stack2，模拟对数组的随机读取。作为栈结构，stack1和stack2只能访问栈顶（最后一个有效元素）。栈顶指针top1和 top2均指向栈顶元素的下一个位置。
输入第一行包含两个整数，分别是数组长度n 和访问次数m，中间用单个空格隔开。第二行包含n个整数，依次给出数组各项（数组下标从 0到n-1）。第三行包含 m个整数，需要访问的数组下标。对于每次访问，输出对应的数组元素。 （前两空每空 2.5分，其余每空3分，共14 分）

const
    SIZE = 100;
var
  stack1, stack2: array [0..SIZE] of integer;
  top1, top2: integer;
  n, m, i, j: integer;

procedure clearStack();
var
    i: integer;

begin
    for i := top1 to SIZE do
        stack1[i] := 0;
    for i := top2 to SIZE do
        stack2[i] := 0;
end;

begin
  read(n, m);
  for i := 0 to n - 1 do
    read(stack1[i]);
  top1 :=  n ;
  top2 :=  0 ;
  for j := 0 to m - 1 do
  begin
    read(i);
    while (i < top1 - 1) do
    begin
      dec(top1);
        stack2[top2]:=stack1[top1]    ;
      inc(top2);
    end;
    while (i > top1 - 1) do
    begin
      dec(top2);
        stack1[top1]:=stack2[top2]   ;
      inc(top1);
    end;
    clearStack();
    writeln(stack1[ top1-1 ]);
  end;
end.

2. （最大子矩阵和）给出 m行n列的整数矩阵，求最大的子矩阵和（子矩阵不能为空）。
输入第一行包含两个整数m和 n，即矩阵的行数和列数。之后m行，每行 n个整数，描述整个矩阵。程序最终输出最大的子矩阵和。（第一空2 分，其余3分，共 14分）

const
  SIZE = 100;
var
  matrix: array [1..SIZE, 1..SIZE] of integer;
  rowsum: array [1..SIZE, 0..SIZE] of integer;
    // rowsum[i, j]记录前 i行前 j个数的和
  m, n, i, j, first, last, area, ans: integer;

begin
  read(m, n);
  for i := 1 to m do
    for j := 1 to n do
      read(matrix[i, j]);
  ans := matrix [1,1] ;
  for i := 1 to m do
       rowsum[i,0]:=0   ;
  for i := 1 to m do
    for j := 1 to n do
      rowsum[i, j] := rowsum[i,j-1]+matrix[i][j] ;
  for first := 1 to n do
    for last := first to n do
    begin
        area:=0  ;
      for i := 1 to m do
      begin
        area := area + wsum[i,last]-rowsum[i,first-1] ;
        if (area > ans) then
          ans := area;
        if (area < 0) then
          area := 0;
      end;
    end;
  writeln(ans);
end.