大連理工大學數據結構試題及答案

1、數據結構期末試卷一、選擇題組成數據的基本單位是（ 。數據項(B) 數據類型(C) 數據元素(D) 數據變量2設數據結構A=(D，R)，其中D=1，2，3，4，R=r，r=，則數據結構A 是（。線性結構集合數組的邏輯結構不同于下列（ ）的邏輯結構。線性表棧隊列樹二叉樹中第上的結點數最多有（ ）個。2i2i2i-12i-1設指針變量p 指向單鏈表結點A，則刪除結點A 的后繼結點B 需要的操作為（ 。p-next=p-next-next(B) p=p-next(C) p=p-next-next(D) p-next=pS Q 的初始狀態(tài)為空，元素E1E2、E3、E4E5 E6 S，一個元素出棧后即進入

2、隊列Q6 個元素出列的順序為E2E4E3、E6、E5 E1，則棧S 的容量至少應該是（ 。643210 階對稱矩陣壓縮存儲到一維數組A 中，則數組A 的長度最少為（ 。(A) 100405580設結點A 3 個兄弟結點且結點B 為結點A 的雙親結點，則結點B 的度數數為（ 。3451根據二叉樹的定義可知二叉樹共有（）種不同的形態(tài)。4567設有以下四種排序方法，則（）的空間復雜度最大。冒泡排序堆排序希爾排序二、填空題設順序循環(huán)隊列的隊頭指針和隊尾指針分別為F 和其中隊頭指針F 指向當前隊頭元素的前一個位置，隊尾指針 R 指向當前隊尾元素所在的位置，則出隊列語句為F =。設線性表中有 n 個數據元

3、素，則在順序存儲結構上實現順序查找的平均時間復雜度為 ，在鏈式存儲結構上實現順序查找的平均時間復雜度。設一棵二叉樹中有 n 個結點，則當用二叉鏈表作為其存儲結構時，該二叉鏈表中共有 個指針域個空指針域。設指針變量p 指向單鏈表中結點指針變量s 指向被插入的結點則在結點A 的面插入結點B 的操作序列。設無向圖G 中有n 個頂點和e 條邊，則其對應的鄰接表中個表頭結點和 個表結點。設無向圖G中有n 個頂點e 條邊所有頂點的度數之和為則e 和m有 關系。設一棵二叉樹的前序遍歷序列和中序遍歷序列均為則該二叉樹的后序遍歷序為。設一棵完全二叉樹中有21 個結點，如果按照從上到下、從左到右的順序從1 開始順

4、編號，則編號為 8 的雙親結點的編號是，編號為 8 的左孩子結點的編號是 。9.下列程序段的功能實現子串t 在主串s 中位置的算法要求在下劃線處填上正確語句intindex(char s , char t )i=j=0;while(istrlen(s) & jnext=p-next; s-next=sn, 2em=2eCBA8.4，169.i-j+1，010.n-1三 判 斷題h1.X2 . 3 . X4 . 5 . X6 . X7. 8 . 0 9. 10. 四、應用題h 81h鏈式存儲結構略，前序ABDE，中序DBEA，后序DE2103哈夫曼樹略，WPL=78h 25 323.(18,5,16,19,2,2，3)h4 68564.線性探測：81025322768鏈地址法：6 275.