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

一. 单项选择题(共20题,每题1.5分,共计30分。每题有且仅有一个正确答案。)

1. 2E+03表示( )。

  • A.2.03
  • B.5
  • C.8
  • D.2000

2. 一个字节(byte)由( )个二进制位组成。

  • A.8
  • B.16
  • C.32
  • D.以上都有可能

3. 以下逻辑表达式的值恒为真的是( )。

  • A.P∨(﹁P∧Q) ∨(﹁P∧﹁Q)
  • B.Q∨(﹁P∧Q) ∨(P∧﹁Q)
  • C.P∨Q∨(P∧﹁Q) ∨(﹁P∧Q)
  • D.P∨﹁Q∨(P∧﹁Q) ∨(﹁P∧﹁Q)

4. Linux下可执行文件的默认扩展名为( )。

  • A.exe
  • B.com
  • C.dll
  • D.以是都不是

5. 如果树根算是第1层,那么一棵n层的二叉树最多有( )结点。

  • A.2n-1
  • B.2n
  • C.2n+1
  • D.2n+1

6. 提出“存储程序”的计算机工作原理的是( )。

  • A.克劳德·香农
  • B.戈登·摩尔
  • C.查尔斯·巴比奇
  • D.冯·诺依曼

7. 设X、Y、Z分别代表三进制下的一位数字,若等式XY+ZX=XYX在三进制下成立,那么同样在三进制下,等式XY×ZX=( )也成立。

  • A.YXZ
  • B.ZXY
  • C.XYZ
  • D.XZY

8. Pascal 语言、C 语言和 C++语言都属于( )。

  • A.面向对象语言
  • B.脚本语言
  • C.解释性语言
  • D.编译性语言

9. 前缀表达式“+3×2+5 12”的值是( )。

  • A.23
  • B.25
  • C.37
  • D.65

10. 主存储器的存取速度比中央处理器(CPU)的工作速度慢得多,从而使得后者的效率受到影响。而根据局部性原理,CPU所访问的存储单元通常都趋于聚集在一个较小的连续区域中。于是,为了提高系统整体的执行效率,在CPU中引入了( )。

  • A.寄存器
  • B.高速缓存
  • C.闪存
  • D.外存

11. 一个字长为8位的整数的补码是11111001,则它的原码是( )。

  • A.00000111
  • B.01111001
  • C.11111001
  • D.10000111

12. 基于比较的排序时间复杂度的下限是( ),其中n表示待排序的元素个数。

  • A.O(n)
  • B.O(n log n)
  • C.O(log n)
  • D.O(n2)

13. 一个自然数在十进制下有n位,则它在二进制下的位数与( )最接近。

  • A.5n
  • B.n*log210
  • C.10*log2n
  • D.10nlog2n

14. 在下列HTML语句中,可以正确产生一个指向NOI官方网站的超链接的是( )。

  • A.<a url=”http://www.noi.cn”>欢迎访问NOI网站</a>
  • B.<a href=”http://www.noi.cn”>欢迎访问NOI网站</a>
  • C.<a> http://www.noi.cn </a>
  • D.<a name=”http://www.noi.cn”>欢迎访问NOI网站</a>

15. 元素R1、R2、R3、R4、R5入栈的顺序为R1、R2、R3、R4、R5。如果第1个出栈的是R3,那么第5个出栈的不可能是( )。

  • A.R1
  • B.R2
  • C.R4
  • D.R5

16. 双向链表中有两个指针域llink的rlink,分别指向该结点的前驱及后继。设p指向链表中的一个结点,它的左右结点均非空。现要求删除结点P,则下面语句序列中错误的是( )。

  • A.p^.rlink^.llink=p^.rlink; p^.llink^.rlink=p^.llink;dispose(p);
  • B.p^.llink^.rlink=p^.rlink; p^.rlink^.llink=p^.llink;dispose(p);
  • C.p^.rlink^.llink=p^.llink; p^.rlink^.llink^.rlink=p^.rlink;dispose(p);
  • D.p^.llink^.rlink=p^.rlink; p^.llink^.rlink^.llink=p^.lli

17. 一棵二叉树的前序遍历序列是ABCDEFG,后序遍历序列是CBFEGDA,则根结点的左子树的结点个数可能是( )。

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

18. 关于拓扑排序,下面说法正确的是( )。

  • A.所有连通的有向图都可以实现拓扑排序。
  • B.对同一个图而言,拓扑排序的结果是唯一的。
  • C.拓扑排序中入度为0的结点总会排在入度大于0的结点的前面。
  • D.拓扑排序结果序列中的第一个结点一定是入度为0的点。

19. 完全二叉树的顺序存储方案,是指将完全二叉树的结点从上至下、从左至右依次存放到一个顺序结构的数组中,假定根结点存放在数组的1号位置,则第K号结点的父结点如果存在的话,应当存放在数组的( )号位置。

  • A.2k
  • B.2k+1
  • C.k/2下取整
  • D.(k+1)/2下取整

20. 全国青少年信息学奥林匹克系列活动的主办单位是( )。

  • A.教育部
  • B.科技部
  • C.共青团中央
  • D.中国计算机学会

二. 问题求解(共2题,每空5分,共10分)

1. LZW编码是一种自适应词典编码。在编码的过程中,开始时只有一部基础构造元素的编码词典,如果在编码的过程中遇到一个新的词条,则该词条及一个新的编码会被追加到词典中,并用于后继信息的编码。 举例说明,考虑一个待编码的信息串:“xyx yy yy xyx”。初始词典只有3个条目,第一个为x,编码为1:第二个为y,编码为2:第三个为空格,编码为3:于是串“xyx”的编码为1-2-1(其中-为编码分隔符),加上后面的一个空格就是1-2-1-3。但由于有了一个空格,我们就知道前面的“xyx”是一个单词,而由于该单词没有在词典中,我们就可以自适应的把这个词条添加到词典里,编码为4,然后按照新的词典对后继信息进行编码,以此类推。于是,最后得到编码:1-2-1-3-2-2-3-5-3-4。 现在已知初始词典的3个条目如上述,则信息串“yyxy xx yyxy xyx xx xyx”的编码是:
答案:22123113431213536

2. 队列快照是指在某一时刻队列中的元素组成的有序序列。例如,当元素1、2、3入队,元素1出队后,此刻的队列快照是“2 3” 。当元素2、3也出队后,队列快照是“”,即为空。现有3个正整数元素依次入队、出队。已知它们的和为8,则共有 种可能的不同的队列快照(不同的队列的相同快照只计一次)。例如,“5 1”、“4 2 2”、“”都是可能的队列快照;而“7”不是可能的队列快照,因为剩下的2个正整数的和不可能是1。
答案:49

三.阅读程序写结果(共4题,每题8分,其中第4题(1)(2)各4分,共计32分)

1.

Var
al,a2,a3,x:integer;
procedure  swap (var  a,b:integer);
Var
t:integer;
begin
var
t:integer;
begin  
t:=a;
a:=b;
b:=t;
end;
begin
readln(al,a2,a3);
if al >a2 then
swap(a 1,a2);
if a2>a3  then
swap (a2,a3);
if  al>a2  then
swap(a1,a2);
   readlnl(x);
      if  x<a2 then
            if x<al then
              writeln(x, ‘ ‘,a1,’ ‘,a2,’ ‘,a3)
            e1se
              writeln(a1, ’ ‘,x,’ ‘,a2,’ ‘,a3)
      else
            if x<a3 then
              writeln(al,’ ‘,a2,’ ‘,x,’ ‘,a3)
            else
    			writeln(al,’ ‘, a2, ‘ ‘, a3, ‘ ‘.x);
end.

输入:
91  2  20
77
输出:2 20 77 91

2.

Var
n,m,i:integer;
function rsum(j:integer):integer;
var
sum:integer;
begin
sum:=0;
while j <> 0 do
begin
sum:=sum * 10 +(j mod 10);
j:=j div 10;
end;
rsum:=sum;  
end;
begin
    readln(n,m);
for  i:=n to m do
if i=rsum(i)
then write(I, ‘ ‘);
end.

输入:90  120
输出:99 101 111

3.

Var
S:string;
i:integer;
m1,m2:char;
begin
   readln(s);
n1:= ‘ ‘;
m2:=’ ‘;
for i:=1 to length(s) do
if  s[i] > m1 then
   begin
m2:=m1;
m1:=s[i];
end
else if s[i] > m2 then
  m2:=s[i];
writeln(ord(m1), ‘ ‘, ord(m2));
end.

输入:Expo 2010 Shanchai China
输出:120 112

4.

const 
 NUM=5;
Var
n:integer;
function r(n:integer}:intecer;
Var
    i:integer;
begin
      if n< = NUM  then
    begin
        r:=n;
        exit;
     end;
      for  i:=1 to NUM d0
          if r(n-i) < 0  then
          begin
              r:=i;
             exit;
          end;
         begin
           readln(n);
writeln(r(n));
end. 
   (1)
输入: 7
输入: 16
输出:1|4

四.完善程序(前4空,每空2.5分,后6空,每空3分,共28分)

1. (哥德巴赫猜想)哥德巴赫猜想是指,任一大于2的偶数都可写成两个质数之和。迄今为止,这仍然是一个著名的世界难题,被誉为数学王冠上的明珠。试编写程序。验证任一大于2且不超过n的偶数都能写成两个质数之和。

const 
  size=1000; 
var 
  n,r,i,j,k,ans:integer;
  p:array [1..size] of integer;
  tmp:boolean; 
begin 
  readln(n);
  r:=1; 
  p[1]:=2; 
  for i:=3 to n do 
  begin 
            tmp:=true          ; 
    for j:=1 to r do 
       if I mod        p[j]       =0  then 
         begin 
            tmp:=false; 
            break; 
         end; 
    if tmp then 
       begin 
          inc(r);                p[r]:=i     ; 
       end; 
   end; 
   ans:=0; 
   for i:=2 to (n div 2) do 
     begin 
       tmp:=false; 
       for j:=1 to r do 
          if  i+i=   p[j]+p[k]    then 
          begin 
            tmp:=true; 
            break; 
          end; 
     if tmp then 
        inc(ans); 
  end; 
  writeln(ans); 
end.

若输入n为2020,则输出   1004    时表示验证成功,即大于2且不超过2010的偶数都满足哥德巴赫猜想。

2. (过河问题)在一个月黑风高的夜晚,有一群人在河的右岸,想通过唯一的一根独木桥走
到河的左岸。在这伸手不见五指的黑夜里,过桥时必须借助灯光来照明,不幸的是,他们只有一盏灯。另外,独木桥上最多承受两个人同时经过,否则将会坍塌。每个人单独过桥都需要一定的时间,不同的人需要的时间可能不同。两个人一起过桥时,由于只有一盏灯,所以需要的时间是较慢的那个人单独过桥时所花的时间。现输入n(2<=n<100)和这n个人单独过桥时需要的时间,请计算总共最少需要多少时间,他们才能全部到达河的左岸。
例如,有3个人甲、乙、丙,他们单独过桥的时间分别为1、2、4则总共最少需要的时间为7。具体方法是:甲、乙一起过桥到河的左岸,甲单独回到河的右岸将灯带回,然后甲、丙再一起过桥到河的左岸,总时间为2+1+4=7。

const
  size=100;
  infinity=10000;
  left=true;
  right=false;
  left_to_right=true;  
  right_to_left=false;
var
  n,i:integer;
  time:array [1..size] of integer;
  pos:array [1..size] of boolean;
function max(a,b:integer):integer;
begin
  if a>b then
max:=a
  else
max:=b;
end;
function go(stage:boolean):integer;
var
  I,j,num,tmp,ans:integer;
begin
  if (stage=right_to_lefft) then
begin
   num:=0;
   ans:=0;
   for i:=1 to n do
     if pos[i]=right then  
       begin
         inc(num);
         if time[i]>ans then
           ans:=time[i];
       end;
    if      num<=2        then
       begin
          go:=ans;
          exit;
       end;
    ans:=infinity;
    for i:=1 to n-1 do
       if pos[i]=right then
          for j:=i+1 to n do
            if pos[j]=right then
               begin
                    pos[i]:=left;
                    pos[j]:=left;
                    tmp:=max(time[i],time[j])+       go(LEFT_TO_RIGHT)       ;
                    if tmp<ans then
                        ans:=tmp;
                    pos[i]:=right;  
                    pos[j]:=right;
               end;
      go:=ans;
  else
     if (stage=left_to_right) then
       begin
         ans:=infinity;
         for i:=1 to n do
           if       pos[i]=LEFT           then
              begin
                pos[i]:=right;
                tmp:=         time[i]+go(RIGHT_TO_LEFT)          ;
                if tmp<ans then
                  ans:=tmp;
                           pos[i]:= LEFT              ;
               end;
         go:=ans;
end
else
  go:=0;
  end;
begin  
  readln(n);
  for i:=1 to n do
begin
   read(time[i]);
   pos[i]:=right;
end;
  writeln(go(right_to_left));
end.