西北工業大學99考研題

一．（15分）請給出下列概念或術語的解釋。
1．廣義表
2．平衡因子
3．平均查找長度（ASL）
4．伙伴空間
5．AOE-網的關鍵路徑
二．（8分）簡述直接插入排序，簡單選擇排序，2-路歸并排序的基本思想以及在時間復雜度和排序穩定性上的差別。
三．（8分）一個循環隊列的數據結構描述如下：
TYPE seuueuetp=RECORD
         elem：ARRAY[1。。maxsize] OF elemtp；
        Front，rear：0。。maxize；
      END；
給出循環隊列的隊空和隊滿的判斷條件，并且分析一下該條件對隊列實際存儲空間大小的影響，如果為了不損失存儲空間，你如何改進循環隊列的隊空和隊滿的判斷條件？
四．（10分）試比較順序文件，索引非順序文件，索引順序文件，散列文件的存儲代價，檢索，插入，刪除記錄時的優點和缺點。
五．（10分）一個深度為L的滿K叉樹有以下性質：第L層的結點都是葉子結點，其余各層上么個結點都有K 棵非空子樹，如果按層次順序從1開始對全部結點進行編號，求：
1． 各層的結點的數目是多少？
2． 編號為n的結點的雙親結點（若存在）的編號是多少？
3． 編號為n的結點的第i 個孩子結點（若存在）的編號是多少？
4． 編號為n的結點有右兄弟的條件是什么？如果有，其右兄弟的編號是多少？
請給出計算和推導過程。
六．（14分）閱讀下列算法的類PASCAL描述，根據算法的要求，對相應的空格處寫出正確合理的語句。
1． 后序遍歷二叉樹的非遞歸算法，bt是二叉樹的根，S是一個棧，maxsize是棧的最大容量。
TYPE bitreptr=^bnodetp;
bitreptr=RECORD

     data:datatype;
     lchild,rchild:bitreptr
    END;
TYPE stacktyp=RECORD
    data:ARRAY[1…maxsize] OF bitreptr；
     top：0…maxsize；
END；
PROCEDURE posterorder（be：bitreptr）；
BEGIN 
   S．Top：=0；p：=bt；
   REPEAT
      WHILE p<>NIL DO 
         BEGIN
   S.top:=s.top+1;
   IF S.top>maxsize THEN stackfull
   ELSE BEGIN S.data[S.top]:=p
           (1)_____________________;
END
END;
IF S.data[top]^.rchild<>NIL THEN  (2)_________________
ELSE BEGIN
      REPEAT
         Write (S.data[top]^.data);
      UNTIL S.top=0 or S.data[top]^.rchild<>S.data[S.top+1];
      IF S.data[top]^.rchild<> S.data[S.top+1];
      THEN (3)_________________;
UNTIL(4)______________________;
END
2.算術表達式求值的流程，其中OPTR為算術符棧，OPND2為操作數棧，precede(oper 1，oper2)是比較運算符優先級別的函數，operate(opnd1,oper,opnd2)為兩操作數的運算結果。（#表示運算起始和終止符號）
   FUNCTION  exp_reduced:operandtype;
   INITSTACK(OPTR);PUsH(OPTR"#"INITSTACK(OPND);read(w)
   WHILE NOT((W='#") and (GETTOP(OPTR)='#'))DO
       IF w NOT in op then PUSH(OPND,w);
       ELSE CASE precede(GETTOP(OPTR),w)of
             '<':[(1)                    ;read(w0;);
             '=':[(2)                      ; read(w);];
             '>':[theta-POP(OPTR);b:=POP(OPND);a:=POP(OPND);(3)               ；]
   ENDC;
RETURN(GETTOP(OPND);
ENDF;
七、（10分）簡述無向圖和有向圖有哪幾種存儲結構，并說明各種結構在圖的不同操作（圖的遍歷，有向圖的拓撲排序等）中有什么樣的優越性？
八、（15分）遍歷一棵二叉樹的中序序列和后序序列分別為，中序BFDGAEHC，后序FGDBHCA，寫出這棵二叉樹的邏輯結構和存儲結構，已知一棵二叉樹的中序序列和后序序列分別由INO[1..n]和POST[1..n]數據存放，并且假定沒有數據域值相同的結點，證明可由此生成一棵唯一的二叉樹，并寫出生成的算法。
九、（10分）考慮邊界標志法的兩種策略（最佳適配和首次適配）：
1． 數據結構的主要區別是什么？
2． 分配算法的主要區別是什么？
3． 回收算法的主要區別是什么？
要求寫出相應的結構和核心算法。
十、（10分）考慮空間釋放遵從“最后分配者最先釋放”規則的動態存儲管理問題，并且設每個空間申請中都指定所申請的空閑塊大小。
1． 設計一個適當的數據結構實現動態存儲管理；
2． 寫一個為大小為n的空間申請分配存儲塊的算法；
3． 寫一個回收釋放塊的算法。