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

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

2、next ）。已知指針 n 所指結(jié)點不是尾結(jié)點，若在指針 p 所指結(jié)點之后插入結(jié)點 s,則應(yīng)執(zhí)行下列哪一個操作？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é)點生成一棵哈夫曼樹，它的帶權(quán)路徑長度為( )。A. 24 B. 71 C. 48 D. 5310. 無向圖 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) 。對該圖進

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

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. 一個棧的入棧序

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

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

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