杭電[數(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è)計問題中計算機(jī)的操作對象以及它們之間的關(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)的特點 二.

2、 線性表的存儲結(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.線性表的邏輯順序與存儲順序總是一致的。 F 2. 線性結(jié)構(gòu)的基本特征是：每個結(jié)點有且僅有一個直接前驅(qū)和一個直接后繼。 F 3. 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)優(yōu)于順序存儲結(jié)構(gòu)。 F 選擇題：線性表L在（B ）情況下適于使用鏈表結(jié)構(gòu)實現(xiàn)

3、。 A.不需修改L的結(jié)構(gòu) B.需不斷對L進(jìn)行刪除、插入 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)) 二. 隊列

4、 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ù)語：長度、子串 三. 串

5、的基本操作：求串的長度、求子串、串聯(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,Con

6、cat (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)用：給定二叉樹的先序和中序(或

7、后序和中序)序列，畫岀相應(yīng)的二叉樹 4. 線索二叉樹：先序、中序、后序線索化 三. 樹和森林 1. 樹的存儲結(jié)構(gòu)：雙親表示法 孩子表示法 孩子-兄弟(二叉樹)表示法 2. 樹(森林)與二叉樹的相互轉(zhuǎn)換 3. 樹的遍歷：先根、后根次序遍歷 4. 森林的遍歷：先序、中序遍歷 四. 赫夫曼樹及其應(yīng)用 1. 最優(yōu)二叉樹（赫夫曼樹），求 WPL 2. 赫夫曼編碼 五. 各種二叉樹概念的區(qū)分 1. 滿二叉樹 2. 完全二叉樹 3. 正則二叉樹（嚴(yán)格二叉樹） 4. 最優(yōu)二叉樹 5. （折半查找的）判定樹 6. 二叉排序樹 7. 平衡二叉樹 8. 堆 六

8、. 二叉樹有關(guān)的遞歸算法 例： 判斷題：1.已知二叉樹的先序序列和后序序列并不能唯一地確定這棵二叉樹， 因為不知道二叉樹的根結(jié)點 是哪一個。f i-1 k 2. 一般二叉樹的第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)行編號，并采用順序存儲表示，則 編號為

9、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ù)語 無向圖、有向圖、（無向/有向）完全圖、子圖、（強(qiáng)）連

10、通圖、（強(qiáng)）連通分量、生成樹 二. 圖的存儲結(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如下

11、，畫岀該有向圖的鄰接矩陣和鄰接表，并根據(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.

12、哈希函數(shù)的構(gòu)造方法 3. 處理沖突的方法 4. 哈希表的造表、查找 四. 平均查找長度的計算 1. 等概率情況下，查找成功時的平均查找長度 ASL 2. 查找不成功時的查找長度 例： 判斷題：1.任一個二叉排序樹的平均查找長度都小于用順序查找法查找同樣結(jié)點的線性表的平均查找長 度。 2.當(dāng)二叉排序樹是一棵平衡樹時，其平均查找長度為 O（log2n）。 選擇題：1.折半查找算法要求被查找的表是 （c ）。 A.鍵值有序的鏈表 B.鍵值不一定有序的鏈表 C.鍵值有序的順序表 D.鍵值不一定有序的順序表 2.若查找表是一個有序的單鏈表，則應(yīng)采用 （a）方法。 A.順序查

13、找 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,用開放定址法的二次探測再散列處

14、理沖突。 依次存入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,4

15、5,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)可用三元式表示(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é)點是最后一個

16、元素結(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ù)元素的操作

17、僅限一端進(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 '的后序遍歷。(f) 19. 通常，二叉樹的第i層上有2-1個結(jié)點。⑴ 2

18、0. 中序線索二叉樹的優(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 一個無向圖的連通分量是其極大的連通子圖

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

20、ogn),比快速排序好⑴ 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)

21、結(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. L中含有大量結(jié)點 3帶頭結(jié)點的單鏈表 L為空的判斷條件是 b_ 帶頭結(jié)點的循環(huán)鏈表 L為空的判斷條件是 。 A. L==n ullB. L->n ext==n ull C. L-> next==L D. L!=null 4若順序表中各結(jié)點的查找概率不等，則可用如下策略提高順序查找的效率：若找到指定的結(jié)點，將該結(jié)點與其后繼（若存在）結(jié)點交換位置，使得經(jīng)常被查找的結(jié)點

22、逐漸移至 表尾。以下為據(jù)此策略編寫的算法，請選擇適當(dāng)?shù)膬?nèi)容，完成此功能。 順序表的存儲結(jié)構(gòu)為： typedef struct{ ElemType *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.elem[0].key=key; i=ST.le ngth; while(ST.elem[i].

23、key!=key)f; _ if( G—) {ST.elem[i] <--> ST.elem[i+1]; 在下列數(shù)據(jù)結(jié)構(gòu)中（c b）具有先進(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,2 c:2,1,3 d:2,3,1 e:3,1,2 f:3,2,1 （b ）這種數(shù)據(jù)結(jié)構(gòu)。 （e ）的序列。 9在計算遞歸函數(shù)時，如不用遞歸過程，應(yīng)借助于 A.線性表B.棧C.隊列D.雙向隊列 若帶頭結(jié)點的鏈表只設(shè)尾結(jié)

24、點指針。下列選擇中（ 單鏈表 B）雙向鏈表 C循環(huán)單鏈表 棧和隊列的一個共同點是 （c A.都是先進(jìn)先出 C.只允許在端點處插入和刪除元素 循環(huán)隊列用數(shù)組 A[0..m-1]存放其元素值， 的元素個數(shù)是（c ）。 A. rear-fro nt-1B. Rear-fro nt+1 C. （rear-fr on t+m）%mD. Rear-fro nt 13如下關(guān)于串的陳述中，正確的是 A.串是數(shù)據(jù)元素類型特殊的線性表 10 A) 11 12 ）。 c）最適用于隊列。 D）雙向循環(huán)鏈表 B.都是先進(jìn)后出 D.沒有共同點 設(shè)頭尾指針分別為front和rear,則當(dāng)前

25、隊列中 （a, c B.串中的元素是字母 ）。 e; } return i; J A. i>0 B. i>=0 C. i

26、 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 )

27、a: 220 b: 200 c: 140 d: 124 16 對廣義表 A= ((a,(b)),(c,()),d )執(zhí)行操作 gettail(gethead(gettail(A))) 的結(jié)果是：(b) o a: () b: (0) c: d d: (d) 17假設(shè)用于通訊的電文僅由 6個字符組成，字母在電文中出現(xiàn)的頻率分別為 7, 19, 22, 6, 32, 14o若為這6個字母設(shè)計哈夫曼編碼(設(shè)生成新的二叉樹的規(guī)則是按給出的次序從左至 右的結(jié)合，新生成的二叉樹總是插入在最右) ，則頻率為7的字符編碼是( g ),頻率 為32的字符編碼是( c )o a: 00 b: 01

28、c: 10 d: 11 e: 011 f: 110 g: 1110 h:1111 18對二叉排序樹( c )可得到有序序列。 a:按層遍歷 b:前序遍歷 c:中序遍歷 d:后序遍歷 19設(shè)一棵二叉樹 BT的存儲結(jié)構(gòu)如下： 1 2 3 4 5 6 7 8 第3層有( a )個結(jié)點(根結(jié)點為第 1層)。 A . 2 B. 3 C. 4 D. 5 20先序遍歷圖示二叉樹可得到( a )的序列。 (A) / \ (B) (C) / \ \ (H) (D) (G) / \ (E) (F) \ (I) a) A B H D E F I C G b) H B E

29、 D F I A C G c) H E I F D B G C A 21在有n個結(jié)點的二叉樹的二叉鏈表表示中，空指針數(shù) (b )o a.不定 b.n+1 c.n d.n-1 22若某二叉樹有20個葉子結(jié)點，有20個結(jié)點僅有一個孩子，則該二叉樹的總結(jié)點數(shù)是 ）。 A. 40 B.55 23已知某二叉樹的先序遍歷次序為 則該二叉樹的后序遍歷次序為（ C. 59 abcdefg中序遍歷次序為 c ）。層次遍歷次序為（ D. 61 badcgfe, a ) o a: abcdefg b: cdebgfa c: bdgfeca .24圖示的三棵二叉樹中（c）為最優(yōu)二叉樹。

30、 d: edcgfba 2 7 5 4 25已知某二叉樹的后序遍歷和中序遍歷次序分別為 DBFGECA和BDACFEG。 則其先序遍歷次序為（ b ），層次遍歷次序為（a ）o a: abcdefg b: abdcefg c: abcdfeg d: abcdegf 26已知某樹的先根遍歷次序為 abcdefg后根遍歷次序為 cdebgfa。 若將該樹轉(zhuǎn)換為二叉樹，其后序遍歷次序為（ d ）o a: abcdefg b: cdebgfa c: cdegbfa d: edcgfba 27設(shè)x和y是二叉樹中的任意兩個結(jié)點，若在先根序列中 x在y之前，而在后根序列中 x 在

31、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-1 B. n C. n+1 D. n+2 29對一棵完全二叉樹進(jìn)行層序編號。則編號為 n的結(jié)點若存在右孩子，其位序是（d ）o 編號為n的結(jié)點若存在雙親，其位置是（a ）o a:n/2 b: 2n c:2 n-1 d:2 n+1 e:n f: 2（n +1） 30設(shè)森林F中有三棵樹，第一、第二和第三棵樹的結(jié)點個數(shù)分別為 m1、m2和m3，則與 森林F對應(yīng)的二叉樹根結(jié)點的

32、右子樹上的結(jié)點個數(shù)是 （_d_）。 A. m1B. m1+m2 C. m3 D. m2+m3 31下列二叉樹中，（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 = V 34任何一個連通圖的

33、最小生成樹 （±J。 A ?只有一棵 B.有一棵或多棵 C. 一定有多棵 D.可能不存在 e f e f 35深度優(yōu)先遍歷圖使用了數(shù)據(jù)結(jié)構(gòu)（ b ），而廣度優(yōu)先遍歷圖使用了數(shù)據(jù)結(jié)構(gòu)（ c ）o A）數(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）適用于求圖的最小代價生成樹

34、。 h: ac 及 bed D） 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 m A.奇數(shù) B.偶數(shù) ）。 c:哈希表的裝填因子。 d:以上都是 中，一般來說，m應(yīng)?。╟ ） o C.素數(shù) D.充分大的數(shù) 4

35、2在順序表查找中，為避免查找過程中每一步都檢測整個表是否查找完畢, 可采用a方法。 A.設(shè)置監(jiān)視哨 B.鏈表存貯 C.二分查找 D.快速查找 43靜態(tài)查找表和動態(tài)查找表的區(qū)別在于 （b ）o A. 前者是順序存儲，而后者是鏈?zhǔn)酱鎯? B. 前者只能進(jìn)行查找操作，而后者可進(jìn)行查找、插入和刪除操作 C. 前者只能順序查找，而后者只能折半查找 D. 前者可被排序，而后者不能被排序 44在一個含有n個元素的有序表上進(jìn)行折半查找， 找到一個元素最多要進(jìn)行 （b ）次元素 比較。 A . Iljog2（n）」 B. Iljog2（n） +1 C.」og2（n+1）」 D. ILlog2（n

36、+1） +1 45設(shè)輸入序列為20,45,30,89,70,38,62 ,19依次插入到一棵 2-3樹中（初始狀態(tài)為空）， (30 62 ) (19, 20) ( 38 45 ) ( 70, 89 ) (19 20) (38 ) ( 62 ) ( 89 ) a: (19) ( 30 ) (19 ) ( 30,38 ) ( 62 ) ( 89 ) 該B-樹為（b ）。再刪除38,該B-樹為（f ）o c: d: ( / (19, 20) ( 45 62) 30 70 ) I \ (89 ) (20 ) (19 ) (30 ) ( 62 ) ( 89 )

37、 e: 46 根據(jù)插入次序(80, 90, 100, 110, 85, 70, 75, 60, 72) 圖(a)是最終變化的結(jié)果。若仍以該插入次序建立平衡二叉樹。 終變化的結(jié)果。 80 f: 建立二叉排序樹。 圖( c)是最 70 80 60 75 75 60 72 110 72 a: 90 75100 80 7080 75 60 72 110 60 70 90 72 b: 100 90 85 10 110 70 85 11 c: 47若有序表中關(guān)鍵字序列為： 折半查找，則在等概率情況下，查找成功時的平均查找長度是 行(c

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

39、)p A.二叉排序樹 B.赫夫曼樹 C.堆 D.平衡二叉樹 50當(dāng)待排序序列的關(guān)鍵字次序為倒序時，若需為之進(jì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已知一組待排序的

40、記錄關(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)。 F

41、2. 棧和隊列也是線性表。如果需要，可對它們中的任一元素進(jìn)行插入 /刪除操作。F 3. 棧是數(shù)據(jù)對象特定的線性表。F 4 .在單鏈表P指針?biāo)附Y(jié)點之后插入 S結(jié)點的操作是: P-> next= S ; S-> next = P-> next; F T T B的后根遍歷相當(dāng)于 B '的中序遍歷。T m個關(guān)鍵字。除根之外的所有非終端結(jié) 5 .一個無向圖的連通分量是其極大的連通子圖。 6. 鄰接表可以表示有向圖，也可以表示無向圖。 7 .假設(shè)B是一棵樹，B '是對應(yīng)的二叉樹。則 8.通常，二叉樹的第i層上有2i-1個結(jié)點。F 9 ?對于一棵 m階的B-樹，樹中每個結(jié)點至多有

42、點至少有 m/2個關(guān)鍵字。F 10.對于任何待排序序列來說，快速排序均快于起泡排序。 F 1.選擇題（每題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+1 c.n d.n-1 3. 下列二叉樹中，（a ）可用于實現(xiàn)符號不等長高效編碼。 a.最優(yōu)二叉樹 b. 次優(yōu)查找樹 c.

43、二叉平衡樹 ??d.二叉排序樹 4. 下列查找方法中，（ a ）適用于查找有序單鏈表。 a.順序查找 b. 二分查找 c. 分塊查找 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 m b. L log2 m」+

44、1 c. m/2 d .廠 m/2 n -1 e.廠 m/2 n f. m 8 .已知一組待排序的記錄關(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,

45、 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 分 卜） o F列選擇中（c）是快速排序一趟排序的結(jié)果。 （b）是希爾排序（初始步長為 4） 一趟排序的結(jié)果。 （e）是起泡排序一趟排序的結(jié)果。 （a）是初始堆（大堆頂） 1?有向圖的存儲結(jié)構(gòu)有（鄰接矩陣）、（鄰接表）、（十字鏈表）等方法。

46、2?已知某二叉樹的先序遍歷次序為 其后序遍歷次序為（ 3.已知如下程序段 for（ i=n; i>0; i--） ｛ x++; for（ j=n; j>=i; i--） y++; edcgbfa)。 ｛語句 四. afbcdeg，中序遍歷次序為 cedbgfa。 層次遍歷次序為（afbcgde ）。 1} ｛語句 ｛語句3｝ ｛語句4｝ 2} }； 語句1執(zhí)行的頻度為 .請在下劃線上填入適當(dāng)?shù)恼Z句，完成以下法算。 Status Preordertraverse(Bitree T,Status(*Visit)(Telemtype e)){ //先序非遞歸

47、遍歷二叉樹。 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）/

48、2 ）。 a 0 1 :56 : 52 92 2 .已知 Hash函數(shù)為 ，散列地址為 『，12, 49, 戈成功的平均查找長度。 A a 3 4 =K mod 13 ，56，24, 6 8 34 ASL=22 3.右圖為一棵3階B樹。（20，25） a.畫出在該樹上插入元素 1「° ' B樹。 g 0 14, / 1 A \ 0 1\ 12 13 14 49 弓二次探測再散列處 2，06，55）在散列

49、 b. c. a. a. 4.已知某無向圖的鄰接表存儲結(jié)； . 請畫出該圖。 b. 根據(jù)存儲結(jié)構(gòu)給出其深度優(yōu)先遍歷序列及廣度優(yōu)先遍歷序列。 c. 畫出其深度優(yōu)先生成樹及廣度優(yōu)先生成樹。 b.接著，再刪除元素 35,畫出刪除后的 B樹。 14 20 10 15 21,25 (10,14)( 21)( 35) b. a 10 d. 15 2 21 L DFS^a cbd 設(shè)在某通信系統(tǒng) 044 , 5.

50、 0.26 , 0.18 2 赫夫曼編碼3： 0.08:000 0.05:0110 4 0.10:002 0.12:010 35 3 八 eylBFS: 飛沖使用了△個字符 它們出現(xiàn)的頻率分別為 acebd 2 d 1 0 e c 0卄，試構(gòu)造一棵赫夫曼樹I并給局夫曼編碼0八 赫夫曼樹： 0.26:10 0.18:110 0.14:111 b 0.07:0111 五?算法設(shè)計題（共17分） 結(jié)點的類型定義如下: 1. typedef struct LNode { int data; struct LNode *n ext;

51、 } LNode, *Li nklist; 寫一算法，將帶頭結(jié)點的有序單鏈表 A 0.05 , 0.1 , 0.12 , 8 10 12 14 5 J a 26 和B合并成一新的有序表 Co (注:不破壞A和B的原有結(jié)構(gòu).) Merge(Linklist A, Linklist B, Linklist &C ) void Merge(Linklist A, Linklist B, Linklist &C) { C=

52、(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

53、)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