海曙区中小学信息学竞赛初赛试题 [2014年]

1. 二进制数11001111转为八进制后值是（ ）

2. 在计算机系统中，数值一律用补码来表示（存储）。 那么在Free Pascal的中，-15用shortint变量类型存储在计算机内，其二进制编码为：（ ）

3. 如果x=5,y=6，则下列表达式的值为True的是（ ）

4. 一台计算机的内存容量是4GB，那么4GB =（ ）字节。

5. 已知二维数组定义a:array[0..100,0..3] of real;则数组a需要存储空间的字节数是（ ）

6. 在Free Pascal中产生一个随机整数赋给R，要求100≤R≤200，正确的语句是（ ）

7. IPv6是用于替代现行版本IPv4的下一代IP协议，其中IPv6地址长度为（ ）

8. 以下关于防火墙系统描述不正确的是（ ）

9. 计算机界最负盛名、最崇高的一个奖项，对获奖条件要求极高，评奖程序又是极严，一般每年只奖励一名计算机科学家，只有极少数年度有两名合作者或在同一方向作出贡献的科学家共享此奖，有“计算机界的诺贝尔奖”之称，其奖项名称取自（ ）

10. HTML指的是 ( )

11. 苹果手机iPhone使用的操作系统是（ ）

12. 下列语句在Free Pascal中不合法的是（ ）

13. 有以下的程序段： k:=0; for i:=1 to n-1 do for j:=n downto i+1 do if a[j]>a[j-1] then inc(k); writeln(k); 当n=10时，运行该程段，输出k值的最大值是( )

14. 以下程序段 for i:=1 to n do begin h:=1;r:=n;m:=(h+r) div 2; while (h<=r) and (a[i]<>b[m]) do begin if a[i]>b[m] then h:=m+1 else r:=m-1; m:=(h+r) div 2; end; if a[i]=b[m] then writeln(‘Yes’) else writeln(‘NO’); end; 该程序段中算法的时间复杂度为( )

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

16. 共有10个结点的二叉树中，叶子结点最多有( )

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

18. 给定一个长度为5的进队序列（每个元素互不相同），一共存在的出队序列种数为：( )

19. 线性表若采用链表存贮结构，要求内存中可用存贮单元地址（　 　）

20. 表达式A+B*C/D的后缀表达式是( )

1. 5面不同颜色的旗，20种不同颜色的盆花，现在需要取出两面旗夹着3盆花排成一列，有多少不同方案数？
答案：136800

2. 同一平面内有N条互不平行的直线，其中有P条直线相交于同一点，那么N条直线将这个平面共分成了多少个区域？
答案：(N*N-P*P+N+3P)/2

1.

program t2014_1;
var s,s1:string;
    i,k,n:integer;
begin
  s:='abbccdgggvvvvvv33333*';
  i:=1;
  repeat
    n:=1;k:=i+1;
    while s[i]=s[k] do begin
       n:=n+1;delete(s,k,1);
    end;
    if n>1 then
      begin
       str(n,s1);
       insert(s1,s,k)
      end;
    i:=i+1;
 until s[i]='*';
 writeln(s);
end.

输出：ab2c2dg3v635*

2.

program t2014_2
var n,k:integer;
function s(n,k:integer):longint;
  begin
    if (n<k)or(k=0) then
        s:=0
    else if (k=1)or(k=n) then
             s:=1
         else
             s:=s(n-1,k-1)+k*s(n-1,k)
  end;
begin
  readln(n,k);
  writeln(s(n,k));
end.
输入：
5 3

输出：15

3.

program jb2014_3
var
f:array[0..400,0..400] of integer;
 n,mv,mw,v,w,x,i,j,k:integer;
function max(a,b:integer):integer;
begin
   max:=a;
   if max<b then max:=b;
end;
begin
  readln(mv,mw);
  readln(n);
  for k:=1 to n do
    begin
      readln(v,w,x);
      for i:=mv downto v do
         for j:=mw downto w do
             f[i,j]:=max(f[i,j],f[i-v,j-w]+x);
     end;
 writeln(f[mv,mw]);
end.
输入：
32 35
4
16 4 12
8 11 24
22 7 31
4 40 22

输出：55

4.

program t2014_4;
var
 s:array[1..10000] of string; x:string;
 n,i,j,k,max:integer;
begin
 readln(n);
 readln(s[1]);k:=1;  max:=1;
 for i:=2 to n do
   begin
    readln(x);
    j:=k;
    while (pos(s[j],x)=0) and (j>0) do j:=j-1;
    s[j+1]:=x;
    if max< j+1 then
      begin
        max:=j+1;
        k:=k+1;
      end;
   end;
 writeln(max);
end.
输入：
10
h
hpe
hpeh
hpehp
hpehxt
hpej
hpeju
hpejuyr
hu
hws

输出：5

1. 第1题： “振荡”冒泡排序：
将n个整数从小到大排序（n≤1000），下面的程序是对普通冒泡法排序的一个改进：先从一端开始扫描，进行比较、交换，然后改变下一趟扫描的方向，作同样的处理，使冒泡过程来回“振荡”进行，并逐步缩小扫描范围，直到n个数都排好序为止。

program t2014_5;
var n,i:integer;
    a:             array[1..1000] of integer             ; 
procedure shakesort(x:integer);
  var i,h,t,k:integer;
      b:boolean;
  begin
    h:=1;t:=x;
    repeat
        b:=true  ;
      for i:=h to    t-1    do
        if  a[i]>a[i+1] then begin
            k:=a[i];a[i]:=a[i+1];a[i+1]:=k;
            b:=false;
        end;
      t:=t-1;
      for i:=t-1 downto h do 
        if       a[i]>a[i+1]      then  begin
          k:=a[i];a[i]:=a[i+1];a[i+1]:=k;
          b:=false;
        end;
      h:=h+1
     until b;
    end;
  begin
    randomize;readln(n);
    for i:=1 to n do a[i]:=random(1000)+1;
         shakesort(n)      ;
    for i:=1 to n do write(a[i]:4);
    writeln
  end.

2. 第2题：家族问题
若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。
规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。
输入：
第一行：三个整数n,m,p，分别表示有n个人，m个亲戚关系，询问p对亲戚关系。
以下m行：每行两个数Mi，Mj,(1<=Mi，Mj<=N),表示Ai和Bi具有亲戚关系。
接下来p行：每行两个数Pi，Pj，询问Pi和Pj是否具有亲戚关系。
输出：
P行，每行一个’Yes’或’No’。表示第i个询问的答案为“具有”或“不具有”亲戚关系。
输入样例：
6 5 3
1 2
1 5
3 4
5 2
1 3
1 4
2 3
5 6
输出样例：
Yes
Yes
No
请将程序补充完整。

program t2014_6;
var
 r:array[1..5000] of longint;
 n,m,p,i,a,b:longint;
function gfa(u:longint):longint;  
begin
  if r[u]=u then
     exit(u)
  else
         r[u]:=gfa(r[u])       ;  //压缩优化亲戚关系树
  gfa:=r[u];
end;
procedure union(x,y:longint);  //加入亲戚关系
var fx,fy:longint;
begin
  fx:=gfa(x);fy:=gfa(y);
  if fx<>fy then
          r[fx]:=fy       ; 
end;
function query(x,y:longint):boolean;   //查询x和y是否具有亲戚关系
begin
  query:=     gfa(x)=gfa(y)       ;
end;
begin
  readln(n,m,p);
  for i:=1 to n do r[i]:=      i       ;
  for i:=1 to m do
   begin
     readln(a,b);
           union(a,b)       ;
   end;
  for i:=1 to p do
   begin
     readln(a,b);
     if (query(a,b)) then
       writeln('Yes')
     else
       writeln('No');
   end;
end.