南京理工大學(xué)紫金學(xué)院《數(shù)據(jù)結(jié)構(gòu)》試卷-高清數(shù)位重置新版

1、1 / 6、選擇題1. 樹(shù)最適合用來(lái)表示（）。A.有序數(shù)據(jù)C.元素之間具有分支層次關(guān)系的數(shù)據(jù)2. 一個(gè)堆是一棵（）二叉樹(shù)。A.普通 B.排序 C.滿3. 設(shè)哈夫曼樹(shù)中的葉子結(jié)點(diǎn)總數(shù)為 m，有（）個(gè)空指針域。A. 2m-1B. 2mC. 2m+14. 線性結(jié)構(gòu)的順序存儲(chǔ)結(jié)構(gòu)是一種（A.隨機(jī)存取B.順序存取5. 一下是平衡二叉樹(shù)的是（）。二分查找值為 22 的數(shù)據(jù)時(shí)要進(jìn)行（）B. 無(wú)序數(shù)據(jù)元素D.元素之間無(wú)聯(lián)系的數(shù)據(jù)D.完全若用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，則該哈夫曼樹(shù)中共D. 4m）的存儲(chǔ)結(jié)構(gòu)。C. 索引存取D.散列存取2 / 6A. 2B. 3C. 4D. 58.設(shè)單鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為（data ,

2、next ）。已知指針 n 所指結(jié)點(diǎn)不是尾結(jié)點(diǎn)，若在指針 p 所指結(jié)點(diǎn)之后插入結(jié)點(diǎn) s,則應(yīng)執(zhí)行下列哪一個(gè)操作？A. s-n ext=p; p-next=s;n ext=s;B. s-n ext=p-n ext;p-3 / 69. 由權(quán)值分別為 11. 8. 6. 2. 5 的葉子結(jié)點(diǎn)生成一棵哈夫曼樹(shù)，它的帶權(quán)路徑長(zhǎng)度為( )。A. 24 B. 71 C. 48 D. 5310. 無(wú)向圖 G = ( V, E ) ，其中 V = a ，b，c，d，e，f ，E = (a, b) , (a, c) , (a, e) , (b,e) , (c, f) , (f, d) , (e, d) 。對(duì)該圖進(jìn)

3、行深度優(yōu)先遍歷，下面不能得到的序列是( )。A. acfdeb B. aebdfc C. aedfcb D. abecdf11. 設(shè)有廣義表 D ( a, b, D ) ，其長(zhǎng)度為( )，深度為( )。A.gB. 3C. 2D. 512. 線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，則采 用( )存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A. 單鏈表 B. 僅有頭指針的單循環(huán)鏈表 C. 雙鏈表 D. 僅有頭指針的單循環(huán)鏈表13. 在有 n 個(gè)結(jié)點(diǎn)的二叉鏈表中，值為非空的鏈域的個(gè)數(shù)為( )。A. n-1 B. 2n-1 C. n+1D. 2n+114. 稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種，

4、即( )。A. 二維數(shù)組和三維數(shù)組 B. 三元組與散列 C. 三元組與十字鏈表 D. 散列和十字鏈 表15. 以下不是堆的序列是( )。A. 100, 85, 98, 77, 80, 60, 82, 40, 20, 10, 66B. 100, 98, 85, 82, 80, 77, 66, 60, 40, 20, 10C. 10, 20, 40, 60, 66, 77, 80, 82, 85, 98, 100D. 100, 85, 40, 77, 80, 60, 66, 98, 82, 10, 20C. s-next=D. p-next=s; s-next=p;4 / 616. 一個(gè)棧的入棧序

5、列是 a, b, c, d, e ，則棧的不可能輸出序列是( )A. edcba B. decba C. dcead D. abcde二、填空題1. 下面程序段的時(shí)間復(fù)雜度是 _ 。_i = 1;While ( i = n )i = i * 5;2. 在一個(gè)單鏈表中，要?jiǎng)h除某一個(gè)結(jié)點(diǎn)，必須找到該結(jié)點(diǎn)的 _ 結(jié)_ 點(diǎn)。3. 在一個(gè)長(zhǎng)度為 n 的順序表中，在第 1 個(gè)元素 ( 1 = i = n+1 )之前插入一個(gè)新元素時(shí)須向后移動(dòng) _ 個(gè)_元素。4. 有一個(gè) 10 階對(duì)稱(chēng)矩陣 A，采用壓縮存儲(chǔ)方式(以行為主存儲(chǔ)，且 LOC ( A00 ) = 1則 A85 的地址是 _。5. 設(shè)在一棵二叉樹(shù)中，

6、度為 0 的結(jié)點(diǎn)個(gè)數(shù)為 8，度為 2 的結(jié)點(diǎn)個(gè)數(shù)為 _。6. 設(shè)二叉樹(shù)結(jié)點(diǎn)的先根序列為 ABEDCFGH ，中根序列為 EDBAFCHG ，則二叉樹(shù)中葉子結(jié)點(diǎn)是 _。_7. 求最小生成樹(shù)算法有 Prim 算法和 Kruskal 算法兩種， _ 算_ 法適合稠密圖，_ 算_ 法適合稀疏圖。8. 數(shù)據(jù)表中有 10000 個(gè)元素，如果僅要求求出其中最大的 10 個(gè)元素，則采用是 算法最節(jié)省時(shí)間5 / 69.循環(huán)隊(duì)列中隊(duì)滿條件為:三、綜合題1.畫(huà)出廣義表 LS = ( (), ( e ), ( a, ( b, c, d )的頭尾鏈表存儲(chǔ)結(jié)構(gòu)2.已知一棵二叉樹(shù)的先序序列與中序序列分別為：ABCDEFGH

7、I 和 BCAEDGHFI(1)給出該二叉樹(shù)的后序遍歷序列。(2)畫(huà)出該二叉樹(shù)的帶頭結(jié)點(diǎn)的中序線索二叉樹(shù)(3)將該二叉樹(shù)轉(zhuǎn)換成森林。6 / 6（1）構(gòu)造一棵二叉排序樹(shù)（只需最后結(jié)果圖）（2）畫(huà)出構(gòu)造的一棵平衡二叉樹(shù)（只需最后結(jié)果圖）。（3）HASH 表表長(zhǎng)為 12，HASH 函數(shù)為 H （key ） = key%11 ，試用線性探測(cè)再散列解決沖突的方法構(gòu)造哈希表。012345678910116.設(shè)待排序的關(guān)鍵字序列為 27,46, 5, 18, 16, 51,32, 26 ,分別使用以下排序方法進(jìn)設(shè)有無(wú)向圖 G,要求使用 Prim 算法構(gòu)造以頂點(diǎn) 造最小生成樹(shù)的每一步過(guò)程(無(wú)需注明權(quán)值)。3.C 為起點(diǎn)的最小生成樹(shù)，同時(shí), 寫(xiě)出構(gòu)5.輸入一個(gè)正整數(shù)序列 23, 32, 16, 14, 42, 71, 57, 28, 55, 19, 12, 50 7 / 6行排序，寫(xiě)出題目所給定趟數(shù)的結(jié)果。（1） 第三趟直接插入排序的結(jié)果。（2） 第一趟希爾排序的結(jié)果（增量為 3 ）。（3） 第二趟歸并排序。（4） 第一趟快速排序。四、算法設(shè)計(jì)題有一個(gè)帶頭結(jié)點(diǎn)的單鏈表 head，其 ElemType 類(lèi)型