不是VIP会员,不能显示答案,请在后台“我的信息” 在线升级 VIP

一、 选择题(每题有且仅有一个正确答案,选对得1.5分,选错,不选或多选均不得分)

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

  • A.仅传输视频信号
  • B.仅传输音频信号
  • C.同时传输视频和音频信号
  • D.稳压电源输入

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

  • A.15
  • B.8
  • C.12
  • D.2

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

  • A.381MB
  • B.12MB
  • C.191MB
  • D.95MB

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

  • A.32位操作系统是针对32位的CPU设计的
  • B.64位操作系统是针对64位的CPU设计的
  • C.64位操作系统理论上能支持的内存大小可根据寻址空间计算而得
  • D.32位操作系统支持的内存大小不可能超过4G

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

  • A.插入为O(logn),删除为O(logn)
  • B. 插入为O(n),删除为O(n)
  • C.插入为O(n),删除为O(logn)
  • D.插入为O(logn),删除为O(n)

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

  • A.0(10)
  • B.0(16)
  • C.14(10)
  • D.-14(10)

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

  • A.两者都可以实现图的存储
  • B.两者可相互转换
  • C. 在一般情况下,邻接表在处理稀疏图时有明显优势
  • D.邻接矩阵的实现远比邻接表复杂

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

  • A.Free Pascal
  • B.Lazarus
  • C.Dev-C++
  • D.C++

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

  • A.64位
  • B.128位
  • C.256位
  • D.32位

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

  • A.电脑断网了
  • B.电脑DNS服务出现故障
  • C.CPU短路
  • D.显示器异常

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

  • A.7字节
  • B.8字节
  • C.7位
  • D.8位

12. 字符串"ababacbab"和字符串 "abcba"的最长公共子串是:

  • A.abcba
  • B.cba
  • C.abc
  • D.ab

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

  • A.3
  • B.4
  • C.5
  • D.6

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

  • A.7
  • B.8
  • C.9
  • D.10

15. 给定一个长度为5的进队序列(每个元素互不相同),一共存在的出队序列种数为:

  • A.1
  • B.5
  • C.25
  • D.42

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

  • A.键盘
  • B.显示器
  • C.CPU
  • D.电源

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

  • A. 8进制
  • B.2进制
  • C.10进制
  • D.16进制

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

  • A.4MB/s
  • B.512KB/s
  • C.1MB/s
  • D.8MB/s

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

  • A.刘翔
  • B.姚期智
  • C.高德纳
  • D.犹大 伯尔

20. NOIP的英文全称是:

  • A.National Olympiad in Informatics in Provinces
  • B. National Olympiad in Informatics in Profession
  • C. Normal Olympiad in Informatics in Profession
  • D. Normal Olympiad in Informatics in Provinces

二、问题求解(每小题5分,共10分)

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

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

三、阅读程序写结果(每题8分,共32分)

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

四、 程序填空(前5空,每空2分,后6空,每空3分,共28分)

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.