2014年NOIP提高组初赛真题

一、单项选择题（共 15 题，每题 1.5 分，共计 22.5 分；每题有且仅有一个正确 选项）
1. 以下哪个是面向对象的高级语言( )。
  • A. 汇编语言
  • B. C++
  • C. FORTRAN
  • D. Basic
2. 1TB代表的字节数量是( )。
  • A. 2的10次方
  • B. 2的20次方
  • C. 2的30次方
  • D. 2的40次方
3. 二进制数00100100和00010101的和是( )。
  • A. 00101000
  • B. 001010100
  • C. 01000101
  • D. 00111001
4. TCP协议属于哪一层协议( )。
  • A. 应用层
  • B. 传输层
  • C. 网络层
  • D. 数据链路层
5. 下列几个32位IP地址中，书写错误的是( ).
  • A. 162.105.130.27
  • B. 192.168.0.1
  • C. 256.256.129.1
  • D. 10.0.0.1
6. 在无向图中，所有顶点的度数之和是边数的( )倍。
  • A. 0.5
  • B. 1
  • C. 2
  • D. 4
7. 对长度为n的有序单链表，若检索每个元素的概率相等，则顺序检索到表中任一元素的平均检索长度为( )。
  • A. n/2
  • B. (n+1)/2
  • C. (n-1)/2
  • D. n/4
8. 编译器的主要功能是( )。
  • A. 将一种高级语言翻译成另一种高级语言
  • B. 将源程序翻译成指令
  • C. 将低级语言翻译成高级语言
  • D. 将源程序重新组合
9. 二进制数111.101所对应的十进制数是( )。
  • A. 5.625
  • B. 5.5
  • C. 6.125
  • D. 7.625
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的值大约是( )。
  • A. 2.500000
  • B. 2.750000
  • C. 3.500000
  • D. 0.000000
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所指结点的先后位置交换，同时要保持链表的连续，以下程序段中错误的是( )。
  • A. q^.next:=r^.next; p^.next:=r; r^.next:=q;
  • B. p^.next:=r; q^.next:=r^.next; r^.next:=q;
  • C. q^.next:=r^.next; r^.next:=q; p^.next:=r;
  • D. r^.next:=q; q^.next:=r^.next; p^.next:=r;
12. 同时查找2n个数中的最大值和最小值，最少比较次数为( )。
  • A. 3(n-2)/2
  • B. 4n-2
  • C. 3n-2
  • D. 2n-2
13. 设G是有6个结点的完全图要得到一棵生成树，需要从G中删去( )条边。
  • A. 6
  • B. 9
  • C. 10
  • D. 15
14. 以下时间复杂度不是O(n2)的排序方法是( )。
  • A. 插入排序
  • B. 归并排序
  • C. 冒泡排序
  • D. 选择排序
15. 以下程序段实现了找第二小元素的算法。输入是n个不等的数构成的数组S，输出S中第二小的数SecondMin。在最坏情况下，该算法需要做( )次比较。 if S[1]


  • A.2n

  • B.n-1

  • C.2n-3

  • D.2n-2




查看

  • A. 2n
  • B. n-1
  • C. 2n-3
  • D. 2n-2
二、不定项选择题（共 5 题，每题 1.5 分，共计7.5 分；每题有一个或多个正确  选项，多选或少选均不得分）
16. 若逻辑变量A、C为真，B、D为假，以下逻辑运算表达式为真的有( )。
  • A. (B∨C∨D)∨D∧A
  • B. ((┐A∧B)∨C)∧┐B
  • C. A∧(D∨┐C)∧B
  • D. (A∧B)∨(C∧D)∨┐A)
17. 下列( )软件属于操作系统软件。
  • A. Microsoft Word
  • B. Windows XP
  • C. Android
  • D. MacOSX
  • E. Oracle
18. 在NOI比赛中，对于程序设计题，选手提交的答案不得包含下列哪些内容( )。
  • A. 试图访问网络
  • B. 打开或创建题目规定的输入/输出文件之外的其他文件
  • C. 运行其他程序
  • D. 改变文件系统的访问权限
  • E. 读写文件系统的管理信息
19. 以下哪些结构可以用来存储图( )。
  • A. 邻接矩阵
  • B. 栈
  • C. 邻接表
  • D. 二叉树
20. 下列各无符号十进制整数中，能用八位二进制表示的数有( )。
  • A. 296
  • B. 133
  • C. 256
  • D. 199
三、问题求解（共  2 题，每题  5 分，共计  10 分；每题全部答对得  
21. 由数字1,1,2,4,8,8所组成的不同的四位数的个数是_________。
22. 如图所示，图中每条边上的数字表示该边的长度，则从A到E的最短距离是_________。
四、阅读程序写结果（共  4 题，每题  8 分，共计  32 分）
23. 
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
输出：____①_____
24. 
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
输出：____①_____
25. 
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
输出：____①_____
26. 
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
输出：____①_____
五、完善程序（第  1 题  12 分，第  2 题  16分，共计 28 分）
27. （双栈模拟数组）只使用两个栈结构 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 :=  ____①_____ ;
  top2 :=  ____②_____ ;
  for j := 0 to m - 1 do
  begin
    read(i);
    while (i < top1 - 1) do
    begin
      dec(top1);
        ____③_____    ;
      inc(top2);
    end;
    while (i > top1 - 1) do
    begin
      dec(top2);
        ____④_____   ;
      inc(top1);
    end;
    clearStack();
    writeln(stack1[ ____⑤_____ ]);
  end;
end.
28. （最大子矩阵和）给出 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 ____①_____ ;
  for i := 1 to m do
       ____②_____   ;
  for i := 1 to m do
    for j := 1 to n do
      rowsum[i, j] := ____③_____ ;
  for first := 1 to n do
    for last := first to n do
    begin
        ____④_____  ;
      for i := 1 to m do
      begin
        area := area + ____⑤_____ ;
        if (area > ans) then
          ans := area;
        if (area < 0) then
          area := 0;
      end;
    end;
  writeln(ans);
end.
查看参考答案