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

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

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

2、 線性表的存儲(chǔ)結(jié)構(gòu) 1. 順序存儲(chǔ)結(jié)構(gòu)（順序表）插入/刪除元素時(shí)，需移動(dòng)元素 2. 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（鏈表，分為單向鏈表、雙向鏈表） 帶頭結(jié)點(diǎn)的鏈表和不帶頭結(jié)點(diǎn)的鏈表； 循環(huán)鏈表； 鏈表空與非空的情況。 3. 兩種存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)比較，各適合那些場(chǎng)合。 三. 線性表操作的實(shí)現(xiàn)（算法描述） 插入元素、刪除元素、查找、判表是否滿(mǎn)足某種特性 例： 判斷題：1.線性表的邏輯順序與存儲(chǔ)順序總是一致的。 F 2. 線性結(jié)構(gòu)的基本特征是：每個(gè)結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)和一個(gè)直接后繼。 F 3. 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)于順序存儲(chǔ)結(jié)構(gòu)。 F 選擇題：線性表L在（B ）情況下適于使用鏈表結(jié)構(gòu)實(shí)現(xiàn)

3、。 A.不需修改L的結(jié)構(gòu) B.需不斷對(duì)L進(jìn)行刪除、插入 C.需經(jīng)常修改L中結(jié)點(diǎn)值 填空題：1.對(duì)于順序表中，在第 D. L中含有大量結(jié)點(diǎn) i個(gè)元素前插入一個(gè)元素需移動(dòng) n-i+1個(gè)元素，要?jiǎng)h除第i個(gè)元素，需移動(dòng) n丄個(gè)元素。 2. 在雙向循環(huán)鏈表中某結(jié)點(diǎn)（由指針 p指示）之后插入s指針?biāo)附Y(jié)點(diǎn)的操作是: 第三章 棧和隊(duì)列 一. 棧 1. 棧的定義 2. 棧的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu) 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 3. 棧的應(yīng)用：二叉樹(shù)的先序、中序、后序遍歷算法 圖的深度優(yōu)先遍歷算法 (將遞歸算法改寫(xiě)為非遞歸算法可借助棧來(lái)完成； 遞歸算法的執(zhí)行需用棧來(lái)實(shí)現(xiàn)) 二. 隊(duì)列

4、 1. 隊(duì)列的定義 2. 隊(duì)列的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)(循環(huán)隊(duì)列) ，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 3. 隊(duì)列的應(yīng)用：二叉樹(shù)層序遍歷 圖的廣度優(yōu)先遍歷算法 4. 循環(huán)隊(duì)列：?隊(duì)空、隊(duì)滿(mǎn)的判斷條件 ?求隊(duì)列的長(zhǎng)度 ?循環(huán)隊(duì)列通常用 front和rear來(lái)指示隊(duì)頭和隊(duì)尾的位置來(lái)表示一個(gè)隊(duì)列；如 果用front指示隊(duì)頭，用length表示隊(duì)列的長(zhǎng)度，也可以表示一個(gè)隊(duì)列。相應(yīng)的 有關(guān)操作怎樣實(shí)現(xiàn)？ 例： 判斷題：因?yàn)闂Ｊ翘厥獾木€性表，所以對(duì)線性表的所有操作都可以用于對(duì)棧操作。 填空題：循環(huán)隊(duì)列隊(duì)滿(mǎn)的條件是 rear->front。 第四章 串 一. 串的定義 二. 串的術(shù)語(yǔ)：長(zhǎng)度、子串 三. 串

5、的基本操作：求串的長(zhǎng)度、求子串、串聯(lián)接、串替換、串匹配(子串定位) 例：已知下列字符串： a='THIS', b=''(一個(gè)空格)，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)))); 試問(wèn)：s，t，u，v，LENGTH(s)各是什么？ 第五章 數(shù)組和廣義表 一. 數(shù)組數(shù)組的順序存儲(chǔ)：行主順序法，列主順序法。元素存儲(chǔ)地址計(jì)算 特殊矩陣的壓縮存儲(chǔ) 元素存儲(chǔ)地址計(jì)算 二. 廣義表1.廣義表的概念：廣義表，長(zhǎng)度，深度，表頭，表尾； 2. 廣義表的頭尾鏈表存儲(chǔ)結(jié)構(gòu) 第六章 樹(shù)和二叉樹(shù) 一. 樹(shù)、二叉樹(shù)的定義 二. 二叉樹(shù) 1. 二叉樹(shù)的性質(zhì)(5條) 2. 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)(按層序存放) 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(二叉鏈表、三叉鏈表) (空指針域的個(gè)數(shù)) 3. 遍歷二叉樹(shù)：先序、中序、后序、層序 應(yīng)用：給定二叉樹(shù)的先序和中序(或

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

8、. 二叉樹(shù)有關(guān)的遞歸算法 例： 判斷題：1.已知二叉樹(shù)的先序序列和后序序列并不能唯一地確定這棵二叉樹(shù)， 因?yàn)椴恢蓝鏄?shù)的根結(jié)點(diǎn) 是哪一個(gè)。f i-1 k 2. 一般二叉樹(shù)的第i層上有2 個(gè)結(jié)點(diǎn)，深度為k的二叉樹(shù)有2 -1個(gè)結(jié)點(diǎn)。f 選擇題：1.下列二叉樹(shù)中，（a ） 可用于實(shí)現(xiàn)符號(hào)不等長(zhǎng)高效編碼。 A.最優(yōu)二叉樹(shù) B.二叉查找樹(shù) C.平衡二叉樹(shù) ？？ D.二叉排序樹(shù) 2 ?結(jié)點(diǎn)數(shù)為n的二叉樹(shù)高度至多為 （b）。 A.不定 B. n C. [og?* +1 D.log?* 填空題：1.將滿(mǎn)二叉樹(shù)（含n個(gè)結(jié)點(diǎn)）中各結(jié)點(diǎn)從上到下，從左到右進(jìn)行編號(hào)，并采用順序存儲(chǔ)表示，則 編號(hào)為

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

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

11、，畫(huà)岀該有向圖的鄰接矩陣和鄰接表，并根據(jù)你的鄰接表分別寫(xiě)岀深度優(yōu)先遍歷和 1. 順序查找表（設(shè)置崗哨） 2. 有序查找表（折半/二分查找） 要求：元素值有序的順序表 3. 索引順序查找表 二. 動(dòng)態(tài)查找表 1. 二叉排序樹(shù)（二叉查找樹(shù)） 定義、查找、插入、刪除 從空樹(shù)開(kāi)始創(chuàng)建一棵二叉排序樹(shù) 2. 平衡二叉樹(shù) 定義、查找、插入 從空樹(shù)開(kāi)始創(chuàng)建一棵平衡的二叉排序樹(shù) 3. n個(gè)元素的二叉排序樹(shù)、平衡二叉樹(shù)的深度 4. B-樹(shù)（B+樹(shù)）（常用于文件系統(tǒng)） 定義、查找、插入、刪除從空樹(shù)開(kāi)始創(chuàng)建一棵 3階B-樹(shù) （2-3 樹(shù)） 三. 哈希表 1. 哈希表的定義 2.

12、哈希函數(shù)的構(gòu)造方法 3. 處理沖突的方法 4. 哈希表的造表、查找 四. 平均查找長(zhǎng)度的計(jì)算 1. 等概率情況下，查找成功時(shí)的平均查找長(zhǎng)度 ASL 2. 查找不成功時(shí)的查找長(zhǎng)度 例： 判斷題：1.任一個(gè)二叉排序樹(shù)的平均查找長(zhǎng)度都小于用順序查找法查找同樣結(jié)點(diǎn)的線性表的平均查找長(zhǎng) 度。 2.當(dāng)二叉排序樹(shù)是一棵平衡樹(shù)時(shí)，其平均查找長(zhǎng)度為 O（log2n）。 選擇題：1.折半查找算法要求被查找的表是 （c ）。 A.鍵值有序的鏈表 B.鍵值不一定有序的鏈表 C.鍵值有序的順序表 D.鍵值不一定有序的順序表 2.若查找表是一個(gè)有序的單鏈表，則應(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的元素時(shí)，需依次比較關(guān)鍵字（c）。 A. 40,58,87 B. 46,87 C. 40,66,87 D. 46,66,87 應(yīng)用題：1.已知如下所示長(zhǎng)度為 8的表：（12，71, 36, 45, 47，50, 2, 9），按表中元素順序構(gòu)造一棵平衡 的二叉排序樹(shù)，請(qǐng)畫(huà)岀該樹(shù)。 （二叉排序樹(shù)，2-3樹(shù)） 2.設(shè)哈希表長(zhǎng)為16,哈希函數(shù)為H(key)=key mod13,用開(kāi)放定址法的二次探測(cè)再散列處

14、理沖突。 依次存入10個(gè)元素：17,24,36,21,83,96,13,34,57,46 ，請(qǐng)畫(huà)出它們?cè)诒碇械姆植记樾巍? 第十章 內(nèi)部排序 一.內(nèi)部排序的方法 1. 直接插入排序 2. 希爾排序 3. 起泡排序 4. 快速排序 5. 簡(jiǎn)單選擇排序 6. 堆排序 7. 歸并排序 8. 基數(shù)排序 二.各種內(nèi)部排序方法的比較 (最好、最壞、平均)時(shí)間復(fù)雜度 平均空間復(fù)雜度 例： 判斷題：歸并排序和堆排序的平均時(shí)間和最壞情況下的時(shí)間性能都是 O(nlogn),因此，它們?cè)谧顗那闆r下 的時(shí)間性能比快速排序好。 應(yīng)用題：若要按升序?qū)﹃P(guān)鍵字序列 (36,4

15、5,85,16,23,16,58,22,59,74,12,46)進(jìn)行排序，請(qǐng)寫(xiě)出：(1).堆排序初始 建堆(大頂堆)的結(jié)果； (2) .以第一個(gè)元素為樞軸的快速排序一趟掃描的結(jié)果； (3) .起泡排序第一趟的結(jié)果； (4) .希爾排序第一趟(增量 5)的結(jié)果 (5) .基數(shù)排序第一趟的結(jié)果。 附錄： 期末復(fù)習(xí)題 一.是非題(共分，每題分) I. 數(shù)據(jù)結(jié)構(gòu)可用三元式表示(D，S，P)。其中：D是數(shù)據(jù)對(duì)象，S是D上的關(guān)系，P是對(duì) D的基本操作集。⑴ 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è)

16、元素結(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) 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) II. 隊(duì)列是一種操作受限的線性表，凡對(duì)數(shù)據(jù)元素的操作

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

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

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

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

21、結(jié)構(gòu) B.順序組織和鏈接組織 C.線性結(jié)構(gòu)和非線性結(jié)構(gòu) D.基本類(lèi)型和組合類(lèi)型 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為空的判斷條件是 。 A. L==n ullB. L->n ext==n ull C. L-> next==L D. L!=null 4若順序表中各結(jié)點(diǎn)的查找概率不等，則可用如下策略提高順序查找的效率：若找到指定的結(jié)點(diǎn)，將該結(jié)點(diǎn)與其后繼（若存在）結(jié)點(diǎn)交換位置，使得經(jīng)常被查找的結(jié)點(diǎn)

22、逐漸移至 表尾。以下為據(jù)此策略編寫(xiě)的算法，請(qǐng)選擇適當(dāng)?shù)膬?nèi)容，完成此功能。 順序表的存儲(chǔ)結(jié)構(gòu)為： typedef struct{ ElemType *elem; //數(shù)據(jù)元素存儲(chǔ)空間，0號(hào)單元作監(jiān)視哨 int len gth; // 表長(zhǎng)度 }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若對(duì)編號(hào)為 a:1,2,3 ）具有先進(jìn)先出（FIFO）特性, 特性。 c.隊(duì)列 d.廣義表 b.棧 1 , 2, 3的列車(chē)車(chē)廂依次通過(guò)扳道棧進(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在計(jì)算遞歸函數(shù)時(shí)，如不用遞歸過(guò)程，應(yīng)借助于 A.線性表B.棧C.隊(duì)列D.雙向隊(duì)列 若帶頭結(jié)點(diǎn)的鏈表只設(shè)尾結(jié)

24、點(diǎn)指針。下列選擇中（ 單鏈表 B）雙向鏈表 C循環(huán)單鏈表 棧和隊(duì)列的一個(gè)共同點(diǎn)是 （c A.都是先進(jìn)先出 C.只允許在端點(diǎn)處插入和刪除元素 循環(huán)隊(duì)列用數(shù)組 A[0..m-1]存放其元素值， 的元素個(gè)數(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ù)元素類(lèi)型特殊的線性表 10 A) 11 12 ）。 c）最適用于隊(duì)列。 D）雙向循環(huán)鏈表 B.都是先進(jìn)后出 D.沒(méi)有共同點(diǎn) 設(shè)頭尾指針?lè)謩e為front和rear,則當(dāng)前

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

26、 d.數(shù)組 同時(shí)滿(mǎn)足 C.串中若干個(gè)元素構(gòu)成的子序列稱(chēng)為子串 D.空串即為空格串 14 對(duì)字符串 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個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址 ? 已知A的起始地址為100。則按行存儲(chǔ)時(shí)，元素 Ao6的第一個(gè)字節(jié)的地址是(d ) 按列存儲(chǔ)時(shí)，元素 Ao6的第一個(gè)字節(jié)的地址是( a )

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

28、c: 10 d: 11 e: 011 f: 110 g: 1110 h:1111 18對(duì)二叉排序樹(shù)( c )可得到有序序列。 a:按層遍歷 b:前序遍歷 c:中序遍歷 d:后序遍歷 19設(shè)一棵二叉樹(shù) BT的存儲(chǔ)結(jié)構(gòu)如下： 1 2 3 4 5 6 7 8 第3層有( a )個(gè)結(jié)點(diǎn)(根結(jié)點(diǎn)為第 1層)。 A . 2 B. 3 C. 4 D. 5 20先序遍歷圖示二叉樹(shù)可得到( 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個(gè)結(jié)點(diǎn)的二叉樹(shù)的二叉鏈表表示中，空指針數(shù) (b )o a.不定 b.n+1 c.n d.n-1 22若某二叉樹(shù)有20個(gè)葉子結(jié)點(diǎn)，有20個(gè)結(jié)點(diǎn)僅有一個(gè)孩子，則該二叉樹(shù)的總結(jié)點(diǎn)數(shù)是 ）。 A. 40 B.55 23已知某二叉樹(shù)的先序遍歷次序?yàn)?則該二叉樹(shù)的后序遍歷次序?yàn)椋? C. 59 abcdefg中序遍歷次序?yàn)?c ）。層次遍歷次序?yàn)椋? D. 61 badcgfe, a ) o a: abcdefg b: cdebgfa c: bdgfeca .24圖示的三棵二叉樹(shù)中（c）為最優(yōu)二叉樹(shù)。

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

31、y之后，則x和y的關(guān)系是（c ）。A. x是y的左兄弟 B. x是y的右兄 弟 C. x是y的祖先D. x是y的子孫 28用三叉鏈表作二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，當(dāng)二叉樹(shù)中有 n個(gè)結(jié)點(diǎn)時(shí)，有（d ）個(gè)空指針。 A. n-1 B. n C. n+1 D. n+2 29對(duì)一棵完全二叉樹(shù)進(jìn)行層序編號(hào)。則編號(hào)為 n的結(jié)點(diǎn)若存在右孩子，其位序是（d ）o 編號(hào)為n的結(jié)點(diǎn)若存在雙親，其位置是（a ）o a:n/2 b: 2n c:2 n-1 d:2 n+1 e:n f: 2（n +1） 30設(shè)森林F中有三棵樹(shù)，第一、第二和第三棵樹(shù)的結(jié)點(diǎn)個(gè)數(shù)分別為 m1、m2和m3，則與 森林F對(duì)應(yīng)的二叉樹(shù)根結(jié)點(diǎn)的

32、右子樹(shù)上的結(jié)點(diǎn)個(gè)數(shù)是 （_d_）。 A. m1B. m1+m2 C. m3 D. m2+m3 31下列二叉樹(shù)中，（a ）可用于實(shí)現(xiàn)符號(hào)不等長(zhǎng)高效編碼。 a:最優(yōu)二叉樹(shù) b:次優(yōu)查找樹(shù) c:二叉平衡樹(shù) d:二叉排序樹(shù) 32鄰接表存儲(chǔ)結(jié)構(gòu)下圖的深度優(yōu)先遍歷算法類(lèi)似于二叉樹(shù)的 （a ）遍歷。 A.先根 B.中根 C.后根 D.層次 33設(shè)無(wú)向圖G = （V,E）和G'= （V‘,E'），若G’是G的生成樹(shù)，則下面不正確的說(shuō)法是 （b ）。 A. G '是G的子圖 B. G 是 G的連通分量 C. G’是G的無(wú)環(huán)子圖 D. G 是 G的極小連通子圖且 V = V 34任何一個(gè)連通圖的

33、最小生成樹(shù) （±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）隊(duì)列D）線性表 36已知某有向圖的鄰接表存儲(chǔ)結(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）適用于求圖的最小代價(jià)生成樹(shù)

34、。 h: ac 及 bed D） hash查找 （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:處理沖突的方法。 41 在 Hash 函數(shù) H（k）=k MOD m A.奇數(shù) B.偶數(shù) ）。 c:哈希表的裝填因子。 d:以上都是 中，一般來(lái)說(shuō)，m應(yīng)?。╟ ） o C.素?cái)?shù) D.充分大的數(shù) 4

35、2在順序表查找中，為避免查找過(guò)程中每一步都檢測(cè)整個(gè)表是否查找完畢, 可采用a方法。 A.設(shè)置監(jiān)視哨 B.鏈表存貯 C.二分查找 D.快速查找 43靜態(tài)查找表和動(dòng)態(tài)查找表的區(qū)別在于 （b ）o A. 前者是順序存儲(chǔ)，而后者是鏈?zhǔn)酱鎯?chǔ) B. 前者只能進(jìn)行查找操作，而后者可進(jìn)行查找、插入和刪除操作 C. 前者只能順序查找，而后者只能折半查找 D. 前者可被排序，而后者不能被排序 44在一個(gè)含有n個(gè)元素的有序表上進(jìn)行折半查找， 找到一個(gè)元素最多要進(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樹(shù)中（初始狀態(tài)為空）， (30 62 ) (19, 20) ( 38 45 ) ( 70, 89 ) (19 20) (38 ) ( 62 ) ( 89 ) a: (19) ( 30 ) (19 ) ( 30,38 ) ( 62 ) ( 89 ) 該B-樹(shù)為（b ）。再刪除38,該B-樹(shù)為（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é)果。若仍以該插入次序建立平衡二叉樹(shù)。 終變化的結(jié)果。 80 f: 建立二叉排序樹(shù)。 圖( 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)鍵字序列為： 折半查找，則在等概率情況下，查找成功時(shí)的平均查找長(zhǎng)度是 行(c

38、)次比較。 48已知哈希表地址空間為 A[9]，哈希函數(shù)為H(k)=k mod 7，采用線性探測(cè)再散列處理沖突。 若依次將數(shù)據(jù)序列：76,45,88,21,94,77,17存入該散列表中，貝U元素17存儲(chǔ)的下標(biāo)為(h )； 在等概率情況下查找成功的平均查找長(zhǎng)度為 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。對(duì)其進(jìn)行 (c )。查找32時(shí)需進(jìn) )。 H. 7 49若從二叉樹(shù)的根結(jié)點(diǎn)到其它任一結(jié)點(diǎn)的路徑上所經(jīng)過(guò)的結(jié)點(diǎn)序列按其關(guān)鍵字遞增有序， 則該二叉樹(shù)是(c

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

40、記錄關(guān)鍵字初始排列如下： 56,26,86,35,75,19,77,58,48,42 下列選擇中（ d ）是快速排序一趟排序的結(jié)果。 （c ）是希爾排序 （初始步長(zhǎng)為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)酱鎯?chǔ)結(jié)構(gòu)優(yōu)于順序存儲(chǔ)結(jié)構(gòu)。 F

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

42、點(diǎn)至少有 m/2個(gè)關(guān)鍵字。F 10.對(duì)于任何待排序序列來(lái)說(shuō)，快速排序均快于起泡排序。 F 1.選擇題（每題2分共28分） 1. 在下列排序方法中，（c ）方法平均時(shí)間復(fù)雜度為 0（nlogn），最壞情況下時(shí)間復(fù)雜度 為0（ n2）; （ d ）方法所有情況下時(shí)間復(fù)雜度均為 0（nlogn）。 a.插入排序 b. 希爾排序 c. 快速排序 d. 堆排序 2.在有n個(gè)結(jié)點(diǎn)的二叉樹(shù)的二叉鏈表表示中，空指針數(shù)為（ b ）。 a.不定 b. n+1 c.n d.n-1 3. 下列二叉樹(shù)中，（a ）可用于實(shí)現(xiàn)符號(hào)不等長(zhǎng)高效編碼。 a.最優(yōu)二叉樹(shù) b. 次優(yōu)查找樹(shù) c.

43、二叉平衡樹(shù) ??d.二叉排序樹(shù) 4. 下列查找方法中，（ a ）適用于查找有序單鏈表。 a.順序查找 b. 二分查找 c. 分塊查找 d. 哈希查找 5. 在順序表查找中，為避免查找過(guò)程中每一步都檢測(cè)整個(gè)表是否查找完畢， 可采用（a ） 方法。 a.設(shè)置監(jiān)視哨 b. 鏈表存貯 c. 二分查找 d. 快速查找 6. 在下列數(shù)據(jù)結(jié)構(gòu)中，（c ）具有先進(jìn)先出特性，（b ）具有先進(jìn)后出特性。 a.線性表 b .棧 c .隊(duì)列 d .廣義表 7. 具有m個(gè)結(jié)點(diǎn)的二叉排序樹(shù)，其最大深度為（ 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）是希爾排序（初始步長(zhǎng)為 4） 一趟排序的結(jié)果。 （e）是起泡排序一趟排序的結(jié)果。 （a）是初始堆（大堆頂） 1?有向圖的存儲(chǔ)結(jié)構(gòu)有（鄰接矩陣）、（鄰接表）、（十字鏈表）等方法。

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

47、遍歷二叉樹(shù)。 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; 簡(jiǎn)答題(每題5分共25分) 1.將圖示森林轉(zhuǎn)換為二叉樹(shù)，并對(duì)該二叉樹(shù)中序全序線索化。 n+1）;語(yǔ)句4執(zhí)行的頻度為（n（n+1）/

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

49、 b. c. a. a. 4.已知某無(wú)向圖的鄰接表存儲(chǔ)結(jié)； . 請(qǐng)畫(huà)出該圖。 b. 根據(jù)存儲(chǔ)結(jié)構(gòu)給出其深度優(yōu)先遍歷序列及廣度優(yōu)先遍歷序列。 c. 畫(huà)出其深度優(yōu)先生成樹(shù)及廣度優(yōu)先生成樹(shù)。 b.接著，再刪除元素 35,畫(huà)出刪除后的 B樹(shù)。 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: 飛沖使用了△個(gè)字符 它們出現(xiàn)的頻率分別為 acebd 2 d 1 0 e c 0卄，試構(gòu)造一棵赫夫曼樹(shù)I并給局夫曼編碼0八 赫夫曼樹(shù)： 0.26:10 0.18:110 0.14:111 b 0.07:0111 五?算法設(shè)計(jì)題（共17分） 結(jié)點(diǎn)的類(lèi)型定義如下: 1. typedef struct LNode { int data; struct LNode *n ext;

51、 } LNode, *Li nklist; 寫(xiě)一算法，將帶頭結(jié)點(diǎn)的有序單鏈表 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. 二叉樹(shù)用二叉鏈表存儲(chǔ)表示。 typedef struct BiTNode { TelemType data; Struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; 編寫(xiě)一個(gè)復(fù)制一棵二叉樹(shù)的遞歸算法。 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