必看!!!!!數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)題與部分答案解析

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

2、8 .順序存儲方式的優(yōu)點(diǎn)是存儲密度大，且插入、刪除運(yùn)算效率高。9 .棧和隊(duì)列是操作上受限制的線性表。10 .隊(duì)列是與線性表完全不同的一種數(shù)據(jù)結(jié)構(gòu)。棧和隊(duì)列是操作上受限制的線性表以，二叉樹是樹的11 .隊(duì)列是一種操作受限的線性表，凡對數(shù)據(jù)元素的操作僅限一端進(jìn)行。對列不是12 .棧和隊(duì)列也是線性表。如果需要，可對它們中的任一元素進(jìn)行操作。13 .棧是限定僅在表頭進(jìn)行插入和表尾進(jìn)行刪除運(yùn)算的線性表。14 .二叉樹中每個結(jié)點(diǎn)有兩個子結(jié)點(diǎn)，而對一般的樹，則無此限制，所特殊情形。15 二叉樹是一棵結(jié)點(diǎn)的度最大為二的樹二叉樹和樹相互獨(dú)立。16 赫夫曼樹中結(jié)點(diǎn)個數(shù)一定是奇數(shù)。17在二叉樹的中序遍歷序列中，任意

3、一個結(jié)點(diǎn)均處在其左孩子結(jié)點(diǎn)的后面。18假設(shè)B是一棵樹，B'是對應(yīng)的二叉樹。則B的后根遍歷相當(dāng)于B'的后序遍歷后根遍歷相當(dāng)于中序遍歷。19.通常，二叉樹的第i層上有2i-1個結(jié)點(diǎn)。應(yīng)該為12i-1個20.中序線索二叉樹的優(yōu)點(diǎn)是便于在中序下查找直接前驅(qū)結(jié)點(diǎn)和直接后繼結(jié)點(diǎn)。21二叉樹的先序遍歷序列中，任意一個結(jié)點(diǎn)均處在其孩子結(jié)點(diǎn)的前面。22由樹結(jié)點(diǎn)的先根序列和后根序列可以唯一地確定一棵樹。23鄰接多重表可以用以表不無向圖，也可用以表木有向圖。只能表不無向圖，有向圖用字鏈表24可從任意有向圖中得到關(guān)于所有頂點(diǎn)的拓?fù)浯涡驇Лh(huán)圖沒有。25有向圖的十字鏈表是將鄰接表和逆鄰接表合二為一的鏈表表

4、示形式。26 關(guān)鍵路徑是AOE網(wǎng)中源點(diǎn)到匯點(diǎn)的最短路徑。27 連通圖G的生成樹是一個包含G的所有n個頂點(diǎn)和n-1條邊的子圖。28 一個無向圖的連通分量是其極大的連通子圖。29 十字鏈表可以表示無向圖，也可用以表示有向圖。30 鄰接表可以表布有向圖，也可以表不無向圖。（t）31 .二叉排序樹的平均查找長度為O（logn）°（t）32 .二叉排序樹的最大查找長度與（LOG2N）同階。33 選用女?的HASH函數(shù)可避免沖突。哈希函數(shù)有幾種處理沖突的方法34 折半查找不適用于有序鏈表的查找。35 .對于目前所知的排序方法，快速排序具有最好的平均性能。36對于任何待排序序列來說，快速排序均快于

5、冒泡排序。37在最壞情況下，堆排序的時間性能是O(nlogn),比快速排序好38快速排序具有最好的平均時間性能，它在任何時候的時間復(fù)雜度都是O(nlogn)。(f)39 .字符串是數(shù)據(jù)對象特定的線性表。40 .空串與空格串是相同的。41 .對于一棵m階的B用.樹中每個結(jié)點(diǎn)至多有m個關(guān)鍵字.除根之外的所有非終端結(jié)點(diǎn)至少有rm/2Y關(guān)鍵字。42 .當(dāng)二叉排序樹是一棵平衡二叉樹時，其平均查找長度為O(log2n)。(t)43.廣義表的表頭和表尾都是廣義表。44二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表。選擇題。1從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成(c)。A.動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B.順序組織和鏈接組織C.線性結(jié)構(gòu)和非

6、線性結(jié)構(gòu)D.基本類型和組合類型2線性表L在(b)情況下適于使用鏈表結(jié)構(gòu)實(shí)現(xiàn)。A.不需彳改L的結(jié)構(gòu)B.需不斷對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=nullB.L->next=nullC.L->next=LD.L!=null4若順序表中各結(jié)點(diǎn)的查找概率不等，則可用如下策略提高順序查找的效率：若找到指定的結(jié)點(diǎn)，將該結(jié)點(diǎn)與其后繼(若存在)結(jié)點(diǎn)交換位置，使得經(jīng)常被查找的結(jié)點(diǎn)逐漸移至表尾。以下為據(jù)此策略編寫的算法，請選擇適當(dāng)?shù)膬?nèi)容，完成此功能。順序表的存儲結(jié)構(gòu)為：typedefstr

7、uctElemType*elem;/數(shù)據(jù)元素存儲空間，0號單元作監(jiān)視哨intlength;/表長度SSTable;intsearch_seq(SSTableST,KeyTypekey)/在順序表ST中順序查找關(guān)鍵字等于key的數(shù)據(jù)元素。/若找到，則將該元素與其后繼交換位置，并返回其在表中的位置，否則為0。ST.elem0.key=key;i=ST.length;while(ST.elemi.key!=key)f;if(一G一)ST.elemi<->ST.elemi+1;returni;C.i<ST.lengthG.A和C同時滿足D.i<=ST.lengthH.B和D同時

8、滿足A.i>0B.i>=0E.i+F.i-5若入棧順序?yàn)锳、B、C、D、巳則下列（d）出棧序列是不可能的。A. A、B、C、D、EB. B、C、D、A、EC. C、D、B、E、AD. D、E、C、A、B6遞歸程序可借助于（ca.線性表b.隊(duì)列7在下列數(shù)據(jù)結(jié)構(gòu)中（c）轉(zhuǎn)化為非遞歸程序。c:棧d.數(shù)組）具有先進(jìn)先出（FIFO）特性,（b）具有先進(jìn)后出（FILO）特性。a.線性表b.棧c.隊(duì)列d.廣義表8若對編號為1,2,3的列車車廂依次通過扳道棧進(jìn)行調(diào)度，不能得到（e）的序列。a:1,2,3b:1,3,2c:2,1,3d:2,3,1e:3,1,2f:3,2,19在計算遞歸函數(shù)時，如不用

9、遞歸過程，應(yīng)借助于Lbj這種數(shù)據(jù)結(jié)構(gòu)。A.線性表B.棧C.隊(duì)列D.雙向隊(duì)列10若帶頭結(jié)點(diǎn)的鏈表只設(shè)尾結(jié)點(diǎn)指針。下列選擇中（c）最適用于隊(duì)歹U。A）單鏈表B）雙向鏈表C循環(huán)單鏈表D）雙向循環(huán)鏈表11棧和隊(duì)列的一個共同點(diǎn)是（c）。A.都是先進(jìn)先出B.都是先進(jìn)后出C.只允許在端點(diǎn)處插入和刪除元素12循環(huán)隊(duì)列用數(shù)組A0.m-1存放其元素值,的元素個數(shù)是（c）。A. rear-front-1C.（rear-front+m）%m13如下關(guān)于串的陳述中，正確的是（a,cA.串是數(shù)據(jù)元素類型特殊的線性表D.沒有共同點(diǎn)設(shè)頭尾指針分別為front和rear,則當(dāng)前隊(duì)列中B. Rear-front+1D.Rear-

10、front）。B.串中的元素是字母C.串中若干個元素構(gòu)成的子序列稱為子串D.空串即為空格串14對字符串s='datstructure執(zhí)行操作replace(s,substring(s,6,8),'bas')的結(jié)果是(b)。a:'databaseb:'d-atase'c:'bas'd:'dOiasucture'15設(shè)有二維數(shù)組A5X7,每一元素用相鄰的4個字節(jié)存儲，存儲器按字節(jié)編址.已知A的起始地址為100。則按行存儲時，元素A06的第一個字節(jié)的地址是（d）按列存儲時，元素A06的第一個字節(jié)的地址是（a）a:220b

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

12、遍歷d:后序遍歷19設(shè)一棵二叉樹BT的存儲結(jié)構(gòu)如下：12345678lchild:>300600)dataABCDEFGHrchild()540870)其中Ichild,rchild分別為結(jié)點(diǎn)的左、右孩子指針域,data為結(jié)點(diǎn)的數(shù)據(jù)域。則該二叉樹白高度為（d）;第3層有（a）個結(jié)點(diǎn)（根結(jié)點(diǎn)為第1層）。A.2B.3C.4D.520先序遍歷圖示二叉樹可得到(a)的序列。(A)/(B) (C)/(H) (D)(G)/(E)(F)(I)a) ABHDEFICGb) HBEDFIACGc) HEIFDBGCAn-1;21在有n個結(jié)點(diǎn)的二叉樹的二叉鏈表表示中，空指針數(shù)為n+1;非空指針樹為(b)。a

13、.不定b.n+1c.nd.n-1（c）。度為2的節(jié)點(diǎn)A.40B.5523已知某二叉樹的先序遍歷次序?yàn)閯t該二叉樹的后序遍歷次序?yàn)椋╪2=n0T;其中no表示度為0的節(jié)點(diǎn)C.59D.61abcdefg中序遍歷次序?yàn)閎adcgfe,c）。層次遍歷次序?yàn)椋╝）。a:abcdefgb:cdebgfac:bdgfecad:edcgfba22若某二叉樹有20個葉子結(jié)點(diǎn)，有20個結(jié)點(diǎn)僅有一個孩子，則該二叉樹的總結(jié)點(diǎn)數(shù)是.24圖示的三棵二叉樹中（c）為最優(yōu)二叉樹。25已知某二叉樹的后序遍歷和中序遍歷次序分別為則其先序遍歷次序?yàn)椋╞）,層次遍歷次序?yàn)椋―BFGECA和BDACFEG。a)。d:abcdegfa:a

14、bcdefgb:abdcefgc:abcdfeg已知某樹的先根遍歷次序?yàn)閍bcdefg后根遍歷次序?yàn)閏debgfa。若將該樹轉(zhuǎn)換為二叉樹，其后序遍歷次序?yàn)椋╠）。a:abcdefgb:cdebgfac:cdegbfad:edcgfba設(shè)x和y是二叉樹中的任意兩個結(jié)點(diǎn)，若在先根序列中x在y之前，而在后根序列中x在y之后，則x和y的關(guān)系是（c）。A.x是y的左兄弟B.x是y的右兄弟C.x是y的祖先D.x是y的子孫用三叉鏈表作二叉樹的存儲結(jié)構(gòu)，當(dāng)二叉樹中有n個結(jié)點(diǎn)時，有（d）個空指針。26272829303132333435A)36A.n-1B.nC.n+1D.n+2對一棵完全二叉樹進(jìn)行層序編號。則

15、編號為n的結(jié)點(diǎn)若存在右孩子，其位序是（d）。編號為n的結(jié)點(diǎn)若存在雙親，其位置是（a）。a:n/2b:2nc:2n-1d:2n+1e:nf:2（n+1）設(shè)森林F中有三棵樹，第一、第二和第三棵樹的結(jié)點(diǎn)個數(shù)分別為m1、m2和m3,則與森林F對應(yīng)的二叉樹根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)個數(shù)是（d）。A.m1B.m1+m2C.m3D.m2+m3下列二叉樹中，（a）可用于實(shí)現(xiàn)符號不等長高效編碼。a:最優(yōu)二叉機(jī)b:次優(yōu)查找樹c:二叉平衡樹d:二叉排序樹鄰接表存儲結(jié)構(gòu)下圖的深度優(yōu)先遍歷算法類似于二叉樹的（a）遍歷。A.先根B.中根C.后根D.層次設(shè)無向圖G=（V,E）nG=（V,E）,若G是G的生成樹，則下面不正確的說

16、法是（b）。''一,'一、一一一、一A.G是G的子圖B.G是G的連通分量（極大連通子圖稱為連通分量）'一,1_、一.一一'C.G是G的無環(huán)子圖D.G是G的極小連通子圖且V=V任何一個連通圖白最小生成樹3。最小生成樹其實(shí)是最小權(quán)重生成樹的簡稱A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在efef深度優(yōu)先遍歷圖使用了數(shù)據(jù)結(jié)構(gòu)（b數(shù)組B）棧C）隊(duì)列）,而廣度優(yōu)先遍歷圖使用了數(shù)據(jù)結(jié)構(gòu)（D）線性表c)。已知某有向圖的鄰接表存儲結(jié)構(gòu)如圖所示。根據(jù)存儲結(jié)構(gòu)依教材中的算法其深度優(yōu)先遍歷次序?yàn)椋◤V度優(yōu)先遍歷此序?yàn)椋╟）。各強(qiáng)連通分量的頂點(diǎn)集為d)。(h）。有向圖

17、的極大強(qiáng)連通子圖，稱為強(qiáng)連通分量a:abcde.b:edcba.c:ecdab.d:ecadb.e: abc及edf: bc及aedg: ab及cedh:ac及bed37下列查找方法中（a）適用于查找單鏈表。A）順序查找B）折半查找C）分塊查找D）hash查找38下列算法中（c普利姆算法）適用于求圖的最小代價生成樹。（b）能對圖作廣度優(yōu)先遍歷。A）DFS算法B）BFS算法C）Prim算法D）Dijkstra算法39關(guān)鍵路徑是指在只有一個源點(diǎn)和一個匯點(diǎn)的有向無環(huán)網(wǎng)中源點(diǎn)至匯點(diǎn)（c）的路徑。a:弧的數(shù)目最多b:弧的數(shù)目最少c:權(quán)值之和最大d:權(quán)值之和最小40希表的查找效率取決于（d）。a:哈希函數(shù)

18、b:處理沖突的方法。c:哈希表的裝填因子。d:以上都是41在Hash函數(shù)H（k尸kMODm中，一般來說，m應(yīng)?。╟）。A.奇數(shù)B.偶數(shù)C.素數(shù)D.充分大的數(shù)42在順序表查找中，為避免查找過程中每一步都檢測整個表是否查找完畢，可采用a方法。A.設(shè)置監(jiān)視哨B.鏈表存貯C.二分查找D.快速查找43靜態(tài)查找表和動態(tài)查找表的區(qū)別在于（b）。A.前者是順序存儲，而后者是鏈?zhǔn)酱鎯.前者只能進(jìn)行查找操作，而后者可進(jìn)行查找、插入和刪除操作C.前者只能順序查找，而后者只能折半查找D.前者可被排序，而后者不能被排序44在一個含有n個元素的有序表上進(jìn)行折半查找，找到一個元素最多要進(jìn)行（b）次元素比較。A.og2（n

19、）B.og2（n）_+1C.og2（n+1）D.og2（n+1）1+145設(shè)輸入序列為20,45,30,89,70,38,62,19依次插入到一棵2-3樹中（初始狀態(tài)為空），該B-樹為（b）。再刪除38,該B-樹為（f）。(19,20)(3845)(70,89)a:c:d:(19,20)(4562)(89)f:e:46根據(jù)插入次序(80,90,100,110,85,70,75,60,72)建立二叉排序樹。圖(a)是最終變化的結(jié)果。若仍以該插入次序建立平衡二叉樹。圖(c)是最終變化的結(jié)果。c:d:47若有序表中關(guān)鍵字序列為：14,20,25,32,34,45,57,69,77,83,92。畫出二

20、叉判定樹計算，關(guān)鍵字在第幾層，就經(jīng)過幾次比較對其進(jìn)行折半查找，則在等概率情況下，查找成功時的平均查找長度是(c)。查找32時需進(jìn)行(c)次比較。A.1B.2C.3D.448已知哈希表地址空間為A9,哈希函數(shù)為H(k)=kmod7,采用線性探測再散列處理沖突指加數(shù)為1。若依次將數(shù)據(jù)序列：76,45,88,21,94,77,17存入該散列表中，則元素17存儲的下標(biāo)為(h);在等概率情況下查找成功的平均查找長度為(c)。A.0B.1C.2D.3E.4F.5G.6H.749若從二叉樹的根結(jié)點(diǎn)到其它任一結(jié)點(diǎn)的路徑上所經(jīng)過的結(jié)點(diǎn)序列按其關(guān)鍵字遞增有序，則該二叉樹是(c)。A.二叉排序樹B.赫夫曼樹C.堆D

21、.平衡二叉樹50當(dāng)待排序序列的關(guān)鍵字次序?yàn)榈剐驎r，若需為之進(jìn)行正序排序，下列方案中(d)為佳。A,起泡排序B.快速排序C,直接插入排序D.簡單選擇排序51下列排序算法中，算法可能會出現(xiàn)：初始數(shù)據(jù)有序時，花費(fèi)的時間反而最多。A.堆排序B.起泡排序C.歸并排序D.快速排序52在下列排序方法中，(c快速排序)方法平均時間復(fù)雜度為0(nlogn),最壞情況下時間復(fù)雜度為0(n2);(d)方法所有情況下時間復(fù)雜度均為0(nlogn)。a.插入排序b.希爾排序c.快速排序d.堆排序53已知一組待排序的記錄關(guān)鍵字初始排列如下：56,26,86,35,75,19,77,58,48,42下列選擇中(d)是快速排

22、序一趟排序的結(jié)果。(c)是希爾排序(初始步長為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.三.填空題樹型結(jié)構(gòu)、圖型結(jié)構(gòu)。1數(shù)據(jù)結(jié)構(gòu)通常有下列4類基本結(jié)構(gòu)：集合、線性結(jié)構(gòu)2設(shè)單鏈表中結(jié)點(diǎn)形式為datanext結(jié)點(diǎn)且p->next非空，此時若要刪除指針,若單鏈表長度大于等于2,指針p指向表中某個p所指的結(jié)點(diǎn)，可以通過如下方法進(jìn)行：

23、將p所指結(jié)點(diǎn)的后繼的元素值復(fù)制到該結(jié)點(diǎn)，然后刪除其后繼結(jié)點(diǎn)。相應(yīng)的語句序列為:p->data=p->next->data;p->next=p->next->next;free(p->next)換指針的同時還要交換數(shù)3線性表的順序存儲結(jié)構(gòu)是以數(shù)組下標(biāo)來表示數(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)時，鏈表的鏈接可用語句(q->netx=p->next)實(shí)現(xiàn)。5已知某樹的先根遍歷次序?yàn)閍bcdefg后根遍歷次序?yàn)閏debgfa。若將該樹轉(zhuǎn)換為二叉樹，其后序遍歷次

24、序?yàn)?)。層次遍歷次序?yàn)?)。6已知某二叉樹的先序遍歷次序?yàn)閍fbcdeg后序遍歷次序?yàn)閏edbgfa。其后序遍歷次序?yàn)?)。層次遍歷次序?yàn)?)。7在二叉機(jī)勺第i層上至少有1個結(jié)點(diǎn)，至多有2個結(jié)點(diǎn)，深度為k的二叉樹至多有_2_-1一個結(jié)點(diǎn).8對樹的遍歷有先序遍歷樹和后序遍歷樹。若以二叉鏈表作樹的存儲結(jié)構(gòu)，則樹的先序遍歷可借用二叉樹的遍歷算法來實(shí)現(xiàn)，而樹的后序遍歷可借用二叉樹的中序遍歷遍歷算法來實(shí)現(xiàn)。9設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少是2*h-1,至多是滿樹。10對任何一棵二叉樹T,若其終端結(jié)點(diǎn)數(shù)為n0度為2的結(jié)點(diǎn)為n2,則n0與n2的關(guān)系為(n0=

25、n2+1)。11如果對完全二叉樹中結(jié)點(diǎn)從1開始按層進(jìn)行編號，設(shè)最大編號為n；那么，可以斷定編號為i（i>1）的結(jié)點(diǎn)的父結(jié)點(diǎn)編號為（i/2向下取整）；所有編號（i>n/2）的結(jié)點(diǎn)為葉子結(jié)點(diǎn)。12n個頂點(diǎn)的連通圖至少有條邊，至多有n*（n-1）/2條邊，此時即是完全圖條邊。13對于圖的存儲結(jié)構(gòu)有（數(shù)組表示法）、（鄰接表法）（十字鏈表法）（鄰接多重表法）等方法。14在一個無向圖的鄰接表中，若表結(jié)點(diǎn)的個數(shù)是3則圖中邊的條數(shù)是m/2條。15若有序表中關(guān)鍵字序列為：12,22,33,44,55,66,77,88,99對其進(jìn)行折半查找，則在等概率情況下，查找成功時的平均查找長度是（）。查找99時

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

27、的B-樹，第一層至少有一個結(jié)點(diǎn)；第二層至少有2個結(jié)點(diǎn),除根之外的所有非終端結(jié)點(diǎn)至少有（）棵子樹，樹中每個結(jié)點(diǎn)至多有（）棵子樹。22在哈希表中，處理沖突的方法有開放定址法，23哈希表的查找效率取決于（哈希函數(shù)是否均勻;處理沖突的方法；哈希表的裝填因子）。24高度為4（包含不帶關(guān)鍵字白葉子結(jié)點(diǎn)層）的7?階？B?樹最少有個關(guān)鍵字，最多有個關(guān)鍵字；如果其中的某結(jié)點(diǎn)正好有2個兒子，那么，該結(jié)點(diǎn)必定是結(jié)點(diǎn)°25對n個元素的序列進(jìn)行內(nèi)部排序，若用起泡排序法，最少的比較次數(shù)是n1最多的比較次數(shù)是n（n-1）/2。25(算法填空)StatusPreordertraverse(BitreeT,Statu

28、s(*Visit)(Telemtypee)/先序非遞歸遍歷二叉樹。Initstack(S);Push(S,T);While(!stackempty(S)While(gettop(S,p)&&_p)if(!Visit(p->data)returnERROR;push(s,p->lchild)Pop(S,p);if(!stackempty(s)pop(S,p);push(S,p->rchild);returnok;26(算法填空)下列算法試圖完成在數(shù)組A中搜索有無關(guān)鍵字key,若有，返回數(shù)組下標(biāo)，若無，返回-1。在:”處填上合適的內(nèi)容，完成該算法。intBinar

29、ySearch(keytypeA,intlow,inthigh,keytypekey)while(low<=high)middle=(low+high)/2;if(Amiddle=key)returnmiddle;if(key<Amiddle)high=middle-1;elselow=middle+1;return-1;/endofBinarySearch27(算法填空)下列函數(shù)為堆排序中的堆調(diào)整過程(調(diào)整H.rs的關(guān)鍵字，使H.rs.m成為一小頂堆)。請?jiān)?”處填上合適的內(nèi)容，完成該算法。Voidheapadjust(heaptypeH,ints,intm)rc=H.rs;fo

30、r(j=2*s;j<=m;j*=2)if(j<m&&rj+1>rj)+j;if(rc>H.rj)break;H.rs=H.rj;s=j;H.Rs=rc;/heapadjust圖示結(jié)構(gòu)題1已知在電文中只出現(xiàn)頻率為(5,26,7,23,20,19)的6個字符,畫出你建的哈夫曼樹，并給出其哈夫曼編碼。DBFGECA和BDACFEG2.已知某二叉樹的后序遍歷和中序遍歷次序分別為請畫出該二叉樹，并為之建立先序線索沒有左子樹，則建立該節(jié)點(diǎn)的前驅(qū)，若沒有右子樹,這指向該節(jié)點(diǎn)的后繼。已知某二叉樹的先序遍歷次序?yàn)椋篴,b,c,d,e,f,g.中序遍歷次序?yàn)椋篵,a,d,f

31、,e,g,c畫出該二叉樹，并在該二叉樹上建立中序線索。某二叉樹的中序遍歷次序?yàn)锽EGFDAC,先序遍歷次序?yàn)锳BDEFGC。試畫出該二叉樹，并為之建立中序線索（圖示之）。已知某二叉樹的后序遍歷和中序遍歷次序分別為FBEDGCA和FBADECG,請構(gòu)造并畫出該二叉樹。30%,10%,05%,04%,13%,18%設(shè)某一電文只出現(xiàn)a,b,c,d,e,f,g7個字母；出現(xiàn)頻率分別為及20%,請給出各字母的哈夫曼編碼。將圖示森林轉(zhuǎn)換為二叉樹，并對該二叉樹先序全序線索化。將圖示森林轉(zhuǎn)換為二叉樹，并對該二叉樹中序全序線索化。某二叉樹的結(jié)點(diǎn)數(shù)據(jù)采用順序存儲表示如下：101112131415161718190

32、123456789（1）試畫出此二叉樹的圖形表示。（2）將此二叉樹看作森林的二叉樹表示，試將它還原為森林。10已知某有向圖如圖所示：1）給出其十字鏈表存儲結(jié)構(gòu)2）給出其深度優(yōu)先遍歷次序。3）給出其廣度優(yōu)先遍歷次序。de4）給出各強(qiáng)連通分量。11設(shè)輸入序列為20,45,30,89,70,38,62,19依次插入到一棵2-3樹中(初始狀態(tài)為空)，請畫出該B-樹。12右圖為一棵3階B樹。(20,25)1)畫出在該樹上插入元素15/后的B樹。(10,14)(21)(35)2)接著，再刪除元素35,畫出刪除后的B樹。13已知Hash函數(shù)為H(K)=Kmod13,散列地址為0-14,用線性探測再散列處理沖

33、突，給出關(guān)鍵字(56,34,68,23,16,70,48,35,83,12,14,57)在散列地址的分布。并指出平土成功的查找長度是多少？0123456789101112131414根據(jù)插入次序(20,30,70,60,10,100,110,90,80。)建立平衡的二叉排序樹。15設(shè)哈希表長為16,哈希函數(shù)為H(key尸keymod13,用開放定址法的二次探測再散列處理沖突(di=12,-12,22,-22,32,-32)。依次存入12個元素:56,82,17,24,36,21,83,96,13,34,57,50。請畫出它們在表中的分布情形。16已知待排序序列為：25,12,9,20,7,31

34、,24,35,17,10,試寫出:(1) .堆排序初始建堆(大頂堆)的結(jié)果；(2) .以第一個元素為樞軸的快速排序一趟掃描的結(jié)果；(3) .希爾排序第一趟(增量為5)的結(jié)果。算法設(shè)計題1設(shè)有一個帶頭結(jié)點(diǎn)、元素按值遞增有序的單鏈表，結(jié)點(diǎn)的類型定義如下：typedefstructLNodeintdata;structLNode*next;LNode,*LinkList;編寫算法，刪除其中所有值相同的多余元素結(jié)點(diǎn)2某線性表中元素以降序排列，現(xiàn)要插入一個元素X,插入后該線性元素仍保持降序。線性表采用帶頭結(jié)點(diǎn)單鏈表方式存貯。？請編寫該插入算法。3編寫在一有序順序表中插入數(shù)據(jù)元素X的算法INSERT(L,X)。4寫一算法，Delete(linklist&L,X)，刪除單鏈表中所有值為X的結(jié)點(diǎn)。單鏈表結(jié)點(diǎn)的類型定義如下：typedefstructLNodeintdata;structLNode*next;