北京交通大學1993年數據結構考研試題

來源：時間：2007-06-06 13:36:15

1993年碩士學位研究生入學考試試題
一．有向圖G=(V,E),其中={V1,V2,V3,V4}; E={<V3,V1>,<V3,V2>,<V4,V3>,<V4,V2>,<V1,V4>}試畫出G的三種存貯結構圖
二．設G=(V,E)是一個帶有權的連通圖,則
1．請回答什么是G的最小生成樹；
2．設G為
請找出的所有最小生成樹。
三.試證明折半查找算法的比較次數C≤∟log2x」+1.其中N 為有序表的元素個數
四.假設以數組sq[0..7]存放循環隊列元素,變量F指向對頭元素的前一位置,變量指向對尾元素，如用和分別表示入隊和出隊操作，請給出
1. 隊空的初始條件;
2. 執行操作序列A3D1A5D2A1D2A4時的狀態,并作必要的說明.
五.試構造一棵二叉樹,包含權為1,4,9,16,25,36,49,64,81,100等10個終端結點,且具有最小的加權路徑長度WPL.
六.廣義表的接點結構如下:
其中LINK為指向表中下一元素的指針;TAG為標志域,具體含義如下:
0 表示該結點為原子結點.DATA為其數據
1 表示該結點為一個字表，DATA為指向該子表的指針
1.說明下列算法A的功能(注:P,T,M,N,R,Q為指針;算法中的NIL對應圖中的^)
PROCEDURE  A(P,T)
  BEGIN
       Q:=NIL;
     WHILE  P<>NIL DO
      BEGIN
       IF P^.TAG<> 0 THEN
          BEGIN
             M:=P^.DATA;
            A(M,N);
           P^.DATA:=N
          END;
  R:=P^.LINK;
  P^.LINK:=Q;
  Q:=P;
  P:=R
END;
T:=Q
END.
3. 對于P所指的廣義表,畫出執行算法A后的表結構以及P為:

七.已知二叉樹T,試寫出復制該二叉樹的算法(t→T)
1. 遞歸算法
2. 非遞歸算法

結束

特別聲明：①凡本網注明稿件來源為"原創"的，轉載必須注明"稿件來源：育路網"，違者將依法追究責任；

②部分稿件來源于網絡，如有侵權，請聯系我們溝通解決。