數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)提綱（附：期末復(fù)習(xí)題及期末樣卷）第一章 緒論一. 基本概念和術(shù)語(yǔ)數(shù)據(jù)結(jié)構(gòu)是一門研究非數(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ǔ)結(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)值 填空題：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)先遍歷算法(將遞歸算法改寫為非遞歸算法可借助棧來(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. 循環(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 (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.廣義表的概念：廣義表，長(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ù)的先序和中序(或后序和中序)序列，畫(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ù)），求 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è)。fi-1k2.一般二叉樹(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.將滿二叉樹(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（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)）連通圖、（強(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如下，畫(huà)岀該有向圖的鄰接矩陣和鄰接表，并根據(jù)你的鄰接表分別寫岀深度優(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. 哈希函數(shù)的構(gòu)造方法3. 處理沖突的方法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.鍵值不一定有序的順序表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)放定址法的二次探測(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)寫出：(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(zhǎng) )中指針p所指結(jié)點(diǎn)是最后一個(gè)元素結(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ù)元素的操作僅限一端進(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)。20. 中序線索二叉樹(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ú)向圖的連通分量是其極大的連通子圖。(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(nlogn),比快速排序好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個(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)結(jié)構(gòu)B.順序組織和鏈接組織C.線性結(jié)構(gòu)和非線性結(jié)構(gòu)D.基本類型和組合類型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 ullC. L-> next=L D. L!=null4若順序表中各結(jié)點(diǎn)的查找概率不等，則可用如下策略提高順序查找的效率：若找到指定的結(jié)點(diǎn)，將該結(jié)點(diǎn)與其后繼（若存在）結(jié)點(diǎn)交換位置，使得經(jīng)常被查找的結(jié)點(diǎn)逐漸移至 表尾。以下為據(jù)此策略編寫的算法，請(qǐng)選擇適當(dāng)?shù)膬?nèi)容，完成此功能。順序表的存儲(chǔ)結(jié)構(gòu)為：typedef structElemType *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.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若對(duì)編號(hào)為a:1,2,3）具有先進(jìn)先出（FIFO）特性, 特性。c.隊(duì)列d.廣義表b.棧1 , 2, 3的列車車廂依次通過(guò)扳道棧進(jìn)行調(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在計(jì)算遞歸函數(shù)時(shí)，如不用遞歸過(guò)程，應(yīng)借助于A.線性表B.棧C.隊(duì)列D.雙向隊(duì)列若帶頭結(jié)點(diǎn)的鏈表只設(shè)尾結(jié)點(diǎn)指針。下列選擇中（ 單鏈表 B）雙向鏈表 C循環(huán)單鏈表 棧和隊(duì)列的一個(gè)共同點(diǎn)是（cA.都是先進(jìn)先出C.只允許在端點(diǎn)處插入和刪除元素循環(huán)隊(duì)列用數(shù)組 A0.m-1存放其元素值， 的元素個(gè)數(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）最適用于隊(duì)列。D）雙向循環(huán)鏈表B.都是先進(jìn)后出D.沒(méi)有共同點(diǎn)設(shè)頭尾指針?lè)謩e為front和rear,則當(dāng)前隊(duì)列中（a, cB.串中的元素是字母）。e;return i;JA.i>0B. i>=0C. i<ST.le ngthD. i<=ST.le ngthE.i+F. i-G. A和C同時(shí)滿足H. B和D5若入棧順序?yàn)锳、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.隊(duì)列c:棧d.數(shù)組同時(shí)滿足C.串中若干個(gè)元素構(gòu)成的子序列稱為子串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 )a: 220 b: 200c: 140 d:12416 對(duì)廣義表 A= (a,(b),(c,(),d )執(zhí)行操作 gettail(gethead(gettail(A)的結(jié)果是：(b) oa: ()b: (0)c: dd: (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 )oa: 00b: 01c: 10d: 11e: 011f: 110g: 1110h:111118對(duì)二叉排序樹(shù)( c )可得到有序序列。a:按層遍歷b:前序遍歷c:中序遍歷d:后序遍歷19設(shè)一棵二叉樹(shù) BT的存儲(chǔ)結(jié)構(gòu)如下：12345678第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)(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 )oa.不定b.n+1c.nd.n-122若某二叉樹(shù)有20個(gè)葉子結(jié)點(diǎn)，有20個(gè)結(jié)點(diǎn)僅有一個(gè)孩子，則該二叉樹(shù)的總結(jié)點(diǎn)數(shù)是）。A. 40B.5523已知某二叉樹(shù)的先序遍歷次序?yàn)?則該二叉樹(shù)的后序遍歷次序?yàn)椋–. 59abcdefg中序遍歷次序?yàn)?c ）。層次遍歷次序?yàn)椋―. 61badcgfe,a ) oa: abcdefg b: cdebgfa c: bdgfeca.24圖示的三棵二叉樹(shù)中（c）為最優(yōu)二叉樹(shù)。d: edcgfba275425已知某二叉樹(shù)的后序遍歷和中序遍歷次序分別為DBFGECA和BDACFEG。則其先序遍歷次序?yàn)椋╞ ），層次遍歷次序?yàn)椋╝ ）oa: abcdefg b: abdcefg c: abcdfegd: abcdegf26已知某樹(shù)的先根遍歷次序?yàn)閍bcdefg后根遍歷次序?yàn)?cdebgfa。若將該樹(shù)轉(zhuǎn)換為二叉樹(shù)，其后序遍歷次序?yàn)椋?d ）oa: 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)若存在右孩子，其位序是（d ）o編號(hào)為n的結(jié)點(diǎn)若存在雙親，其位置是（a ）oa:n/2b: 2nc:2 n-1d:2 n+1e:nf: 2（n +1）30設(shè)森林F中有三棵樹(shù)，第一、第二和第三棵樹(shù)的結(jié)點(diǎn)個(gè)數(shù)分別為m1、m2和m3，則與森林F對(duì)應(yīng)的二叉樹(shù)根結(jié)點(diǎn)的右子樹(shù)上的結(jié)點(diǎn)個(gè)數(shù)是（_d_）。A. m1B. m1+m2 C. m3 D. 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.中根 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ù)（±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）隊(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ù)。h: ac 及 bedD） 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 mA.奇數(shù)B.偶數(shù)）。c:哈希表的裝填因子。d:以上都是中，一般來(lái)說(shuō)，m應(yīng)?。╟ ） oC.素?cái)?shù) D.充分大的數(shù)42在順序表查找中，為避免查找過(guò)程中每一步都檢測(cè)整個(gè)表是否查找完畢, 可采用a方法。A.設(shè)置監(jiān)視哨B.鏈表存貯C.二分查找D.快速查找43靜態(tài)查找表和動(dòng)態(tài)查找表的區(qū)別在于（b ）oA. 前者是順序存儲(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） +1C.og2（n+1）D. ILlog2（n+1） +145設(shè)輸入序列為20,45,30,89,70,38,62 ,19依次插入到一棵 2-3樹(shù)中（初始狀態(tài)為空），(3062 )(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 ）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é)果。若仍以該插入次序建立平衡二叉樹(shù)。 終變化的結(jié)果。80f:建立二叉排序樹(shù)。 圖(c)是最7080607575607211072a:90751008070807560 7211060709072b:100908510110708511c:47若有序表中關(guān)鍵字序列為： 折半查找，則在等概率情況下，查找成功時(shí)的平均查找長(zhǎng)度是 行(c )次比較。48已知哈希表地址空間為A9，哈希函數(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.1C.2D.3E. 4F. 5G. 614, 20,d:25, 32, 34, 45,57, 69, 77, 83, 92。對(duì)其進(jìn)行(c )。查找32時(shí)需進(jìn))。H. 749若從二叉樹(shù)的根結(jié)點(diǎn)到其它任一結(jié)點(diǎn)的路徑上所經(jīng)過(guò)的結(jié)點(diǎn)序列按其關(guān)鍵字遞增有序， 則該二叉樹(shù)是(c )pA.二叉排序樹(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已知一組待排序的記錄關(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)。F2. 棧和隊(duì)列也是線性表。如果需要，可對(duì)它們中的任一元素進(jìn)行插入/刪除操作。F3. 棧是數(shù)據(jù)對(duì)象特定的線性表。F4 .在單鏈表P指針?biāo)附Y(jié)點(diǎn)之后插入 S結(jié)點(diǎn)的操作是:P-> next= S ; S-> next = P-> next;FTTB的后根遍歷相當(dāng)于 B '的中序遍歷。Tm個(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)。F9 對(duì)于一棵 m階的B-樹(shù)，樹(shù)中每個(gè)結(jié)點(diǎn)至多有 點(diǎn)至少有 m/2個(gè)關(guān)鍵字。F10.對(duì)于任何待排序序列來(lái)說(shuō)，快速排序均快于起泡排序。F1.選擇題（每題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+1c.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ù)，其最大深度為（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）是希爾排序（初始步長(zhǎng)為 4） 一趟排序的結(jié)果。（e）是起泡排序一趟排序的結(jié)果。（a）是初始堆（大堆頂）1有向圖的存儲(chǔ)結(jié)構(gòu)有（鄰接矩陣）、（鄰接表）、（十字鏈表）等方法。 2已知某二叉樹(shù)的先序遍歷次序?yàn)槠浜笮虮闅v次序?yàn)椋?.已知如下程序段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ǔ)句42；語(yǔ)句1執(zhí)行的頻度為.請(qǐng)?jiān)谙聞澗€上填入適當(dāng)?shù)恼Z(yǔ)句，完成以下法算。Status Preordertraverse(Bitree T,Status(*Visit)(Telemtype e)/先序非遞歸遍歷二叉樹(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）/2 ）。a01:56 :52 922 .已知 Hash函數(shù)為，散列地址為，12, 49, 戈成功的平均查找長(zhǎng)度。Aa34=K mod 13 ，56，24,6834ASL=223.右圖為一棵3階B樹(shù)。（20，25）a.畫(huà)出在該樹(shù)上插入元素 1° ' B樹(shù)。g014,/ 1A 0 1 12131449弓二次探測(cè)再散列處2，06，55）在散列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ù)。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:飛沖使用了個(gè)字符 它們出現(xiàn)的頻率分別為acebd 2d10ec0卄，試構(gòu)造一棵赫夫曼樹(shù)I并給局夫曼編碼0八赫夫曼樹(shù)：0.26:100.18:1100.14:111 b0.07:0111五算法設(shè)計(jì)題（共17分）結(jié)點(diǎn)的類型定義如下:1.typedef struct LNode int data;struct LNode *n ext; LNode, *Li nklist;寫一算法，將帶頭結(jié)點(diǎn)的有序單鏈表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. 二叉樹(shù)用二叉鏈表存儲(chǔ)表示。 typedef struct BiTNode TelemType data; Struct BiTNode *lchild, *rchild; BiTNode, *BiTree; 編寫一個(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