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

數(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. 鏈?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進行刪除、插入C.需經(jīng)常修改L中結(jié)點值 填空題：1.對于順序表中，在第D. L中含有大量結(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和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 (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)第六章 樹和二叉樹一. 樹、二叉樹的定義二. 二叉樹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.正則二叉樹（嚴(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é)點從上到下，從左到右進行編號，并采用順序存儲表示，則 編號為i的結(jié)點，其雙親編號為i/2，其左孩子編號為2i（2i>n），其右孩子編號為2i+1 （2i+1>n）。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ù)語無向圖、有向圖、（無向/有向）完全圖、子圖、（強）連通圖、（強）連通分量、生成樹二. 圖的存儲結(jié)構(gòu)無向圖：鄰接矩陣、鄰接表、鄰接多重表有向圖：鄰接矩陣、鄰接表、逆鄰接表、十字鏈表三. 圖的遍歷（針對具體的存儲結(jié)構(gòu)進行）深度優(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ù)你的鄰接表分別寫岀深度優(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. 等概率情況下，查找成功時的平均查找長度ASL2. 查找不成功時的查找長度例：判斷題：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）。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.歸并排序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)進行排序，請寫出：(1).堆排序初始建堆(大頂堆)的結(jié)果；(2) .以第一個元素為樞軸的快速排序一趟掃描的結(jié)果；(3) .起泡排序第一趟的結(jié)果；(4) .希爾排序第一趟(增量 5)的結(jié)果(5) .基數(shù)排序第一趟的結(jié)果。附錄：期末復(fù)習(xí)題一.是非題(共分，每題分)I. 數(shù)據(jù)結(jié)構(gòu)可用三元式表示(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. 棧和隊列是操作上受限制的線性表。10. 隊列是與線性表完全不同的一種數(shù)據(jù)結(jié)構(gòu)。(f)II. 隊列是一種操作受限的線性表，凡對數(shù)據(jù)元素的操作僅限一端進行。(f)12. 棧和隊列也是線性表。如果需要，可對它們中的任一元素進行操作。(f)13. 棧是限定僅在表頭進行插入和表尾進行刪除運算的線性表。(f)14. 二叉樹中每個結(jié)點有兩個子結(jié)點，而對一般的樹，則無此限制，所以，二叉樹是樹的特殊情形。(f)15二叉樹是一棵結(jié)點的度最大為二的樹。16赫夫曼樹中結(jié)點個數(shù)一定是奇數(shù)。17在二叉樹的中序遍歷序列中，任意一個結(jié)點均處在其左孩子結(jié)點的后面。18 假設(shè)B是一棵樹，B '是對應(yīng)的二叉樹。則B的后根遍歷相當(dāng)于 B '的后序遍歷。(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一個無向圖的連通分量是其極大的連通子圖。(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. 字符串是數(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進行刪除、插入C.需經(jīng)常修改L中結(jié)點值D. 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 search_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）具有先進后出（FILO ）a.線性表8若對編號為a:1,2,3）具有先進先出（FIFO）特性, 特性。c.隊列d.廣義表b.棧1 , 2, 3的列車車廂依次通過扳道棧進行調(diào)度，不能得到b:1,3,2c:2,1,3d:2,3,1e: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.都是先進先出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）最適用于隊列。D）雙向循環(huán)鏈表B.都是先進后出D.沒有共同點設(shè)頭尾指針分別為front和rear,則當(dāng)前隊列中（a, cB.串中的元素是字母）。e;return i;JA.i>0B. i>=0C. i<ST.le ngthD. i<=ST.le ngthE.i+F. i-G. A和C同時滿足H. B和D5若入棧順序為A、B、C、D、E,則下列（d）出棧序列是不可能的。AA、B、C、D、EB . B、C、D、A、ECC、D、B、E、AD. D、E、C、A、B6遞歸程序可借助于（c）轉(zhuǎn)化為非遞歸程序。a線性表b.隊列c:棧d.數(shù)組同時滿足C.串中若干個元素構(gòu)成的子序列稱為子串D.空串即為空格串14 對字符串 s= ' datatructure 執(zhí)行操作 replace(s,substring(s,6,8),' bas ')的結(jié)果是(b )。a: database c-ctase ' c: bas ' d: dObasucture '15設(shè)有二維數(shù)組 A 5 x 7，每一元素用相鄰的4個字節(jié)存儲，存儲器按字節(jié)編址已知A的起始地址為100。則按行存儲時，元素Ao6的第一個字節(jié)的地址是(d )按列存儲時，元素 Ao6的第一個字節(jié)的地址是(a )a: 220 b: 200c: 140 d:12416 對廣義表 A= (a,(b),(c,(),d )執(zhí)行操作 gettail(gethead(gettail(A)的結(jié)果是：(b) oa: ()b: (0)c: dd: (d)17假設(shè)用于通訊的電文僅由 6個字符組成，字母在電文中出現(xiàn)的頻率分別為7, 19, 22, 6, 32,14o若為這6個字母設(shè)計哈夫曼編碼(設(shè)生成新的二叉樹的規(guī)則是按給出的次序從左至右的結(jié)合，新生成的二叉樹總是插入在最右)，則頻率為7的字符編碼是(g ),頻率為32的字符編碼是( c )oa: 00b: 01c: 10d: 11e: 011f: 110g: 1110h:111118對二叉排序樹( c )可得到有序序列。a:按層遍歷b:前序遍歷c:中序遍歷d:后序遍歷19設(shè)一棵二叉樹 BT的存儲結(jié)構(gòu)如下：12345678第3層有( a )個結(jié)點(根結(jié)點為第1層)。A . 2B. 3C. 4D. 520先序遍歷圖示二叉樹可得到( a )的序列。(A)/ (B)(C)/ (H)(D)(G)/ (E)(F)(I)a) A B H D E F I C Gb) H B E D F I A C Gc) H E I F D B G C A21在有n個結(jié)點的二叉樹的二叉鏈表表示中，空指針數(shù)(b )oa.不定b.n+1c.nd.n-122若某二叉樹有20個葉子結(jié)點，有20個結(jié)點僅有一個孩子，則該二叉樹的總結(jié)點數(shù)是）。A. 40B.5523已知某二叉樹的先序遍歷次序為 則該二叉樹的后序遍歷次序為（C. 59abcdefg中序遍歷次序為 c ）。層次遍歷次序為（D. 61badcgfe,a ) oa: abcdefg b: cdebgfa c: bdgfeca.24圖示的三棵二叉樹中（c）為最優(yōu)二叉樹。d: edcgfba275425已知某二叉樹的后序遍歷和中序遍歷次序分別為DBFGECA和BDACFEG。則其先序遍歷次序為（b ），層次遍歷次序為（a ）oa: abcdefg b: abdcefg c: abcdfegd: abcdegf26已知某樹的先根遍歷次序為abcdefg后根遍歷次序為 cdebgfa。若將該樹轉(zhuǎn)換為二叉樹，其后序遍歷次序為（ d ）oa: abcdefg b: cdebgfa c: cdegbfa d: edcgfba27設(shè)x和y是二叉樹中的任意兩個結(jié)點，若在先根序列中x在y之前，而在后根序列中 x在y之后，則x和y的關(guān)系是（c ）。A. x是y的左兄弟B. x是y的右兄弟C. x是y的祖先D. x是y的子孫28用三叉鏈表作二叉樹的存儲結(jié)構(gòu)，當(dāng)二叉樹中有n個結(jié)點時，有（d ）個空指針。A. n-1B. nC. n+1D. n+229對一棵完全二叉樹進行層序編號。則編號為n的結(jié)點若存在右孩子，其位序是（d ）o編號為n的結(jié)點若存在雙親，其位置是（a ）oa:n/2b: 2nc:2 n-1d:2 n+1e:nf: 2（n +1）30設(shè)森林F中有三棵樹，第一、第二和第三棵樹的結(jié)點個數(shù)分別為m1、m2和m3，則與森林F對應(yīng)的二叉樹根結(jié)點的右子樹上的結(jié)點個數(shù)是（_d_）。A. m1B. m1+m2 C. m3 D. m2+m331下列二叉樹中，（a ）可用于實現(xiàn)符號不等長高效編碼。a:最優(yōu)二叉樹b:次優(yōu)查找樹c:二叉平衡樹d:二叉排序樹32鄰接表存儲結(jié)構(gòu)下圖的深度優(yōu)先遍歷算法類似于二叉樹的（a ）遍歷。A.先根B.中根 C.后根D.層次33設(shè)無向圖G = （V,E）和G'= （V,E'），若G是G的生成樹，則下面不正確的說法是（b ）。A. G '是G的子圖 B. G 是 G的連通分量C. G是G的無環(huán)子圖D. G 是 G的極小連通子圖且 V = V34任何一個連通圖的最小生成樹（±J。A 只有一棵B.有一棵或多棵C. 一定有多棵D.可能不存在e fe f35深度優(yōu)先遍歷圖使用了數(shù)據(jù)結(jié)構(gòu)（ b ），而廣度優(yōu)先遍歷圖使用了數(shù)據(jù)結(jié)構(gòu)（ c ）oA）數(shù)組B ）棧C）隊列D）線性表36已知某有向圖的鄰接表存儲結(jié)構(gòu)如圖所示。a: abcde.b: edcba.c: ecdab.d:ecadb.）。e: abc及 ed f: bc 及 aed g: ab 及 ced 37下列查找方法中（a ）適用于查找單鏈表。A ）順序查找B ）折半查找C）分塊查找38下列算法中（c）適用于求圖的最小代價生成樹。h: ac 及 bedD） hash查找（b）能對圖作廣度優(yōu)先遍歷。A) DFS算法 B) BFS算法 C) Prim算法D) Dijkstra 算法39關(guān)鍵路徑是指在只有一個源點和一個匯點的有向無環(huán)網(wǎng)中源點至匯點（c ）的路徑。a:弧的數(shù)目最多 b:弧的數(shù)目最少c:權(quán)值之和最大d:權(quán)值之和最小40希表的查找效率取決于（ d a:哈希函數(shù) b:處理沖突的方法。41 在 Hash 函數(shù) H（k）=k MOD mA.奇數(shù)B.偶數(shù)）。c:哈希表的裝填因子。d:以上都是中，一般來說，m應(yīng)?。╟ ） oC.素數(shù) D.充分大的數(shù)42在順序表查找中，為避免查找過程中每一步都檢測整個表是否查找完畢, 可采用a方法。A.設(shè)置監(jiān)視哨B.鏈表存貯C.二分查找D.快速查找43靜態(tài)查找表和動態(tài)查找表的區(qū)別在于（b ）oA. 前者是順序存儲，而后者是鏈?zhǔn)酱鎯. 前者只能進行查找操作，而后者可進行查找、插入和刪除操作C. 前者只能順序查找，而后者只能折半查找D. 前者可被排序，而后者不能被排序44在一個含有n個元素的有序表上進行折半查找，找到一個元素最多要進行（b ）次元素比較。A . Iljog2（n） B. Iljog2（n） +1C.og2（n+1）D. ILlog2（n+1） +145設(shè)輸入序列為20,45,30,89,70,38,62 ,19依次插入到一棵 2-3樹中（初始狀態(tài)為空），(3062 )(19, 20) ( 38 45 )( 70, 89 )(19 20)(38 ) ( 62 )( 89 )a:(19) ( 30 )(19 )( 30,38 ) ( 62 )( 89 )該B-樹為（b ）。再刪除38,該B-樹為（f ）oc:d:(/(19, 20)( 45 62)3070)I (89 )(20 )(19 )(30 ) ( 62 )( 89 )e:46 根據(jù)插入次序(80, 90, 100, 110, 85, 70, 75, 60, 72) 圖(a)是最終變化的結(jié)果。若仍以該插入次序建立平衡二叉樹。 終變化的結(jié)果。80f:建立二叉排序樹。 圖(c)是最7080607575607211072a:90751008070807560 7211060709072b:100908510110708511c:47若有序表中關(guān)鍵字序列為： 折半查找，則在等概率情況下，查找成功時的平均查找長度是 行(c )次比較。48已知哈希表地址空間為A9，哈希函數(shù)為H(k)=k mod 7，采用線性探測再散列處理沖突。若依次將數(shù)據(jù)序列：76,45,88,21,94,77,17存入該散列表中，貝U元素17存儲的下標(biāo)為(h )； 在等概率情況下查找成功的平均查找長度為A.0B.1C.2D.3E. 4F. 5G. 614, 20,d:25, 32, 34, 45,57, 69, 77, 83, 92。對其進行(c )。查找32時需進)。H. 749若從二叉樹的根結(jié)點到其它任一結(jié)點的路徑上所經(jīng)過的結(jié)點序列按其關(guān)鍵字遞增有序， 則該二叉樹是(c )pA.二叉排序樹B.赫夫曼樹C.堆D.平衡二叉樹50當(dāng)待排序序列的關(guān)鍵字次序為倒序時，若需為之進行正序排序，下列方案中.為佳。A.起泡排序B.快速排序C.直接插入排序D.簡單選擇排序51下列排序算法中，g算法可能會出現(xiàn)：初始數(shù)據(jù)有序時，花費的時間反而最多。A.堆排序B.起泡排序C.歸并排序D.快速排序52在下列排序方法中，（c ）方法平均時間復(fù)雜度為O（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 ）是快速排序一趟排序的結(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.期末樣卷.是非題（每題1分共10分）1. 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)優(yōu)于順序存儲結(jié)構(gòu)。F2. 棧和隊列也是線性表。如果需要，可對它們中的任一元素進行插入/刪除操作。F3. 棧是數(shù)據(jù)對象特定的線性表。F4 .在單鏈表P指針?biāo)附Y(jié)點之后插入 S結(jié)點的操作是:P-> 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)鍵字。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.分塊查找d.哈希查找5. 在順序表查找中，為避免查找過程中每一步都檢測整個表是否查找完畢，可采用（a ）方法。a.設(shè)置監(jiān)視哨b.鏈表存貯c.二分查找d.快速查找6. 在下列數(shù)據(jù)結(jié)構(gòu)中，（c ）具有先進先出特性，（b ）具有先進后出特性。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,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有向圖的存儲結(jié)構(gòu)有（鄰接矩陣）、（鄰接表）、（十字鏈表）等方法。 2已知某二叉樹的先序遍歷次序為其后序遍歷次序為（3.已知如下程序段for（ i=n; i>0; 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 );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 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.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).)Merge(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->data<=pb->data) pc->data=pa->data; pa=pa->n ext; else pc->data=pb->data; pb=pb->n 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