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

1、百度文庫(kù)-讓每個(gè)人平等地提升自我1一是非題I.數(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ù)元素的集合。3 判斷帶頭結(jié)點(diǎn)的非空循環(huán)單鏈表(頭指針為 L)中指針 p 所指結(jié)點(diǎn)是最后一個(gè)元素結(jié)點(diǎn)的條件是：p-next=L。(t)4 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)具有可直接存取表中任一元素的優(yōu)點(diǎn)。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

2、- next = P-n ext; P- next= S ;)7對(duì)于插入、刪除而言，線性表的鏈?zhǔn)酱鎯?chǔ)優(yōu)于順序存儲(chǔ)。8.順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。(f)9.棧和隊(duì)列是操作上受限制的線性表。10.隊(duì)列是與線性表完仝不同的一種數(shù)據(jù)結(jié)構(gòu)。(f)(棧和隊(duì)列是操作上受限制的線性表)II.隊(duì)列是一種操作受限的線性表，凡對(duì)數(shù)據(jù)元素的操作僅限一端進(jìn)行。(f)(兩端)12.棧和隊(duì)列也是線性表。如果需要，可對(duì)- (f)(女“果需要，可對(duì)它們中的任一元素進(jìn)行操作 .”這里的意思是在 0(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.二叉樹中每個(gè)結(jié)點(diǎn)有兩個(gè)子結(jié)點(diǎn)，而對(duì)一般的樹，則無(wú)此限制，所以，-特殊情形。(f)(二叉樹和樹相互獨(dú)立)15 二叉樹是一棵結(jié)點(diǎn)的度最大為二的樹。(二叉樹和樹相互獨(dú)立)16赫夫曼樹中結(jié)點(diǎn)個(gè)數(shù)一定是奇數(shù)。17 在二叉樹的中序遍歷序列中，任意一個(gè)結(jié)點(diǎn)均處在其左孩子結(jié)點(diǎn)的后面。(LDR)18 假設(shè) B 是一棵樹，B是對(duì)應(yīng)的二叉樹。則 B 的后根遍歷相當(dāng)于 B的后序遍歷。(f) (后根遍歷相當(dāng)于中序遍歷)19.通常，二叉樹的第 i 層上有 2-1個(gè)結(jié)點(diǎn)。(應(yīng)該為 12i-1個(gè))2

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

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

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

7、44 二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表。選擇題。1 從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成(_C_J。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 。百度文庫(kù)-讓每個(gè)人平等地提升自我4A. L=nullC. L-n ext=LB. L-n ext=nullD. L!=null百度文庫(kù)-讓每個(gè)人平等地提升自我

8、54 若順序表中各結(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 structElemType *elem; ey=key;i=;whilei.key!=key）if（G 一）i f i+1；eE,則下列（d）出棧序列是不可能的。B . B、C、D、A、ED. D、E、C、A、B）轉(zhuǎn)化為非遞歸程序。c:棧d.數(shù)組）具有先進(jìn)先出（FIFO）特性，（b ）具有先進(jìn)后出（FILO）特性。a.線性表b.棧c.隊(duì)

9、列d. 廣義表若對(duì)編號(hào)為 1, 2, 3 的列車車廂依次通過(guò)扳道棧進(jìn)行調(diào)度，不能得到a:1,2,3b:1,3,2c:2,1,3d:2,3,1e:3,1,2f:3,2,1在計(jì)算遞歸函數(shù)時(shí)，如不用遞歸過(guò)程，應(yīng)借助于LbX 這種數(shù)據(jù)結(jié)構(gòu)。A.線性表B.棧C.隊(duì)列D.雙向隊(duì)列I 若帶頭結(jié)點(diǎn)的鏈表只設(shè)尾結(jié)點(diǎn)指針。下列選擇中（c ）最適用于隊(duì)列。A）單鏈表 B）雙向鏈表 C 循環(huán)單鏈表D）雙向循環(huán)鏈表?xiàng)：完?duì)列的一個(gè)共同點(diǎn)是（c ）A.都是先進(jìn)先出C.只允許在端點(diǎn)處插入和刪除元素 !循環(huán)隊(duì)列用數(shù)組 A0.m-1存放其元素值， 的元素個(gè)數(shù)是（c ） A. rear-fr on t-1C. （rear-fro

10、nt+m）%mreturn i;A.i0B. i=0E.i+F.i-5若入棧順序?yàn)锳、B、C、C. iD. i 哈夫曼樹25 已知某二叉樹的后序遍歷和中序遍歷次序分別為 則其先序遍歷次序?yàn)椋╞ ）,層次遍歷次序?yàn)椋╝a: abcdefg b: abdcefg c: abcdfeg若將該樹轉(zhuǎn)換為二叉樹，其后序遍歷次序?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 是二叉樹中的任意兩個(gè)結(jié)點(diǎn)，若在先根序列中x 在 y 之前

11、，而在后根序列中x在 y 之后，則 x 和 y 的關(guān)系是（c ）。A. x 是 y 的左兄弟B. x 是 y 的右兄弟后序： DBFGEC A 誰(shuí)后訪問(wèn)誰(shuí)是根LRD中序： BDACFEGLDR(A)/ (B)(C) (D)(E)/ (F)(G)26 已知某樹的先根遍歷次序?yàn)镈BFGECA 和 BDACFEG 。)。d: abcdegfabcdefg 后根遍歷次序?yàn)?cdebgfa。24a百度文庫(kù)-讓每個(gè)人平等地提升自我11C. x 是 y 的祖先（不一定是父子）D. x 是 y 的子孫28 用三叉鏈表作二叉樹的存儲(chǔ)結(jié)構(gòu)，當(dāng)二叉樹中有n 個(gè)結(jié)點(diǎn)時(shí)，有（d ）個(gè)空指針。A. n-1B. nC. n

12、+1D. n+2三叉鏈表：較二叉鏈表多一雙親指針域百度文庫(kù)-讓每個(gè)人平等地提升自我12二叉鏈表:2n-（n-1）=n+12n 個(gè)指針域有效指針域根節(jié)點(diǎn)雙親指針必為空，故n+1+1= n+2編號(hào)為 n 的結(jié)點(diǎn)若存在雙親，其位置是（a ）。a: n/2b: 2nc:2 n-1d:2 n+1 e:n f: 2（n+1）30 設(shè)森林 F 中有三棵樹，第一、第二和第三棵樹的結(jié)點(diǎn)個(gè)數(shù)分別為m1、m2 和 m3，則與森林 F 對(duì)應(yīng)的二叉樹根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)個(gè)數(shù)是dj。A. m1B. m1+m2C. m3D. m2+m3(A)(B)(C)/ / / m1m2m3（A）/ （左） （右）m-1m2+m331

13、 下列二叉樹中，（a ）可用于實(shí)現(xiàn)符號(hào)不等長(zhǎng)高效編碼。 a:最優(yōu)二叉樹b:次優(yōu)查找樹c:二叉平衡樹哈夫曼樹32 鄰接表存儲(chǔ)結(jié)構(gòu)下圖的深度優(yōu)先遍歷算法類似于二叉樹的（a ）遍歷。A.先根B.中根C.后根D.層次33 設(shè)無(wú)向圖 G = （V,E）和 G = （V ,E，若 G是 G 的生成樹，則下面不正確的說(shuō)法是34 任何一個(gè)連通圖的最小生成樹（J。A .只有一棵B.有一棵或多棵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)如圖所示。0E21AF- Ik1

14、D0-34A2C_J429對(duì)一棵完全二叉樹進(jìn)行層序編號(hào)。則編號(hào)為n 的結(jié)點(diǎn)若存在右孩子，其位序是（d ）。d:二叉排序樹(b )。A. G 是 G 的子圖 C.G是 G 的無(wú)環(huán)子圖 生成樹：極小 連通分量：極大B. G 是 G 的連通分量D. G 是 G 的極小連通子圖且C. 一定有多棵D.可能不存在百度文庫(kù)-讓每個(gè)人平等地提升自我133B120A4A2A百度文庫(kù)-讓每個(gè)人平等地提升自我14根據(jù)存儲(chǔ)結(jié)構(gòu)依教材中的算法其深度優(yōu)先遍歷次序?yàn)椋╠）。廣度優(yōu)先遍歷此序?yàn)椋╟）。各強(qiáng)連通分量的頂點(diǎn)集為（h ）。a: abcde.b: edcba. c: ecdab.d: ecadb.e: abc 及 e

15、d f: bc 及 aed g: ab 及 ced h: ac 及 bed37 下列查找方法中（a ）適用于查找單鏈表。A）順序查找B）折半查找C）分塊查找D）hash 查找38 下列算法中（c ）適用于求圖的最小代價(jià)生成樹。（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 ）。a:哈希函數(shù)b:處理沖突的方法。c:哈希表的裝填因子。d:以上都是1哈希函數(shù)

16、是否均勻；2處理沖突的方法；3哈希表的裝填因子。41 在 Hash 函數(shù) H（k）=k MOD m 中，一般來(lái)說(shuō)，m 應(yīng)?。╟ ）。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. 前者只能順序查找，而后者只能折半查找D. 前者可被排序，而后者不能被排序動(dòng)態(tài)查找表在查找過(guò)程中插入元素或

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

18、 20, 45, 30, 89, 70, 38, 62 , 19 依次插入到一棵 2-3 樹中（初始狀態(tài)為空）,該 B-樹為（b ）。再刪除 38,該 B-樹為（f(3062 )/ I(19，20)( 38 45)(） 。(70， 89 )(45a:(30/(19 20)）、（38）b:(4570(20)45(62(89)(19) ( 30 )（19）20)、(30,38)c:d:(19, 20)3070(45 62)）、（89）（20）（19）e:）、（70）/ （62 ）（ 89 ）（70）/、62 ）（ 89 ）45、（30f:46 根據(jù)插入次序（80，90，100，110，85，圖（a

19、 ）是最終變化的結(jié)果。若仍以該插入次序建立平衡二叉樹。圖 終變化的結(jié)果。70806075607211072a:90）（70）/、（62 ）（ 89 ）70，75，60，72）建立二叉排序樹。（c ）是最75708085b:9010011090百度文庫(kù)-讓每個(gè)人平等地提升自我177510080100708011060V28575110d:34, 45, 57, 69, 77, 83, 92 對(duì)其進(jìn)行(c )。查找 32 時(shí)需進(jìn)c:47 若有序表中關(guān)鍵字序列為：14, 20, 25 , 32,折半查找，則在等概率情況下，查找成功時(shí)的平均查找長(zhǎng)度是 行(c )次比較。A. 1B. 2C. 3D. 4

20、已知哈希表地址空間為A9，哈希函數(shù)為 H(k)=k mod 7，采用線性探測(cè)再散列處理沖突。若依次將數(shù)據(jù)序列：76,45,88,21,94,77,17 存入該散列表中， 在等概率情況下查找成功的平均查找長(zhǎng)度為(c )A. 0B. 1C. 2E. 4F. 5G. 648則元素 17 存儲(chǔ)的下標(biāo)為(h );D. 3H. 749505152若從二叉樹的根結(jié)點(diǎn)到其它任一結(jié)點(diǎn)的路徑上所經(jīng)過(guò)的結(jié)點(diǎn)序列按其關(guān)鍵字遞增有序， 則該二叉樹是(_cA.二叉排序樹B.赫夫曼樹C.堆D.平衡二叉樹當(dāng)待排序序列的關(guān)鍵字次序?yàn)榈剐驎r(shí)，若需為之進(jìn)行正序排序，下列方案中LdJ 為佳。A.起泡排序C.直接插入排序 下列排序算法

21、中，A.堆排序 在下列排序方法中，B.快速排序D.簡(jiǎn)單選擇排序(_dl 算法可能會(huì)出現(xiàn)：初始數(shù)據(jù)有序時(shí)，花費(fèi)的時(shí)間反而最多。B.起泡排序C.歸并排序D.快速排序(c )方法平均時(shí)間復(fù)雜度為 0(nlogn),0(n2); ( d)方法所有情況下時(shí)間復(fù)雜度均為b.希爾排序最壞情況下時(shí)間復(fù)雜度為a.插入排序b.希爾排序c.快速排序已知一組待排序的記錄關(guān)鍵字初始排列如下： 下列選擇中(d )是快速排序一趟排序的結(jié)果。(初始步長(zhǎng)為 3)一趟排序的結(jié)果。(aA)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

22、,42,58,48,56,75,86,77.D)42,26,48,35,19,56,77,58,75,86.0(nlogn) 53d.堆排序56,26,86,35,75,19,77,58,48,42(c )是希爾排序)是初始堆(大堆頂)三填空題1 數(shù)據(jù)結(jié)構(gòu)通常有下列 4 類基本結(jié)構(gòu)：集合、 線性結(jié)構(gòu)、樹型結(jié)構(gòu)、圖型結(jié)構(gòu)。datn ext，若單鏈表長(zhǎng)度大于等于 2，指針 p 指向表中某個(gè)p 所指的結(jié)點(diǎn)，可以通過(guò)如下方法進(jìn)行：將 p 所指2 設(shè)單鏈表中結(jié)點(diǎn)形式為結(jié)點(diǎn)且 p-next 非空，此時(shí)若要?jiǎng)h除指針 結(jié)點(diǎn)的后繼的元素值復(fù)制到該結(jié)點(diǎn)，然后刪除其后繼結(jié)點(diǎn)。相應(yīng)的語(yǔ)句序列為:p-data = p-

23、next-data ； p-next = p-next-next ； free(p -next) ； _百度文庫(kù)-讓每個(gè)人平等地提升自我4183 線性表的順序存儲(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í)現(xiàn)。5 已知某樹的先根遍歷次序?yàn)閍bcdefg 后根遍歷次序?yàn)?cdebgfa。若將該樹轉(zhuǎn)換為二叉樹，其后序遍歷次序?yàn)椋╡dcgfba）。層次遍歷次序?yàn)椋╝bcfdge）。6 已知某二叉樹的先序遍歷次序?yàn)閍f

24、bcdeg 中序遍歷次序?yàn)?cedbgfa。其后序遍歷次序?yàn)椋╡dcgbfa）。層次遍歷次序?yàn)椋╝fbcgde）。7 在二叉樹的第 i 層上至少有 1 個(gè)結(jié)點(diǎn)，至多有 2i-1個(gè)結(jié)點(diǎn)，深度為 k 的二叉樹至多有 2i-1 個(gè)結(jié)點(diǎn).8 對(duì)樹的遍歷有先序遍歷樹和后序遍歷樹。若以二叉鏈表作樹的存儲(chǔ)結(jié)構(gòu)，則樹的先序遍歷可借用二叉樹的先序遍歷算法來(lái)實(shí)現(xiàn)，而樹的后序遍歷可借用二叉樹的中序遍歷算法來(lái)實(shí)現(xiàn)。9 設(shè)高度為 h 的二叉樹上只有度為0 和度為 2 的結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少是 2*h-1，至多是滿樹。10 對(duì)任何一棵二叉樹 T,若其終端結(jié)點(diǎn)數(shù)為 n0.度為 2 的結(jié)點(diǎn)為 n2,則 n0

25、 與 n2 的關(guān)系為 （n=n2+1）。11 如果對(duì)完全二叉樹中結(jié)點(diǎn)從1 開始按層進(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,則圖中邊的條數(shù)是 m/2 條。15 若有序表中關(guān)鍵字序列為：12，22，33，44，55，66，77，88，99 對(duì)其進(jìn)行折半查找，則在等概率情況下，查找成功時(shí)

26、的平均查找長(zhǎng)度是（3）。查找 99 時(shí)需進(jìn)行（2）次比較。16 在哈希表中，處理沖突的方法有開放定址法，再哈希法，鏈地址法 等。17 在二叉樹的第 i 層上至少有 1 個(gè)結(jié)點(diǎn)，至多有 2i-1個(gè)結(jié)點(diǎn)，深度為 k 的二叉樹至多有 2k-1 個(gè)結(jié)點(diǎn).18 對(duì)于一棵高度為 K 的二叉排序樹，結(jié)點(diǎn)數(shù)最少可有 _ 個(gè)，最多可有 _個(gè)。19 用中序遍歷對(duì)二叉排序樹進(jìn)行訪問(wèn)可得到有序序列。20 已知 Hash 函數(shù)為 H（K）=K mod 13 ，散列地址為 0 -14，用二次探測(cè)再散列 處理沖突，關(guān)鍵字（23，34，56，24，75，12，49, 52，36，92） 的分布如圖，則平均成功的查找長(zhǎng)度為（）

27、、平均失敗的查找長(zhǎng)度為（）。0123456789101112131452 36925634232475124921 一棵m階的E-樹，第一層至少有一個(gè)結(jié)點(diǎn)；第二層至少有2 個(gè)結(jié)點(diǎn)，除根之外的所有非終端結(jié)點(diǎn)至少有（廠 m/2n）棵子樹，樹中每個(gè)結(jié)點(diǎn)至多有（m）棵子樹。22 在哈希表中，處理沖突的方法有開放定址法，再哈希法，鏈地址法，建立一個(gè)公共溢出區(qū)。23 哈希表的查找效率取決于（哈希函數(shù)是否均勻）（處理沖突的方法）和（哈希表的裝填因子）。24 高度為 4 （包含不帶關(guān)鍵字的葉子結(jié)點(diǎn)層）的 7 階 B 樹最少有 廠 m/2n-1 個(gè)關(guān)鍵字，最 多有 m-1個(gè)關(guān)鍵字；如果其中的某結(jié)點(diǎn)正好有 2 個(gè)

28、兒子，那么，該結(jié)點(diǎn)必定是 _結(jié)點(diǎn)。百度文庫(kù)-讓每個(gè)人平等地提升自我1925 對(duì) n 個(gè)元素的序列進(jìn)行內(nèi)部排序，若用起泡排序法，最少的比較次數(shù)是n-1,最多的比較次數(shù)是 n(n-1)/2。25 (算法填空)Status Preordertraverse(Bitree T,Status(*Visit)(Telemtype e) m成為一小頂堆)。請(qǐng)?jiān)凇癬 ”處填上合適的內(nèi)容，完成該算法。Void heapadjust( heaptype H , int s , int m ) rc=s;for (j=2*s;j=m;j*=2) if (jrj) +j;if ( rc j) break;s=j; s

29、=j;s = rc ;知某二叉樹的后序遍歷和中序遍歷次序分別為DBFGECA 和 BDACFEG請(qǐng)畫出該二叉樹，并為之建立先序線索。3 已知某二叉樹的先序遍歷次序?yàn)椋篴,b,c,d,e,f,g中序遍歷次序?yàn)椋篵,a,d,f,e,g,c畫出該二叉樹，并在該二叉樹上建立中序線索。4 某二叉樹的中序遍歷次序?yàn)锽EGFDAC， 先序遍歷次序?yàn)?ABDEFGC。試畫出該二叉樹，并為之建立中序線索(圖示之)。5 已知某二叉樹的后序遍歷和中序遍歷次序分別為FBEDGCA 和 FBADECG，請(qǐng)構(gòu)造并畫出該二叉樹。6 設(shè)某一電文只出現(xiàn) a,b,c,d,e,f,g 7 個(gè)字母；出現(xiàn)頻率分別為30%,10%,05

30、%,04%,13%,18%及 20%，請(qǐng)給出各字母的哈夫曼編碼。7 將圖示森林轉(zhuǎn)換為二叉樹，并對(duì)該二叉樹先序全序線索化。百度文庫(kù)-讓每個(gè)人平等地提升自我42012 368 958將圖示森林轉(zhuǎn)換為二叉樹，并對(duì)該二叉樹中序全序線索化。百度文庫(kù)-讓每個(gè)人平等地提升自我219 某二叉樹的結(jié)點(diǎn)數(shù)據(jù)采用順序存儲(chǔ)表示如下:012345678910111213141516171819ABCDEFGHI(1)試畫出此二叉樹的圖形表示。(2)將此二叉樹看作森林的二叉樹表示，試將它還原為森林。10 已知某有向圖如圖所示：1) 給出其十字鏈表存儲(chǔ)結(jié)構(gòu)2) 給出其深度優(yōu)先遍歷次序。3) 給出其廣度優(yōu)先遍歷次序。4) 給

31、出各強(qiáng)連通分量。11 設(shè)輸入序列為 20,45,30,89,70,38,62,19 依次插入到一棵 2-3 樹中(初始狀態(tài)為 空)，請(qǐng)畫出該 B-樹。12 右圖為一棵 3 階 B樹。(20, 25)1) 畫出在該樹上插入元素 15/|后的 B 樹。(10, 14)(21)(35)2) 接著，再刪除元素 35，畫出刪除后的 B 樹。13 已知 Hash 函數(shù)為 H(K)=K mod 13 ， 散列地址為 0 -14， 用線性探測(cè)再散列處理 沖突， 給出關(guān)鍵字(56,34, 68, 23, 16, 70, 48, 35, 83, 12, 14, 57) 在散列地址的分布。并指出平均成功的查找長(zhǎng)度是

32、多少？012345678 910111213 1414 根據(jù)插入次序(20, 30, 70, 60, 10, 100, 110, 90, 80。)建立平衡的二叉排序樹。15 設(shè)哈希表長(zhǎng)為 16,哈希函數(shù)為 H(key)=key mod 13，用開放定址法的二次探測(cè)再散列 處理沖突(di=12,-12, 22,-22, 32, -32)。依次存入 12 個(gè)元素：56, 82, 17,24, 36,21,83,96,13,34,57,50。請(qǐng)畫出它們?cè)诒碇械姆植记樾巍?6 已知待排序序列為：25,12,9,20,7,31,24,35,17,10，試寫出:(1) .堆排序初始建堆(大頂堆)的結(jié)果；(

33、2) .以第一個(gè)元素為樞軸的快速排序一趟掃描的結(jié)果；(3) .希爾排序第一趟(增量為 5)的結(jié)果。算法設(shè)計(jì)題1 設(shè)有一個(gè)帶頭結(jié)點(diǎn)、元素按值遞增有序的單鏈表，結(jié)點(diǎn)的類型定義如下: typedef struct LNode int data;struct LNode *n ext;abcde百度文庫(kù)-讓每個(gè)人平等地提升自我22 LNode, *Li nkList;編寫算法，刪除其中所有值相同的多余元素結(jié)點(diǎn)2 某線性表中元素以降序排列，現(xiàn)要插入一個(gè)元素X，插入后該線性元素仍保持降序。線性表采用帶頭結(jié)點(diǎn)單鏈表方式存貯。？請(qǐng)編寫該插入算法。3 編寫在一有序順序表中插入數(shù)據(jù)元素X 的算法 INSERT(L,X)。4 寫一算法，Delete(linklist &L , X),刪除單鏈表中所有值為X 的結(jié)點(diǎn)。單鏈表結(jié)點(diǎn)的類型定義如下：typedef struct LNode int data;struct LNode *n ext; LNode, *L in klist;5 寫一算法，Contrary(linklist &L),對(duì)一帶頭結(jié)點(diǎn)且僅設(shè)尾指針L 的循環(huán)單鏈表就地逆置。(即表頭變表尾，表尾變表頭。)6 已知線性表中的元素以值遞增有序排列，并以帶頭結(jié)點(diǎn)的單鏈表作存儲(chǔ)結(jié)構(gòu)。試寫一高效的算