大連理工大學(xué)軟件學(xué)院2014數(shù)據(jù)結(jié)構(gòu)期末考試學(xué)長(zhǎng)手抄整理

1、數(shù)據(jù)結(jié)構(gòu)2014-2015期末試卷（1.不保證題目完全沒有問題 2.部分圖片來自網(wǎng)絡(luò)）一、選擇（2*15=30，）1. 若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素的算法的時(shí) 間復(fù)雜度為（）A.O（O）B.O（l）C0（n）D.O（n2）2. 用不帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)隊(duì)列時(shí)，其隊(duì)頭指針指向隊(duì)頭結(jié)點(diǎn)，其隊(duì)尾指針指向隊(duì)尾 結(jié)點(diǎn)，則在進(jìn)行刪除操作時(shí)（）A. 僅修改隊(duì)頭指針B.僅修改隊(duì)尾指針C.隊(duì)頭、隊(duì)尾指針都不修改D.隊(duì)頭、隊(duì)尾指針都可能要修改3. 設(shè)棧S和隊(duì)列Q的初始狀態(tài)均為空，元素a,b,c,d,e,f,g依次進(jìn)入棧S,若每個(gè)元素出棧后立即進(jìn)入隊(duì)列Q,旦7個(gè)元素出隊(duì)的順序是b

2、,d,c,f,e,a,g,則棧S的容量至少是（） A.lB.2C3D.44. 對(duì)n（n>2）個(gè)權(quán)值均不相同的字符構(gòu)成哈夫曼樹，關(guān)于該樹的敘述中，錯(cuò)誤的是（）A.該樹一定是一棵完全二叉樹B.樹中一定沒有度為1的結(jié)點(diǎn)C. 樹中兩個(gè)權(quán)值最小的結(jié)點(diǎn)一定是兄弟結(jié)點(diǎn)D. 樹中任一非葉結(jié)點(diǎn)的權(quán)值一定不小于下一層任一結(jié)點(diǎn)的權(quán)值5. 一棵二叉樹的前序遍歷序列為ABCDEFG,它的中序遍歷序列可能是（）A.CABDEFGB.ABCDEFGCDACEFBGD.ADCFEG6. 下列線索二叉樹中（用虛線表示線索），符合后序線索二叉樹定義的是（D ）NULL7. 下面關(guān)于二分查找的敘述正確的是（）A.表必須有序，

3、表可以順序方式存儲(chǔ)，也可以鏈表方式存儲(chǔ)B. 表必須有序，H表中數(shù)據(jù)必須是整型，實(shí)型或字符型C. 表必須有序，而且只能從小到大排列D. 表必須有序，且表只能以順序方式存儲(chǔ)8. 下列排序算法中，在每一趟都能選出一個(gè)元素放到其最終位置上，并且其時(shí)間性能受 數(shù)據(jù)初始特性影響的是（ ）A.直接插入排序 B.快速排序C.直接選擇排序D.堆排序9. 卜列關(guān)于無向連通圖特性的敘述中，正確的是（）I. 所有頂點(diǎn)的度之和為偶數(shù)II. 邊數(shù)大于頂點(diǎn)個(gè)數(shù)減1III至少有一個(gè)頂點(diǎn)的度為1A.只有IB.只有IIC.I和IID.I和III10. 在I、列所示的平衡二叉樹中插入關(guān)鍵字48后，得到一棵新平衡二叉樹，在新平衡二

4、叉樹中，關(guān)鍵字37所在結(jié)點(diǎn)的左、右子結(jié)點(diǎn)保存的關(guān)鍵字分別是（）A.13,48B.24,48C.24,53D.24,9011. 若數(shù)據(jù)元素序列11,12,13,7,8,9,23,4,5是采用卜列排序方法之一得到的第二趟排序后的結(jié)果，則該排序算法只能是（） A.冒泡排序B.插入排序12. 卜列排序算法中，其中（）是穩(wěn)定的 A.堆排序，冒泡排序 C.直接選擇排序，歸并排序C選擇排序D.二路歸并排序B.快速排序，堆排序D.歸并排序，冒泡排序13. 下列敘述中，不符合m階B-樹定義要求的是（）A.根節(jié)點(diǎn)最多有m棵子樹B.所有葉結(jié)點(diǎn)都在同一層上C.各結(jié)點(diǎn)內(nèi)關(guān)鍵字均升序或降序排列D.葉結(jié)點(diǎn)之間通過指針鏈接1

5、4. 己知關(guān)鍵序列5,8,12,19,28,20,15,22是小根堆（最小堆），插入關(guān)鍵字3,調(diào)整后得到 的小根堆是（）A.3,5,12,8,28,20,15,22,19B3,5,12,19,20,15,22,8,28C.3,8,12,5,20,15,22,28,19D3,12,5,8,28,20,15,22,1915.下列AOE網(wǎng)表示一項(xiàng)包含8個(gè)活動(dòng)的工程，通過同時(shí)加快若干活動(dòng)的進(jìn)度可以縮短 整個(gè)工程的工期，下列選項(xiàng)中，加快其進(jìn)度就可以縮短工程工期的是（）A.c 和 eB.d 和 eC.f 和 dD.f 和 h二、簡(jiǎn)答(60，)1. (10')用序列(46,88,45,39,70,5

6、8,101,10,66,34)建立-棵二叉搜索樹，畫出該樹，并求在 等概率情況卜節(jié)找成功和查找不成功的平均查找長(zhǎng)度，畫出依次刪除46,58后的二叉搜 索樹2. (8')設(shè)字符a,b,c,d,e,f的使用頻度分別為25,20,6,14,28,7,求a,b,c,d,e,f的哈夫曼編碼并 給出相應(yīng)的哈夫曼樹，計(jì)算帶權(quán)路徑長(zhǎng)度3. (10')設(shè)G=(V,E)的鄰接表存儲(chǔ)如卜所示，試畫出該圖，給出深度優(yōu)先和廣度優(yōu)先搜索序 列，并畫出深度優(yōu)先和廣度優(yōu)先生成樹4. (6)己知一個(gè)森林的先序序列和后序序列如卜，清構(gòu)造出該森林先序序列：ABCDEFGHIJKLMNO后序序列：CDEBFHIJGA

7、MLONK5. (6)圖的鄰接矩陣如卜，試給出弗洛伊德算法求各點(diǎn)間最短距離的矩陣序列AA2,A3,A40 2 oo oo'oo 0 1 6= 5 8 0 4.3 oo oo 0.6. (10。一組記錄的關(guān)鍵碼為45,81,67,36,40,85,52,43,按照遞增序進(jìn)行排序.分別給出冒泡排序、快速排序(以第一個(gè)元素為軸)、二路歸并排序的第-趟排序結(jié) 果(2).畫出初始的最大堆(給出調(diào)整過程)7. (10')選擇哈希函數(shù)H(Kev)=Key%13,用開放定址法處理沖突，探查的地址序列為H(Key),H(Key)+l,H(Key)+3,H(Key)+5,試構(gòu)造給定關(guān)鍵字序列22,31,40,03,47,69,14,27,15,01,61,55,78的哈希表：查找27,15各要比較多少呢？計(jì)算在