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

1. 计算机主机最主要是由CPU 与（）构成：

2. 操作系统是重要的系统软件，下面几个软件中不属于操作系统的是:

3. 在计算机网络中，IP地址127.0.0.1表示：

4. 无线局域网的英文缩写是：

5. 以下哪个不是常见智能手机的操作系统：

6. 第四代移动通值技术即 4G是集3G与WLAN于一体，它最高能以多少bps的速度下载:

7. 只运行一个普通的串行程序，采用四核CPU的电脑与双核的电脑相比（假设其他配置 均相同）:

8. 在下面各世界顶级的奖项中，为计算机科学与技术试域作出杰出贡献的科学家设立的奖项是：

9. 以下哪个指可以显示网页服务器或者文件系统的HTML文件内容，并让用户与这些文件交互的一种软件：

10. 十进制100.625等于二进制数:

11. 体育课的铃声响了，同学们都陆陆续续地奔向操场，按老师的要求从高到矮站成一排。每个同学来到操场时，都从排尾走向排头，找到第一个比自己高的同学，并站在他的后面。这种站队的方法类似于以下哪个算法：

12. 对有序数组{5,13,19,21,37,56,64,75,88,92,100}进行二分查找，等概率的情况下，查找成功的平均査找长度(平均比较次数)是：

13. 由3个a, 1个b和2个c构成的所有字符串中，包含子申"abc"的共有几个：

14. 递归过程和函数调用时，处理参数和返回地址，通常使用哪种数据结构：

15. 设栈S的初始状态为空，元素a， b， c， d， e， f 依次入找，出找顺序为b，d，c，f，e， a那么栈容量至少应该是：

16. 满二又树的叶结点个数为N, 则它的结点总数为：

17. 在含有n个元素的双向链表中查询是否存在关键字为k的元素，最坏情况运行的时间是：

18. 假设A=true, B=false, C=true, D=true, 逻辑运算表达式A∧B∨C∧D的值是：

19. 一个有n个顶点的无向图（无重边边）最多有几条边：

20. 现有4个砝码，重量分別为l克、2克、4克和8。那么可以称出几种不同重量的物体（物体重量必须大于0):

1. 现有80枚硬币，其中有一枚是假币，其重量稍轻，所有真币的重量都相同。如果使用 不带砝码的天平称重,最坏情况下至少需要称________ 次，就一定可以找出假币？
答案：4

2. 5男5女围着一张圆桌坐下，要求男女隔位就座，问有______种不同的方案？两个方案相同，当且仅当经过一定的旋转（不允许翻转），毎个座位上的人都相同。
答案：2880

1.

program exp1; 
var
  a:array[1..6] of longint;
  s,t,i,j:longint; 
begin
  a[1]:=1;t:=0;
  for i:=2 to 6 do
  begin
    s:=0;
    for j:=1 to i-1 do
      s:=s+a[j];
    a[i]:=s+1; 
  end;
  for i:=1 to 6 do
    t:=t+a[i]; 
  writeln('t=',t); 
end.
输出：t=63

2.

program exp2; 
var a,b,f: integer;
  function gd(m,n:integer):integer; 
begin
if n=0 then gd:=m
  else gd:=gd(n,m mod n);
end;
begin
  readln(a,b);
  write('(',a,',',b,')=');
  f:=gd(a,b);
  writeln(f) 
end.
输入：172 16
输出：(172,16)=4

3.

program exp3;
var
  visited:array[1..100] of boolean;
  e:array[1..100,1..100] of longint;
  n,m,ans,i,j,a,b,c:longint;
procedure dfs(x,len:longint); 
var
  i:longint;
begin
  visited[x]:=true;
  if len>ans then ans:=len;
  for i:=1 to n do
    if (not visited[i]) and (e[x,i]<>-1) then 
    dfs(i,len+e[x,i]);
  visited[x]:=false; 
end;
begin
  readln(n,m);
  for i:=1 to n do
    for j:=1 to n do e[i,j]:=-1;
  for i:=1 to m do
    begin
      readln(a,b,c);
      e[a,b]:=c;
      e[b,a]:=c;
    end;
  for i:=1 to n do visited[i]:=false;
  ans:=0;
  for i:=1 to n do dfs(i,0);
  writeln(ans); 
end.
输入：
4 6
1 2 10
2 3 20
3 4 30
4 1 40
1 3 50
2 4 60
输出：150

4.

program exp4;
var
  p,e:array[1..100] of longint;
  n,i,m,ans:longint;

function pow(x,w:longint):longint; 
var
  i,ret:longint;
begin
  ret:=1;
  for i:=1 to w do
    ret:=ret*x;
  exit(ret); 
end;

begin 
  readln(n);
  m:=0;  i:=2;
  while n<>1 do
  begin
    if n mod i = 0 then
    begin
      inc(m);
      p[m]:=i;
      e[m]:=0;
      while n mod i = 0 do
      begin
        inc(e[m]);
        n:=n div i;
      end; 
    end;
    inc(i); 
  end;
  ans:=1;
  for i:=1 to m do
    ans:=ans*(p[i]-1)*pow(p[i],e[i]-1);
  writeln(ans);
end.
输入：19800
输出：4800

1. 输入一个正整数 n(2 <= n <= 10^6)，以及 n 个不同的正整数(范围在1<=a[i]<=n)。这个数可以理解为n的一种排列，假设 (1 , 2 , 3, 4,……,n)是第1个排列，( n, n-1, ......, 1)是最后一个排列，根据这n个数组成的排列，输出下一个排列，每一个数后输出一个空格；若这n个数已经是最一个排列，输出“No Next Permutation”。
输入：5
1 2 5 4 3
输出：
1 3 2 4 5

var
  n,num,i,mid,t:longint; 
  a,b:array[1..1000000] of longint; 
  begin 
  readln(n);
  for i:=1 to n do read(a[i]);
  num:=0;
  i:=n;
  while i>1 do
  begin
    if a[i]<a[i-1] then
    begin
      inc(num); b[num]:=a[i];
    end
    else
    begin
      inc(num); b[num]:=a[i];
      inc(num);  b[num]:=a[i-1];
      mid:=i-2;
      break;
    end;
    dec(i)
  end;
  if i=1 then writeln('No Next Permutation')
  else
  begin
    for i:=1 to num-1 do
      if  b[i]>b[num] then
        begin
          t:=b[i];b[i]:=b[num];b[num]:=t;
          break;
        end;
    for i:=1 to mid do write(a[i],' ');
    write(b[num],' ');
    for i:=1 to num-1 do write(b[i],' ') ;
    writeln;
  end;
end.

2. 某地共派出M名选手参加宁波市程序设计竞赛，现在他们正赶往火车站参加比赛。火车站共有N(1<=N<=100000)个检票口。由于检票员的操作速度不同，每个检票口的通行速度也就不同，平均测量，第k个检票口的速度为每人Tk秒（范围1~10^9）。
在候车时，精于计算的选手们就开始思考，假设一开始所有检票口都处于准备状态，每个检票口一次只能通过一人。那么M (2 <= M <= 10^9)名选手至少需要多少时间全部通过检。输入N，M，以及N个检票口的检票时间。求最少全部通过时间。
输入：
7 10
3
8
3
6
9
2
4

输出：
8

var
  a:array[1..100000]of longint;
  i,n,m:longint;
  left,right,mid: int64;  
function check(midTime:int64):boolean;
var 
  sum:int64;
  i:longint;
begin
  sum:=0;
  for i:=1 to n do
    begin
      sum:= sum+midTime div a[i]   ;
      if sum>=m  then  exit(true)  ;
    end;
  exit(false);
end;

begin
  readln(n,m);
  for i:=1 to n do readln(a[i]);
  left:=0;
  right:=a[1];
  right:=right*m;
  while left<right do
    begin
      mid:=(left+right) div 2;
      if  check(mid)   then right:=mid;
      else  left:=mid+1     ;
    end;
   writeln(left)   ;   
end.