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

1、是非題(正確的打“/ ，錯誤的打“X” O)數(shù)據(jù)結(jié)構(gòu)可用三元式表示(D, S, P)。其中：D是數(shù)據(jù)對象，S是D上的關(guān)系， P是對D的基本操作集。X 線性表的鏈式存儲結(jié)構(gòu)具有可直接存取表中任一元素的優(yōu)點。 字符串是數(shù)據(jù)對象特定的線性表。二叉樹是一棵結(jié)點的度最大為二的樹。 X 鄰接多重表可以用以表示無向圖，也可用以表示有向圖。 可從任意有向圖中得到關(guān)于所有頂點的拓撲次序。 X 一棵無向連通圖的生成樹是其極大的連通子圖。二叉排序樹的查找長度至多為log 2no X對于一棵m階的B樹.樹中每個結(jié)點至多有 m個關(guān)鍵字。除根之外的所有非終端結(jié)點至 少有廠m/2個關(guān)鍵字。X10. 對于目前所知的排序方法，

2、快速排序具有最好的平均性能。11. 順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。12. 二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表。13. 連通圖 G 的生成樹是一個包含 G 的所有 n 個頂點和 n-1 條邊的子圖。 X14. 折半查找不適用于有序鏈表的查找。15. 完全二叉樹必定是平衡二叉樹。16. 中序線索二叉樹的優(yōu)點是便于在中序下查找直接前驅(qū)結(jié)點和直接后繼結(jié)點。17. 隊列是與線性表完全不同的一種數(shù)據(jù)結(jié)構(gòu)。18. 平均查找長度與記錄的查找概率有關(guān)。19. 二叉樹中每個結(jié)點有兩個子結(jié)點，而對一般的樹，則無此限制，所 特殊情形。 X1.2.3.4.56789以，二叉樹是樹的20. 算

3、法的時間復(fù)雜性越好，可讀性就越差；反之，算法的可讀性越好，則時間復(fù)雜性就越 差。 X選擇題1. 若對編號為 1，2，3 的列車車廂依次通過扳道棧進行調(diào)度，不能得到 a:1,2,3 b:1,3,2 c:2,1,3 d:2,3,1 e:3,1,2 f:3,2,1( e ) 的序列。2. 遞歸程序可借助于 ( ba: 線性表 b: 棧轉(zhuǎn)化為非遞歸程序。c: 隊列 d: 數(shù)組)( b ) 具有先進后出 (FILO ) a: 線性表 b: 棧 c:3. 在下列數(shù)據(jù)結(jié)構(gòu)中 ( c具有先進先出(FIFO)特性， 特性。隊列 d: 廣義表4. 對字符串 s= data - structure 執(zhí)行操作 rep

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

5、)() c: d d: (d)假設(shè)用于通訊的電文僅由 6 個字符組成，字母在電文中出現(xiàn)的頻率分別為 7, 19, 22, 6, 32, 14。 若為這 6 個字母設(shè)計哈夫曼編碼（設(shè)生成新的二叉樹的規(guī)則是按給出的次序從 左至右的結(jié)合，新生成的二叉樹總是插入在最右） ，則頻率為 7 的字符編碼是（ g 頻率為 32 的字符編碼是（a: oo b: o1 e: o11 f: 11o），對二叉排序樹（ bb:8.? ? a: 按層遍歷c )。c: 1o d: 11g: 111o h:1111）可得到有序序列。前序遍歷 c:中序遍歷 d:后序遍歷9已知某樹的先根遍歷次序為abcdefg ，后根遍歷次序為

6、 cdebgfa 。若將該樹轉(zhuǎn)換為二叉樹 , 其后序遍歷次序為（ a: abcdefg b: cdebgfa c: cdegbfad )。d: edcgfba10對一棵完全二叉樹進行層序編號。則編號為編號為n的結(jié)點若存在雙親，其位置是（a: n/2b: 2nc:2n-1n 的結(jié)點若存在右孩子 a ） 。d:2n+1, 其位序是 （ d ） 。e:nf: 2(n+1)11關(guān)鍵路徑是指在只有一個源點和一個匯點的有向無環(huán)網(wǎng)中源點至匯點（權(quán)值之和最大 d: 權(quán)值之和最小a: 弧的數(shù)目最多 b: 弧的數(shù)目最少 c:12. 哈希表的查找效率取決于（a:哈希函數(shù) b: 處理沖突的方法。13從邏輯上可以把數(shù)據(jù)

7、結(jié)構(gòu)分成A. 動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)C. 線性結(jié)構(gòu)和非線性結(jié)構(gòu)d ）。c:c ）的路徑。哈希表的裝填因子。 d: 以上都是( c ) 。B.D.順序組織和鏈接組織 基本類型和組合類型14在計算遞歸函數(shù)時，如不用遞歸過程，應(yīng)借助于 A. 線性表 B. 棧 C.（ b ） 這種數(shù)據(jù)結(jié)構(gòu)。 隊列 D.雙向隊列15若已知某二叉樹的中序和后序遍歷序列分別 序列為 （ a ） 。BCAEFD 和 CBFEDA ，則該二叉樹的先序A. ABCDEF B. ABDCEF C. ABDCFE D. ACBDFE（d ）為佳。16.當(dāng)待排序序列的關(guān)鍵字次序為倒序時，若需為之進行正序排序，下列方案中 A.起泡排序B.快

8、速排序C.直接插入排序D.簡單選擇排序17若從二叉樹的根結(jié)點到其它任一結(jié)點的路徑上所經(jīng)過的結(jié)點序列按其關(guān)鍵字遞增有序, 則該二叉樹是（C ）。A.二叉排序樹B.赫夫曼樹C.D.平衡二叉樹D. 519下列排序算法中，（A.堆排序 B.d ）算法可能會出現(xiàn)：初始數(shù)據(jù)為正序時, 起泡排序C.歸并排序花費的時間反而最多。D.快速排序20.右圖為一棵3階B-樹。 在該樹上插入元素 15 后的B-樹是（c ）。m1、m2和m3,則與21設(shè)森林F中有三棵樹，第一、第二和第三棵樹的結(jié)點個數(shù)分別為 森林F對應(yīng)的二叉樹根結(jié)點的右子樹上的結(jié)點個數(shù)是A. m1B. m1+m2 C. m3 D. m2+m322.根據(jù)插

9、入次序（80，90，100，110，85，70，75，60，72）建立二叉排序樹。 圖（a ）是最終變化的結(jié)果。若仍以該插入次序建立平衡二叉樹。圖（c ）是最終變化的結(jié)果。/70八6075/728080a:/75八708090c:851060/7275 k八70/8590oo*10b:907523.設(shè)輸入序列為 20,45,30,89,70,38,62B-樹為（b ）。再刪除38,該B-樹為（(30 62(19，20)( 38 45）、）（70，89）a:）(89)(19)( 30八6072d:10085 5110,19依次插入到一棵2-3樹中（初始狀態(tài)為空），該f )。(45(30)）、（7

10、0）b:(62 )( 89 )(70)(19 )( 30,38(62 )( 89 )c:d:(70)(30 70)/I、(19, 20)( 45 62 )( 89 )(20/(19 )(45/)、(30 )、/(62 )、(89 )e:f:24.已知一組待排序的記錄關(guān)鍵字初始排列如下:（g）是快速排序法一趟排序的結(jié)果；a ）是希爾排序法（初始步長為 4）一趟排序的結(jié)果；b ）是初始堆（大堆頂）；d）是基數(shù)排序法一趟排序的結(jié)果。A. 27,34,11,25,45,43,87,66,67,78B.87,78,45,66,67,43,11,25,27,34C. 11,43,34,25,45,66,2

11、7,67,87,78D.11,43,34,45,25,66,87,67,27,78E. 34,45,25,67,43,11,66,27,78,87F.87,45,11,25,34,78,27,66,67,43G 27,34,11,25,43,45,67,66,87,78H.34,11,27,25,43,78,45,67,66,8745,34,87,25,67,43,11,66,27,78。34, 45, 57, 69, 77, 83, 92。對其進行 折半查找，則在等概率情況下，查找成功時的平均查找長度是 （c ）次比較。A. 1B. 2C. 3D. 426.設(shè)一棵二叉樹BT的存儲結(jié)構(gòu)如下：1

12、23 4567825.若有序表中關(guān)鍵字序列為：14, 20,25,32,（c ）。查找32時需進行第3層有（a）個結(jié)點（根結(jié)點為第A . 2B. 3C. 41層）D. 527. 一個連通圖的最小生成樹A .只有一棵 B.（b ）。有一棵或多棵C.定有多棵D. 可能不存在28.若某二叉樹有20個葉子結(jié)點，有20個結(jié)點僅有一個孩子，則該二叉樹的總結(jié)點數(shù)是（c）。A . 40B. 55C. 59D. 6129.已知哈希表地址空間為 沖突。若依次將數(shù)據(jù)序列： 下標為（f）;在等概率情況下查找成功的平均查找長度為A. 0B. 1C. 2D. 3A0.8，哈希函數(shù)為H（k）=k mod7,采用線性探測再散

13、列處理76,45,88,21,94,77,17存入該散列表中，則元素 17存儲的（c ）。E. 4F. 5G. 6H. 730.已知某有向圖的鄰接表存儲結(jié)構(gòu)如圖所示。? ?0EDCB1A1234n2*1 4根據(jù)存儲結(jié)構(gòu)，依教材中的算法其深度優(yōu)先遍歷次序為( 廣度優(yōu)先遍歷次序為( e )。各強連通分量的頂點集為(a: abede. b: edeba. e: eedab. d: eeadb.e: abe 及 ed f: ae 及 bed g: ab 及 eed 31.已知某無向圖的鄰接表如下所示；()是其原圖。()是按該鄰接表遍歷所得深度優(yōu)先生成樹。()是按該鄰接表遍歷所得廣度優(yōu)先生成樹。d ）。

14、h: be及aedE. a32.若順序表中各結(jié)點的查找概率不等,則可用如下策略提高順序查找的效率：若找到指定數(shù)據(jù)元素存儲空間，0號單元作監(jiān)視哨 表長度0。D. i=ST.le ngth和C同時滿足 H. B 和D同時滿足33 .下列函數(shù)為堆排序中的堆調(diào)整過程 請在“”處填上合適的內(nèi)容的結(jié)點，將該結(jié)點與其后繼(若存在)結(jié)點交換位置，使得經(jīng)常被查找的結(jié)點逐漸移至表尾。以下為據(jù)此策略編寫的算法，請選擇適當(dāng)?shù)膬?nèi)容，完成此功能。順序表的存儲結(jié)構(gòu)為：typ edef structElemT ype *elem; /int len gth; /SSTable;int search_seq(SSTable S

15、T, KeyTy pe key) /在順序表ST中順序查找關(guān)鍵字等于key的數(shù)據(jù)元素。/若找到，則將該元素與其后繼交換位置，并返回其在表中的位置，否則為ST.elem0.key=key;i=ST.le ngth;while(ST.elemi.key!=key) ;if( ) ST.elemi ST.elemi+1;return i;A. i0 B. i=0 C. iST.le ngthE. i+ F. i- G. A(調(diào)整H.rs的關(guān)鍵字，使H.rs.m成為一小頂堆)。 ,完成該算法。Void hea padjust( hea ptype & H , int s , int m ) rc=H.

16、rs;for (j=2*s;j=m;j*=2) if (jH.rj+1.key);b: !(c:(d: !(e:g:h:rc.keyv H.r|j.key);H.rj.keyH.rj.key);H.rs=rc; rc=H.rs; h.rj=rc; rc=H.rj;f:三算法設(shè)計題1. 單鏈表結(jié)點的類型定義如下：typedef struct LNode int data; struct LNode *next; LNode, *Linklist;寫一算法， Contrary(linklist &L) , 對一帶頭結(jié)點且僅設(shè)尾指針 L 的循環(huán)單鏈表 就地逆置。 (即表頭變表尾，表尾變表頭。 )2二叉樹用二叉鏈表存儲表示。typedef struct BiTNode TelemType data; Struct BiTNode *lchild, *rchild; BiTNode, *BiTree;試編寫銷毀二叉樹 T 的算法 DestroyBiTree ( BiTree &T) 。3設(shè)帶