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

1、杭電-數(shù)據(jù)結(jié)構(gòu)（c語(yǔ)言版）杭州電子科技大學(xué)一一數(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ù)類型、算法。數(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ù)類型（三元組）算法（5個(gè)重要特性）二.算法的時(shí)間復(fù)雜度和空間復(fù)雜度算法的評(píng)價(jià)：正確性、可讀性、健壯性、高效率、低存儲(chǔ)量第二章 線性表一.線性表的定義線性結(jié)構(gòu)的特點(diǎn)二.線性表的存儲(chǔ)結(jié)構(gòu)1.順序存儲(chǔ)

2、結(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)（算法描述）插入元素、刪除元素、查找、判表是否滿足某種特性例：判斷題：1.線性表的邏輯順序與存儲(chǔ)順序總是一致的。F2.線性結(jié)構(gòu)的基本特征是：每個(gè)結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)和一個(gè)直接后繼。F3.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)于順序存儲(chǔ)結(jié)構(gòu)。F選擇題：線性表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、空題：1.對(duì)于順序表中，在第i個(gè)元素前插入一個(gè)元素需移動(dòng)n-i+1個(gè)元素，要?jiǎng)h除第i個(gè)元素,需移動(dòng)n-i個(gè)元素。2.在雙向循環(huán)鏈表中某結(jié)點(diǎn)（由指針p指示）之后插入s指針?biāo)附Y(jié)點(diǎn)的操作是：第三章 棧和隊(duì)列一.棧1.棧的定義Copyright ?澤豬2012-05-16杭州電子科技大學(xué)一一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ì)列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

4、.循環(huán)隊(duì)列：隊(duì)空、隊(duì)滿的判斷條件求隊(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ì)滿的條件是rear-front。第四章 串一.串的定義二.串的術(shù)語(yǔ)：長(zhǎng)度、子串三.串的基本操作：求串的長(zhǎng)度、求子串、串聯(lián)接、串替換、串匹配(子串定位)例：已知下列字符串：a=THIS, b=(一個(gè)空格)，c=GOOD, d=NE, f=A SAMPLE,執(zhí)行如下操作：s=Concat

5、(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);試問(wèn)：s, t，u，v，LENGTH(s)各是什么？第五章數(shù)組和廣義表一.數(shù)組數(shù)組的順序存儲(chǔ)：行主順序法，列主順序法。元素存儲(chǔ)地址計(jì)算特殊矩陣的壓縮存儲(chǔ)元素存儲(chǔ)地址計(jì)算二.廣義表1.廣義表

6、的概念：廣義表，長(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ù)）Copyright ?澤豬2012-05-16杭州電子科技大學(xué)一一3.遍歷二叉樹(shù)：先序、中序、后序、層序應(yīng)用：給定二叉樹(shù)的先序和中序（或后序和中序）序列，畫(huà)岀相應(yīng)的二叉樹(shù)4.線索二叉樹(shù)：先序、中序、后序線索化三.樹(shù)和森林1.樹(shù)的存儲(chǔ)結(jié)構(gòu)：雙親表示法孩子表示法 孩子-兄弟（二叉樹(shù)）表示法2.樹(shù)（森林）與二叉樹(shù)的相互轉(zhuǎn)換3.樹(shù)的遍歷：先根、后根次序遍歷4.森林的遍

7、歷：先序、中序遍歷四.赫夫曼樹(shù)及其應(yīng)用1.最優(yōu)二叉樹(shù)（赫夫曼樹(shù)），求WPL2.赫夫曼編碼五.各種二叉樹(shù)概念的區(qū)分1.滿二叉樹(shù)2.完全二叉樹(shù)3.正則二叉樹(shù)（嚴(yán)格二叉樹(shù)）4.最優(yōu)二叉樹(shù)5.（折半查找的）判定樹(shù)6.二叉排序樹(shù)7.平衡二叉樹(shù)8.堆六.二叉樹(shù)有關(guān)的遞歸算法例：判斷題：1.已知二叉樹(shù)的先序序列和后序序列并不能唯一地確定這棵二叉樹(shù)，因?yàn)椴恢蓝鏄?shù)的根結(jié) 點(diǎn)是哪一個(gè)。f2.一般二叉樹(shù)的第i層上有2i-1個(gè)結(jié)點(diǎn)，深度為k的二叉樹(shù)有2k-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ù)高

8、度至多為（b）。A.不定B.nC. |llog2n +1D. log2n填空題：1.將滿二叉樹(shù)（含n個(gè)結(jié)點(diǎn)）中各結(jié)點(diǎn)從上到下，從左到右進(jìn)行編號(hào)，并采用順序存儲(chǔ)表示，則編號(hào)為i的結(jié)點(diǎn)，其雙親編號(hào)為i/2_，其左孩子編號(hào)為2i（2in）_，其右孩子編號(hào)為2i+1（2i+1n）_。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,1

9、2,18）為葉結(jié)點(diǎn)權(quán)值，構(gòu)造一棵赫夫曼樹(shù)，并求其帶權(quán)路徑長(zhǎng)度。第七章 圖一.圖的定義和術(shù)語(yǔ)無(wú)向圖、有向圖、（無(wú)向/有向）完全圖、子圖、（強(qiáng)）連通圖、（強(qiáng)）連通分量、生成樹(shù)二.圖的存儲(chǔ)結(jié)構(gòu)Copyright ?澤豬2012-05-16杭州電子科技大學(xué)一一無(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)）概念

10、最短路徑：Dijkstra算法例：判斷題：一個(gè)連通圖的連通分量是包含該圖中的所有（n個(gè)）頂點(diǎn)和任意n-1條邊的子圖。f應(yīng)用題：已知圖G如下，畫(huà)岀該有向圖的鄰接矩陣和鄰接表，并根據(jù)你的鄰接表分別寫(xiě)岀深度優(yōu)先遍歷和 廣度優(yōu)先遍歷的頂點(diǎn)序列。第九章 查找一.靜態(tài)查找表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.8-樹(shù)（B+樹(shù)）（常用于文件系統(tǒng)）定

11、義、查找、插入、刪除從空樹(shù)開(kāi)始創(chuàng)建一棵3階B-樹(shù)（2-3樹(shù)）三.哈希表1.哈希表的定義2.哈希函數(shù)的構(gòu)造方法3.處理沖突的方法Copyright ?澤豬2012-05-16杭州電子科技大學(xué)一一4.哈希表的造表、查找四.平均查找長(zhǎng)度的計(jì)算1.等概率情況下，查找成功時(shí)的平均查找長(zhǎng)度ASL2.查找不成功時(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.鍵值不一

12、定有序的順序表2.若查找表是一個(gè)有序的單鏈表，則應(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的元素時(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)

13、放定址法的二次探測(cè)再散列處理沖突。 依次存入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,45,85,16,23,16,58,22,59,74,12,46)進(jìn)行排序，請(qǐng)寫(xiě)出：

14、(1).堆排序初始建堆(大頂堆)的結(jié)果；(2) .以第一個(gè)元素為樞軸的快速排序一趟掃描的結(jié)果；(3) .起泡排序第一趟的結(jié)果；(4) .希爾排序第一趟(增量5)的結(jié)果(5) .基數(shù)排序第一趟的結(jié)果。Copyright ?澤豬2012-05-16杭州電子科技大學(xué)一一附錄：期末復(fù)習(xí)題一.是非題（共分，每題分）1.數(shù)據(jù)結(jié)構(gòu)可用三元式表示（D, S, P）。其中:D是數(shù)據(jù)對(duì)象，S是D上的關(guān)系，P是對(duì)D的基本操作集。（f）2簡(jiǎn)單地說(shuō)，數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的數(shù)據(jù)元素 的集合。（t）3判斷帶頭結(jié)點(diǎn)的非空循環(huán)單鏈表（頭指針為L(zhǎng)）中指針p所指結(jié)點(diǎn)是最后一個(gè)元素結(jié)點(diǎn)的條件是：p-next=L。（t）4線性表的鏈?zhǔn)酱?/p>

15、儲(chǔ)結(jié)構(gòu)具有可直接存取表中 任一元素的優(yōu)點(diǎn)。（f）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ǔ)。（t）8.順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插Copyright ?澤豬2012-05-16杭州電子科技大學(xué)一一入、刪除運(yùn)算效率高。（f）9.棧和隊(duì)列是操作上受限制的線性表。（t）10.隊(duì)列是與線性表完全不同的一種數(shù)據(jù)結(jié)構(gòu)。（f）11.隊(duì)列是一種操作受限的線性表，凡對(duì)數(shù)據(jù) 元素的操作僅限一端進(jìn)行。（f）12.棧和隊(duì)列也是線性表。如果需要

16、，可對(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ù)。（f）16赫夫曼樹(shù)中結(jié)點(diǎn)個(gè)數(shù)一定是奇數(shù)。（t）仃 在二叉樹(shù)的中序遍歷序列中，任意一個(gè)結(jié)點(diǎn) 均處在其左孩子結(jié)點(diǎn)的后面。（t）18假設(shè)B是一棵樹(shù)，B是對(duì)應(yīng)的二叉樹(shù)。 則B的后根遍歷相當(dāng)于B的后序遍歷。（f）19.通常，二叉樹(shù)的第i層上有2i-1個(gè)結(jié)點(diǎn)。（f）20.中序線索二叉樹(shù)的優(yōu)點(diǎn)是便于在中序下查 找直接前驅(qū)結(jié)點(diǎn)和直接后繼結(jié)點(diǎn)。（t）Copyright ?

17、澤豬2012-05-16杭州電子科技大學(xué)一一21二叉樹(shù)的先序遍歷序列中，任意一個(gè)結(jié)點(diǎn)均處在其孩子結(jié)點(diǎn)的前面。（t）22由樹(shù)結(jié)點(diǎn)的先根序列和后根序列可以唯一地確定一棵樹(shù)。（t）23鄰接多重表可以用以表示無(wú)向圖，也可用以 表示有向圖。（f）24可從任意有向圖中得到關(guān)于所有頂點(diǎn)的拓?fù)浯涡颉＃╢）25有向圖的十字鏈表是將鄰接表和逆鄰接表 合二為一的鏈表表示形式。（t）26關(guān)鍵路徑是AOE網(wǎng)中源點(diǎn)到匯點(diǎn)的最短路 徑。（f）27連通圖G的生成樹(shù)是一個(gè)包含G的所有n個(gè)頂點(diǎn)和n-1條邊的子圖。（f）28一個(gè)無(wú)向圖的連通分量是其極大的連通子圖。（t）29十字鏈表可以表示無(wú)向圖， 也可用以表示有 向圖。（f）30

18、鄰接表可以表示有向圖， 也可以表示無(wú)向 圖。 （t）31.二叉排序樹(shù)的平均查找長(zhǎng)度為O（logn ）（t）32.二叉排序樹(shù)的最大查找長(zhǎng)度與（LOG2N）Copyright ?澤豬2012-05-16杭州電子科技大學(xué)一一同階。(f)33選用好的HASH函數(shù)可避免沖突。(f)34折半查找不適用于有序鏈表的查找。(t)35.對(duì)于目前所知的排序方法，快速排序具有最 好的平均性能。(t)36對(duì)于任何待排序序列來(lái)說(shuō)，快速排序均快于 冒泡排序。(f)37在最壞情況下，堆排序的時(shí)間性能是O(nlogn),比快速排序好(t)38快速排序具有最好的平均時(shí)間性能，它在任 何時(shí)候的時(shí)間復(fù)雜度都是O(n log n)。

19、(f)39.字符串是數(shù)據(jù)對(duì)象特定的線性表。(t)40.空串與空格串是相同的。(f)41.對(duì)于一棵m階的B-樹(shù).樹(shù)中每個(gè)結(jié)點(diǎn)至多有m個(gè)關(guān)鍵字.除根之外的所有非終端結(jié)點(diǎn)至少有廠m/2n個(gè)關(guān)鍵字。(f)42.當(dāng)二叉排序樹(shù)是一棵平衡二叉樹(shù)時(shí)，其平均查找長(zhǎng)度為O(log2n)。(t)43.廣義表的表頭和表尾都是廣義表。(f)44二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表。(t)Copyright ?澤豬2012-05-16杭州電子科技大學(xué)一一選擇題。1從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（c_J。A.動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B.順序組織和鏈接組織C.線性結(jié)構(gòu)和非線性結(jié)構(gòu)D.基本類型和組合類型2線性表L在（b ）情況下適于使用

20、鏈表結(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=nullB.L-next=nullC. L-next=LD.L!=null4若順序表中各結(jié)點(diǎn)的查找概率不等， 則可用如 下策略提高順序查找的效率：若找到指定Copyright ?澤豬2012-05-16杭州電子科技大學(xué)一一的結(jié)點(diǎn)，將該結(jié)點(diǎn)與其后繼(若存在)結(jié)點(diǎn)交 換位置，使得經(jīng)常被查找的結(jié)點(diǎn)逐漸移至表尾。以下為據(jù)此策略編寫(xiě)的算法，請(qǐng)選擇適 當(dāng)?shù)膬?nèi)容，完成此功能。順序表的存儲(chǔ)結(jié)構(gòu)為：typedef st

21、ructElemType *elem; /數(shù)據(jù)元素存儲(chǔ)空間，0號(hào)單元作監(jiān)視哨intlength; /表長(zhǎng)度SSTable;int search_seq(SSTable ST,KeyType key) /在順序表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;Copyright ?澤豬2012-05-16杭州電子科技大學(xué)一一return i;A. i0B.

22、 i=0C. ivST. lengthD. iv=ST .lengthE.i+F. i-G. A和C同時(shí)滿足H. B和D同時(shí)滿足5若入棧順序?yàn)锳、B、C、D、E,則下列(d )出棧序列是不可能的。A.A、B、C、D、ED、A、EC.C、D、B、E、AC、A、B6遞歸程序可借助于(c序。a.線性表b.隊(duì)列7在下列數(shù)據(jù)結(jié)構(gòu)中(c )具有先進(jìn)先出(FIFO)特性，B.B、C、D.D、E、)轉(zhuǎn)化為非遞歸程c:棧d.數(shù)組(b )具有先進(jìn)后出(FILO)特性。a.線性表b.棧c.隊(duì)列d.廣義表8若對(duì)編號(hào)為1,2,3的列車(chē)車(chē)廂依次通過(guò)扳道Copyright ?澤豬2012-05-16杭州電子科技大學(xué)一一棧進(jìn)

23、行調(diào)度，不能得到（e ）的序列。a:1,2,3b:1,3,2c:2,1,3d:2,3,1e:3,1,2f:3,2,19在計(jì)算遞歸函數(shù)時(shí)， 如不用遞歸過(guò)程， 應(yīng)借助 于（b ）這種數(shù)據(jù)結(jié)構(gòu)。A.線性表B.棧C.隊(duì)列D.雙向隊(duì)列10若帶頭結(jié)點(diǎn)的鏈表只設(shè)尾結(jié)點(diǎn)指針。下列選 擇中（c）最適用于隊(duì)列。A）單鏈表B）雙向鏈表C循環(huán)單鏈表D）雙向循環(huán)鏈表11棧和隊(duì)列的一個(gè)共同點(diǎn)是（c ）。A.都 是 先 進(jìn) 先 出B.都是先進(jìn)后出C.只允許在端點(diǎn)處插入和刪除元素D.沒(méi)有共同點(diǎn)12循環(huán)隊(duì)列用數(shù)組A0.m-1存放其元素值， 設(shè) 頭尾指針?lè)謩e為front和rear，貝U當(dāng)前隊(duì)列中的元素個(gè)數(shù)是（c）。A.rear-

24、front-1B. Rear-front+1C.(rear-front+m)%mCopyright ?澤豬2012-05-16杭州電子科技大學(xué)一一D. Rear-front13如下關(guān)于串的陳述中，正確的是(a, c )。A.串是數(shù)據(jù)元素類型特殊的線性表B.串中的元素是字母C.串中若干個(gè)元素構(gòu)成的子序列稱為子串D.空串即為空格串14對(duì)字符串s=datatructure執(zhí)行操作replace(s,substring(s,6,8),bas)的結(jié)果是(b )。a:databaseb:datdoasec:basd:dabasucture15設(shè)有二維數(shù)組A5 x 7，每一元素用相鄰的4個(gè) 字節(jié)存儲(chǔ)，存儲(chǔ)器

25、按字節(jié)編址.已知A的起始地址為100。則按行存儲(chǔ)時(shí)，元素A06的第一個(gè)字節(jié)的地址是(d)按列存儲(chǔ)時(shí)， 元素A06的第一個(gè)字節(jié)的地址 是(a)a: 220 b: 200 c: 140 d:12416對(duì)廣義表A= (a,(b),(c,(),d)執(zhí)行操作gettail(gethead(gettail(A)的結(jié)果是：(b)oCopyright ?澤豬2012-05-16杭州電子科技大學(xué)一一d： （d）仃 假設(shè)用于通訊的電文僅由6個(gè)字符組成，字母在電文中出現(xiàn)的頻率分別為7, 19, 22, 6, 32,14。若為這6個(gè)字母設(shè)計(jì)哈夫曼編碼（設(shè)生 成新的二叉樹(shù)的規(guī)則是按給出的次序從左至右的結(jié)合，新生成的二叉

26、樹(shù)總是插入在最 右），則頻率為7的字符編碼是（g），頻率為32的字符編碼是（c）。a: 00b: 01c: 10 d:11a:按層遍歷b:前序遍歷c:中序遍歷d:后序遍歷19設(shè)一棵二叉樹(shù)BT的存儲(chǔ)結(jié)構(gòu)如下：12345678 1Ichild 23 G 060a：()b：()c: de: 011h:1111f: 110g: 111018對(duì)二叉排序樹(shù)（c）可得到有序序列Copyright ?澤豬2012-05-16杭州電子科技大學(xué)一一0 0_data A B C D E F_GHrchild 05408700其中Ichild,rchild分別為結(jié)點(diǎn)的左、 右孩 子指針域，data為結(jié)點(diǎn)的數(shù)據(jù)域。則該

27、二叉樹(shù)的高度為(_；第3層有(_a一)個(gè)結(jié)點(diǎn)(根結(jié)點(diǎn)為第1層)。A.2B. 3C.4D. 520先序遍歷圖示二叉樹(shù)可得到(a)的序列。(A)/ (B)(C)/ (H)(D)(G)/ (E)(F)Copyright ?澤豬2012-05-16杭州電子科技大學(xué)一一(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個(gè)結(jié)點(diǎn)的二叉樹(shù)的二叉鏈表表示中， 空指針數(shù)（b）。a.不定b.n+1c.nd.n-122若某二叉樹(shù)有20個(gè)葉子結(jié)點(diǎn)，有20個(gè)結(jié)點(diǎn) 僅有一個(gè)孩子，則該二叉樹(shù)的總結(jié)點(diǎn)數(shù)是（- c_）。A.40B. 55C.59D.

28、 6123已知某二叉樹(shù)的先序遍歷次序?yàn)閍bcdefg中序遍歷次序?yàn)閎adcgfe則該二叉樹(shù)的后序遍歷次序?yàn)椋╟）。層次遍歷次序?yàn)椋╝）。a:abcdefgb: cdebgfac:bdgfeca d: edcgfba.24圖示的三棵二叉樹(shù)中（c）為最優(yōu)二叉樹(shù)。Copyright ?澤豬2012-05-16525別為DBFGECA和BDACFEG。則其先序遍歷次序?yàn)?b),層次遍歷次序?yàn)?(a)。a: abcdefg b: abdcefg c: abcdfeg d: abcdegf26已知某樹(shù)的先根遍歷次序?yàn)閍bcdefg后根遍Copyright ?澤豬2012-05-16杭州電子科技大學(xué)一一X.

29、B)2已知某二叉樹(shù)的后序遍歷和中序遍歷次序分杭州電子科技大學(xué)一一歷次序?yàn)閏debgfe。若將該樹(shù)轉(zhuǎn)換為二叉樹(shù)，其后序遍歷次序?yàn)椋╠）。a: abcdefg b: cdebgfa c: cdegbfa d: edcgfba27設(shè)x和y是二叉樹(shù)中的任意兩個(gè)結(jié)點(diǎn)，若在 先根序列中x在y之前，而在后根序列中x在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-1B. nC. n+1D. n+229對(duì)一棵完全二叉樹(shù)進(jìn)行層序編號(hào)。則編號(hào)為n的結(jié)點(diǎn)若存在右孩子

30、，其位序是（d ）。編號(hào)為n的結(jié)點(diǎn)若存在雙親，其位置是（a ）。a: n/2b: 2nc:2n-1Copyright ?澤豬2012-05-16杭州電子科技大學(xué)一一d:2n+1 e:n f: 2(n+1)30設(shè)森林F中有三棵樹(shù)，第一、第二和第三棵 樹(shù)的結(jié)點(diǎn)個(gè)數(shù)分別為ml、m2和m3,則與 森林F對(duì)應(yīng)的二叉樹(shù)根結(jié)點(diǎn)的右子樹(shù)上的 結(jié)點(diǎn)個(gè)數(shù)是(d )。A. mlB. m1+m2C. m3D. m2+m331下列二叉樹(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)先遍歷算法類 似于二叉樹(shù)的(a )遍歷。A.先根B.中根

31、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=V34任何一個(gè)連通圖的最小生成樹(shù)(b)。Copyright ?澤豬2012-05-1635深度優(yōu)先遍歷圖使用了數(shù)據(jù)結(jié)構(gòu)（b），而 廣度優(yōu)先遍歷圖使用了數(shù)據(jù)結(jié)構(gòu)（c）。A）數(shù)組B）棧C）隊(duì)列D）線性表36已知某有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如圖所示根據(jù)存儲(chǔ)結(jié)構(gòu)依教材中的算法其深度優(yōu)先遍 歷次序?yàn)椋╠）。廣度優(yōu)先遍歷此序?yàn)椋╟）。各強(qiáng)連通分量的頂點(diǎn)集為（h）。Copyright ?澤豬2012

32、-05-16杭州電子科技大學(xué)一一A只有一棵B.有一棵或多棵C.一定有多棵e fD.可能不存在杭州電子科技大學(xué)一一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）適用于求圖的最小代價(jià)生 成樹(shù)。（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

33、:權(quán)值之和最大d:權(quán)值之和最小40希表的查找效率取決于（d）。a:哈希函數(shù)b:處理沖突的方法。c:哈希表的裝填因子。d:以上都是41在Hash函數(shù)H(k)=k MOD m中，般來(lái)說(shuō)，m應(yīng)取（c）。A.奇數(shù)B.偶數(shù)C.素?cái)?shù)Copyright ?澤豬2012-05-16杭州電子科技大學(xué)一一D.充分大的數(shù)42在順序表查找中，為避免查找過(guò)程中每一步 都檢測(cè)整個(gè)表是否查找完畢，可采用_a_方法。A.設(shè)置監(jiān)視哨B.鏈表存貯C.二分查找D.快速查找43靜態(tài)查找表和動(dòng)態(tài)查找表的區(qū)別在于（b ）。A.前者是順序存儲(chǔ)，而后者是鏈?zhǔn)酱鎯?chǔ)B.前者只能進(jìn)行查找操作，而后者可進(jìn)行 查找、插入和刪除操作C.前者只能順序查找

34、，而后者只能折半查 找D.前者可被排序，而后者不能被排序44在一個(gè)含有n個(gè)元素的有序表上進(jìn)行折半查 找，找到一個(gè)元素最多要進(jìn)行（b ）次元素 比較。A.log2（n）B. Iog2（n） +1C. Iogz（n+1）D. log2（n+1） +145設(shè)輸入序列為20, 45, 30, 89, 70, 38, 62 19依次插入到一棵2-3樹(shù)中（初始狀態(tài)為空），該B-樹(shù)為（b）。再刪除38,該B-樹(shù)為Copyright ?澤豬2012-05-16杭州電子科技大學(xué)一一(3062)45(19 , 20 )38 45 )(70 , 89 )(30)(70 )(19 20)(38 ) ( 62(89 )

35、a:b:4545 )20(20 )6270 )(89(1919)(30,38 )(62 )3089 )Copyright ?澤豬2012-05-16杭州電子科技大學(xué)一一C：d:(19,20)(45 62)(70)(19)(30) (62)(89)e:f:46根據(jù)插入次序(80,90,100,110, 85,70,75,60,72)建立二叉排序樹(shù)。圖(a)是最終變化的結(jié)果。若仍以該插Copyright ?澤豬2012-05-16(30(45)70)/ 、(20)(89)杭州電子科技大學(xué)一一入次序建立平衡二叉樹(shù)。圖（C）是最終變化的結(jié)果8080709075758510060851007211072

36、110a:b:9090706075100Copyright ?澤豬2012-05-166072C：d:47若有序表中關(guān)鍵字序列為：14,20,25,32,34,45,57,69,77,83，92。對(duì)其進(jìn)行折半查找，則在等概率情況下，查找成功時(shí)的平均查找長(zhǎng)度是(c )。查找32時(shí)需進(jìn)行(c )次比較。A. 1B. 2C. 3D. 448已知哈希表地址空間為A9，哈希函數(shù)為H(k)=k mod 7,采用線性探測(cè)再散列處理沖突。若依次將數(shù)據(jù)序列：76,45,88,21,94,77,17存1006080110727585杭州電子科技大學(xué)一一70110弋弋7085入該散列表中，則元素17存儲(chǔ)的下標(biāo)為t

37、h_);Copyright ?澤豬2012-05-16杭州電子科技大學(xué)一一在等概率情況下查找成功的平均查找長(zhǎng)度為(c )。A. 0C. 2D.3E. 4G. 6H.7B. 1F. 549若從二叉樹(shù)的根結(jié)點(diǎn)到其它任一結(jié)點(diǎn)的路徑 上所經(jīng)過(guò)的結(jié)點(diǎn)序列按其關(guān)鍵字遞增有序， 則該二叉樹(shù)是(c )。A.二叉排序樹(shù)B.赫夫曼樹(shù)C.堆D.平衡二叉樹(shù)50當(dāng)待排序序列的關(guān)鍵字次序?yàn)榈剐驎r(shí)，若需 為之進(jìn)行正序排序，下列方案中(_d_)為佳。A.起泡排序 速排序C.直接插入排序 單選擇排序B.快D.簡(jiǎn)51下列排序算法中，g 算法可能會(huì)出現(xiàn)：初始 數(shù)據(jù)有序時(shí)，花費(fèi)的時(shí)間反而最多。A.堆排序B.起泡排序C.歸并排序D.快

38、速排序52在下列排序方法中，(c)方法平均時(shí)間Copyright ?澤豬2012-05-16杭州電子科技大學(xué)一一復(fù)雜度為O(nlogn),最壞情況下時(shí)間復(fù)雜度為0(n2); (d)方 法所有情況下時(shí)間復(fù)雜度均為0(nlogn)。a.插入排序b.希爾排序c.快速排序d.堆排序53已知一組待排序的記錄關(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,

39、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)。F2.棧和隊(duì)列也是線性表。如果需要，可對(duì)它 們中的任一元素進(jìn)行插入/刪除操作。FCopyright ?澤豬2012-05-16杭州電子科技大學(xué)一一3.棧是數(shù)據(jù)對(duì)象特定的線性表。F4.在單鏈表P指針?biāo)附Y(jié)點(diǎn)之后插入S結(jié)點(diǎn)的操作是:P-next= S ; S- next = P-next; F5.一個(gè)無(wú)向圖的連通分量是其極大的連通子 圖。T6.鄰接表可以表示有向圖，也

40、可以表示無(wú)向 圖。T7.假設(shè)B是一棵樹(shù)，B是對(duì)應(yīng)的二叉樹(shù)。 則B的后根遍歷相當(dāng)于B的中序遍歷。T8.通常，二叉樹(shù)的第i層上有2i-1個(gè)結(jié)點(diǎn)。F9.對(duì)于一棵m階的B-樹(shù)，樹(shù)中每個(gè)結(jié)點(diǎn)至 多有m個(gè)關(guān)鍵字。除根之外的所有非終端結(jié)點(diǎn) 至少有m/2個(gè)關(guān)鍵字。F10.對(duì)于任何待排序序列來(lái)說(shuō)，快速排序均快于起泡排序二.選擇題(每題2分共28分)1.在下列排序方法中， (c)方法平均時(shí)間 復(fù)雜度為O(nlogn)，最壞情況下時(shí)間復(fù)雜度為0(n2)； (d)方法所有情況下時(shí)間復(fù)雜度均為0(nlogn)。a.插入排序b.希爾排序c.快速排序d.堆排序Copyright ?澤豬2012-05-16杭州電子科技大學(xué)一

41、一2.在有n個(gè)結(jié)點(diǎn)的二叉樹(shù)的二叉鏈表表示中， 空指針數(shù)為（b）。a.不定b.n+1 c.nd.n-13.下列二叉樹(shù)中，（a）可用于實(shí)現(xiàn)符號(hào)不 等長(zhǎng)高效編碼。a.最優(yōu)二叉樹(shù)b.次優(yōu)查找樹(shù)c.二叉平衡樹(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ù)，其最大深度C

42、opyright ?澤豬2012-05-16杭州電子科技大學(xué)一一為（f），最小深度為（b)a. log2mb log2m+1c.m/2d .廠m/2n-1e.廠m/2nf.m8已知一組待排序的記錄關(guān)鍵字初始排列如下：56,34,58,26,79,52,64,37,28,84,57下列選擇中（c）是快速排序一趟排序的結(jié)（b）是希爾排序（初始步長(zhǎng)為4）一趟排序 的結(jié)果。(e) 是起泡:排序-趟扌非序的結(jié)果。(a) 是:初始堆（大堆頂） 。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

43、,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,Copyright ?澤豬2012-05-16杭州電子科技大學(xué)一一57,84。f. 34,56,26,58,52,79,37,64,28,84,57。三.填空題（每題2分共20分）1有向圖的存儲(chǔ)結(jié)構(gòu)有（鄰接矩陣）、（鄰 接表）、（十字鏈表）等方法。2.已知某二叉樹(shù)的先序遍歷次序?yàn)閍fbcdeg，中序遍歷次序?yàn)閏edbgfa。其后序遍歷次序?yàn)椋╡dcgbfa）。層次遍 歷次序?yàn)椋╝fbcgde）。3.已知如下

44、程序段for（ i=n; i0; i-）語(yǔ)句1x+;語(yǔ)句2for（ j=n; j=i; i-）語(yǔ)句3y+;語(yǔ)句4;語(yǔ)句1執(zhí)行的頻度為（n+1）;語(yǔ)句4執(zhí) 行的頻度為（n（n+1）/2）。4.請(qǐng)?jiān)谙聞澗€上填入適當(dāng)?shù)恼Z(yǔ)句，完成以 下法算。StatusPreordertraverse（BitreeCopyright ?澤豬2012-05-16杭州電子科技大學(xué)一一T,Status(*Visit)(Telemtype e)先序非遞歸遍歷二叉樹(shù)。Initstack ( 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ù)中序全序線索化。Copyright ?澤豬2012-05-16杭州電子科技大學(xué)一一2.已知Hash函數(shù)為H(K)=K mod 13，散列地理沖突，給出關(guān)鍵字(23，34，56,24，75，12,4表中的分布，并求在等概率情況下查找成功的平均