試卷作業(yè)數據結構（信息）-2019秋數據結構B期末考試 A卷參考答案

西南交通大學2019-2020學年第1學期期末考試A

課程代碼3271035課程名稱數據結構B考試時間120分鐘

參考答案

一、單項選擇題（每小題2分，共30分）

1~5CBDBA6~10CBDAC11-15ABCAC

二、判斷題（正確的劃“，錯誤的劃“X”，每小題1分，共11分）

1~5VXVVX6~10XXVVX11V

三、填空題（每空1分，共18分）

1112B[16]3歸并

4開放定址法5鏈地址法6AECBDF

76y/3x2+*+8實現棧的復制

9二叉樹后序遍歷遞歸算法10q->prior=p;

11d12013是否有環(huán)路

14n-115ala516索引表

175,3,8,12,77,65,16,97,27,7018確定性

四、算法填空（每空2分，共10分）

(1)pa=pa->data(2)pa

(3)0(4)hl>hr

(5)hl+1

五、綜合題（共31分）

1、關鍵碼序列（503,087,512,061,908,170,897,275,653,426）,執(zhí)行希爾排序,

增量數組dlta[]={5,3,2,1）,請寫出每一趟排序結束時的關鍵碼狀態(tài)。（4分）

解：

170087275061426503897512653908（1分）

061087275170426503897512653908（1分）

061087275170426503653512897908（1分）

061087170275426503653512897908（1分）

2、使用克魯斯卡爾算法構造如圖1所示的一棵最小生成樹，并寫出構造過程。（6分）

圖1

解：每個圖1分

44

?

（a）

（d）

⑴

3、對關鍵字序列（72,87,61,23,94,16,05,58）進行堆排序，使之按關鍵字遞減

次序排列（小頂堆），請寫出排序過程中得到的初始堆和前三趟的序列狀態(tài)。（5分）

解：初始堆圖2分，后面每一趟的圖各1分

初始堆第I的

4、請將如圖所示的森林轉換成二叉樹。（要求寫出轉換過程）（5分）

5、對如圖3所示的有向圖，試圖利用Dijkstra算法求源點1到其他各頂點的最短路徑,

要求給出相應的求解步驟。（6分）

圖3

6

(1分)

6

6

25(1分)

6

（1分）

6

（1分）

（1分）

或按以下方式做：（表結構正確1分，i=l至IJi=5每列1分）

終點從1到各終點的D值和最短路徑的求解過程

i=li=2i=3i=4i=5

220(1,2)19(1,3,2)

315(1,3)

400000029(1,3,6,4)

5000029(1,3,2,5)29(1,3,2,5)29(1,3,2,5)

60025(1,3,6)25(1,3,6)

Vj32645

S{1,3}{1,3,2)(1,3,2,6)(1,3,2,6,4)(1,3,2,6,4,5)

6、設電文由6個字符A,B,C,D,E,F組成，它們在電文中出現的次數分別為：10,

4,8,3,2,7,畫出對應的哈夫曼樹，并寫出每個字符的編碼。（5