宁波市第30届中学生计算机程序设计初赛试题 [2015年]

1. 关于硬盘下面的说法哪个是不正确的:

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

3. 关于微型计算机主板下面说法哪个是正确的：

4. 关于CPU下面哪个说法是不正确的：

5. 关于ASCII码和汉字编码，下面哪个说法是正确的：

6. 下列软件中是操作系统的是：

7. 关于互联网，下面的说法哪一个是正确的：

8. 关于HTML下面哪种说法是正确的：

9. 机器语言是用二进制代码表示的计算机能直接识别和执行的一种机器指令的集合，一般由高级程序设计语言编译生成。关于机器语言，下面哪个说法是正确的：

10. 已知大写字母A的ASCII编码为65（十进制），则十进制70表示ASCII码中的字符为：

11. 若根节点的深度为1，1024个节点的二叉树，深度最少是

12. 有六个元素ABCDEF 从左至右依次顺序进入队列，在进队过程中会有元素从队首出队列，且最终所有元素出队列。问下列唯一合法的出队序列？

13. 后缀表达式abc+*d-中，a=1,b=2,c=3,d=4,则该后缀表达式的值是

14. 无向完全图是图中每对顶点之间都恰有一条边的简单图。已知无向完全图 G 有 5 个顶点，则它共有（ ）条边

15. 深度优先搜索时，控制与记录搜索过程的数据结构是：

16. 有一个由2015个整数构成的顺序表，假定表中的元素已经按降序排列，采用二分查找定位一个元素。则最多需要几次比较就能确定是否存在所查找的元素：

17. 在含有 2015 个元素的双向链表中查询是否存在关键字为 key 的元素最坏情况下运行的查找次数是（ ）。

18. 一个正整数在十六进制下有200位，则它在二进制下最多可能有（ ）位。

19. 2014年美国计算机科学家莱斯利·兰波特，因提出多核与分布协作算法，获得（ ）大奖，奖金为25万美元。

20. 以下哪一位是目前唯一一个获得过有“计算机界的诺贝尔奖”之称的“图灵奖”的美籍华人

1. 原字符串中任意一段连续的字符所组成的新字符串称为子串。 则字符“AAABBC”共有______________不同的非空子串。
答案：17

2. 小明在玩一个数字游戏，他随手在纸上写下了一个三位数abc，接着将这个三位数各个数位上数字全部排列写下，依次为acb，bac，bca，cab，cba这五个数。现在，小明算出后面写下的五个数的和为1340，你猜出小明写下的这个三位数为______ 。
答案：214

1.

var 
    a,b,c,t:longint;  
begin 
    readln(a,b,c);  
    if a>b then begin t:=a; a:=b; b:=t; end;  
    if a>c then begin t:=a; a:=c; c:=t; end;  
    if b>c then begin t:=b; b:=c; c:=t; end;  
    writeln(a,' ',b,' ',c);  
end.
输入：
10 20 15

输出：10 15 20 

2.

var n,i,ans: integer;  
begin  
    readln(n);  
	ans:= 0; 
    for i:= 1 to n do 
     if (n mod i)= 0 then ans := ans+i;  
    writeln(ans);  
end.
输入：
25
输出：31

3.

var 
    n,i,j,t,ans:longint; 
    x,y:array[0..500] of longint; 
begin 
    readln(n); 
    for i:=1 to n do 
        readln(x[i],y[i]); 
    for i:=1 to n-1 do 
        for j:=1 to n-i do 
        begin 
            if x[j]>x[j+1] then 
            begin 
                t:=x[j]; 
                x[j]:=x[j+1]; 
                x[j+1]:=t; 
            end; 
            if y[j]>y[j+1] then 
            begin 
                t:=y[j]; 
                y[j]:=y[j+1]; 
                y[j+1]:=t; 
            end; 
        end; 
    ans:=0; 
    for i:=1 to n do 
        ans:=ans+abs(i-x[i])+abs(i-y[i]); 
    writeln(ans); 
end.
输入：
6
1 1
1 2
2 1
5 6
6 5
6 6

输出：8

4.

var
    a:array[1..20] of longint; 
    f:Array[0..20000]of boolean; 
    i,n:longint; 
procedure dfs(t,sum:longint); 
begin 
    if t>n then 
    begin 
        f[sum]:=true; 
        exit; 
    end; 
    dfs(t+1,sum); 
    dfs(t+1,sum+a[t]); 
end; 
begin 
    readln(n); 
    for i:=1 to n do 
        read(a[i]); 
    dfs(1 ,0); 
    for i:=1 to 20000 do 
        if not f[i] then break; 
    writeln(i); 
end.
输入 
9 
1 2 4 8 16 32 64 128 256
输出：512

1. (螺旋矩阵) 一个n行m列的螺旋矩阵可由如下方法生成：从矩阵的左上角（第1行第1列）出发，初始时向右移动；如果前方是未曾经过的格子，则继续前进，否则右转；重复上述操作直至经过矩阵中所有格子。根据经过顺序，在格子中依次填入1, 2, 3, ... , n^2，便构成了一个螺旋矩阵。输入n和m，输出一个螺旋矩阵，同一行中相邻两个数字中间有一个空格，行末没有空格。

var 
    n, m, i, j, t, s:longint; 
    a:array[-1..11,-1..11] of longint; 
    dx:array[1..4] of longint=(-1,0,0,1); 
    dy:array[1..4] of longint=(0,-1,1,0); 
begin 
    readln(n,m); 
i:=1;    j:=1;     
t:=1;    s:=1;  //t表示当前要填的数值s表示当前填的方向 
    a[i,j]:=t; 
    while     t<n*m      do begin 
        inc(t); 
        i:=i+dx[s]; 
        j:=      j+dy[s]      ; 
        if (i>n) or (i<1) or (    j>m   ) or (j<1) or (a[i,j]<>0) then  
          begin 
            i:=i-dx[s]; 
            j:=j-dy[s]; 
            dec(t); 
            s:=s+1; 
            if s=5 then       s:=1      ; 
            continue; 
        end; 
        a[i,j]:=t; 
    end; 
for i:=1 to n do  
begin 
        for j:=1 to m-1 do write(a[i,j],' '); 
        writeln(      a[i,m]      ); 
    end; 
end. 

2. （二叉树先序遍历）给出一棵二叉树的中序与后序排列。求出它的先序排列，其中树结点用不同的大写字母表示，例如输入BADCE，BDECA分别表示中序和后序，输出：ABCDE表示先序遍历。

var 
  mid, last: string; 
procedure dfs(mid, last:string); 
var 
  i, len: longint; 
  root: char; 
begin 
  if length(mid)= 0 then exit; 
  len := length(mid); 
  root :=     last[len]      ; 
  for i := 1 to len do 
    if        mid[i]=root        then break; 
         write(root)       ; 
  dfs(copy(mid, 1, i-1),       copy(last,1,i-1)       ); 
  dfs(      copy(mid,i+1,len-i)      ,copy(last, i, len-i)); 
end; 
begin 
  readln(mid); 
  readln(last); 
  dfs(mid, last); 
  writeln; 
end.