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

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

3、,二叉樹是樹的特殊情形。 X20. 算法的時間復雜性越好,可讀性就越差；反之,算法的可讀性越好,則時間復雜性就越 差。 X.選擇題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. 遞歸程序可借助于a: 線性表 b:數(shù)組( b ) 轉(zhuǎn)化為非遞歸程序。 棧 c: 隊列 d:3. 在下列數(shù)據(jù)結構中(c )具有先進先出(FIFO)特性， ( b ) 具有先進后出 (FILO )特性。a: 線性表 b:棧 c:隊列 d:廣義表,8), 'bas&#

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

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

6、二叉排序樹（ b ）可得到有序序列。? ? a: 按層遍歷 b: 前序遍歷 c: 中序遍歷 d: 后序遍歷9已知某樹的先根遍歷次序為 abcdefg ，后根遍歷次序為 cdebgfa 。 若將該樹轉(zhuǎn)換為二叉樹 , 其后序遍歷次序為（ d ）。 a: abcdefg b: cdebgfa c: cdegbfa d: edcgfba10對一棵完全二叉樹進行層序編號。則編號為n 的結點若存在右孩子編號為n的結點若存在雙親，其位置是（a ）。a: n/2b: 2nc:2n-1d:2n+1 e:n, 其位序是 ( d ) 。f: 2(n+1)11關鍵路徑是指在只有一個源點和一個匯點的有向無環(huán)網(wǎng)中源點至匯

7、點（c ）的路徑。a: 弧的數(shù)目最多 b: 弧的數(shù)目最少 c: 權值之和最大 d: 權值之和最小12. 哈希表的查找效率取決于（ d ）。 a:哈希函數(shù) b: 處理沖突的方法。13從邏輯上可以把數(shù)據(jù)結構分成（ c ） 。A. 動態(tài)結構和靜態(tài)結構B.C. 線性結構和非線性結構D.c: 哈希表的裝填因子。 d: 以上都是順序組織和鏈接組織基本類型和組合類型14在計算遞歸函數(shù)時，如不用遞歸過程，應借助于（ b ） 這種數(shù)據(jù)結構。A. 線性表 B.棧C.隊列 D.雙向隊列15若已知某二叉樹的中序和后序遍歷序列分別BCAEFD 和 CBFEDA ，則該二叉樹的先序序列為 （ a ） 。A. ABCDEF

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

9、 設森林F中有三棵樹，第一、第二和第三棵樹的結點個數(shù)分別為 森林F對應的二叉樹根結點的右子樹上的結點個數(shù)是（d）。A. m1B. m1+m2 C. m3 D. m2+m322.根據(jù)插入次序（80, 90, 100, 110, 85, 70, 75, 60, 72）建立二叉排序樹。 圖（a ）是最終變化的結果。若仍以該插入次序建立平衡二叉樹。圖（c ）是最終變化的結果。110a:b:100Woc:d:23.設輸入序列為 20,45,30,89,70,38,62,19依次插入到一棵2-3樹中（初始狀態(tài)為空）,B-樹為（b ）。再刪除38,該B-樹為（19, 20）（ 38 45）（ 70 , 89

10、 ）（45）（30 /）（70 ）（19 20 ）（38 ）（62 ）（ 89b:（八45）、（20 ）（70 ）（19 ）（ 30,38）（62 ）（ 89 ）c:d:(3070)(19, 20)( 45 62 )( 89 )(45)f:e:B. 3C. 4D. 5（g）是快速排序法一趟排序的結果；（a ）疋希爾排序法（初始步長為4）一趟排序的結果；（b ）是初始堆（大堆頂）；（d）是基數(shù)排序法一趟排序的結果。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,27,67,87

11、,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,8724.已知一組待排序的記錄關鍵字初始排列如下:45,34,87,25,67,43,11,66,27,78。25若有序表中關鍵字序列為：14，20，25，32，34，45，57，69，77，83，92。對其進行折半查找，則在等概率情況下，查找成功時的平均查找長度是（c ）。查找32

12、時需進行（c ）次比較。A. 1B. 2C. 3D. 426.設一棵二叉樹BT的存儲結構如下：123 45678lchild 23data A 1rchild 050)60 003 CD EFG H40 87 00其中Ichild ，rchild 分別為結點的左、右孩子指針域，data為結點的數(shù)據(jù)域。則該二叉樹的高度為（d ）；第3層有（a ）個結點（根結點為第1層）。27. 一個連通圖的最小生成樹（b ）。A .只有一棵B. 有一棵或多棵C.定有多棵D.可能不存在28. 若某二叉樹有20個葉子結點，有20個結點僅有一個孩子，則該二叉樹的總結點數(shù)是（c）。A . 40B. 55C. 59D.

13、6129. 已知哈希表地址空間為A0.8，哈希函數(shù)為 H（k）=k mod7，采用線性探測再散列處理沖突。若依次將數(shù)據(jù)序列：76,45,88,21,94,77,17存入該散列表中，則元素 17存儲的下標為（f）;在等概率情況下查找成功的平均查找長度為（c）。A. 0B. 1C. 2D. 3E. 4F. 5G. 6H. 730已知某有向圖的鄰接表存儲結構如圖所示。? 012342根據(jù)存儲結構，依教材中的算法其深度優(yōu)先遍歷次序為( 廣度優(yōu)先遍歷次序為( c )。各強連通分量的頂點集為(a: abcde. b: edcba. c: ecdab. d: ecadb.e: abc 及 ed f: ac及

14、 bed g: ab 及 ced31.已知某無向圖的鄰接表如下所示;0a3 _>1 2丨 1丨丨1 b3 一2(4 一3rr>i n3(14 e5 _廠ali5 f4 _羅>i丨i()_是其原圖。()_是按該鄰接表遍歷所得深度優(yōu)先生成樹。() 是按該鄰接表遍歷所得廣度優(yōu)先生成樹。B. a b c d e fC. a b c dI Ief4A0Ah: bc）。及aedE. a bc dF. abf ee fe f32 若順序表中各結點的查找概率不等，則可用如下策略提高順序查找的效率：若找到指定的結點，將該結點與其后繼(若存在)結點交換位置，使得經(jīng)常被查找的結點逐漸移至表尾。以下

15、為據(jù)此策略編寫的算法，請選擇適當?shù)膬?nèi)容，完成此功能。順序表的存儲結構為：typedef structElemType *elem; /數(shù)據(jù)元素存儲空間，0號單元作監(jiān)視哨int len gth; /表長度SSTable;int search_seq(SSTable ST, KeyType key) /在順序表ST中順序查找關鍵字等于key的數(shù)據(jù)元素。/若找到，則將該元素與其后繼交換位置，并返回其在表中的位置，否則為0。ST.elem0.key=key;i=ST.le ngth;while(ST.elemi.key!=key) ;if( ) ST.elemi<-> ST.elemi+1

16、;return i;A. i>0 B. i>=0 C. i<ST.le ngthD. i<=ST.le ngthE. i+ F. i- G. A和C同時滿足 H. B 和D同時滿足33.下列函數(shù)為堆排序中的堆調(diào)整過程(調(diào)整H.rs的關鍵字，使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

17、=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;f:rc=H.rs;g: h.rj=rc;h: rc=H.rj;算法設計題1. 單鏈表結點的類型定義如下：typedef struct LNode int data; struct LNode *next; LNode, *Linklist;寫一算法， Contrary(linklist &L) , 對一帶頭結點且僅設尾指針 L 的循環(huán)單鏈表 就地逆置。 (即表頭變表尾，表尾變表頭。 )2二叉樹用二叉鏈表存儲表示。typedef struct BiTNode TelemType data; Struct BiTNode *lchild, *rchild; BiTNode, *BiTree;試編寫銷毀二叉樹 T 的算法 DestroyBiTree ( BiTr