數(shù)據(jù)結(jié)構(gòu)試題含答案

1、 一是非題（正確的打“”，錯誤的打“×”。）1. 數(shù)據(jù)結(jié)構(gòu)可用三元式表示（D，S，P）。其中：D是數(shù)據(jù)對象，S是D上的關(guān)系，P是對D的基本操作集。×2. 線性表的鏈式存儲結(jié)構(gòu)具有可直接存取表中任一元素的優(yōu)點。 ×3. 字符串是數(shù)據(jù)對象特定的線性表。4. 二叉樹是一棵結(jié)點的度最大為二的樹。 ×5 鄰接多重表可以用以表示無向圖，也可用以表示有向圖。×6 可從任意有向圖中得到關(guān)于所有頂點的拓撲次序。×7 一棵無向連通圖的生成樹是其極大的連通子圖。×8 二叉排序樹的查找長度至多為log2。×<9> 對于一棵m階

2、的B-樹.樹中每個結(jié)點至多有m 個關(guān)鍵字。除根之外的所有非終端結(jié)點至少有m/2個關(guān)鍵字。×10對于目前所知的排序方法，快速排序具有最好的平均性能。11. 順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。×12. 二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表。13. 連通圖G的生成樹是一個包含G的所有n個頂點和n-1條邊的子圖。×14. 折半查找不適用于有序鏈表的查找。15. 完全二叉樹必定是平衡二叉樹。16. 中序線索二叉樹的優(yōu)點是便于在中序下查找直接前驅(qū)結(jié)點和直接后繼結(jié)點。17. 隊列是與線性表完全不同的一種數(shù)據(jù)結(jié)構(gòu)。×18. 平均查找長度與記錄的查找

3、概率有關(guān)。19. 二叉樹中每個結(jié)點有兩個子結(jié)點，而對一般的樹，則無此限制，所 以，二叉樹是樹的特殊情形。×20. 算法的時間復(fù)雜性越好，可讀性就越差；反之，算法的可讀性越好，則時間復(fù)雜性就越差。×二選擇題1. 若對編號為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,12. 遞歸程序可借助于( b )轉(zhuǎn)化為非遞歸程序。 a:線性表 b: 棧 c:隊列 d:數(shù)組 3. 在下列數(shù)據(jù)結(jié)構(gòu)中( c )具有先進先出（FIFO）特性，( b )具有先進后出(FILO）

4、特性。a:線性表 b:棧 c:隊列 d:廣義表4. 對字符串s=data-structure 執(zhí)行操作replace(s,substring(s,6,8),bas)的結(jié)果是 ( d ) 。a: database b: data-base c: bas d: data-basucture 5. 設(shè)有二維數(shù)組A 5 x 7 ,每一元素用相鄰的4個字節(jié)存儲，存儲器按字節(jié)編址。已知A的起始地址為100。則按行存儲時，元素A06的第一個字節(jié)的地址是（ d ）按列存儲時，元素A06的第一個字節(jié)的地址是（ a ）a: 220 b: 200 c: 140 d: 1246. 對廣義表 A=（a,(b)）,(c,

5、(),d）執(zhí)行操作gettail(gethead(gettail(A)的結(jié)果是：（ b ） 。a:（） b: （） c: d d: (d)7假設(shè)用于通訊的電文僅由6個字符組成，字母在電文中出現(xiàn)的頻率分別為7, 19, 22, 6, 32, 14。 若為這6個字母設(shè)計哈夫曼編碼（設(shè)生成新的二叉樹的規(guī)則是按給出的次序從左至右的結(jié)合，新生成的二叉樹總是插入在最右），則頻率為7的字符編碼是（ g ），頻率為32的字符編碼是（ c ）。a: 00 b: 01 c: 10 d: 11 e: 011 f: 110 g: 1110 h:11118. 對二叉排序樹（ b ）可得到有序序列。 a:按層遍歷 b:前

6、序遍歷 c:中序遍歷 d:后序遍歷9已知某樹的先根遍歷次序為abcdefg，后根遍歷次序為cdebgfa。若將該樹轉(zhuǎn)換為二叉樹,其后序遍歷次序為（ d ）。 a: abcdefg b: cdebgfa c: cdegbfa d: edcgfba10對一棵完全二叉樹進行層序編號。則編號為n的結(jié)點若存在右孩子,其位序是( d )。編號為n的結(jié)點若存在雙親,其位置是( a )。a: n/2 b: 2n c:2n-1 d:2n+1 e:n f: 2(n+1)11關(guān)鍵路徑是指在只有一個源點和一個匯點的有向無環(huán)網(wǎng)中源點至匯點（ c ）的路徑。a:弧的數(shù)目最多 b:弧的數(shù)目最少 c:權(quán)值之和最大 d:權(quán)值之

7、和最小12. 哈希表的查找效率取決于（ d ）。 a: 哈希函數(shù) b:處理沖突的方法。 c:哈希表的裝填因子。 d:以上都是13從邏輯上可以把數(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. 基本類型和組合類型14在計算遞歸函數(shù)時，如不用遞歸過程，應(yīng)借助于( b )這種數(shù)據(jù)結(jié)構(gòu)。A. 線性表 B. 棧 C. 隊列 D. 雙向隊列15若已知某二叉樹的中序和后序遍歷序列分別BCAEFD和CBFEDA，則該二叉樹的先序序列為( a )。A. ABCDEF B. ABDCEF C. ABDCFE D. ACBDFE16當待排序序列的關(guān)鍵字次序

8、為倒序時，若需為之進行正序排序，下列方案中( d )為佳。 A. 起泡排序 B. 快速排序C. 直接插入排序 D. 簡單選擇排序17若從二叉樹的根結(jié)點到其它任一結(jié)點的路徑上所經(jīng)過的結(jié)點序列按其關(guān)鍵字遞增有序，則該二叉樹是( c )。A. 二叉排序樹 B. 赫夫曼樹 C. 堆 D. 平衡二叉樹18下圖所有可能的拓撲序列有( b )種。A. 2 B. 3 C. 4 D. 519下列排序算法中，( d )算法可能會出現(xiàn)：初始數(shù)據(jù)為正序時，花費的時間反而最多。A. 堆排序 B. 起泡排序 C. 歸并排序 D. 快速排序20右圖為一棵3階B-樹。 20 ，25在該樹上插入元素15 后的B-樹是( c )

9、。 10 , 14 21 35 A. 15 , 25 B. 20 , 25 10 , 14 20 , 21 35 10 , 14 15 , 21 35 C. 20 D. 14 , 25 14 25 10 , 15 20 , 21 3510 15 21 3521設(shè)森林F中有三棵樹，第一、第二和第三棵樹的結(jié)點個數(shù)分別為m1、m2和m3，則與森林F對應(yīng)的二叉樹根結(jié)點的右子樹上的結(jié)點個數(shù)是( d )。A. m1 B. m1+m2 C. m3 D. m2+m322. 根據(jù)插入次序（80，90，100，110，85，70，75，60，72）建立二叉排序樹。圖（ a ）是最終變化的結(jié)果。若仍以該插入次序建立

10、平衡二叉樹。圖（ c ）是最終變化的結(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:23.設(shè)輸入序列為20,45,30,89,70,38,62，19依次插入到一棵2-3樹中(初始狀態(tài)為空)，該B-樹為（ b ）。再刪除38，該B-樹為（ f ）。 （ 30 62 ） （ 45 ） （19，20）（ 38 45 ） （ 70，89 ） （ 30 ） （ 70 ）（19 20） （38

11、）（ 62 ） （ 89 ） a: b: （ 45 70 ） （ 45 ） （20） （ 62 ） （ 89 ） （ 20 ） （ 70 ）（19）（ 30 ） （ 19 ） ( 30,38 ）（ 62 ） （ 89 ） c: d: （ 30 70 ） （ 45 ） （19，20） （ 45 62） （ 89 ） （ 20 ） （ 70 ）（19 ） （30 ）（ 62 ） （ 89 ） e: f:24已知一組待排序的記錄關(guān)鍵字初始排列如下：45,34,87,25,67,43,11,66,27,78 。( g )是快速排序法一趟排序的結(jié)果；( a )是希爾排序法（初始步長為4）一趟排序的結(jié)果；

12、( b )是初始堆（大堆頂）；( d )是基數(shù)排序法一趟排序的結(jié)果。A27,34,11,25,45,43,87,66,67,78 B87,78,45,66,67,43,11,25,27,34C11,43,34,25,45,66,27,67,87,78 D11,43,34,45,25,66,87,67,27,78E 34,45,25,67,43,11,66,27,78,87 F87,45,11,25,34,78,27,66,67,43G27,34,11,25,43,45,67,66,87,78 H34,11,27,25,43,78,45,67,66,8725若有序表中關(guān)鍵字序列為：14，20，2

13、5，32，34，45，57，69，77，83，92。對其進行折半查找，則在等概率情況下，查找成功時的平均查找長度是( c )。查找32時需進行( c )次比較。A. 1 B. 2 C. 3 D. 4 26. 設(shè)一棵二叉樹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 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.

14、527. 一個連通圖的最小生成樹( b )。 A只有一棵 B. 有一棵或多棵 C. 一定有多棵 D. 可能不存在28若某二叉樹有20個葉子結(jié)點，有20個結(jié)點僅有一個孩子，則該二叉樹的總結(jié)點數(shù)是( c )。 A40 B. 55 C. 59 D. 6129已知哈希表地址空間為A0.8，哈希函數(shù)為H(k)=k mod 7，采用線性探測再散列處理沖突。若依次將數(shù)據(jù)序列：76,45,88,21,94,77,17存入該散列表中，則元素17存儲的下標為( f )；在等概率情況下查找成功的平均查找長度為( c )。 A. 0 B. 1 C. 2 D. 3E. 4 F. 5 G. 6 H. 730已知某有向圖的

15、鄰接表存儲結(jié)構(gòu)如圖所示。 0 E 2 1 1 D 0 3 4 2 C 43 B 1 2 0 4 A 2 根據(jù)存儲結(jié)構(gòu)，依教材中的算法其深度優(yōu)先遍歷次序為（ d ）。廣度優(yōu)先遍歷次序為（ c ）。各強連通分量的頂點集為（ ）。a: abcde. b: edcba. c: ecdab. d: ecadb. e: abc及ed f: ac及bed g: ab及ced h: bc及aed31. 已知某無向圖的鄰接表如下所示； ( )是其原圖。 ( )是按該鄰接表遍歷所得深度優(yōu)先生成樹。( )是按該鄰接表遍歷所得廣度優(yōu)先生成樹。 0 a 3 2 1 1 b 3 0 2 c 4 3 0 3 d 5 2 1

16、 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 d c c d c d f e e f e f32若順序表中各結(jié)點的查找概率不等，則可用如下策略提高順序查找的效率：若找到指定的結(jié)點，將該結(jié)點與其后繼（若存在）結(jié)點交換位置，使得經(jīng)常被查找的結(jié)點逐漸移至表尾。以下為據(jù)此策略編寫的算法，請選擇適當?shù)膬?nèi)容，完成此功能。順序表的存儲結(jié)構(gòu)為：typedef struct ElemType *elem; /數(shù)據(jù)元素存儲空間，0號單元作監(jiān)視哨 int length; /表長度 SSTable

17、;int search_seq(SSTable ST, KeyType key) /在順序表ST中順序查找關(guān)鍵字等于key的數(shù)據(jù)元素。/若找到，則將該元素與其后繼交換位置，并返回其在表中的位置，否則為0。ST.elem0.key=key;i=ST.length;while(ST.elemi.key!=key) ;if( ) ST.elemiST.elemi+1； ； return i;A. i>0 B. i>=0 C. i<ST.length D. i<=ST.lengthE. i+ F. i- G. A和C同時滿足 H. B和D同時滿足33下列函數(shù)為堆排序中的堆調(diào)整過

18、程（調(diào)整H.rs的關(guān)鍵字，使H.rs.m成為一小頂堆）。請在“ ”處填上合適的內(nèi)容,完成該算法。Void heapadjust( heaptype & H , int s , int m ) rc=H.rs;for (j=2*s;j<=m;j*=2) if (j<m && ) +j;if ( ) break;H.rs=H.rj; s=j; ;/heapadjusta: (H.rj.key>H.rj+1.key);b: !(rc.key< H.rj.key); c: (H.rj.key<H.rj+1.key); d: !(rc.key >H.rj.key); e: H.rs=rc;