數(shù)據(jù)結(jié)構(gòu)復習題

1、一 是非題(線性結(jié)構(gòu))4 線性表的鏈式存儲結(jié)構(gòu)具有可直接存取表中任一元素的優(yōu)點。 錯5 線性表的順序存儲結(jié)構(gòu)優(yōu)于鏈式存儲結(jié)構(gòu)。 錯6. 在單鏈表P指針所指結(jié)點之后插入S結(jié)點的操作是： 錯P->next= S ; S-> next = P->next;。7 對于插入、刪除而言，線性表的鏈式存儲優(yōu)于順序存儲。 對 8. 順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。 錯10 線性表的順序存儲結(jié)構(gòu)具有可直接存取表中任一元素的優(yōu)點。 對11. 棧和隊列是操作上受限制的線性表。 對12. 隊列是與線性表完全不同的一種數(shù)據(jù)結(jié)構(gòu)。 錯13. 隊列是一種操作受限的線性表，凡對數(shù)據(jù)元

2、素的操作僅限一端進行。錯15. 棧是限定僅在表頭進行插入和表尾進行刪除運算的線性表。 錯16 隊列是一種運算受限的線性表 對(樹形結(jié)構(gòu))1. 二叉樹中每個結(jié)點有兩個子結(jié)點，而對一般的樹，則無此限制，所 以，二叉樹是樹的特殊情形。 錯2. 二叉樹是一棵結(jié)點的度最大為二的樹。 錯 3. 赫夫曼樹中結(jié)點個數(shù)一定是奇數(shù)。 對5. 假設B是一棵樹，B是對應的二叉樹。則B的后根遍歷相當于B的后序遍歷 。錯6. 通常，二叉樹的第i層上有2i-1個結(jié)點。 錯7. 中序線索二叉樹的優(yōu)點是便于在中序下查找直接前驅(qū)結(jié)點和直接后繼結(jié)點。 對8 二叉樹的先序遍歷序列中，任意一個結(jié)點均處在其孩子結(jié)點的前面。 對(圖形結(jié)構(gòu)

3、)1 鄰接多重表可以用以表示無向圖，也可用以表示有向圖。 錯2 可從任意有向圖中得到關(guān)于所有頂點的拓撲次序。 錯6. 一個無向圖的連通分量是其極大的連通子圖。 對7. 連通圖的生成樹是一個包含圖G所有n個頂點和任意n-1條邊的子圖。 錯9. 鄰接表可以表示有向圖，也可以表示無向圖。（ ） 對 （查找)1. 二叉排序樹的平均查找長度為O(log)。 對2. 二叉排序樹的最大查找長度與（LOG2N）同階。 錯 3 選用好的HASH函數(shù)可避免沖突。 錯4 折半查找不適用于有序鏈表的查找。 對5 一般來說，折半查找不適用于有序鏈表的查找。 對6 二叉排序樹的查找和折半查找的時間性能相同。 錯（排序)1

4、. 對于目前所知的排序方法，快速排序具有最好的平均性能。 對2 對于任何待排序序列來說，快速排序均快于冒泡排序。錯3 在最壞情況下，堆排序的時間性能是O(nlogn),比快速排序好 對選擇題。（1-19是線性、樹形、圖形結(jié)構(gòu)，20-29是查找和排序）1、從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成( C )。 A. 動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B. 順序組織和鏈接組織C. 線性結(jié)構(gòu)和非線性結(jié)構(gòu) D. 基本類型和組合類型2、線性表L在( B )情況下適于使用鏈表結(jié)構(gòu)實現(xiàn)。 A. 不需修改L的結(jié)構(gòu) B. 需不斷對L進行刪除、插入 C. 需經(jīng)常修改L中結(jié)點值 D. L中含有大量結(jié)點 3、若入棧順序為A、B、C、D、E，則下列

5、( D )出棧序列是不可能的。AA、B、C、D、E BB、C、D、A、ECC、D、B、E、A DD、E、C、A、B4、遞歸程序可借助于(C )轉(zhuǎn)化為非遞歸程序。 a.線性表 b.隊列 c: 棧 d.數(shù)組 5、在下列數(shù)據(jù)結(jié)構(gòu)中( C )具有先進先出（FIFO）特性，( B )具有先進后出(FILO）特性。a線性表 b棧 c隊列 d廣義表 6、若對編號為1，2，3的列車車廂依次通過扳道棧進行調(diào)度，不能得到 ( e ) 的序列。 a:1,2,3 b:1,3,2 c:2,1,3 d:2,3,1 e:3,1,2 f:3,2,17、假設用于通訊的電文僅由6個字符組成，字母在電文中出現(xiàn)的頻率分別為7, 19

6、, 22, 6, 32, 14。 若為這6個字母設計哈夫曼編碼（設生成新的二叉樹的規(guī)則是按給出的次序從左至右的結(jié)合，新生成的二叉樹總是插入在最右），則頻率為7的字符編碼是（ g），頻率為32的字符編碼是（ c ）。a: 00 b: 01 c: 10 d: 11 e: 011 f: 110 g: 1110 h:11118、對二叉排序樹（ C ）可得到有序序列。a:按層遍歷 b:前序遍歷 c:中序遍歷 d:后序遍歷 9、設一棵二叉樹BT的存儲結(jié)構(gòu)如下: 1 2 3 4 5 6 7 8 lchild 2 3 0 0 6 0 0 0 data A B C D E F G H rchild 0 5 4

7、0 8 7 0 0 其中l(wèi)child，rchild分別為結(jié)點的左、右孩子指針域，data為結(jié)點的數(shù)據(jù)域。則該二叉樹的高度為( D )；第3層有( A )個結(jié)點（根結(jié)點為第1層）。 A2 B. 3 C. 4 D. 510、在有n個結(jié)點的二叉樹的二叉鏈表表示中，空指針數(shù) （ B ）。 a.不定 b.n+1 c.n d.n-111、若某二叉樹有20個葉子結(jié)點，有20個結(jié)點僅有一個孩子，則該二叉樹的總結(jié)點數(shù)是( C )。 A40 B. 55 C. 59 D. 6112、已知某二叉樹的先序遍歷次序為abcdefg中序遍歷次序為badcgfe，則該二叉樹的后序遍歷次序為（ C ）。層次遍歷次序為（ a ）

8、。 a: abcdefg b: cdebgfa c: bdgfeca d: edcgfba13、.圖示的三棵二叉樹中(C )為最優(yōu)二叉樹。 A) B) C) c a 2 7 a b c d d b 7 5 2 4 4 5 a b c d 7 5 2 414、對一棵完全二叉樹進行層序編號。則編號為n的結(jié)點若存在右孩子,其位序是(d )。編號為n的結(jié)點若存在雙親,其位置是( a)。a: n/2 b: 2n c:2n-1 d:2n+1 e:n f: 2(n+1)15、設森林F中有三棵樹，第一、第二和第三棵樹的結(jié)點個數(shù)分別為m1、m2和m3，則與森林F對應的二叉樹根結(jié)點的右子樹上的結(jié)點個數(shù)是( d )

9、。A. m1 B. m1+m2 C. m3 D. m2+m316、下列二叉樹中，( a )可用于實現(xiàn)符號不等長高效編碼。a:最優(yōu)二叉樹 b:次優(yōu)查找樹 c:二叉平衡樹 d:二叉排序樹17、設無向圖G = (V,E)和G= (V,E)，若G是G的生成樹，則下面不正確的說法是( b )。A. G是G的子圖         B. G是G的連通分量C. G是G的無環(huán)子圖      D. G是G的極小連通子圖且V= V18、任何一個連通圖的最小生成樹( b)。 A只有一棵 B. 有一棵

10、或多棵 C. 一定有多棵 D. 可能不存在19、已知某無向圖的鄰接表如下所示； ( 19 )是其原圖。 E ( 20 )是按該鄰接表遍歷所得深度優(yōu)先生成樹。 C( 21 )是按該鄰接表遍歷所得廣度優(yōu)先生成樹。D 0 a 3 2 1 1 b 3 0 2 c 4 3 0 3 d 5 2 1 0 4 e 5 2 5 f 4 3A. a b B. a b C. a b c d c d c d e f e f e f D. a b E. a b F. a b c d c d c d e f e f e f20、下列查找方法中（ a ）適用于查找單鏈表。 A）順序查找 B）折半查找 C）分塊查找 D）ha

11、sh查找21、哈希表的查找效率取決于（ d ）。a: 哈希函數(shù) b:處理沖突的方法。 c:哈希表的裝填因子。 d:以上都是22、在Hash函數(shù)H(k)=k MOD m中，一般來說，m應取( C )。 A. 奇數(shù) B. 偶數(shù) C. 素數(shù) D. 充分大的數(shù)23、在順序表查找中，為避免查找過程中每一步都檢測整個表是否查找完畢，可采用 方法。AA.設置監(jiān)視哨 B.鏈表存貯 C.二分查找 D.快速查找24、靜態(tài)查找表和動態(tài)查找表的區(qū)別在于( B )。A. 前者是順序存儲，而后者是鏈式存儲B. 前者只能進行查找操作，而后者可進行查找、插入和刪除操作 C. 前者只能順序查找，而后者只能折半查找 D. 前者可

12、被排序，而后者不能被排序25、根據(jù)插入次序（80，90，100，110，85，70，75，60，72）建立二叉排序樹。圖（ a ）是最終變化的結(jié)果。 80 80 70 90 75 90 60 75 85 100 60 70 85 100 72 110 72 110 a: b: 90 90 75 100 80 100 70 80 110 75 70 85 110 60 72 85 60 72 c: d:26、若有序表中關(guān)鍵字序列為：14，20，25，32，34，45，57，69，77，83，92。對其進行折半查找，則在等概率情況下，查找成功時的平均查找長度是( C )。查找32時需進行( C )

13、次比較。A. 1 B. 2 C. 3 D. 4 27、已知哈希表地址空間為A0.8，哈希函數(shù)為H(k)=k mod 7，采用線性探測再散列處理沖突。若依次將數(shù)據(jù)序列：76,45,88,21,94,77,17存入該散列表中，則元素17存儲的下標為( h )；在等概率情況下查找成功的平均查找長度為( C )。 A. 0 B. 1 C. 2 D. 3E. 4 F. 5 G. 6 H. 728、若從二叉樹的根結(jié)點到其它任一結(jié)點的路徑上所經(jīng)過的結(jié)點序列按其關(guān)鍵字遞增有序，則該二叉樹是( C )。A. 二叉排序樹 B. 赫夫曼樹 C. 堆 D. 平衡二叉樹29、已知一組待排序的記錄關(guān)鍵字初始排列如下：56

14、,26,86,35,75,19,77,58,48,42下列選擇中（ D ）是快速排序一趟排序的結(jié)果。（ B ）是歸并排序一趟排序的結(jié)果。（ A ）是初始堆（大堆頂）。A）86,75,77,58,42,19,56,35,48,26.B）26,56,35,86, 19, 75, 58, 77, 42, 48.C）35,26,19,42,58,48,56,75,86,77.D）42,26,48,35,19,56,77,58,75,86. 三填空題（1-13是線性、樹形、圖形結(jié)構(gòu)，14-15是查找和排序）1、數(shù)據(jù)結(jié)構(gòu)通常有下列4類基本結(jié)構(gòu)：集合、 線性結(jié)構(gòu) 、樹型結(jié)構(gòu)、圖型結(jié)構(gòu)。2、線性表的順序存儲結(jié)

15、構(gòu)是以 物理存儲地址 來表示數(shù)據(jù)元素之間的邏輯關(guān)系的。3、遞歸過程可借助于數(shù)據(jù)結(jié)構(gòu) ( 棧 )改寫成非遞歸過程。4、設循環(huán)隊列存于一維數(shù)組中，尾指針rear指示隊尾元素在隊列中的當前位置，頭指針front指示隊列中隊頭元素的前一個位置，則隊列長度( （rear-front +m）%m )。5、在二叉樹的第i層上至少有_1_個結(jié)點, 至多有_2i-1_個結(jié)點 ,深度為k的二叉樹至多有_2k_-1_個結(jié)點.6、對樹的遍歷有先序遍歷樹和后序遍歷樹。若以二叉鏈表作樹的存儲結(jié)構(gòu),則樹的先序遍歷可借用二叉樹的 先序 遍歷算法來實現(xiàn),而樹的后序遍歷可借用二叉樹的 中序 遍歷算法來實現(xiàn)。7、設森林F中有三棵樹

16、，第一、第二和第三棵樹的結(jié)點個數(shù)分別為m1、m2和m3，則與森林F對應的二叉樹根結(jié)點的左子樹上的結(jié)點個數(shù)是（m1-1 ），右子樹上的結(jié)點個數(shù)是（ m2+m3 ）。8、若某二叉樹有n0個葉子結(jié)點，有n1個結(jié)點僅有一個孩子，則該二叉樹的總結(jié)點數(shù)是（ 2 n0 + n1-1）。9、如果對完全二叉樹中結(jié)點從1開始按層進行編號，設最大編號為n；那么，可以斷定編號為i (i>1)的結(jié)點的父結(jié)點編號為( i/2 )；所有編號（ >n/2 ）的結(jié)點為葉子結(jié)點。 10、若某二叉樹中，有20個結(jié)點沒有孩子，有20個結(jié)點僅有一個孩子，則該二叉樹的總結(jié)點數(shù)是 59 。11、 n個頂點的連通圖至少有 n-1

17、 條邊，至多有 n(n-1)/2 條邊。12、對于圖的存儲結(jié)構(gòu)有（ 鄰接表 ）、（ 鄰接矩陣 ）等方法。13、在一個無向圖的鄰接表中，若表結(jié)點的個數(shù)是m，則圖中邊的條數(shù)是_m/2_條。14、若有序表中關(guān)鍵字序列為：12，22，33，44，55，66，77，88，99，100，101對其進行折半查找，則在等概率情況下，查找成功時的平均查找長度是（ 3 ）。查找99時需進行（ 2 ）次比較。15、用 中序 遍歷對二叉排序樹進行訪問可得到有序序列。已知Hash函數(shù)為 H（K）=K mod 13 ，散列地址為0 -14，用二次探測再散列處理沖突，關(guān)鍵字（23，34，56，24，75，12，49, 52

18、，36，92）的分布如圖，則平均成功的查找長度為（ ）。 0 1 2 3 4 5 6 7 8 9 10 11 12 13 1452 36925634 2324751249圖示結(jié)構(gòu)題（1-4是線性、樹形、圖形結(jié)構(gòu)，5-6是查找排序）1. 已知在電文中只出現(xiàn)頻率為 ( 5,26,7,23,20,19 )的個字符，畫出你建的哈夫曼樹，并給出其哈夫曼編碼。2.已知某二叉樹的后序遍歷和中序遍歷次序分別為DBFGECA和BDACFEG請畫出該二叉樹。3將圖示森林轉(zhuǎn)換為二叉樹，并對該二叉樹先序遍歷。 hda jibfec mlkg 4某二叉樹的結(jié)點數(shù)據(jù)采用順序存儲表示如下：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19ABC D E  F   GH    I（1）