大連理工大學(xué)數(shù)據(jù)結(jié)構(gòu)試題及答案

1、數(shù)據(jù)結(jié)構(gòu)期末試卷一、選擇題組成數(shù)據(jù)的基本單位是（ 。數(shù)據(jù)項(xiàng)(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)。線性表?xiàng)ｊ?duì)列樹二叉樹中第上的結(jié)點(diǎn)數(shù)最多有（ ）個(gè)。2i2i2i-12i-1設(shè)指針變量p 指向單鏈表結(jié)點(diǎn)A，則刪除結(jié)點(diǎn)A 的后繼結(jié)點(diǎn)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，一個(gè)元素出棧后即進(jìn)入

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

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

4、編號(hào)，則編號(hào)為 8 的雙親結(jié)點(diǎn)的編號(hào)是，編號(hào)為 8 的左孩子結(jié)點(diǎn)的編號(hào)是 。9.下列程序段的功能實(shí)現(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鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)略，前序ABDE，中序DBEA，后序DE2103哈夫曼樹略，WPL=78h 25 323.(18,5,16,19,2,2，3)h4 68564.線性探測(cè)：81025322768鏈地址法：6 275.