宁波市海曙区程序设计竞赛初赛 [2016年]

1. 字符在计算机内部是连续表示的，字符“T”的ASCII码对应的二进制数为1010100，则大写字符“S”的ASCII码对应的二进制是（）

2. 单字节10和-10在计算机内部分别表示为（）

3. 控制器是（ ）的重要组成部分。

4. 在外部设备中，打印机属于（ ）。

5. 每个不同的二进制数可以表示一种颜色，如果一幅图像有256种颜色，最少需要几位二进制数来表示？（ ）

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

7. 下面哪个是即时通讯工具（ ）

8. 下列软件不能用子浏览网页的是（ ）

9. 二维数组A的每个元素是由6个字符(char)组成的串。其行下标从0至100，其列下标从0到100,存储时整个数组占用内存空间数约为（ ）。设每个字符占一个字节。

10. 计算机的运算速度取决于给定的时间内，它的处理器所能处理的数据量。处理器一次能处理的数据量叫字长。已知64位的酷睿处理器一次能处理64个信息位，相当于（）字节。

11. 以下运算结果为True的是（ ）

12. 如图有两个栈s1,s2,有一数字序列12 3 4,依次进入其中任意一个栈，任一个数字入栈后也可随时出找，则不可能的出栈序列是：

13. 线性表若采用队列存贮结构，要求内存中可用存贮单元地址（ ）。

14. 一个包含n个分支结点（非叶结点）的完全二叉树，它的叶结点数目最多为：

15. 快速排序最坏情况下的算法复杂度为：

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

17. 排序算法是稳定的意思是关键码相同的记录排序前后相对位置不发生改变，下列哪种排序算法是不稳定的：

18. 已知n个顶点的有向图，若该图是强连通的（从所有顶点都存在路径到达其他顶点）， 则该图中最少有多少条有向边？

19. 现在主要使用的IPv4地址是由（）位二进制数码表示的?

20. 美箱匈牙利数学家冯*诺依曼对计算机科学发展所做出的贡献是：()

1. 设有一个共有6级的楼梯，某人每步可走1级，也可走2级，也可走3级，问某人 从底层开始走完全部楼梯的走法共有___________________种。（当有3级楼梯时，共有4种走法，即 1+1+1,1+2,2+1，3)
答案：24

2. 在一个果园里，笑笑已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。笑笑决定把所有的果子合成一堆。 每一次合并，笑笑可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。笑笑在合并果子时总共消耗的体力等于每次合并所耗体力之和。 假定有5堆果子，每堆的数量为12，6，20，15，10，每个果子的重量都为2，笑笑想知道最小的体力耗费是_______。
答案：284

1.

var
  h,m,s,n:longint;
begin
  readln(n);
  h:=n div 3600;
  m:=n div 60 - h*60;
  s:=n mod 60;
  writeln(h,'h',m,'m',s,'s');
end.
输入：4000
输出：1h6m40s

2.

var
  n,a,b,c,i:longint;
begin
  readln(n);
  a:=0; b:=1; i:=1;
  while i<n do
  begin
    c:=a+b;
    a:=b;
    b:=c;
    inc(i);
  end;
  writeln(c);
end.
输入：10

输出：55

3.

var n:longint;
procedure change(t:longint);
begin
  if t=0 then exit;
  change(t div 8);
  write(t mod 8);
end;
begin
  readln(n);
  change(n);
end.
输入：2016
输出：3740

4.

var
  n,i,j,k:longint;
  st:ansistring;
begin
  readln(n);
  readln(st);
  st:=st+st;
  i:=1;j:=2;k:=0;
  while (i<=n) and (j<=n) and (k<n) do
  begin
    if i=j then inc(j);
    if st[i+k]=st[j+k] then inc(k)
    else
    if st[i+k]>st[j+k] then
    begin
      j:=j+k+1;
      k:=0;
    end
    else
    begin
      i:=i+k+1;
      k:=0;
    end;
  end;
  writeln(i);
end.
输入：haishuchusai
输出：9

1. (神奇的幻方)幻方是一种很神奇的N*N矩阵：它由数字1,2,3,...,N*N构成，且每行、每列及两条对角线上的数字之和都相同。
当N为奇数时，我们可以通过以下方法构建一个幻方：
首先将1写在第一行的中间。之后，按如下方式从小到大依次填写每个数(K=1,2,3,N*N)；
1.若(K-1)在第一行但不在最后一列则将填在最后一行，(k—1)所在列的右一列；
2.若(K-1)在最后一列但不在第一行，则将填在第一列，(K-1)所在行的上一行；
3.若(K-1)在第一行最后一列，则将填在(K-1)的正下方；
4.若(K-1)既不在第一行，也不在最后一列，如果(K-1)的右上方还未填数，则将K填在(K-1)的右上方，否则将填在的正下方。
现给定N(奇数)，请按上述方法构t造N*N的幻方。
样例输入：N=3
样例输出：
8 1 6
3 5 7
4 9 2

var
  n,x,y,k:longint;
  a:array[1..39,1..39] of integer;
begin
  readln(n);
  y:=  (n+1) div 2 ; x:=1;
  a[x,y]:=1;
  for k:=2 to n*n do
  begin
    if ( x=1 ) and (y<>n) then
     begin
      x:=n; inc(y);
     end
    else if (y=n) and (x<>1) then
     begin
       y:=1; dec(x);       
     end
    else if (x=1) and (y=n) then inc(x)
    else if a[x-1,y+1]=0 then
     begin
        dec(x)  ; inc(y);
     end
    else inc(x)  ;
    a[x,y]:=k;
  end;
  for x:=1 to n do
   begin
     for y:=1 to n do write(  a[x,y]  ,' ');
     writeln;
   end;
end.

2. (跳石头)这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会己经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有N块岩石(不含起
点和终点的岩石)。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。
为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点到终点之间移走M块岩石(不能移走起点和终点的岩石)。
输入第一行包含三个整数L，N，M,分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。
接下来一行，N个整数，第i个整数Di(0<Di<L)表示第i块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置。
【样例输入】
25 5 2
2 11 14 17 21
【样例输出】
4
将与起点距离为2和14的两个岩石移走后，最短的跳跃距离为4 (从与起点距离17的岩石跳到距离21的岩石，或者从距离21的岩石跳到终点)。
算法：由于答案是线性的，可以二分枚举最终答案，再每次验证答案的正确性，从而逼近直到确定最终的最长距离。

var
  d:array[0..100005] of longint; 
  i,Len,n,m,l,r,mid:longint;
function check(ans:longint):boolean;//判断 ans 是否为可行的答案 
var
  i,last,tot:longint; 
begin
  last:=0; tot:=0; 
  for i:=1 to n do
    if (d[i]-last>=ans) then last:=d[i]
    else  inc(tot) ;
  if Len-last<ans then inc(tot);   
  if (tot<=m) then exit ( true )
  else exit(false);
end;
 
begin
  readln(Len,n,m);
  for i:=1 to n do read(d[i]);
  d[n+1]:=Len;
  l:=0; r:=len; 
  while l<r do
  begin
    mid:=  (l+r+1) div 2 ;
    if (check(mid)) then l:=mid
    else r:=  mid-1  ;
  end;
  writeln(l);
end.