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

1. 很多新款笔记本和电视机上都有HDMI接口，请问这个接口的作用是：

2. 在Pascal中，表达式2 OR 1 SHL 2 AND 10的值是：

3. 在32位操作系统中，Boolean型数组[1..10000,1..10000]需要的内存空间约为：

4. 下列关于32位操作系统和64位操作系统的说法中错误的是：

5. 下面关于二叉堆的复杂度说法中正确的是：

6. 算式11(2)-11(16)的结果是：

7. 下列关于邻接表和邻接矩阵的说法中错误的是：

8. 下列程序中不属于IDE(集成开发环境)的是：

9. IPv4中一个IP地址长度为32位，新一代协议IPv6中一个IP地址的长度为：

10. 小明家里电脑可以正常使用QQ，但是无法浏览网站，其原因可能是：

11. ASCII码表总共有字符128个，请问存放8个ASCII码需要的内存空间是：

12. 字符串＂ababacbab＂和字符串 ＂abcba＂的最长公共子串是：

13. 已知一棵二叉树的前序遍历结果为ABDECFHJIG，中序遍历的结果为DBEAJHFICG，若根节点的深度为0，则这棵二叉树的深度是：

14. 高度为n的均衡的二叉树是指：如果去掉叶结点及相应的树枝，它应该是高度为n-1的满二叉树。在这里，树高等于叶结点的最大深度，根结点的深度为0，如果某个均衡的二叉树共有1024个结点，则该树的树高是：

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

16. 下列设备中属于输入设备的是：

17. 在计算机内部，数据存储采用的进制是：

18. 小明家新安装运营商宣称的4Mb光宽带，请问其下载速度理论上可以达到的最大值是：

19. 第一位获得图灵奖的华人是：

20. NOIP的英文全称是：

1. 平面图的定义为若一个图G画在平面上，除顶点之外，再没有边与边相交。则图G为平面图。那么，边数为9的平面图最少有____个顶点?（仅针对无向图）
答案：6

2. 一个长度为N（1<=n<=26）字符串，最多有____个非空子序列，最少有____个不同的非空字串。（提示：子序列不要连续，子串要求连续）
答案：n(n-1)+1|n(n-1)/2

1.

var
   ans,i,x,n:longint;
begin
   readln(n);
   ans:=-1;
   for i:=1 to n do
    begin
      read(x);
      if ans<x then ans:=x;
    end;
   writeln(ans);
end.
输入：
5
6 5 4 3 2 10
输出：6

2.

var
 num:array[0..1000] of longint;
 i,x,n:longint;
begin
  readln(n);
  fillchar(num,sizeof(num),0);
  for i:=1 to n do
  begin
    read(x);
    num[x]:=num[x]+1;
  end;
  readln(x);
  writeln(num[x]);
end.
输入：
6
66 63 62 66 60 0
66
输出：2

3.

var
  n,i,p,max:longint;
  dp,a:array[0..1000] of longint;
function Binary_Search(x:longint):longint;
var
  l,r,m,i:longint;
begin
  l:=0;
  r:=max;
  while l+3<r do
  begin
    m:=(l+r) div 2;
    if dp[m]>=x then r:=m-1
    else l:=m;
  end;
  for i:=r downto l do
   if dp[i]<x then exit(i);
end;
begin
  readln(n);
  for i:=1 to n do read(a[i]);
  fillchar(dp,sizeof(dp),$20);
  dp[0]:=0;
  max:=0;
  for i:=1 to n do
  begin
    p:=Binary_Search(a[i]);
    p:=p+1;
    dp[p]:=a[i];
    if p>max then max:=p;
  end;
  writeln(max);
end.
输入1：
4
4 3 5 1


输入2：
5
4 4 3 5 1


输出：2|2

4.

var
     px,py,ax,ay,bx,by:double;
     t1x,t1y,t2x,t2y:double;
function Dist(ax,ay,bx,by:double):double;
begin
  exit(sqrt((ax-bx)*(ax-bx)+(ay-by)*(ay-by)));
end;
begin
  read(px,py,ax,ay,bx,by);
  while Dist(ax,ay,bx,by)>1E-10 do
  begin
    t1x:=(ax*2+bx) / 3;
    t1y:=(ay*2+by) / 3;
    t2x:=(ax+bx*2) / 3;
    t2y:=(ay+by*2) / 3;
    if Dist(px,py,t1x,t1y)<Dist(px,py,t2x,t2y) then
    begin
      bx:=t2x;
      by:=t2y;
    end
    else
    begin
      ax:=t1x;
      ay:=t1y;
    end;
  end;
  writeln(trunc(Dist(px,py,ax,ay)));
end.
输入：
0 0 -1 1 1 1
输出：1

1. 输入一个正整数n（2<=n<=108），请将n用质因数乘式的形式表示，如果质因数不止一个，请按照质因数大小升序输出，每个数字后面均有空格。

ar
 i,n,plen:longint;
 prime:array[1..5000] of longint;
procedure Gen_Prime;
var
  h:array[1..10000] of boolean;
  i,j:longint;
begin
  fillchar(h,sizeof(h),false);
  for i:=2 to 10000 do
    if   not h[i]  then
    begin
       j:=2;
       while i*j<=10000 do
       begin
         if h[i*j]=false then
          h[i*j]:=true   ;
         j:=j+1;
       end;
    end;
    plen:=0;
    for i:=2 to 10000 do
     if not h[i] then
     begin
       plen:=plen+1;
       prime[plen]:=i ;
     end;
end;

begin
  read(n);
  Gen_Prime;
  for i:=1 to plen do
    while n mod prime[i]=0 do
    begin
       write(prime[i],' ');
       n:=n div prime[i] ;
    end;
  if n>1  then  write(n,' ');
  writeln;
end.

2. （归并排序求逆序对数）给定N（N<=10000）个互不相同的数，请计算出逆序对的数量。比如对于数列1、5、2、4、6，逆序对数量为2分别是（5,2）、（5,4）。
输入：
5
1 5 2 4 6
输出：
2

var
  a:array[0..10000] of longint;
  i,n,ans:longint;
procedure Merge(l,m,r:longint);
var
  b:array[0..10000] of longint;
  i,j,k:longint;
begin
  i:=l;
  j:=m+1;
  k:=l;
  while (i<=m) and (j<=r) do
     if a[i]<a[j] then
     begin
       b[k]:=a[i];
       i:=i+1;
       k:=k+1;
     end
     else
     begin
       b[k]:=a[j];
       j:=j+1;
       k:=k+1;
       ans:= ans+m-i+1  ;
     end;
  while i<=m do
  begin
      b[k]:=a[i];
      i:=i+1;
        inc(k)  ;
  end;
  while j<=r do
  begin
    b[k]:=a[j];
      inc(j)   ;
    k:=k+1;
  end;
  for i:=l to r do  a[i]:=b[i]   ;
end;
procedure MergeSort(l,r:longint);
var
  m:longint;
begin
   if  l=r  then exit;
   m:=(l+r) div 2;
   MergeSort(l,m);
      MergeSort(m+1,r) ;
   Merge(l,m,r);
end;
begin
   read(n);
   for i:=1 to n do read(a[i]);
   ans:=0;
   MergeSort(1,n);
   writeln(ans);
end.