1、數(shù)據(jù)結(jié)構(gòu)期末試卷一、選擇題組成數(shù)據(jù)的基本單位是（ 。數(shù)據(jù)項(B) 數(shù)據(jù)類型(C) 數(shù)據(jù)元素(D) 數(shù)據(jù)變量2設(shè)數(shù)據(jù)結(jié)構(gòu)A=(D，R)，其中D=1，2，3，4，R=r，r=，則數(shù)據(jù)結(jié)構(gòu)A 是（。線性結(jié)構(gòu)集合數(shù)組的邏輯結(jié)構(gòu)不同于下列（ ）的邏輯結(jié)構(gòu)。線性表棧隊列樹二叉樹中第上的結(jié)點數(shù)最多有（ ）個。2i2i2i-12i-1設(shè)指針變量p 指向單鏈表結(jié)點A，則刪除結(jié)點A 的后繼結(jié)點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 的容量至少應(yīng)該是（ 。643210 階對稱矩陣壓縮存儲到一維數(shù)組A 中，則數(shù)組A 的長度最少為（ 。(A) 100405580設(shè)結(jié)點A 3 個兄弟結(jié)點且結(jié)點B 為結(jié)點A 的雙親結(jié)點，則結(jié)點B 的度數(shù)數(shù)為（ 。3451根據(jù)二叉樹的定義可知二叉樹共有（）種不同的形態(tài)。4567設(shè)有以下四種排序方法，則（）的空間復(fù)雜度最大。冒泡排序堆排序希爾排序二、填空題設(shè)順序循環(huán)隊列的隊頭指針和隊尾指針分別為F 和其中隊頭指針F 指向當(dāng)前隊頭元素的前一個位置，隊尾指針 R 指向當(dāng)前隊尾元素所在的位置，則出隊列語句為F =。設(shè)線性表中有 n 個數(shù)據(jù)元

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

4、編號，則編號為 8 的雙親結(jié)點的編號是，編號為 8 的左孩子結(jié)點的編號是 。9.下列程序段的功能實現(xiàn)子串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. 四、應(yīng)用題h 81h鏈式存儲結(jié)構(gòu)略，前序ABDE，中序DBEA，后序DE2103哈夫曼樹略，WPL=78h 25 323.(18,5,16,19,2,2，3)h4 68564.線性探測：81025322768鏈地址法：6 275.