普及组初赛模拟试题3.doc

信息学竞赛普及组初赛模拟试题(三) 

一、选择一个正确答案代码（A/B/C/D），填入每题的括号内（每题1.5分，多选无分，共30分）
1、MAN英文缩写的含义是（ ）
A.局域网  B.城域网    C.广域网  D.增值网
2、小张用十六进制，八进制和十进制写了如下一个等式：64－13=33
式中三个数是各不相同进位制的数，试问64，13，33，分别为________。
A．八进制，十进制，十六进制     B．十进制，十六进制，八进制
C．八进制，十六进制，十进制     D．十进制，八进制，十六进制
3、表达式(4 MOD (－3))与(－4 MOD 3)的值为：_______。
A．－1，－1      B．1，－1      C．－1，1        D．1，1
4、试指出：下列if语句中，当x=80时, 运行的结果为______。
begin
y:=0;
readln(x);
if x<0  then y:=5
else
    if x<10  then begin
            y:=10;
            if x<100  then y:=100;
            end
    else y:=200;
write('y=',y);
end.
A．y=9          B．y=200        C．y=10       D．y=100       
5、设栈S的初始状态为空，现有5个元素组成的序列{1，2，3，4，5}，对该序列在S栈上依次进行如下操作(从序列中的1开始，出栈后不再进栈)：进栈，进栈，进栈，出栈，进栈，出栈，进栈，试问出栈的元素序列是________。
A．{5，4，3，2，1}    B．{2，1}    C．{2，3}     D．{3，4} 
6、ASCII码是（     ）。
A．国标码    B．二进制编码  C．十进制编码  D．美国标准信息交换码
7、一台计算机的字长是4个字节，这意味着（     ）。
A．能处理的数值最大为4位十进制数9999
B．能处理的字符串最多由4个英文字母组成
C．在CPU中能够同时处理32位二进制数据
D．在CPU中运算的最大结果为2的32次方
8、假设一台计算机的地址总线为16，那么中央处理器CPU能访问的最大存储器容量为(    
A． 2 * 16 KB　B．16KB 　C．216B　 D．16*1024*8 B
9、计算机最终处理的信息形式是（   ）
A．ASCII码     B．BCD码     C．二进制     D．十六进制
10、与十六进制数6F等值的八进制数是（    ）
A．166    B．139     C．157     D．183
11、以下属非法用户自定义标识符的是()。
A．date 　　B．dir 　　C．list 　　D．type 
12、设X和Y是同一种枚举类型变量，则下列语句中合法的是()。
A．X:=ORD(Y)　　B．X:=Y 　　C．READ(X,Y)　　D．WRITE(T,Y)
13、计算机能够直接识别和处理的程序是_______程序
A．汇编语言 　 B．源程序 　 C.机器语言 　 D.高级语言　
14、设有说明
    VAR A：ARRAY['A'．．'E'，1．．4，BOOLEAN] OF REA1；
    则A['A'，3]是(     。
A．一个实型的数组元素
B．一个数组，该数组具有两个实型数组元素
C．一个数组，该数组具有4*2个实型数组元素
D．一个数组，该数组具有5*4*2个实型数组元素
15、下列属于线性时间的排序算法是： （    ）
A. 快速排序　　　B. 桶排序　　　C. 冒泡排序     
16、一棵包含n个节点的树有几条边： 
A. n　　　B. n-1　　　C. 不一定    
17、在Pascal语言中，表达式35 div 3 mod 4 的值是 ________。
A．０　　B．２　　C．３　　　D．６ 
18、在数据结构中，"树"结构下层结点出现三个以上的结点，这种结构称为________。
A．三层树 　 B．三叉树　 C．多层树 　 D．多叉树
19、在Pascal语言中，下列程序段所计算的公式是________。
程序段： S：=0 ；T：=1；
For I：=1 to 10 do
Begin
T：=T*I；
S：=S+T；
end;
A.S=1+2+3+4+……+10
B.S=1*2*3*4*……*10
C.S=1！+2！+3！+4！+……+10！
D.S=1+2*3+3*4+4*5+……+10*11
20、以下说法正确的是（     ）。 
A． CPU与内存不交换信息       B．  CPU与内存直接交换信息
C． CPU与内存间接不交换信息   D．  CPU与内存部分交换信息
二、阅读下列程序，写出程序运行结果（第1题5分，第2，3，4题各6分，共23分）
program exp1;
const n=5;
var I,j,k:integer;
    r:array[0..10] of integer;
begin
for I:=1 to n do
  read(r[I]);
for I:=2 to n do
begin
    k:=r[I];j:=I-1;
    while (k>r[j]) and (j>0) do
      begin r[j+1]:=r[j];j:=j-1;end;
    r[j+1]:=k;
  end;
for I:=1 to n do
  write(r[I],’’);
writeln
end.
键盘输入: 8 4 9 3 5
屏幕输出：
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
屏幕输出：

3、Program exp3(input,output); 
VAR I,J,S:INTEGER;
    B :ARRAY[0..5] OF INTEGER;
BEGIN
     S:=1;
     FOR I:=1 TO 5 DO   B[I]:=I;
     J:=1;
     WHILE J>0 DO
     BEGIN
          J:=5;
          WHILE (J>0) AND (B[J]=10+J-5) DO J:=J-1;
          IF J>0 THEN
             BEGIN
                  S:=S+1;  B[J]:=B[J]+1;
                  FOR i:=J+1 TO 5 DO  B[i]:=B[J]+i-J
             END;
     END;
     WRITELN('S=',S);
END.

4、program exp4(input,output);
var m,n,g:integer;

function gcd(m,n:integer):integer;
begin
 if n=0 then gcd:=m
  else gcd:=gcd(n,m mod n)
end;

begin
 read(m,n);
 g:=gcd(m,n);
 writeln('m=',m,'n=',n,'gcd=',g)
end.
输入：48  9
输出：

三、问题解答（第1题每空4分，第2题8分）
1、数据结构中，下面是一个树结构图，这个树的"先序遍历"结果是________，中序遍历结果是：________________。

24  8  +3  *4  10  7  -*/@
2、给出一个后缀算术表达式为

写出对应的中缀算术表达式：___________________________________________
四、完善程序（第一题每空3分，第二题每空2分，第三题每空4分，共32分 ）
1、连续整数平台问题
已知一个含有多个整数的数组，其中相同的元素集中在一起形成一个平台。以下程序用于对输入的数组求出其中最大平台长度。例如，中元素个数为20，它们依次为
2  2  2  2  3  3  3  3  3  1  1  1  1  1  1  1  1  1  4  4
则它的最大平台长度为9。
const maxlength=100;
var
  a:array[1..maxlength] of integer;
  i,maxi,n,s,t:integer;
begin
  write('n=');readln(n);
  for i:=1 to n do read(a[i]);
  readln;
  maxi:=0;
  t:=   [1]  
  s:=1;
  for i:=2 to n do
    if a[i]=t then   [2]  
      else
        begin
          if s>maxi then maxi:=s;
          t:=a[i];
            [3]  
        end;
    [4]  
  writeln('maxi=',maxi);
end.

2、1000！尾0问题
以下程序用于统计1000！末尾有多少个0。其中1000！=1&acute;2&acute;3&acute;…&acute;1000。实际上我们只要统计1000！有多少个因子10。由于10=5&acute;2，因而只需统计有多少个因子5和2。显然在1～1000的所有数中，5的因子个数比2的因子个数少。因此，只要统计1～1000的所有数中共有多少个因子5就行了。
var  i,j,n:integer;
begin
  n:=0;
  for i:=1 to 200 do
    begin
      j:=i*5;
      while   [5]   =0 do
        begin
          n:=n+1;
          j:=   [6]   
        end;
    end;
  writeln(n:4);
end.
3、[问题描述]找数问题: 以下程序用在n个不同元素中找出第k个最小元素。程序中用分治策略来设计算法。把这n个元素放在一个数组中,然后取出第k个元素为标准m,把n个元素重新排列:小于标准m的元素放在数组前面,大于该标准的放在数组的后面。把该元素m放在两者之间。设小于标准的元素个数为j-1,如果j=k,则A(k)即为所求元素。如果j>k,则第k个元素必在区间[1,j],因此取A[1],…,A[j]为新的元素集合,然后重复上述的”部分排序”的过程。如果j<k,则第k个元素必在区间[j+1,n],因此取A[j],…,A[n]为新的元素集合,重复过程。直至j=k为止。
[程序清单]
var j,k,n:integer;
   a:array[1..100] of integer;
procedure search(b,e:integer);
var I,m,t:integer;
begin
  if b=e then begin j:=b;exit end;
  I:=b;j:=e;m:=  [7]  ;
  Repeat
While a[I]<m do inc(i);
While m<a[j] do   [8]  ;
If I<j then
  Begin t:=a[I];a[I]:=a[j];a[j]:=t end;
Until I>=j;
If I=k then exit;
If   [9]   then search(b,j) else search(j+1,e)
End;
procedure   [10]  
  var I:integer;
  begin
for I:=1 to n do write(a[I],’’);
writeln;
writeln(‘a[‘,k,’]=’,a[k]);
end;
begin
write(‘n=’);readln(n);
write(‘a[1..’,n,’]=’);
for k:=1 to n do read(a[k]);
readln;
write(‘k=’);readln(k);
search(  [11]   ;
pr(n);
readln
end.