一、填空题（共20题，每题1.5分，共计30分。每题有5个备选答案，前10个题为单选题（即每题有且只有一个正确答案，选对得分），后10题为不定项选择题（即每题有1至5个正确答案，只有全部选对才得分）。
1.微型计算机的性能主要取决于（ ）。
A) 内存 
B) 主板 
C) 中央处理器 
D) 硬盘 
E) 显示器
2.能将高级语言程序转换为目标程序的是( ).
A)调试程序 B)解释程序C)编辑程序 D)编译程序E)连接程序
3．A=11001010B,B=00001111B,C=01011100B,则A∨B∧C=( )
A)01011110 B) 00001111
C)01011100 D) 11001110
E) 11001010
4.计算机设备，既是输入设备，又是输出设备的是( )。 
A)键盘 B)触摸屏 C)扫描仪 D)投影仪 E)数字化仪 
5.计算机病毒传染的必要条件是( ) 。
A) 在内存中运行病毒程序
B) 对磁盘进行读写操作
C) 在内存中运行含有病毒的可执行程序
D) 复制文件
E)删除文件
6．已知队列(13，2，11，34，4l，77，5，7，18，26，15)，第一个进入队列的元素是13，则第五个出队列的元素是( )。 
A)5 B)41 C)77 D)13 E)18 
7.在使用E-mail前，需要对Outlook进行设置，其中ISP发送电子邮件的服务器称为( )服务器。
A)POP3 B)SMTP C)DNS D)FTP E)HTTP
8.对给定的整数序列(54,73,21,35,67,78,63,24,89)进行从小到大的排序时,采用快速排序的第一趟扫描的结果是( ).
A)(24,21,35,54,67, 78,63,73,89) 
B)(24,35,21,54,67, 78,63,73,89)
C)(24,21,35,54,67, 63,73,78,89)
D)(21,24,35,54,63, 67,73,78,89)
E)(24,21,35,54,67, 63,73,78,89)
9. 编号为1到13的纸牌顺时针排成一圈，有人从编号为1的牌从数字1开始顺时针数下去，1，2，3，……,一圈又一圈,问当数到数字n 
,所在的纸牌编号为多少?
A) n mod 13 B)1+(n-1) mod 13 C)(n+1) mod 13-1 D)(n+1) mod 13
E) (n-1) mod 13 
10.对下图进行广度优先拓朴排序得到的顶点序列正确的是( ).

二.问题求解（5分*2=10分）
1.某年级学生共选修6门课程，期末考试前，必须提前将这6门课程考完，每人每天只在下午至多考一门课程，设6门课程分别为c1，c2，c3，c4，c5，c6，S(ci)为学习ci的学生集合。已知S(ci)∩S(c6)≠Ø，i=l，2，．．．，5，S(ci)∩S(ci+1)≠Ø，i=1，2，3，4，S(c5)∩S(c1)≠Ø ，问至少安排　　　　天才能考完这6门课程。
2．设有一棵k叉树，其中只有度为0和k两种结点，设n0，nk分别表示度为0和度为k的结点个数，试求出n0和nk之间的关系(n0=数学表达式，数学表达式仅含nk、k和数字)。

三.阅读程序写出正确的程序运行结果(4 *8分=32分)

1 program t1；
var  n，k，s：longint；
begin
 readln(n);
  k:=0；
  s:=1；
  while s <= n do
  begin
    k:=k+1;
    n:=n-s;
    s:=s+6*k
  end;
  writeln (k)
end.
输入:1000000 
输出:
2. program t2;
var x,y1,y2,y3:integer;
 begin
  readln(x);
  y1:=0;y2:=1;y3:=1;
  while y2<=x do
    begin
      y1:=y1+1;y3:=y3+2;y2:=y2+y3;
    end;
  writeln(y1);
end.
输人：x＝400
输出：
3. program  t3；
　 var m，n，i，j：integer；
　　　 p，w，a，b：array[0．．19] of integer；
　 begin
　　 read(n)； m：= 0；
　　 for i：= 0 to n-1 do
　　 begin read (p[i])； b[i] ：=1； end；
　　 for i ：= 0 to n-1 do
　　　 begin
　　　　 if (i>0) then
　　　　 a[m]：= p[i]-p[i-1]
　　　　 else 
　　　　 a[m]：= p[i]；
　　　　 m：= m+1：
　　　　 while ((m>1) and (a[rn-1]=0)) do
　　　　 begin m ；= m-1； b[m] ：= l； end；
　　　　 if (m>0) then
　　　　　 w[i]：=b[m-1]
　　　　 else
　　　　　 w[i]：=b[0]；
　　　　　 a[m-1] ：= a[m-1]-1；
　　　　　 for j ：= 0 to m-1 do b[j] ；= b[j]+1；
　　　　　 while ((m>1) and (a[m-1]=0)) do
　　　　　 begin
　　　　　　 m ：= m-1； b[m] ：=1；
　　　　　 end;
　　　　end;
　　　　for i ：= 0 to n-1 do
　　　　 begin
　　　　　 write(w[i])； write(' ');
　　　　 end；
　　　　writeln(' ')；
end． 
输入：4
　　4 6 6 6
输出：　　
4. program t4；
　 const
　　 u：array[1．．4] of integer = (0，5，3，1)；
　　 v：array[1．．4] 0f integer = (0，7，6，5)；
　 var a，b，c，d，e，f，x，y，z： integer； 
　 begin
　　 read (a，b，c，d，e，f)；
　　 z ：= f + e + d + (c+3) div 4； y ：= 5 * d + u [ c mod 4 ]；
　　 if (b>y) then
　　　　begin
　　　　　z ：= z+ (b-y+8) div 9；
　　　　　x ：= ((b-y+8) div 9 * 9- (b-y)) * 4+11*e+V[c mod 4]；
　　　　　end
　　　　else
　　　　　x ：= (y-b) *4+11*e+v[c mod 4]；
　　　　if (a>x) then
　　　　　z ：= z + (a-x+35) div 36；
　　 writeln(z)；
　 end．
输入: 4 7 9 20 56 47
输出: 

四.完善程序题(2分+3*4分+2分+4*3分=28分)
1．问题描述：工厂在每天的生产中，需要一定数量的零件，同时也可以知道每天生产
一个零件的生产单价。在N天的生产中，当天生产的零件可以满足当天的需要，若当天用不完，
可以放到下一天去使用，但要收取每个零件的保管费，不同的天收取的费用也不相同。
    问题求解：求得一个N天的生产计划(即N天中每天应生产零件个数)，使总的费用最少。
    输入：N(天数    N<=29)   
    每天的需求量    (N个整数)
    每天生产零件的单价(N个整数)
    每天保管零件的单价(N个整数)
    输出：每天的生产零件个数(N个整数)
  例如：当N=3时，其需要与费用如下：
       ┌────┬────┬────┬────┐
       │        │ 第一天 │ 第二天 │ 第三天 │
       ├────┼────┼────┼────┤
       │ 需要量 │   25   │   15   │   30   │
       ├────┼────┼────┼────┤
       │生产单价│   20   │   30   │   32   │
       ├────┼────┼────┼────┤
       │保管单价│    5   │   10   │    0   │
       └────┴────┴────┴────┘
生产计划的安排可以有许多方案，如下面的三种：
       ┌────┬────┬────┬───────────┐
       │ 第一天 │ 第二天 │ 第三天 │  总的费用            │
       ├────┼────┼────┼───────────┤
       │   25   │   15   │   30   │25*20+15*30+30*32=1910│
       ├────┼────┼────┼───────────┤
       │   40   │    0   │   30   │40*20+15*5+30*32=1835 │
       ├────┼────┼────┼───────────┤
       │   70   │    0   │    0   │70*20+45*5+30*10=1925 │
       └────┴────┴────┴───────────┘
程序说明：
  bln]：存放每天的需求量
  cln]：每天生产零件的单价
  d[n]：每天保管零件的单价
  e[n]：生产计划
程序：
program exp5;
var
i,j,n,yu,jO,j1,s  :integer;
b, c, d, e        : array[O..30] of integer;
begin
  readln(n);
  for i:=1 to n do readln(b[i] ,c[i] ,d[i]);
  for i:=1 to n do e[i]:=0;
____(1)____:=10000;    c[n+2]:=0;    b[n+1]:=0;    jO:=1;
while (jO<=n) do
   begin
     yu:=c[jO];    j1:=jO;    s:=b[jO];
     while ____(2)____  do
      begin
         ____(3)____    j1:=j1+1;s:=s+b[j1];
      end;
     ____(4)____  j0:=j1+1:
  end;
for i:=1 to n do write(e[I]:4);
readln;
end.
2. 问题描述]
将一个含有运算符为：(、)、+、-、*、/、^(乘幂运算)、~(求负运算)的中缀表达式，
如：((1+2)*5)^2-(3+5)/2转化为后缀表达式，如：12+5*2^35+2/-．

[解题思路]将中缀表达式转化为后缀表达式，首先规定运算符的优先数如下：
┌───┬───┬───┬─────┬──────┬───┬───┐
│运算符│    ( │    ) │    +，－ │    *  ，/  │   ~  │   ~  │
├───┼───┼───┼─────┼──────┼───┼───┤
│优先数│    0 │    1 │    2     │    3       │   4  │   5  │
└───┴───┴───┴─────┴──────┴───┴───┘
1．若输入是运算量，则将该运算量输出；

2．若是左括号“(”，则将该符号的优先数压入设置的运算符堆栈e[p]中去；

3．输入运算符优先数是2，3，4，5时，如果栈空，则将运算符的优先数进栈。如果栈不空，
则将它与栈顶元素进行比较，倘若优先数大于栈顶元素的优先数，则进栈；小于顶元的，则
顶元退栈并输出该运算符，然后再继续比较，直到大于顶元或栈空时进栈；

4．若是右括号“)”，同时栈顶元又为左括号“(”，则栈顶元退栈，并抹去右括号“)”．
否则转3处理；

5．输入完而栈非空，则将栈内内容逐一退栈并输出。所有输出的结果就为后缀表达式。

过程中用到的相关数据结构如下：
type arraydata = array[1..100] of string[20];
const fh:array[1..8] of string[1]
        =('(',')','+','-','*','/','~','^');
      b:array[1..8] of byte =(0,1,2,2,3,3,4,5);
var d: arraydata; {存储运算量及运算符号}
    i,j,m,k: byte;
[过程程序]
procedure hzbds(var d: arraydata; var m: byte );
  var: array [ 1.. 100 ] of byte;
     i,p,k ,bi:byte;
     bl: boolean;
  begin
    p:=O;k:=1;bj:=0;
    while k<=m do
    begin
      if  d[k]=’(‘ then
      begin
        p:=p+1;e[p]:=1
      end
      else begin
           for i:=2 to 8 do
           if ___(1)___ then
           begin
             b1:= true;
             repeat
               if ___(2)___ then
               begin
                 p:= p+1 ;e[p]:=i;bj:= 1 ;b1:= false
               end
               else if ____(3)___ then
                 if e[p] < >1 then
                 begin
                   p:=p+1;e[p]:=i;bj:=1;b1:=false
                 end
                 else if d[k] < >')' then
                   begin
                     p:=p+1;e[p]:=i;bj:=1;b1:=false
                   end
                   else begin
                      ___(4)___;bj:= 1 ;b1:= false;
                        end
                 else begin
                        write(fh[e[p]] ,' ') ;p:=p-1
                      end;
             until b1 = false;
           end
           if ___(5)___ then write(d[k] ,' ') else bj:=0;
           end;
       k:=k+1
    end
    b1:= true;
    repeat
      if p=0 then b1:= false
      else begin
         write(fh[e[p]],’’);p:=p-1;
           end
    until b1 = false;
    writeln;
  end;
  

20041初赛模拟题参考答案
一．选择题
   1-10:CDDBB BBBBC
11.ABC  12. AD 13.AB 14.AC 15.E 16.ABCDE        17.ABCD 18.ABCD 19.AE 20. BCDE
二．1．4
    2．（k-1）nk+1
三．1．100
 2．20
 3．1  1  2  4
 4．126
四．1．（1）c[n+1]
  （2）yu+d[j0] < c[j1+1]
  （3）yu:=yu+d[j1]
  （4）e[j0]:=s
 2．（1）d[k]=fh[I]
   （2）p=0
   （3）b[e[p]] < b[I]
   （4）p:=p-1
   （5）bj=0 或 bj <> 1