北京交通大學(xué)1993年數(shù)據(jù)結(jié)構(gòu)考研試題

來源：時(shí)間：2007-06-06 13:36:15

1993年碩士學(xué)位研究生入學(xué)考試試題
一．有向圖G=(V,E),其中={V1,V2,V3,V4}; E={<V3,V1>,<V3,V2>,<V4,V3>,<V4,V2>,<V1,V4>}試畫出G的三種存貯結(jié)構(gòu)圖
二．設(shè)G=(V,E)是一個(gè)帶有權(quán)的連通圖,則
1．請(qǐng)回答什么是G的最小生成樹；
2．設(shè)G為
請(qǐng)找出的所有最小生成樹。
三.試證明折半查找算法的比較次數(shù)C≤∟log2x」+1.其中N 為有序表的元素個(gè)數(shù)
四.假設(shè)以數(shù)組sq[0..7]存放循環(huán)隊(duì)列元素,變量F指向?qū)︻^元素的前一位置,變量指向?qū)ξ苍�，如用和分別表示入隊(duì)和出隊(duì)操作，請(qǐng)給出
1. 隊(duì)空的初始條件;
2. 執(zhí)行操作序列A3D1A5D2A1D2A4時(shí)的狀態(tài),并作必要的說明.
五.試構(gòu)造一棵二叉樹,包含權(quán)為1,4,9,16,25,36,49,64,81,100等10個(gè)終端結(jié)點(diǎn),且具有最小的加權(quán)路徑長度WPL.
六.廣義表的接點(diǎn)結(jié)構(gòu)如下:
其中LINK為指向表中下一元素的指針;TAG為標(biāo)志域,具體含義如下:
0 表示該結(jié)點(diǎn)為原子結(jié)點(diǎn).DATA為其數(shù)據(jù)
1 表示該結(jié)點(diǎn)為一個(gè)字表，DATA為指向該子表的指針
1.說明下列算法A的功能(注:P,T,M,N,R,Q為指針;算法中的NIL對(duì)應(yīng)圖中的^)
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. 對(duì)于P所指的廣義表,畫出執(zhí)行算法A后的表結(jié)構(gòu)以及P為:

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

結(jié)束

特別聲明：①凡本網(wǎng)注明稿件來源為"原創(chuàng)"的，轉(zhuǎn)載必須注明"稿件來源：育路網(wǎng)"，違者將依法追究責(zé)任；

②部分稿件來源于網(wǎng)絡(luò)，如有侵權(quán)，請(qǐng)聯(lián)系我們溝通解決。