厦门大学1999年硕士研究生入学考试计算机专业

厦门大学1999年硕士研究生入学考试计算机专业 一 填空 1 hash（杂凑）技术广泛应用于查周过程，选择hash函数的主要标准是---------------------和------------------。 2 在 AOV网 中，存在环意味着-----------------------------。这是------------的。对程序的数据流

厦门大学1999年硕士研究生入学考试计算机专业

一          填空
 1    hash（杂凑）技术广泛应用于查周过程，选择hash函数的主要标准是---------------------和------------------。
2        在 AOV网 中，存在环意味着-----------------------------。这是------------的。对程序的数据流图来说，它表明存在-----------------。
3         遍历图的过程实质上是-----------------------。breath-first   search遍历图的时间复杂度---------------depth-first  search遍历图的时间复杂度，两者不同之处在于-------------------------，反映在数据结构上的差别是--------------------。
4           prim（普里姆）算法适用于求-------------的网的最小生成树；kruskal（克鲁斯卡尔）算法适用于求-----------------的网的最小生成树。
二           作图
1  用 普里姆算法和克鲁斯卡尔算法分别构造下面网络的最小生成树。

2  画出左图二叉树的后序线索二叉树表示法。

三  算法题：
1       设指针p指着双向链表中的结点k，指针f指着将要插入的新结点x，x要插在结点k之后，写出有关指针需要修改的步骤。
2     用分块查找法，有2000项的表分成多少块最理想？每块的理想长度是多少？若每块长度为25 ，平均查找长度是多少？
3    设用于通讯的电文仅由8个字母组成，他们在电文中出现的频率分别为0.30，0.07，0.10，0.03，0.20，0.02，试设计哈夫曼树及其编码。使用0---7的二进制表示形式是另一种编码方案。给出两种编码的对照表`带权路径长度值并比较两种方案的优缺点。
4      如果在1000000个记录中找出2 个最小的记录，你认为采用什么样的排序方法所需的关键字比较次数最少？共计多少次？
    程序设计部分
 四      写出下面程序的输出结果
 1    program    csdge01(output);
               var     a,b,c:   intger;
       fuction    tq( var  x,y:  intger ;  z:integer):  integer;
            begin           z:=x*3;    x:=z+1;   y:=x+z;   tq:=y-1
          end;
        begin   
             a:=1;      b:=1;   c:=1;
     writeln   (tq  ( a,b,c)):6,    a:6,   b:6,    c:6)
       end.
2            program    csdge02(output);
               var     p1,p2,p3:^   intger;
           begin   
                 new(p1);   p1^:=5;
                  new(p3);  p3^:=p1^*3;   new(p2);
                  p2^:=3;    p1^:=p2^+p3^;  p2:=p3;
                  p3^:=p1-p2^;  p2^:=  (p1^*4+p2^)   div   (p3^  mod   4);
                  writeln (p1^:6,  p2^:6,   p3^:6)
               end.
 3      program    csdge03(output);
               var     a,b,c:   intger;
           procedure   p1(var    x:integer);
             function   f2  (y:integer):  integer ;
            procedure   p3( var   z:integer );
               begin     z:z+2;      b:=3*z   
                       end;
                begin     p3(c);    f2 :=y+c    end;
                 begin      x:=f2(b)      end;
                 begin   
                           a:=2 ;   b:=1;   c:=3;    p1(a);
                  writeln (＇a=＇,  a:4  ,       ＇     b=＇ , b:4,     ＇   c=＇,   c:4)
                     end..
4    program     csdege04(output);
       const      n=2   ;
       var     s:array[1..n]   of   char ;
     procedure       al(k:  integer);
        var     ch:char  ;   i: integer ;
      begin   
           for    ch:=＇a＇    to   ＇c＇    do 
         begin     s[k]:=ch;
             if     k=n      then
                 begin  
                   for     i:=1    to     k    do 
                 write(s[i]:1);   write (＇  ＇)
                end
               else     al(k+1)    end
                end;
            begin    al (1)  ;    writeln     end.
五             填空
  1              [程序说明]    如下程序读入字符序列，直至读入全部26个大写英文字母时停止，输出下列内容：
   （1）   读入字符总数；
    （2） 各大写字母首次输入时读入字符顺序号（从1开始计数）；
   （3）  首次读入的5个大写字母出现字数；
   program              csdge05(input,output );
         var      c: char ;     n,m:integer ;
            s,sl:-----------------------------;
            p,g:array[＇a＇..＇z＇]  of   integer ;
        begin  
            s:=-----------------;     sl:=[]    ;    n:=0;------------------------;
         for      c:=＇a＇       to      ＇z＇       do   
               begin    g[c] :=0 ;
                p[c] :=0; end;
          repea t     read(c) ;----------------;
              if     -------------  then 
               begin    
                   s:=s-[c];      p[c] :=n;
                     if   m<5   then  
                       begin    -----------;  m:=m+1   end
                           end;
                  if     --------------------          then    g[c]+1
              unti l      ----------------;       writeln;
                     writeln (n,＇character      counted＇);
                  for    c:=＇a＇     to   ＇z＇    do 
                     begin        write (c,  p[c]:8);
                             if     g[c] <>0     t hen      write  (g[c]:8);   writeln 
                        end
              end.
2[程序说明]    如下程序实现带插入的树检索：   给定一系列整数，输出每个整数出现的次数。为此，从空树开始，在树中检索每一个整数，如果找到，其出现次数加1 ，否则就作为一个新结点插入。
          program              csdge06(input,output );
      type     ref=^word;
               word =record
                   key :integer;
                   count:integer;
                  left  ,right: ref
               end;
        var       root: ref;     k  :integer;
    procedure       printtree(w:ref;  l:integer);
            var    i :integer;
         begin    if  w<>nil     then  
    ---------------------
            begin   printtree(left,l+1);
                 for    i:=1   to    l     do    write(＇  ＇);
                writeln (key);             ----------------------                end
       end;
              procedure        search(x:integer;   var   p:ref);
                  begin   
                      if     p=nil   then   
                       begin   -------------;
                              with     p^    do
                                 begin   key:=x;          count:=1;
                                  left =nil  ;   right= nil           end             end  
                            else     
                              if  x< p^.key    then     search(x,p^.left)   else   ----------------
                                  then             search (x,p^.right)               else -----------------
                          end
                    begin   
                                   ----------------------
                                     while   not   eof  (input )   do 
                                  begin    read(k)   ;        search(k,root)        end;
                  printtree(root,0)
                      end.
六            在5 *5格的棋盘上（如下图所示），找出一种方案。使得从1点出发，按日字跳马，可以不重复地跳经所有方格。要求用递归方法求解。  
  （1）  详细描述你的算法；  （2）   编写完整的pascal程序.