杭電[數(shù)據(jù)結(jié)構(gòu)(c語言版)]

《杭電[數(shù)據(jù)結(jié)構(gòu)(c語言版)]》由會員分享，可在線閱讀，更多相關(guān)《杭電[數(shù)據(jù)結(jié)構(gòu)(c語言版)]（21頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)提綱（附：期末復(fù)習(xí)題及期末樣卷）第一章 緒論一. 基本概念和術(shù)語數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的操作對象以及它們之間的關(guān)系和操 作等的學(xué)科。術(shù)語：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)、抽象數(shù)據(jù)類型、算法。數(shù)據(jù)結(jié)構(gòu)的形式定義（二元組）數(shù)據(jù)的邏輯結(jié)構(gòu)：線性結(jié)構(gòu)非線性結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)（物理結(jié)構(gòu)）:主要有順序存儲結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)抽象數(shù)據(jù)類型（三元組）算法（5個重要特性）二. 算法的時間復(fù)雜度和空間復(fù)雜度算法的評價：正確性、可讀性、健壯性、高效率、低存儲量第二章 線性表一. 線性表的定義線性結(jié)構(gòu)的特點二. 線性表的存儲結(jié)構(gòu)1. 順序存儲結(jié)構(gòu)（順序表）插入/刪除元素時，需移

2、動元素2. 鏈?zhǔn)酱鎯Y(jié)構(gòu)（鏈表，分為單向鏈表、雙向鏈表）帶頭結(jié)點的鏈表和不帶頭結(jié)點的鏈表；循環(huán)鏈表； 鏈表空與非空的情況。3. 兩種存儲結(jié)構(gòu)的優(yōu)缺點比較，各適合那些場合。三. 線性表操作的實現(xiàn)（算法描述）插入元素、刪除元素、查找、判表是否滿足某種特性例：判斷題：1.線性表的邏輯順序與存儲順序總是一致的。F2. 線性結(jié)構(gòu)的基本特征是：每個結(jié)點有且僅有一個直接前驅(qū)和一個直接后繼。F3. 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)優(yōu)于順序存儲結(jié)構(gòu)。F選擇題：線性表L在（B ）情況下適于使用鏈表結(jié)構(gòu)實現(xiàn)。A.不需修改L的結(jié)構(gòu)B.需不斷對L進(jìn)行刪除、插入C.需經(jīng)常修改L中結(jié)點值 填空題：1.對于順序表中，在第D. L中含有大

3、量結(jié)點i個元素前插入一個元素需移動n-i+1個元素，要刪除第i個元素，需移動n丄個元素。2. 在雙向循環(huán)鏈表中某結(jié)點（由指針 p指示）之后插入s指針?biāo)附Y(jié)點的操作是:第三章棧和隊列一. 棧1. 棧的定義2. 棧的存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)3. 棧的應(yīng)用：二叉樹的先序、中序、后序遍歷算法圖的深度優(yōu)先遍歷算法(將遞歸算法改寫為非遞歸算法可借助棧來完成；遞歸算法的執(zhí)行需用棧來實現(xiàn))二. 隊列1. 隊列的定義2. 隊列的存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)(循環(huán)隊列)，鏈?zhǔn)酱鎯Y(jié)構(gòu)3. 隊列的應(yīng)用：二叉樹層序遍歷圖的廣度優(yōu)先遍歷算法4. 循環(huán)隊列：隊空、隊滿的判斷條件求隊列的長度循環(huán)隊列通常用 front和

4、rear來指示隊頭和隊尾的位置來表示一個隊列；如 果用front指示隊頭，用length表示隊列的長度，也可以表示一個隊列。相應(yīng)的 有關(guān)操作怎樣實現(xiàn)？例：判斷題：因為棧是特殊的線性表，所以對線性表的所有操作都可以用于對棧操作。 填空題：循環(huán)隊列隊滿的條件是rear-front。第四章 串一. 串的定義二. 串的術(shù)語：長度、子串三. 串的基本操作：求串的長度、求子串、串聯(lián)接、串替換、串匹配(子串定位)例：已知下列字符串：a=THIS, b=(一個空格)，c=GOOD, d=NE, f=A SAMPLE,執(zhí)行如下操作：s=Concat (a,Concat (Concat (b,SubString

5、(a,3,2) Substring (f, 2 , SubLength(f);t=Replace (f,SubString (f,3,6),c);u=Concat (SubString (c,3,1),d);v=Concat (s,Concat (b,Concat (t,Concat (b,u);試問：s，t，u，v，LENGTH(s)各是什么？第五章數(shù)組和廣義表一. 數(shù)組數(shù)組的順序存儲：行主順序法，列主順序法。元素存儲地址計算特殊矩陣的壓縮存儲元素存儲地址計算二. 廣義表1.廣義表的概念：廣義表，長度，深度，表頭，表尾；2. 廣義表的頭尾鏈表存儲結(jié)構(gòu)第六章 樹和二叉樹一. 樹、二叉樹的定義二

6、. 二叉樹1. 二叉樹的性質(zhì)(5條)2. 二叉樹的存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)(按層序存放)鏈?zhǔn)酱鎯Y(jié)構(gòu)(二叉鏈表、三叉鏈表)(空指針域的個數(shù))3. 遍歷二叉樹：先序、中序、后序、層序應(yīng)用：給定二叉樹的先序和中序(或后序和中序)序列，畫岀相應(yīng)的二叉樹4. 線索二叉樹：先序、中序、后序線索化三. 樹和森林1. 樹的存儲結(jié)構(gòu)：雙親表示法孩子表示法孩子-兄弟(二叉樹)表示法2. 樹(森林)與二叉樹的相互轉(zhuǎn)換3. 樹的遍歷：先根、后根次序遍歷4. 森林的遍歷：先序、中序遍歷四. 赫夫曼樹及其應(yīng)用1. 最優(yōu)二叉樹（赫夫曼樹），求 WPL2. 赫夫曼編碼五. 各種二叉樹概念的區(qū)分1.滿二叉樹2.完全二叉樹3.正

7、則二叉樹（嚴(yán)格二叉樹）4.最優(yōu)二叉樹5.（折半查找的）判定樹6.二叉排序樹7.平衡二叉樹8.堆六. 二叉樹有關(guān)的遞歸算法例：判斷題：1.已知二叉樹的先序序列和后序序列并不能唯一地確定這棵二叉樹，因為不知道二叉樹的根結(jié)點是哪一個。fi-1k2.一般二叉樹的第i層上有2個結(jié)點，深度為k的二叉樹有2 -1個結(jié)點。f選擇題：1.下列二叉樹中，（a ） 可用于實現(xiàn)符號不等長高效編碼。A.最優(yōu)二叉樹B.二叉查找樹C.平衡二叉樹 ？ D.二叉排序樹2結(jié)點數(shù)為n的二叉樹高度至多為 （b）。A.不定 B. n C. og?* +1 D.log?*填空題：1.將滿二叉樹（含n個結(jié)點）中各結(jié)點從上到下，從左到右進(jìn)行

8、編號，并采用順序存儲表示，則 編號為i的結(jié)點，其雙親編號為i/2，其左孩子編號為2i（2in），其右孩子編號為2i+1 （2i+1n）。2.對樹的遍歷有先根次序遍歷樹和后根次序遍歷樹。若以二叉鏈表作樹的存儲結(jié)構(gòu)，則樹的先根遍歷可借用二叉樹的先序遍歷算法來實現(xiàn),而樹的后根遍歷可借用二叉樹的中序遍歷算法來實現(xiàn)。應(yīng)用題：1.已知某二叉樹的先序遍歷序列是ABCDEFGHI，中序遍歷序列是 BDCEAGHFI，畫出該二叉樹。2.以數(shù)據(jù)集（4,5,6,7,10,12,18）為葉結(jié)點權(quán)值，構(gòu)造一棵赫夫曼樹，并求其帶權(quán)路徑長度。第七章 圖一. 圖的定義和術(shù)語無向圖、有向圖、（無向/有向）完全圖、子圖、（強）連

9、通圖、（強）連通分量、生成樹二. 圖的存儲結(jié)構(gòu)無向圖：鄰接矩陣、鄰接表、鄰接多重表有向圖：鄰接矩陣、鄰接表、逆鄰接表、十字鏈表三. 圖的遍歷（針對具體的存儲結(jié)構(gòu)進(jìn)行）深度優(yōu)先搜索遍歷圖（利用棧）廣度優(yōu)先搜索遍歷圖（利用隊列）四. 圖的遍歷的應(yīng)用 求無向圖的連通分量、生成樹（生成森林）五. 圖的應(yīng)用求最小生成樹（無向網(wǎng)）：Prim算法、Kruskal算法拓?fù)渑判颍ˋOV-網(wǎng)）關(guān)鍵路徑（AOE-網(wǎng)）概念最短路徑：Dijkstra算法例:判斷題：一個連通圖的連通分量是包含該圖中的所有（n個）頂點和任意n-1條邊的子圖。f應(yīng)用題：已知圖G如下，畫岀該有向圖的鄰接矩陣和鄰接表，并根據(jù)你的鄰接表分別寫岀深

10、度優(yōu)先遍歷和1. 順序查找表（設(shè)置崗哨）2. 有序查找表（折半/二分查找）要求：元素值有序的順序表3. 索引順序查找表二. 動態(tài)查找表1. 二叉排序樹（二叉查找樹） 定義、查找、插入、刪除 從空樹開始創(chuàng)建一棵二叉排序樹2. 平衡二叉樹定義、查找、插入從空樹開始創(chuàng)建一棵平衡的二叉排序樹3. n個元素的二叉排序樹、平衡二叉樹的深度4. B-樹（B+樹）（常用于文件系統(tǒng)）定義、查找、插入、刪除從空樹開始創(chuàng)建一棵3階B-樹（2-3 樹）三. 哈希表1. 哈希表的定義2. 哈希函數(shù)的構(gòu)造方法3. 處理沖突的方法4. 哈希表的造表、查找四. 平均查找長度的計算1. 等概率情況下，查找成功時的平均查找長度A

11、SL2. 查找不成功時的查找長度例：判斷題：1.任一個二叉排序樹的平均查找長度都小于用順序查找法查找同樣結(jié)點的線性表的平均查找長度。2.當(dāng)二叉排序樹是一棵平衡樹時，其平均查找長度為O（log2n）。選擇題：1.折半查找算法要求被查找的表是（c ）。A.鍵值有序的鏈表B.鍵值不一定有序的鏈表C.鍵值有序的順序表D.鍵值不一定有序的順序表2.若查找表是一個有序的單鏈表，則應(yīng)采用（a）方法。A.順序查找B.折半查找C.分塊查找D.哈希查找3 設(shè)線性表中元素的關(guān)鍵字序列為（8,16,24,29,35,40,46,58,66,73,87,98），用折半查找法查關(guān)鍵字等于87的元素時，需依次比較關(guān)鍵字（c

12、）。A. 40,58,87 B. 46,87 C. 40,66,87 D. 46,66,87應(yīng)用題：1.已知如下所示長度為 8的表：（12，71, 36, 45, 47，50, 2, 9），按表中元素順序構(gòu)造一棵平衡 的二叉排序樹，請畫岀該樹。（二叉排序樹，2-3樹）2.設(shè)哈希表長為16,哈希函數(shù)為H(key)=key mod13,用開放定址法的二次探測再散列處理沖突。 依次存入10個元素：17,24,36,21,83,96,13,34,57,46，請畫出它們在表中的分布情形。第十章 內(nèi)部排序一.內(nèi)部排序的方法1.直接插入排序2.希爾排序3.起泡排序4.快速排序5.簡單選擇排序6.堆排序7.歸

13、并排序8.基數(shù)排序二.各種內(nèi)部排序方法的比較(最好、最壞、平均)時間復(fù)雜度平均空間復(fù)雜度例：判斷題：歸并排序和堆排序的平均時間和最壞情況下的時間性能都是O(nlogn),因此，它們在最壞情況下的時間性能比快速排序好。應(yīng)用題：若要按升序?qū)﹃P(guān)鍵字序列(36,45,85,16,23,16,58,22,59,74,12,46)進(jìn)行排序，請寫出：(1).堆排序初始建堆(大頂堆)的結(jié)果；(2) .以第一個元素為樞軸的快速排序一趟掃描的結(jié)果；(3) .起泡排序第一趟的結(jié)果；(4) .希爾排序第一趟(增量 5)的結(jié)果(5) .基數(shù)排序第一趟的結(jié)果。附錄：期末復(fù)習(xí)題一.是非題(共分，每題分)I. 數(shù)據(jù)結(jié)構(gòu)可用三

14、元式表示(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é)點的非空循環(huán)單鏈表(頭指針為L )中指針p所指結(jié)點是最后一個元素結(jié)點的條件是：p-next=L。(t)4線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)具有可直接存取表中任一元素的優(yōu)點。5線性表的順序存儲結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯Y(jié)構(gòu)。(f)6.在單鏈表P指針?biāo)附Y(jié)點之后插入S結(jié)點的操作是：P-next= S ; S- next = P-next; 。 (f)7對于插入、刪除而言，線性表的鏈?zhǔn)酱鎯?yōu)于順序存儲。8. 順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。(f)9. 棧和隊

15、列是操作上受限制的線性表。10. 隊列是與線性表完全不同的一種數(shù)據(jù)結(jié)構(gòu)。(f)II. 隊列是一種操作受限的線性表，凡對數(shù)據(jù)元素的操作僅限一端進(jìn)行。(f)12. 棧和隊列也是線性表。如果需要，可對它們中的任一元素進(jìn)行操作。(f)13. 棧是限定僅在表頭進(jìn)行插入和表尾進(jìn)行刪除運算的線性表。(f)14. 二叉樹中每個結(jié)點有兩個子結(jié)點，而對一般的樹，則無此限制，所以，二叉樹是樹的特殊情形。(f)15二叉樹是一棵結(jié)點的度最大為二的樹。16赫夫曼樹中結(jié)點個數(shù)一定是奇數(shù)。17在二叉樹的中序遍歷序列中，任意一個結(jié)點均處在其左孩子結(jié)點的后面。18 假設(shè)B是一棵樹，B 是對應(yīng)的二叉樹。則B的后根遍歷相當(dāng)于 B 的

16、后序遍歷。(f)19. 通常，二叉樹的第i層上有2-1個結(jié)點。20. 中序線索二叉樹的優(yōu)點是便于在中序下查找直接前驅(qū)結(jié)點和直接后繼結(jié)點。21二叉樹的先序遍歷序列中，任意一個結(jié)點均處在其孩子結(jié)點的前面。22由樹結(jié)點的先根序列和后根序列可以唯一地確定一棵樹。23鄰接多重表可以用以表示無向圖，也可用以表示有向圖。(f)24可從任意有向圖中得到關(guān)于所有頂點的拓?fù)浯涡颉?f)25有向圖的十字鏈表是將鄰接表和逆鄰接表合二為一的鏈表表示形式。26 關(guān)鍵路徑是 AOE網(wǎng)中源點到匯點的最短路徑。27 連通圖G的生成樹是一個包含 G的所有n個頂點和n-1條邊的子圖。(f)28一個無向圖的連通分量是其極大的連通子圖

17、。(t)29十字鏈表可以表示無向圖，也可用以表示有向圖。(f)30鄰接表可以表示有向圖，也可以表示無向圖。(t )31.二叉排序樹的平均查找長度為O(log n )。(t)32.二叉排序樹的最大查找長度與(LOG2N)同階。(f)33選用好的HASH函數(shù)可避免沖突。(f)34折半查找不適用于有序鏈表的查找。(t)35.對于目前所知的排序方法，快速排序具有最好的平均性能。36對于任何待排序序列來說，快速排序均快于冒泡排序。(f)37在最壞情況下，堆排序的時間性能是O(nlogn),比快速排序好38快速排序具有最好的平均時間性能，它在任何時候的時間復(fù)雜度都是O (n log n)。(f)39. 字

18、符串是數(shù)據(jù)對象特定的線性表。40. 空串與空格串是相同的。(f)41. 對于一棵m階的B-樹樹中每個結(jié)點至多有m個關(guān)鍵字.除根之外的所有非終端結(jié)點至少有廠m/2個關(guān)鍵字。(f)42. 當(dāng)二叉排序樹是一棵平衡二叉樹時，其平均查找長度為O(log2n)。(t)43. 廣義表的表頭和表尾都是廣義表。44二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表。選擇題。1從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成(_c_J。A. 動態(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)實現(xiàn)。A.不需修改L的結(jié)構(gòu)B.需不斷對L進(jìn)行刪除、插入C.需經(jīng)常修改L中結(jié)點值D.

19、 L中含有大量結(jié)點3帶頭結(jié)點的單鏈表 L為空的判斷條件是b_帶頭結(jié)點的循環(huán)鏈表L為空的判斷條件是 。A. L=n ullB. L-n ext=n ullC. L- next=L D. L!=null4若順序表中各結(jié)點的查找概率不等，則可用如下策略提高順序查找的效率：若找到指定的結(jié)點，將該結(jié)點與其后繼（若存在）結(jié)點交換位置，使得經(jīng)常被查找的結(jié)點逐漸移至 表尾。以下為據(jù)此策略編寫的算法，請選擇適當(dāng)?shù)膬?nèi)容，完成此功能。順序表的存儲結(jié)構(gòu)為：typedef structElemType *elem; /數(shù)據(jù)元素存儲空間，0號單元作監(jiān)視哨int len gth; / 表長度SSTable;int sear

20、ch_seq(SSTable ST,KeyType key) /在順序表ST中順序查找關(guān)鍵字等于key的數(shù)據(jù)元素。0。若找到，則將該元素與其后繼交換位置，并返回其在表中的位置，否則為ST.elem0.key=key;i=ST.le ngth;while(ST.elemi.key!=key)f; _if(G)ST.elemi ST.elemi+1;在下列數(shù)據(jù)結(jié)構(gòu)中（cb）具有先進(jìn)后出（FILO ）a.線性表8若對編號為a:1,2,3）具有先進(jìn)先出（FIFO）特性, 特性。c.隊列d.廣義表b.棧1 , 2, 3的列車車廂依次通過扳道棧進(jìn)行調(diào)度，不能得到b:1,3,2c:2,1,3d:2,3,1e

21、:3,1,2f:3,2,1（b ）這種數(shù)據(jù)結(jié)構(gòu)。（e ）的序列。9在計算遞歸函數(shù)時，如不用遞歸過程，應(yīng)借助于A.線性表B.棧C.隊列D.雙向隊列若帶頭結(jié)點的鏈表只設(shè)尾結(jié)點指針。下列選擇中（ 單鏈表 B）雙向鏈表 C循環(huán)單鏈表 棧和隊列的一個共同點是（cA.都是先進(jìn)先出C.只允許在端點處插入和刪除元素循環(huán)隊列用數(shù)組 A0.m-1存放其元素值， 的元素個數(shù)是（c ）。A. rear-fro nt-1B. Rear-fro nt+1C. （rear-fr on t+m）%mD. Rear-fro nt13如下關(guān)于串的陳述中，正確的是A.串是數(shù)據(jù)元素類型特殊的線性表10A)1112）。c）最適用于隊列

22、。D）雙向循環(huán)鏈表B.都是先進(jìn)后出D.沒有共同點設(shè)頭尾指針分別為front和rear,則當(dāng)前隊列中（a, cB.串中的元素是字母）。e;return i;JA.i0B. i=0C. iST.le ngthD. i next= S ; S- next = P- next;FTTB的后根遍歷相當(dāng)于 B 的中序遍歷。Tm個關(guān)鍵字。除根之外的所有非終端結(jié)5 .一個無向圖的連通分量是其極大的連通子圖。6. 鄰接表可以表示有向圖，也可以表示無向圖。7 .假設(shè)B是一棵樹，B 是對應(yīng)的二叉樹。則8.通常，二叉樹的第i層上有2i-1個結(jié)點。F9 對于一棵 m階的B-樹，樹中每個結(jié)點至多有 點至少有 m/2個關(guān)鍵

23、字。F10.對于任何待排序序列來說，快速排序均快于起泡排序。F1.選擇題（每題2分共28分）1. 在下列排序方法中，（c ）方法平均時間復(fù)雜度為0（nlogn），最壞情況下時間復(fù)雜度為0（ n2）; （ d ）方法所有情況下時間復(fù)雜度均為0（nlogn）。a.插入排序 b.希爾排序 c.快速排序 d. 堆排序2.在有n個結(jié)點的二叉樹的二叉鏈表表示中，空指針數(shù)為（b ）。a.不定b. n+1c.nd.n-13.下列二叉樹中，（a）可用于實現(xiàn)符號不等長高效編碼。a.最優(yōu)二叉樹b.次優(yōu)查找樹c.二叉平衡樹?d.二叉排序樹4.下列查找方法中，（a ）適用于查找有序單鏈表。a.順序查找b.二分查找c.分

24、塊查找d.哈希查找5. 在順序表查找中，為避免查找過程中每一步都檢測整個表是否查找完畢，可采用（a ）方法。a.設(shè)置監(jiān)視哨b.鏈表存貯c.二分查找d.快速查找6. 在下列數(shù)據(jù)結(jié)構(gòu)中，（c ）具有先進(jìn)先出特性，（b ）具有先進(jìn)后出特性。a.線性表 b .棧 c .隊列 d.廣義表7. 具有m個結(jié)點的二叉排序樹，其最大深度為（f）,最小深度為（b）。a. log 2 mb. L log2 m+1c. m/2d .廠 m/2 n -1e.廠 m/2 nf. m8 .已知一組待排序的記錄關(guān)鍵字初始排列如下：56,34,58,26,79,52,64,37,28,84,57。a. 84,79,64,37,

25、57,52,58,26,28,34,56。b. 28，34,57,26,56,52,58,37,79,84,64。c. 28，34,37,26,52,56,64,79,58,84,57。d. 52，34,64,84,56,26,37,57,58,28,79。e. 34,56,26,58,52,64,37,28,79,57,84。f. 34，56,26,58,52,79,37,64,28,84,57。.填空題（每題2分共20 分卜）oF列選擇中（c）是快速排序一趟排序的結(jié)果。（b）是希爾排序（初始步長為 4） 一趟排序的結(jié)果。（e）是起泡排序一趟排序的結(jié)果。（a）是初始堆（大堆頂）1有向圖的存儲

26、結(jié)構(gòu)有（鄰接矩陣）、（鄰接表）、（十字鏈表）等方法。 2已知某二叉樹的先序遍歷次序為其后序遍歷次序為（3.已知如下程序段for（ i=n; i0; i-） x+;for（ j=n; j=i; i-）y+;edcgbfa)。語句四.afbcdeg，中序遍歷次序為 cedbgfa。層次遍歷次序為（afbcgde ）。1語句語句3語句42；語句1執(zhí)行的頻度為.請在下劃線上填入適當(dāng)?shù)恼Z句，完成以下法算。Status Preordertraverse(Bitree T,Status(*Visit)(Telemtype e)/先序非遞歸遍歷二叉樹。Ini tstack ( S );Push ( S,T )

27、;While ( !stackempty( S ) While ( gettop( S, p )& p ) visit (p-data ) ; push(S, p-lchild ; Pop ( S , p );If ( !stackempty(s) ) pop(S, p) ; push( S, p-rchild ); return ok;簡答題(每題5分共25分)1.將圖示森林轉(zhuǎn)換為二叉樹，并對該二叉樹中序全序線索化。n+1）;語句4執(zhí)行的頻度為（n（n+1）/2 ）。a01:56 :52 922 .已知 Hash函數(shù)為，散列地址為，12, 49, 戈成功的平均查找長度。Aa34=K mod

28、13 ，56，24,6834ASL=223.右圖為一棵3階B樹。（20，25）a.畫出在該樹上插入元素 1 B樹。g014,/ 1A 0 1 12131449弓二次探測再散列處2，06，55）在散列b.c.a.a.4.已知某無向圖的鄰接表存儲結(jié)；.請畫出該圖。b. 根據(jù)存儲結(jié)構(gòu)給出其深度優(yōu)先遍歷序列及廣度優(yōu)先遍歷序列。c. 畫出其深度優(yōu)先生成樹及廣度優(yōu)先生成樹。b.接著，再刪除元素 35,畫出刪除后的 B樹。1420101521,25(10,14)( 21)( 35) b.a10d.15221LDFSacbd設(shè)在某通信系統(tǒng)044 ,5.0.26 , 0.18 2赫夫曼編碼3：0.08:0000

29、.05:0110 40.10:0020.12:010353八eylBFS:飛沖使用了個字符 它們出現(xiàn)的頻率分別為acebd 2d10ec0卄，試構(gòu)造一棵赫夫曼樹I并給局夫曼編碼0八赫夫曼樹：0.26:100.18:1100.14:111 b0.07:0111五算法設(shè)計題（共17分）結(jié)點的類型定義如下:1.typedef struct LNode int data;struct LNode *n ext; LNode, *Li nklist;寫一算法，將帶頭結(jié)點的有序單鏈表A0.05 , 0.1 ,0.12 ,81012145 Ja26和B合并成一新的有序表Co(注:不破壞A和B的原有結(jié)構(gòu).)M

30、erge(Linklist A, Linklist B, Linklist &C ) void Merge(Linklist A, Linklist B, Linklist &C) C=(Li nklist)malloc(sizeof(LNode);pa=A- n ext; pb=B-n ext; pc=C; while(pa&pb) pc-n ext=(Li nklist)malloc(sizeof(LNode); pc=pc- n ext;if(pa-datadata) pc-data=pa-data; pa=pa-n ext; else pc-data=pb-data; pb=pb-n

31、ext;if(!pa) pa=pb;while(pa) pc-n ext=(Li nklist)malloc(sizeof(LNode); pc=pc- n ext;pc-data=pa-data; pa=pa-next;pc-next=NULL;2. 二叉樹用二叉鏈表存儲表示。 typedef struct BiTNode TelemType data; Struct BiTNode *lchild, *rchild; BiTNode, *BiTree; 編寫一個復(fù)制一棵二叉樹的遞歸算法。BiTree CopyTree(BiTree T) if (!T ) return NULL ;if (!(newT = (BiTNode * )malloc( sizeof(BiTNode) exit(Overflow);newT- data = T- data;newT- lchild =CopyTree(T- lchild);newT- rchild =CopyTree(T- rchild); return newT; / CopyTree