一. 選擇題(每題選擇一個答案, 將序號填入下劃線處,每題2分,共10分)
1. 假定初始序列是遞增的,并且按遞增序排列,則(  )排序方法花時間最少.
     A.快速    B. shell    C.直接插入     D.冒泡
2. 二維數(shù)組 a[0..8, 1..10]按行存放時元素 a[ 8,5 ]的起始地址與按列存放時元素(  )的起始地址相同.
     A. a [8,5]    B. a [3,10]      C. A[5,8]     D. A[0,9]
3. 有一棵平衡二叉樹,根結(jié)點為A,A的右孩子為B,B的左孩為葉結(jié)點C,當A,B二結(jié)點的平衡因子分別為(   )時,在結(jié)點C下, 插入一個新結(jié)點后得到的新樹是不平衡的.
     A. 0,0       B. 1,0         C. –1,0        D. 0,1
4.在循環(huán)鏈表中設(shè)立一個頭結(jié)點的理由是(    ).
     A.便于找到鏈表的首結(jié)點         B.可以用頭結(jié)點記錄鏈表長度
     C.可以使得作插入,刪去時不必顧及插入的或刪去的結(jié)點是否鏈表的首結(jié)點.
     D.可以把首結(jié)點與尾結(jié)點公開
5.非空的廣義表可與有根有序的有向圖對應(yīng),如果一個有根的有向圖中含有回路,那么它對應(yīng)的廣義表是(   )
     A.線性表      B.純表    C.再入表     D.遞歸表
二.填空題(每題2分,共10分)
1. 有20個元素的有序表按二分法查找,假定查找每個元素的概率是相等的,則查找成功的平均比較次數(shù)為________次.
2. 鏈接棧的結(jié)點有二個域: info, link ,棧頂指針為st, 下列程序段可以把元素x壓入棧內(nèi):
     new(p); p?.inf=x; ______;
3. 一個好的散列函數(shù)的標準是________________.
4. 一個循環(huán)隊列用數(shù)組Q[0..100]存貯其元素, 已知隊頭,隊尾指針分別為80與50, 則當前隊列中有_______個元素.
5. 用200個不同的數(shù)來構(gòu)造二叉排序樹, 其高度不會超過_______,但也不會少于_______(假定空二叉樹的高度為0).
三.算法應(yīng)用題(每題6分, 共30分)
1. 對下圖表示的樹林, (1)寫出它的后根序序列.(2)畫出與它對應(yīng)的二叉樹.
           A        D         G
  
           B       E          H
        
          C       F          I
2. 對序列(26,36,41,38,44,15,68,12,6,51,25)散列存貯于數(shù)組A[0..14]中,散列函數(shù)為H(R)=Rmod13, 用線性探測法解決沖突,請畫出散列表的狀況.
3.設(shè)有關(guān)鍵碼序列: 51(1), 73, 47,95,49,51(2).試寫出快速排序(從小到大)與堆排序(從大到小)的最終結(jié)果.
4.畫出下圖的鄰接表(要求:出邊表中的結(jié)點按序號由小到大排列),然后使用該鄰接表手工執(zhí)行深度優(yōu)先算法(從結(jié)點6開始),請寫出你得到的遍歷序列.
                     1
               2        6
      3               5
             4
5.對下圖用用Prim算法從結(jié)點6開始構(gòu)造最小生成樹,(1)請用圖表示構(gòu)造的過程.(2)如果從其他結(jié)點開始,有沒有可能構(gòu)造出不相同的最小生成樹?
(圖略)
四.算法設(shè)計題(共50分)
1. 求帶權(quán)有向圖中每對結(jié)點之間的最短路徑的Floyd算法如下:
   (1)(Path數(shù)組置初態(tài))
       for I:= 1 to n do
         for j:= 1 to n do
          if adj[I,j]<? then path[I,j]:=(1)
                    else path[I,j]:=(2);
       (2)(求最短路徑)
          for k:= 1 to n do
            for I:= 1 to n do
              for j:= 1 to n do
               if adj[I,j]>adj[I,k]+adj[k,j] then
                  begin adj[I,j]:=(3);path[I,j]:=(4) end
請你解答如下問題(1)完成上述算法填空. (2)矩陣adj 的初值是什么?算法結(jié)束時,adj[I,j] 和path[I,j]的值表示什么意義?(14分)
2. 寫出按對放序線索化以t 為根指針的二叉樹的非遞歸算法.假定用負指針表示線索,并且對棧的基本運算均可調(diào)用(12分)
3. 寫一算法,重排實型數(shù)組R[1..n]中元素的順序,使得所有負數(shù)均排在非負數(shù)之前.(要求:不排序,附加空間0(1))(10分)
4. 有一個帶有頭結(jié)點的循環(huán)雙鏈表,表頭指針為head,結(jié)點有四個域,data ,flreg ,llink ,rlink ,其中flreg記錄結(jié)點數(shù)據(jù)的訪問次數(shù).假定鏈表的結(jié)點已按訪問次數(shù)不增序排列.(1)畫出此鏈表的結(jié)構(gòu)示意圖.(2)寫一算法查找鏈表中是否有值為x的結(jié)點,如有,則讓該結(jié)點的訪問次數(shù)加1 ,并且要使鏈表仍保持不增序,如沒有,則不作任何工作.(14分)