數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題附答案

1、一是非題1. 數(shù)據(jù)結(jié)構(gòu)(應(yīng)該是抽象數(shù)據(jù)類型)可用三元式表示(D，S，P)。其中：D是數(shù)據(jù)對(duì)象，S是D上的關(guān)系，P是對(duì)D的基本操作集。(f)2 簡(jiǎn)單地說(shuō),數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合。(t)3 判斷帶頭結(jié)點(diǎn)的非空循環(huán)單鏈表(頭指針為L(zhǎng))中指針p所指結(jié)點(diǎn)是最后一個(gè)元素結(jié)點(diǎn)的條件是：p-next=L。(t)4 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)具有可直接存取表中任一元素的優(yōu)點(diǎn)。(f) 5 線性表的順序存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。(f)6. 在單鏈表P指針?biāo)附Y(jié)點(diǎn)之后插入S結(jié)點(diǎn)的操作是：P-next= S ; S- next = P-next;。(f)(順序弄反了S- next = P-next; P-next

2、= S ;)7 對(duì)于插入、刪除而言，線性表的鏈?zhǔn)酱鎯?chǔ)優(yōu)于順序存儲(chǔ)。(t)8. 順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。(f)9. 棧和隊(duì)列是操作上受限制的線性表。(t)10. 隊(duì)列是與線性表完全不同的一種數(shù)據(jù)結(jié)構(gòu)。(f)(棧和隊(duì)列是操作上受限制的線性表)11. 隊(duì)列是一種操作受限的線性表，凡對(duì)數(shù)據(jù)元素的操作僅限一端進(jìn)行。(f) (兩端)12. 棧和隊(duì)列也是線性表。如果需要，可對(duì)它們中的任一元素進(jìn)行操作。(f)( “如果需要,可對(duì)它們中的任一元素進(jìn)行操作.” 這里的意思是在O(1)的時(shí)間來(lái)讀和改某個(gè)元素。比如數(shù)組的直接索引。棧：如果需要，每一次只能對(duì)棧頂?shù)脑剡M(jìn)行操作隊(duì)列：如果需

3、要，每一次只能對(duì)兩端，或者只能對(duì)隊(duì)列頭的元素進(jìn)行操作。)13. 棧是限定僅在表頭進(jìn)行插入和表尾進(jìn)行刪除運(yùn)算的線性表。(f)14. 二叉樹(shù)中每個(gè)結(jié)點(diǎn)有兩個(gè)子結(jié)點(diǎn)，而對(duì)一般的樹(shù)，則無(wú)此限制，所以，二叉樹(shù)是樹(shù)的 特殊情形。(f)(二叉樹(shù)和樹(shù)相互獨(dú)立)15 二叉樹(shù)是一棵結(jié)點(diǎn)的度最大為二的樹(shù)。(f) (二叉樹(shù)和樹(shù)相互獨(dú)立)16 赫夫曼樹(shù)中結(jié)點(diǎn)個(gè)數(shù)一定是奇數(shù)。(t)17 在二叉樹(shù)的中序遍歷序列中，任意一個(gè)結(jié)點(diǎn)均處在其左孩子結(jié)點(diǎn)的后面。(t)(LDR)18 假設(shè)B是一棵樹(shù)，B是對(duì)應(yīng)的二叉樹(shù)。則B的后根遍歷相當(dāng)于B的后序遍歷 。(f)(后根遍歷相當(dāng)于中序遍歷)19. 通常，二叉樹(shù)的第i層上有2i-1個(gè)結(jié)點(diǎn)。(

4、f)(應(yīng)該為12i-1個(gè))20. 中序線索二叉樹(shù)的優(yōu)點(diǎn)是便于在中序下查找直接前驅(qū)結(jié)點(diǎn)和直接后繼結(jié)點(diǎn)。(t)21 二叉樹(shù)的先序遍歷序列中，任意一個(gè)結(jié)點(diǎn)均處在其孩子結(jié)點(diǎn)的前面。(t)22 由樹(shù)結(jié)點(diǎn)的先根序列和后根序列可以唯一地確定一棵樹(shù)。(t)23 鄰接多重表可以用以表示無(wú)向圖，也可用以表示有向圖。(f)(只能表示無(wú)向圖，有向圖用十字鏈表)24 可從任意有向圖中得到關(guān)于所有頂點(diǎn)的拓?fù)浯涡颉?f)(帶環(huán)圖沒(méi)有)25 有向圖的十字鏈表是將鄰接表和逆鄰接表合二為一的鏈表表示形式。(t)26 關(guān)鍵路徑是AOE網(wǎng)中源點(diǎn)到匯點(diǎn)的最短路徑。(f)(最長(zhǎng))27 連通圖G的生成樹(shù)是一個(gè)包含G的所有n個(gè)頂點(diǎn)和n-1條

5、邊的子圖。(f)（極大連通子圖）28 一個(gè)無(wú)向圖的連通分量是其極大的連通子圖。(t)29 十字鏈表可以表示無(wú)向圖，也可用以表示有向圖。(f)(有向圖)30 鄰接表可以表示有向圖，也可以表示無(wú)向圖。(t)31. 二叉排序樹(shù)的平均查找長(zhǎng)度為O(log)。(t)32. 二叉排序樹(shù)的最大查找長(zhǎng)度與(LOG2N)同階。(f)33 選用好的HASH函數(shù)可避免沖突。(f)(無(wú)法避免，只能減少?zèng)_突)34 折半查找不適用于有序鏈表的查找。(t)(因鏈表地址不連續(xù))35. 對(duì)于目前所知的排序方法，快速排序具有最好的平均性能。(t)36 對(duì)于任何待排序序列來(lái)說(shuō)，快速排序均快于冒泡排序。(f)(快速排序希望初始數(shù)據(jù)隨

6、機(jī))37 在最壞情況下，堆排序的時(shí)間性能是O(nlogn),比快速排序好(t)(堆排序與初始數(shù)據(jù)無(wú)關(guān))38 快速排序具有最好的平均時(shí)間性能，它在任何時(shí)候的時(shí)間復(fù)雜度都是O(n log n)。(f)(退化到n2)39. 字符串是數(shù)據(jù)對(duì)象特定的線性表。(t)40. 空串與空格串是相同的。(f)(空串長(zhǎng)度為0，空格串長(zhǎng)度為其長(zhǎng)度)41. 對(duì)于一棵m階的B-樹(shù).樹(shù)中每個(gè)結(jié)點(diǎn)至多有m 個(gè)關(guān)鍵字.除根之外的所有非終端結(jié)點(diǎn)至 少有m/2個(gè)關(guān)鍵字。(f)(至少有m顆子樹(shù)，關(guān)鍵字?jǐn)?shù)目至少m-1)42. 當(dāng)二叉排序樹(shù)是一棵平衡二叉樹(shù)時(shí)，其平均查找長(zhǎng)度為O(log2n)。(t)43. 廣義表的表頭和表尾都是廣義表。

7、(f)(表頭可能是原子，也可能是列表，而其表尾必定為列表)44 二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表。(t)選擇題。1 從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成( c )。 A. 動(dòng)態(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)實(shí)現(xiàn)。 A. 不需修改L的結(jié)構(gòu) B. 需不斷對(duì)L進(jìn)行刪除、插入 C. 需經(jīng)常修改L中結(jié)點(diǎn)值 D. L中含有大量結(jié)點(diǎn)3 帶頭結(jié)點(diǎn)的單鏈表L為空的判斷條件是 b 。 帶頭結(jié)點(diǎn)的循環(huán)鏈表L為空的判斷條件是 c 。 A. L=null B. L-next=null C. L-next=L D. L

8、!=null4 若順序表中各結(jié)點(diǎn)的查找概率不等，則可用如下策略提高順序查找的效率：若找到指定 的結(jié)點(diǎn)，將該結(jié)點(diǎn)與其后繼(若存在)結(jié)點(diǎn)交換位置，使得經(jīng)常被查找的結(jié)點(diǎn)逐漸移至 表尾。以下為據(jù)此策略編寫的算法，請(qǐng)選擇適當(dāng)?shù)膬?nèi)容，完成此功能。 順序表的存儲(chǔ)結(jié)構(gòu)為：typedef struct ElemType *elem; /數(shù)據(jù)元素存儲(chǔ)空間，0號(hào)單元作監(jiān)視哨 int length; /表長(zhǎng)度 SSTable;int search_seq(SSTable ST,KeyType key) /在順序表ST中順序查找關(guān)鍵字等于key的數(shù)據(jù)元素。/若找到，則將該元素與其后繼交換位置，并返回其在表中的位置，否則

9、為0。ST.elem0.key=key;i=ST.length;while(ST.elemi.key!=key) f ;if( G ) ST.elemiST.elemi+1； e ； return i;A. i0 B. i=0 C. iST.length D. i哈夫曼樹(shù)25 已知某二叉樹(shù)的后序遍歷和中序遍歷次序分別為DBFGECA和BDACFEG。則其先序遍歷次序?yàn)? b )，層次遍歷次序?yàn)? a )。a: abcdefg b: abdcefg c: abcdfeg d: abcdegf后序：DB FGEC A誰(shuí)后訪問(wèn)誰(shuí)是根 L R D中序：BD A CFEG L D R (A) (B) (

10、C) (D) (E) / (F) (G)26 已知某樹(shù)的先根遍歷次序?yàn)閍bcdefg后根遍歷次序?yàn)閏debgfa。 若將該樹(shù)轉(zhuǎn)換為二叉樹(shù),其后序遍歷次序?yàn)? d )。a: abcdefg b: cdebgfa c: cdegbfa d: edcgfba先根：a bcdefg后根：cdebgf a (a) (b) (f) / | (c) (d) (e) (g)27 設(shè)x和y是二叉樹(shù)中的任意兩個(gè)結(jié)點(diǎn)，若在先根序列中x在y之前，而在后根序列中x 在y之后，則x和y的關(guān)系是( c )。 A. x是y的左兄弟 B. x是y的右兄弟 C. x是y的祖先(不一定是父子) D. x是y的子孫28 用三叉鏈表作

11、二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，當(dāng)二叉樹(shù)中有n個(gè)結(jié)點(diǎn)時(shí)，有( d )個(gè)空指針。 A. n-1 B. n C. n+1 D. n+2三叉鏈表：較二叉鏈表多一雙親指針域二叉鏈表：2n - (n-1) = n+12n個(gè)指針域 有效指針域根節(jié)點(diǎn)雙親指針必為空，故n+1+1=n+229 對(duì)一棵完全二叉樹(shù)進(jìn)行層序編號(hào)。則編號(hào)為n的結(jié)點(diǎn)若存在右孩子,其位序是( d )。 編號(hào)為n的結(jié)點(diǎn)若存在雙親,其位置是( a )。 a: n/2 b: 2n c:2n-1 d:2n+1 e:n f: 2(n+1)30 設(shè)森林F中有三棵樹(shù)，第一、第二和第三棵樹(shù)的結(jié)點(diǎn)個(gè)數(shù)分別為m1、m2和m3，則與 森林F對(duì)應(yīng)的二叉樹(shù)根結(jié)點(diǎn)的右子樹(shù)上的結(jié)點(diǎn)

12、個(gè)數(shù)是( d )。A. m1 B. m1+m2 C. m3 D. m2+m3(A) (B) (C)/ / / m1 m2 m3(A)/ (左) (右) m-1 m2+m331 下列二叉樹(shù)中，( a )可用于實(shí)現(xiàn)符號(hào)不等長(zhǎng)高效編碼。 a:最優(yōu)二叉樹(shù) b:次優(yōu)查找樹(shù) c:二叉平衡樹(shù) d:二叉排序樹(shù)哈夫曼樹(shù)32 鄰接表存儲(chǔ)結(jié)構(gòu)下圖的深度優(yōu)先遍歷算法類似于二叉樹(shù)的(a )遍歷。 A. 先根 B. 中根 C. 后根 D. 層次33 設(shè)無(wú)向圖G = (V,E)和G= (V,E)，若G是G的生成樹(shù)，則下面不正確的說(shuō)法是( b )。 A. G是G的子圖 B. G是G的連通分量 C. G是G的無(wú)環(huán)子圖 D. G

13、是G的極小連通子圖且V= V生成樹(shù)：極小連通分量：極大34 任何一個(gè)連通圖的最小生成樹(shù)( b )。 A只有一棵 B. 有一棵或多棵 C. 一定有多棵 D. 可能不存在35 深度優(yōu)先遍歷圖使用了數(shù)據(jù)結(jié)構(gòu)(b )，而廣度優(yōu)先遍歷圖使用了數(shù)據(jù)結(jié)構(gòu)( c )。A)數(shù)組 B)棧 C)隊(duì)列 D)線性表DFS：棧（遞歸）BFS：隊(duì)列（層次）36 已知某有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如圖所示。 0 E 2 1 1 D 0 3 4 2 C 43 B 1 2 0 4 A 2 根據(jù)存儲(chǔ)結(jié)構(gòu)依教材中的算法其深度優(yōu)先遍歷次序?yàn)? d )。 廣度優(yōu)先遍歷此序?yàn)? c )。各強(qiáng)連通分量的頂點(diǎn)集為( h )。 a: abcde. b

14、: edcba. c: ecdab. d: ecadb. e: abc及ed f: bc及aed g: ab及ced h: ac及bed37 下列查找方法中( a )適用于查找單鏈表。 A)順序查找 B)折半查找 C)分塊查找 D)hash查找38 下列算法中(c )適用于求圖的最小代價(jià)生成樹(shù)。( b )能對(duì)圖作廣度優(yōu)先遍歷。 A)DFS算法 B)BFS算法 C)Prim算法 D)Dijkstra算法39 關(guān)鍵路徑是指在只有一個(gè)源點(diǎn)和一個(gè)匯點(diǎn)的有向無(wú)環(huán)網(wǎng)中源點(diǎn)至匯點(diǎn)( c )的路徑。 a:弧的數(shù)目最多 b:弧的數(shù)目最少 c:權(quán)值之和最大 d:權(quán)值之和最小40 哈希表的查找效率取決于( d )。

15、a: 哈希函數(shù) b:處理沖突的方法。 c:哈希表的裝填因子。 d:以上都是 哈希函數(shù)是否均勻； 處理沖突的方法； 哈希表的裝填因子。41 在Hash函數(shù)H(k)=k MOD m中，一般來(lái)說(shuō)，m應(yīng)取( c )。 A. 奇數(shù) B. 偶數(shù) C. 素?cái)?shù) D. 充分大的數(shù)素?cái)?shù)可以有效的減少Hash沖突42 在順序表查找中，為避免查找過(guò)程中每一步都檢測(cè)整個(gè)表是否查找完畢， 可采用 a 方法。 A.設(shè)置監(jiān)視哨 B.鏈表存貯 C.二分查找 D.快速查找43 靜態(tài)查找表和動(dòng)態(tài)查找表的區(qū)別在于( b )。 A. 前者是順序存儲(chǔ)，而后者是鏈?zhǔn)酱鎯?chǔ) B. 前者只能進(jìn)行查找操作，而后者可進(jìn)行查找、插入和刪除操作 C.

16、前者只能順序查找，而后者只能折半查找D. 前者可被排序，而后者不能被排序動(dòng)態(tài)查找表在查找過(guò)程中插入元素或者從查找表中刪除元素靜態(tài)查找表只是查找特定元素或者檢索特定元素的屬性最通俗的解釋：動(dòng)態(tài)查找表可以對(duì)查找表結(jié)構(gòu)進(jìn)行修改，而靜態(tài)查找表只是查詢44 在一個(gè)含有n個(gè)元素的有序表上進(jìn)行折半查找，找到一個(gè)元素最多要進(jìn)行( b )次元素 比較。 Alog2(n) B. log2(n)+1 C. log2(n+1) D. log2(n+1)+1折半查找每次都會(huì)把范圍縮小一半，因?yàn)樽詈笫Ｒ粋€(gè)元素時(shí)，也要執(zhí)行查找過(guò)程，所以+1。每次二分直到最后一次才找到就會(huì)有2k=n/2得到k=log2n+145 設(shè)輸入序列

17、為20, 45, 30, 89, 70, 38, 62，19依次插入到一棵2-3樹(shù)中(初始狀態(tài)為空)， 該B-樹(shù)為( b )。再刪除38，該B-樹(shù)為( f )。 （ 30 62 ） （ 45 ） （19，20）（ 38 45 ） （ 70，89 ） （ 30 ） （ 70 ） （19 20） （38 ）（ 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

18、） （ 89 ） （ 20 ） （ 70 ） （19 ） （30 ）（ 62 ） （ 89 ） e: f:46根據(jù)插入次序(80，90，100，110，85，70，75，60，72)建立二叉排序樹(shù)。 圖( a )是最終變化的結(jié)果。若仍以該插入次序建立平衡二叉樹(shù)。圖( 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:47 若有序表中關(guān)鍵字序列為：14，20，25，3

19、2，34，45，57，69，77，83，92。對(duì)其進(jìn)行 折半查找，則在等概率情況下，查找成功時(shí)的平均查找長(zhǎng)度是( c )。查找32時(shí)需進(jìn) 行( c )次比較。A. 1 B. 2 C. 3 D. 4 48 已知哈希表地址空間為A9，哈希函數(shù)為H(k)=k mod 7，采用線性探測(cè)再散列處理沖突。 若依次將數(shù)據(jù)序列：76,45,88,21,94,77,17存入該散列表中，則元素17存儲(chǔ)的下標(biāo)為( h )； 在等概率情況下查找成功的平均查找長(zhǎng)度為( c )。 A. 0 B. 1 C. 2 D. 3 E. 4 F. 5 G. 6 H. 749 若從二叉樹(shù)的根結(jié)點(diǎn)到其它任一結(jié)點(diǎn)的路徑上所經(jīng)過(guò)的結(jié)點(diǎn)序列按

20、其關(guān)鍵字遞增有序， 則該二叉樹(shù)是( c )。 A. 二叉排序樹(shù) B. 赫夫曼樹(shù) C. 堆 D. 平衡二叉樹(shù)50 當(dāng)待排序序列的關(guān)鍵字次序?yàn)榈剐驎r(shí)，若需為之進(jìn)行正序排序，下列方案中( d )為佳。 A. 起泡排序 B. 快速排序 C. 直接插入排序 D. 簡(jiǎn)單選擇排序51 下列排序算法中，( d)算法可能會(huì)出現(xiàn)：初始數(shù)據(jù)有序時(shí)，花費(fèi)的時(shí)間反而最多。 A. 堆排序 B. 起泡排序 C. 歸并排序 D. 快速排序52 在下列排序方法中，( c )方法平均時(shí)間復(fù)雜度為0(nlogn)， 最壞情況下時(shí)間復(fù)雜度為0(n2)；( d )方法所有情況下時(shí)間復(fù)雜度均為0(nlogn)。 a. 插入排序 b. 希

21、爾排序 c. 快速排序 d. 堆排序 53 已知一組待排序的記錄關(guān)鍵字初始排列如下：56,26,86,35,75,19,77,58,48,42下列選擇中( d )是快速排序一趟排序的結(jié)果。( c )是希爾排序(初始步長(zhǎng)為3)一趟排序的結(jié)果。( a )是初始堆(大堆頂)。 A)86,75,77,58,42,19,56,35,48,26. B)26,56,35,75,19,77,58,48,42,86. C)35,26,19,42,58,48,56,75,86,77. D)42,26,48,35,19,56,77,58,75,86.三填空題1 數(shù)據(jù)結(jié)構(gòu)通常有下列4類基本結(jié)構(gòu)：集合、線性結(jié)構(gòu) 、樹(shù)型

22、結(jié)構(gòu)、圖型結(jié)構(gòu)。2 設(shè)單鏈表中結(jié)點(diǎn)形式為 data next ，若單鏈表長(zhǎng)度大于等于2，指針p指向表中某個(gè)結(jié)點(diǎn)且p-next非空，此時(shí)若要?jiǎng)h除指針p所指的結(jié)點(diǎn)，可以通過(guò)如下方法進(jìn)行：將p所指結(jié)點(diǎn)的后繼的元素值復(fù)制到該結(jié)點(diǎn)，然后刪除其后繼結(jié)點(diǎn)。相應(yīng)的語(yǔ)句序列為：p-data=p-next-data；p-next=p-next-next；free(p-next)； ；3 線性表的順序存儲(chǔ)結(jié)構(gòu)是以數(shù)組下標(biāo)來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系的。4 已知P是單鏈表中某一結(jié)點(diǎn)的指針，P既不是首元結(jié)點(diǎn)也不是尾元結(jié)點(diǎn)，Q是P 的 前驅(qū) 結(jié)點(diǎn)指針。當(dāng)刪除P結(jié)點(diǎn)時(shí)，鏈表的鏈接可用語(yǔ)句(q-next = p-next)實(shí)

23、現(xiàn)。5 已知某樹(shù)的先根遍歷次序?yàn)閍bcdefg后根遍歷次序?yàn)閏debgfa。 若將該樹(shù)轉(zhuǎn)換為二叉樹(shù),其后序遍歷次序?yàn)?edcgfba)。層次遍歷次序?yàn)?abcfdge)。6 已知某二叉樹(shù)的先序遍歷次序?yàn)閍fbcdeg中序遍歷次序?yàn)閏edbgfa。 其后序遍歷次序?yàn)?edcgbfa)。層次遍歷次序?yàn)?afbcgde)。7 在二叉樹(shù)的第i層上至少有1個(gè)結(jié)點(diǎn), 至多有2i-1個(gè)結(jié)點(diǎn) , 深度為k的二叉樹(shù)至多有2i-1個(gè)結(jié)點(diǎn).8 對(duì)樹(shù)的遍歷有先序遍歷樹(shù)和后序遍歷樹(shù)。若以二叉鏈表作樹(shù)的存儲(chǔ)結(jié)構(gòu), 則樹(shù)的先序遍歷可借用二叉樹(shù)的先序遍歷算法來(lái)實(shí)現(xiàn), 而樹(shù)的后序遍歷可借用二叉樹(shù)的中序遍歷算法來(lái)實(shí)現(xiàn)。9 設(shè)高度

24、為h的二叉樹(shù)上只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹(shù)中所包含的結(jié)點(diǎn)數(shù)至少 是2*h-1，至多是滿樹(shù)。10 對(duì)任何一棵二叉樹(shù)T,若其終端結(jié)點(diǎn)數(shù)為n0.度為2的結(jié)點(diǎn)為n2,則n0與n2的關(guān)系為 (n0=n2+1)。11 如果對(duì)完全二叉樹(shù)中結(jié)點(diǎn)從1開(kāi)始按層進(jìn)行編號(hào)，設(shè)最大編號(hào)為n；那么，可以斷定編 號(hào)為i (i1)的結(jié)點(diǎn)的父結(jié)點(diǎn)編號(hào)為(i/2向下取整)；所有編號(hào)(in/2)的結(jié)點(diǎn)為葉子結(jié)點(diǎn)。 12 n個(gè)頂點(diǎn)的連通圖至少有n-1條邊，至多有n(n-1)/2條邊。13 對(duì)于圖的存儲(chǔ)結(jié)構(gòu)有(數(shù)組表示法)、(鄰接表法)、(十字鏈表法)、(鄰接多重表法)等方法。14 在一個(gè)無(wú)向圖的鄰接表中，若表結(jié)點(diǎn)的個(gè)數(shù)是m

25、，則圖中邊的條數(shù)是m/2條。15 若有序表中關(guān)鍵字序列為：12，22，33，44，55，66，77，88，99對(duì)其進(jìn)行折半查找， 則在等概率情況下，查找成功時(shí)的平均查找長(zhǎng)度是(3)。查找99時(shí)需進(jìn)行(2)次比較。16 在哈希表中，處理沖突的方法有開(kāi)放定址法，再哈希法，鏈地址法等。17 在二叉樹(shù)的第i層上至少有1個(gè)結(jié)點(diǎn), 至多有2i-1個(gè)結(jié)點(diǎn) ,深度為k的二叉樹(shù)至多有2k-1個(gè)結(jié)點(diǎn).18 對(duì)于一棵高度為K的二叉排序樹(shù)，結(jié)點(diǎn)數(shù)最少可有 個(gè)，最多可有 個(gè)。19 用中序遍歷對(duì)二叉排序樹(shù)進(jìn)行訪問(wèn)可得到有序序列。20 已知Hash函數(shù)為 H(K)=K mod 13 ，散列地址為0 -14，用二次探測(cè)再散列

26、 處理沖突，關(guān)鍵字(23，34，56，24，75，12，49, 52，36，92) 的分布如圖，則平均成功的查找長(zhǎng)度為( )、平均失敗的查找長(zhǎng)度為( )。 0 1 2 3 4 5 6 7 8 9 10 11 12 13 1452 36925634 232475124921 一棵階的-樹(shù)，第一層至少有一個(gè)結(jié)點(diǎn)；第二層至少有2個(gè)結(jié)點(diǎn)， 除根之外的所有非終端結(jié)點(diǎn)至少有(m/2)棵子樹(shù)， 樹(shù)中每個(gè)結(jié)點(diǎn)至多有( m )棵子樹(shù)。22 在哈希表中，處理沖突的方法有開(kāi)放定址法，再哈希法，鏈地址法，建立一個(gè)公共溢出區(qū)。23 哈希表的查找效率取決于(哈希函數(shù)是否均勻)(處理沖突的方法)和(哈希表的裝填因子)。24

27、高度為4 (包含不帶關(guān)鍵字的葉子結(jié)點(diǎn)層)的7階B樹(shù)最少有m/2-1個(gè)關(guān)鍵字，最多有m-1個(gè)關(guān)鍵字；如果其中的某結(jié)點(diǎn)正好有2個(gè)兒子，那么，該結(jié)點(diǎn)必定是 結(jié)點(diǎn)。25 對(duì)n個(gè)元素的序列進(jìn)行內(nèi)部排序，若用起泡排序法，最少的比較次數(shù)是n-1，最多的比較次數(shù)是n(n-1)/2。25 (算法填空)Status Preordertraverse(Bitree T,Status(*Visit)(Telemtype e) /先序非遞歸遍歷二叉樹(shù)。Initstack ( S ); Push ( S,T );While ( !stackempty( S ) ) While ( gettop( S, p )&p) if

28、 (!Visit (p-data ) ) return ERROR; push(S,p-lchild) ; Pop ( S , p ); if (!StackEmpty(S) Pop(s,p); push( S, p-rchild ); return ok;26 (算法填空)下列算法試圖完成在數(shù)組A中搜索有無(wú)關(guān)鍵字key，若有，返回?cái)?shù)組下標(biāo),若無(wú)，返回-1。在“ ”處填上合適的內(nèi)容,完成該算法。int BinarySearch (keytype A , int low,int high, keytype key )while (low = high) middle = (low+high) /2;if (Amiddle = key) return middle; if (key Amiddle) high = middle -1; else low = middle +1;return -1; /end of BinarySearch27 (算法填空)下列函數(shù)為堆排序中的堆調(diào)整過(guò)程(調(diào)整H.rs的關(guān)鍵字