數(shù)據(jù)結(jié)構(gòu)軟考

數(shù)據(jù)結(jié)構(gòu)軟考第1頁，共160頁，2023年，2月20日，星期五考點(diǎn)分析基本概念：包括數(shù)據(jù)結(jié)構(gòu)和算法的基本概念，以及算法的性質(zhì)。線性表：包括隊(duì)列、棧、鏈表、數(shù)組的基本操作，以及字符串、括號(hào)匹配等二叉樹：二叉樹的基本性質(zhì)、二叉樹遍歷、二叉排序樹圖：圖的基本概念、圖的存儲(chǔ)（鄰接表、鄰接矩陣）、圖的遍歷。排序：各種排序算法的比較查找：二分法和散列表第2頁，共160頁，2023年，2月20日，星期五數(shù)據(jù)結(jié)構(gòu)與算法各知識(shí)點(diǎn)重要程度知識(shí)點(diǎn)04.1105.505.1106.506.1107.507.1108.5合計(jì)比例基本概念12211710.61%線性表437331432842.42%二叉樹11311141218.18%圖21121710.61%排序112111710.61%查找121157.58%第3頁，共160頁，2023年，2月20日，星期五基本概念數(shù)據(jù)：是信息的載體，是描述客觀事物的數(shù)、字符、以及所有能輸入到計(jì)算機(jī)中，被計(jì)算機(jī)程序識(shí)別和處理的符號(hào)的集合。數(shù)據(jù)元素:是數(shù)據(jù)（集合）中的一個(gè)“個(gè)體”,在計(jì)算機(jī)中通常作為一個(gè)整體進(jìn)行考慮和處理。是數(shù)據(jù)結(jié)構(gòu)中討論的基本單位。數(shù)據(jù)元素又稱為元素、結(jié)點(diǎn)、記錄數(shù)據(jù)項(xiàng)：數(shù)據(jù)元素也可以由若干款項(xiàng)構(gòu)成。其中每個(gè)款項(xiàng)稱為一個(gè)“數(shù)據(jù)項(xiàng)”，它是數(shù)據(jù)結(jié)構(gòu)中討論的最小單位數(shù)據(jù)對(duì)象：具有相同性質(zhì)的數(shù)據(jù)元素的集合。第4頁，共160頁，2023年，2月20日，星期五基本概念數(shù)據(jù)結(jié)構(gòu)表示：二元組{D,S}，其中，D是某一數(shù)據(jù)對(duì)象，是數(shù)據(jù)結(jié)構(gòu)中的非空的有限集合；S是該對(duì)象中所有數(shù)據(jù)成員之間的關(guān)系的有限集合數(shù)據(jù)結(jié)構(gòu)主要研究數(shù)據(jù)的“邏輯結(jié)構(gòu)”和“物理結(jié)構(gòu)”。邏輯結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)中結(jié)點(diǎn)的關(guān)系?？梢苑譃榧?，線性結(jié)構(gòu)，樹形結(jié)構(gòu)，網(wǎng)狀結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器內(nèi)的表示。順序存儲(chǔ)，鏈?zhǔn)酱鎯?chǔ)第5頁，共160頁，2023年，2月20日，星期五ABCDE2.021004.820002001210020022000200220032004圖1-2順序存儲(chǔ)結(jié)構(gòu)圖1-3鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)………………第6頁，共160頁，2023年，2月20日，星期五1.在數(shù)據(jù)結(jié)構(gòu)的討論中把數(shù)據(jù)結(jié)構(gòu)從邏輯上分為_____A．內(nèi)部結(jié)構(gòu)與外部結(jié)構(gòu)B．靜態(tài)結(jié)構(gòu)與動(dòng)態(tài)結(jié)構(gòu)C．線性結(jié)構(gòu)與非線性結(jié)構(gòu)

D．緊湊結(jié)構(gòu)與非緊湊結(jié)構(gòu)

2.數(shù)據(jù)結(jié)構(gòu)主要研究數(shù)據(jù)的（）A.邏輯結(jié)構(gòu)B存儲(chǔ)結(jié)構(gòu)C邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)D邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)及其運(yùn)算的實(shí)現(xiàn)第7頁，共160頁，2023年，2月20日，星期五

算法算法:解決某類問題的方法.即它給出了求解問題的步驟描述.一個(gè)算法必須滿足以下五個(gè)重要特性：1.有窮性2.確定性3.可行性4.有輸入5.有輸出算法設(shè)計(jì)的原則:1．正確性2.易讀性3．健壯性4．效率(時(shí)間和空間)時(shí)間復(fù)雜度：算法轉(zhuǎn)化為程序后在計(jì)算機(jī)上從開始運(yùn)行到結(jié)束所需要的時(shí)間。第8頁，共160頁，2023年，2月20日，星期五算法分析的一般步驟:語句頻度:算法中一個(gè)基本操作執(zhí)行的次數(shù).計(jì)算出算法的各個(gè)語句的頻度統(tǒng)計(jì)出算法的語句頻度和T(n)給出T(n)的大O表示稱算法的時(shí)間復(fù)雜度T(n)=O(f(n)),f(n)是問題規(guī)模n的一個(gè)函數(shù),算法執(zhí)行時(shí)間的增長率和f(n)的增長率相同.例如:T(n)=2.7n3+3.8n2+5.3隨著問題規(guī)模n的增長，增長率最快的是n3

，所以：T(n)的大O(n3)第9頁，共160頁，2023年，2月20日，星期五例：交換A和B內(nèi)容程序段的時(shí)間復(fù)雜度。

T=A;(執(zhí)行1次)A=B;(執(zhí)行1次)B=T;(執(zhí)行1次)

解：以上三條單個(gè)語句均執(zhí)行1次，該程序段的執(zhí)行時(shí)間是一個(gè)與問題n無關(guān)的常數(shù)，因此，算法的時(shí)間復(fù)雜度為常數(shù)階,記作T(n)=O(1).第10頁，共160頁，2023年，2月20日，星期五幾種時(shí)間復(fù)雜度O(1):常數(shù)時(shí)間2.O(log2n)：對(duì)數(shù)時(shí)間3.O(n)：線性時(shí)間4.O(nlog2n)：線性對(duì)數(shù)時(shí)間5.O(n2):平方時(shí)間6.O(n3):立方時(shí)間7.O(2n):指數(shù)時(shí)間上述的時(shí)間復(fù)雜度的優(yōu)劣次序如下（n>=16):<O(nlog2n)O(1)<O(log2n)<O(n)<O(n2)<O(n3)<O(2n)第11頁，共160頁，2023年，2月20日，星期五線性表線性表是最簡單最常用的一種數(shù)據(jù)結(jié)構(gòu)，它是具有相同數(shù)據(jù)類型的n（n>=0）個(gè)數(shù)據(jù)元素的有限序列，通常記為：(a1，a2，…ai-1，ai，ai+1，…an)其中n為表長，n＝0時(shí)稱為空表。在線性表中相鄰元素之間存在著順序關(guān)系。對(duì)于元素ai而言，ai-1稱為ai的直接前趨，ai+1稱為ai的直接后繼。線性表的存儲(chǔ)有順序和鏈接兩種存儲(chǔ)方式線性表的順序存儲(chǔ)是指在用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素，我們把用這種存儲(chǔ)形式存儲(chǔ)的線性表稱為順序表。順序表的邏輯順序和物理順序是一致的。第12頁，共160頁，2023年，2月20日，星期五順序表的存儲(chǔ)方式（用數(shù)組實(shí)現(xiàn)）用一組地址連續(xù)的存儲(chǔ)單元依次存放線性表中的數(shù)據(jù)元素LOC(ai+1)=LOC(ai)+lLOC(ai)=LOC(a1)+(i-1)*l

a1

a2

…ai………an

12…i………n

aa+l…a+(i-1)*l………a+(n-1)*l

idle線性表的起始地址，稱作線性表的基地址

一個(gè)數(shù)據(jù)元素所占存儲(chǔ)量第13頁，共160頁，2023年，2月20日，星期五順序表的基本操作1.線性表上的查找：順序查找，按值查找2.線性表上的插入：在線性表L的第i個(gè)位置上插入一個(gè)值為x的新元素，這樣使原序號(hào)為i,i+1,...,n的數(shù)據(jù)元素的序號(hào)變?yōu)閕+1,i+2,...,n+1。主要的操作是移動(dòng)元素，所以平均移動(dòng)次數(shù)是n/2

時(shí)間復(fù)雜度是o（n）3.線性表上的刪除：在線性表L中刪除序號(hào)為i的數(shù)據(jù)元素，刪除后使序號(hào)為i+1,i+2,...,n的元素變?yōu)樾蛱?hào)為i,i+1,...,n-1。主要的操作是移動(dòng)元素，所以平均移動(dòng)次數(shù)是（n-1）/2。時(shí)間復(fù)雜度是o（n）第14頁，共160頁，2023年，2月20日，星期五線性表的線性存儲(chǔ)的優(yōu)缺點(diǎn)：（1）順序存儲(chǔ)的優(yōu)點(diǎn)：

可以隨機(jī)存取表中任意一個(gè)元素；邏輯順序與物理順序一致，存儲(chǔ)位置可以用公式：B+(i-1)*l

計(jì)算；（2）順序存儲(chǔ)的缺點(diǎn)：

插入、刪除操作要移動(dòng)元素存儲(chǔ)空間是預(yù)分配的，不靈活，空間浪費(fèi)；表的存儲(chǔ)空間難擴(kuò)充等第15頁，共160頁，2023年，2月20日，星期五鏈?zhǔn)酱鎯?chǔ)方式：

用任意存儲(chǔ)空間單元來存放線性表的各個(gè)元素，為了能體現(xiàn)元素之間的邏輯關(guān)系（線性），在存放每個(gè)元素的同時(shí)，也存放相關(guān)元素的信息（相關(guān)元素的存儲(chǔ)地址），即用指針來表示元素之間的邏輯關(guān)系。存入一個(gè)數(shù)據(jù)元素占用的空間為：相關(guān)元素的地址信息存放數(shù)據(jù)元素存儲(chǔ)一個(gè)元素占用的空間稱為結(jié)點(diǎn)第16頁，共160頁，2023年，2月20日，星期五線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)存儲(chǔ)空間不一定連續(xù)；邏輯關(guān)系是由指針來體現(xiàn)的；邏輯上相鄰，物理上不一定相鄰；非隨機(jī)存?。樞虼嫒。?，即訪問任何一個(gè)元素的時(shí)間不同；單鏈表的存取必須從頭指針開始第17頁，共160頁，2023年，2月20日，星期五第18頁，共160頁，2023年，2月20日，星期五第19頁，共160頁，2023年，2月20日，星期五關(guān)于頭指針、頭結(jié)點(diǎn)和開始結(jié)點(diǎn)（1）頭指針——指向鏈表中第一個(gè)結(jié)點(diǎn)（頭結(jié)點(diǎn)或無頭結(jié)點(diǎn)時(shí)的開始結(jié)點(diǎn)）的指針。（2）頭結(jié)點(diǎn)——有時(shí)為了方便，增加一個(gè)結(jié)點(diǎn)，其數(shù)據(jù)域可以不存放任何元素，其指針域是指向第一個(gè)元素的存儲(chǔ)地址。（3）開始結(jié)點(diǎn)——在鏈表中，存儲(chǔ)第一個(gè)數(shù)據(jù)元素（a1）的結(jié)點(diǎn)。(4)L->next=NULL;/*空表*/第20頁，共160頁，2023年，2月20日，星期五1.查找操作按序號(hào)查找：由于僅僅知道第一個(gè)元素的存儲(chǔ)地址，第i個(gè)元素的地址不象順序存儲(chǔ)那樣可以立即計(jì)算出來，所以必須利用元素的后繼指針去找到指定元素的存儲(chǔ)地址，然后訪問它！時(shí)間復(fù)雜度是o（n）按值查找：從鏈表的第一個(gè)元素結(jié)點(diǎn)開始，判斷當(dāng)前結(jié)點(diǎn)其值是否等于x，若是，返回該結(jié)點(diǎn)的指針，否則繼續(xù)下一個(gè)，直到鏈表結(jié)束。若找不到則返回空。時(shí)間復(fù)雜度為O（n）鏈?zhǔn)奖淼幕静僮鞯?1頁，共160頁，2023年，2月20日，星期五2.插入(在p所指的結(jié)點(diǎn)之后插入某一元素x)（1）后插結(jié)點(diǎn)：設(shè)p指向線性鏈表中某結(jié)點(diǎn)，s指向待插入的值為x的新結(jié)點(diǎn)，將s結(jié)點(diǎn)插入到p的后面，插入示意圖如下：插入結(jié)點(diǎn)操作：①s->next=p->next;②p->next=s;12第22頁，共160頁，2023年，2月20日，星期五3．刪除（1）刪除結(jié)點(diǎn)：設(shè)p指向線性鏈表中某結(jié)點(diǎn)，刪除*p。操作示意圖如圖2-14所示。圖2-14

刪除*P

通過示意圖可見，要實(shí)現(xiàn)對(duì)結(jié)點(diǎn)*p的刪除，首先要找到*p的前驅(qū)結(jié)點(diǎn)*q，然后完成指針的操作即可。指針的操作由下列語句實(shí)現(xiàn)：

q->next=p->next;free(p);第23頁，共160頁，2023年，2月20日，星期五循環(huán)鏈表上的操作

循環(huán)鏈表上的操作和非循環(huán)鏈表上的操作基本相同，差別在于算法中循環(huán)條件不是判斷指針是否為空P->NEXT==NULL而是判斷指針是否為頭指針：P->NEXT==head;第24頁，共160頁，2023年，2月20日，星期五1．雙向鏈表雙向鏈表由一個(gè)數(shù)據(jù)域和兩個(gè)指針域組成。（1）結(jié)點(diǎn)的結(jié)構(gòu)如下圖所示。雙向鏈表的結(jié)點(diǎn)結(jié)構(gòu)（2）空的雙向循環(huán)鏈表如下圖所示。（b）空表H第25頁，共160頁，2023年，2月20日，星期五

2．雙鏈表的操作（1）刪除結(jié)點(diǎn)具體操作描述： ① p->prior->next=p->next; ② p->next->prior=p->prior; ③ deletep;第26頁，共160頁，2023年，2月20日，星期五（2）插入結(jié)點(diǎn)具體操作描述：

① p->prior=q; ② p->next=q->next; ③ q->next->prior=p; ④ q->next=p;

q

①④

③

②

P第27頁，共160頁，2023年，2月20日，星期五1.線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，結(jié)點(diǎn)的存儲(chǔ)地址()A．必須是不連續(xù)的B．連續(xù)與否均可C．必須是連續(xù)的D.和頭結(jié)點(diǎn)的存儲(chǔ)地址相連續(xù)2.采用順序搜索方法查找長度為n的順序表時(shí)，搜索成功的平均搜索長度為

。A．NB．n／2C．(n-1)／2D．(n+1)／23.下面關(guān)于線性表的敘述中，錯(cuò)誤的為()。A．順序表使用一維數(shù)組實(shí)現(xiàn)的線性表

B．順序表必須占用一片連續(xù)的存儲(chǔ)單C．順序表的空間利用率高于鏈表

D．在鏈表中，每個(gè)結(jié)點(diǎn)只有一個(gè)鏈域第28頁，共160頁，2023年，2月20日，星期五4.在一個(gè)單鏈表中，若q結(jié)點(diǎn)是p結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q與p之間插入結(jié)點(diǎn)s，則執(zhí)行()A．s->link=p->link；p->link=s；B．p->link=s；s->link=q；C．p->link=S->link；s->link=p；D．q->link=s；s->link=p；5.給定一個(gè)有n個(gè)元素的線性表。若采用順序存儲(chǔ)結(jié)構(gòu)，則在等概率前提下，向其插入一個(gè)元素需要移動(dòng)的元素個(gè)數(shù)平均為B。A．n+lB．(n+1)/2C．N-l/2D．n/26.在需要經(jīng)常查找結(jié)點(diǎn)的前驅(qū)與后繼的場合中，使用()比較合適。A．單鏈表B．循環(huán)鏈表C．鏈棧D．雙鏈表7.帶頭結(jié)點(diǎn)的單鏈表head為空的判斷條件是()。A．head=NULLB．head<>NULLC．head->next=headD．head->next=NULL第29頁，共160頁，2023年，2月20日，星期五棧和隊(duì)列棧和隊(duì)列是兩種特殊的線性數(shù)據(jù)結(jié)構(gòu),它們特殊在定義的操作不同,即插入和刪除操作只能在線性表的兩端進(jìn)行.

只能在一段進(jìn)行的-----棧

分別在兩端進(jìn)行的-----隊(duì)列第30頁，共160頁，2023年，2月20日，星期五棧的定義和運(yùn)算棧（Stack）的定義

棧是一種特殊的線性表(數(shù)據(jù)元素之間的關(guān)系是線性關(guān)系)其插入和刪除只能在表的一端進(jìn)行,另一端固定不動(dòng).

a1a2a3進(jìn)棧出棧棧的示意圖棧頂（Top）:插入、刪除的一端;棧底（Bottom）:固定不動(dòng)的一端;入棧(push);又稱壓入,即插入一個(gè)元素;出棧(pop):又稱彈出,即刪除一個(gè)元素;棧的特性由于限制了插入和刪除只能在一端進(jìn)行,那么元素的操作順序有“后進(jìn)先出”的特點(diǎn).第31頁，共160頁，2023年，2月20日，星期五1.一個(gè)隊(duì)列的進(jìn)隊(duì)列順序是1，2，3，4，則出隊(duì)列順序?yàn)?/p>

()。A．4，3，2，1B．1，2，3，4C．2，4，3，1D．3，2，1，42.設(shè)有一個(gè)順序棧S，元素s1，s2，s3，s4，s5，s6依次進(jìn)棧，如果6個(gè)元素的出棧順序?yàn)閟2，s3，s4，s6，s5，s1，則順序棧的容量至少應(yīng)為

()。A．2B．3C．4D．5第32頁，共160頁，2023年，2月20日，星期五棧的操作棧的運(yùn)算1.棧初始化init_stack(s)構(gòu)造一個(gè)空棧.通常是設(shè)置棧頂?shù)奈恢脼?1，即top=-1，表示空棧。2．入棧：Push（s，x）：在棧頂插入一個(gè)元素x，通常是先把top加1，然后把x放到top所在的位置，即s[++top]=x3．出棧：Pop（s）:在棧頂刪除一個(gè)元素,top減14．讀棧頂元素gettop（s）:將棧s的棧頂元素賦給x，top保持不變，即x=s[top--]第33頁，共160頁，2023年，2月20日，星期五棧操作的示意圖如下圖所示。AFEDCBADCBAJIHGFEDCBAtop=-1top=0

top=5top=3top=9

(a)(b)(c)(d)(e)第34頁，共160頁，2023年，2月20日，星期五當(dāng)top=-1時(shí)，表示?？?，如圖3-3（a）；當(dāng)top=0時(shí)，表示棧中有一個(gè)元素，如圖3-3（b）表示棧中已輸入一個(gè)元素A；入棧時(shí)，棧頂指針上移，指針top加1，如圖3-3（c）是6個(gè)元素入棧后的狀況；出棧時(shí)，棧頂指針下移，指針top減1，如圖3-3（d）是在F、E相繼出棧后的情況。此時(shí)棧中還有A、B、C、D4個(gè)元素，top=3，指針已經(jīng)指向了新的棧頂。但是出棧的元素F、E仍然在原先的存儲(chǔ)單元，只是不在棧中了，因?yàn)闂Ｊ侵荒茉跅ｍ斶M(jìn)行操作的線性表。當(dāng)top=9時(shí)，即top=MAXLEN–1，表示棧滿，如圖3-3（e）。第35頁，共160頁，2023年，2月20日，星期五上溢(overflow):棧已經(jīng)滿,又要壓入元素下溢(underflow):棧已經(jīng)空,還要彈出元素注:上溢是一種錯(cuò)誤,使問題的處理無法進(jìn)行下去;而下溢一般認(rèn)為是一種結(jié)束條件，即問題處理結(jié)束。第36頁，共160頁，2023年，2月20日，星期五PUSH和POP命令常用于___操作。A.隊(duì)列B.數(shù)組C.棧D.記錄

2.若push、pop分別表示入棧、出棧操作，初始棧為空且元素1、2、3依次進(jìn)棧，則經(jīng)過操作序列push、push、pop、pop、push、pop之后，得到的出棧序列為()

A．321

B．213

C．231

D．123

第37頁，共160頁，2023年，2月20日，星期五棧的應(yīng)用可以用棧來檢查算術(shù)表達(dá)式中的括號(hào)是否匹配。分析表達(dá)式時(shí),初始棧為空，從左到右掃描字符，遇到左括號(hào)“（”將其進(jìn)棧，遇到右括號(hào)“）”則執(zhí)行出棧的操作。例如：((a+b*(a+b))/c+(a+b)可以用來計(jì)算表達(dá)式。棧在中斷系統(tǒng)中，可以用來保護(hù)和恢復(fù)現(xiàn)場。棧常常用于函數(shù)的遞歸調(diào)用和函數(shù)嵌套調(diào)用。第38頁，共160頁，2023年，2月20日，星期五棧的應(yīng)用表達(dá)式求值表達(dá)式是由運(yùn)算對(duì)象、運(yùn)算符、括號(hào)等組成的有意義的式子。1．中綴表達(dá)式（InfixNotation）一般我們所用表達(dá)式是將運(yùn)算符號(hào)放在兩運(yùn)算對(duì)象的中間，比如：a+b，c/d等等，我們把這樣的式子稱為中綴表達(dá)式。2．后綴表達(dá)式（PostfixNotation）后綴表達(dá)式規(guī)定把運(yùn)算符放在兩個(gè)運(yùn)算對(duì)象（操作數(shù)）的后面。在后綴表達(dá)式中，不存在運(yùn)算符的優(yōu)先級(jí)問題，也不存在任何括號(hào)，計(jì)算的順序完全按照運(yùn)算符出現(xiàn)的先后次次序進(jìn)行。3．中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式其轉(zhuǎn)換方法采用運(yùn)算符優(yōu)先算法。轉(zhuǎn)換過程需要兩個(gè)棧：一個(gè)運(yùn)算符號(hào)棧和一個(gè)后綴表達(dá)式輸出符號(hào)棧。

利用棧將中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式第39頁，共160頁，2023年，2月20日，星期五求解階乘n!的過程計(jì)算

fact(4)計(jì)算4*fact(3)計(jì)算3*fact(2)計(jì)算2*fact(1)計(jì)算fact(1)遞歸調(diào)用回歸求值返回24返回6返回2返回1第40頁，共160頁，2023年，2月20日，星期五遞歸過程與遞歸工作棧遞歸過程在實(shí)現(xiàn)時(shí)，需要自己調(diào)用自己。層層向下遞歸，返回次序正好相反：遞歸調(diào)用

n!(n-1)!(n-2)!1!=1

返回次序遞歸算法包括“遞推”和“回歸”兩個(gè)部分第41頁，共160頁，2023年，2月20日，星期五1.判斷一個(gè)表達(dá)式中左右括號(hào)是否匹配，采用()實(shí)現(xiàn)較為方便。

A.線性表的順序存儲(chǔ)B.隊(duì)列

C.線性表的鏈?zhǔn)酱鎯?chǔ)D.棧2.可以用棧來檢查算術(shù)表達(dá)式中的括號(hào)是否匹配。分析算術(shù)表達(dá)式時(shí)，初始棧為空，從左到右掃描字符，遇到字符“(”就將其入棧，遇到“)”就執(zhí)行出棧操作。對(duì)算術(shù)表達(dá)式“(a+b*(a+b))/c)+(a+b)”,檢查時(shí)，__(33)__；對(duì)算術(shù)表達(dá)式“((a+b/(a+b)-c/a)/b”,檢查時(shí)，__(34)__。這兩種情況都表明所檢查的算術(shù)表達(dá)式括號(hào)不匹配。33A.棧為空卻要進(jìn)行出棧操作

B.棧已滿卻要進(jìn)行入棧操作C.表達(dá)式處理已結(jié)束，棧中仍留下有字符"(“D.表達(dá)式處理已結(jié)束，棧中仍留下有字符")"

34.A.棧為空卻要進(jìn)行出棧操作

B．棧已滿卻要進(jìn)行入棧操作

C．表達(dá)式處理已結(jié)束，棧中仍留下有字符"("

D．表達(dá)式處理已結(jié)束，棧中仍留下有字符")"第42頁，共160頁，2023年，2月20日，星期五隊(duì)列定義:只允許在表的一端進(jìn)行插入，而在另一端刪除元素的線性表。在隊(duì)列中，允許插入的一端叫隊(duì)尾（rear），允許刪除的一端稱為隊(duì)首(front)。入隊(duì):在隊(duì)尾插入一個(gè)元素出隊(duì):在隊(duì)首刪除一個(gè)元素特點(diǎn)：先進(jìn)先出(FIFO)

a1，a2，a3，…，an出隊(duì)列入隊(duì)列隊(duì)頭隊(duì)尾第43頁，共160頁，2023年，2月20日，星期五隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)1.存儲(chǔ)方式:同一般線性表的順序存儲(chǔ)結(jié)構(gòu)完全相同.但是由于在兩端操作,設(shè)兩個(gè)指示器,(rear和front)分別指示隊(duì)列的尾和首.

特別約定頭指針始終指向隊(duì)列頭元素,而尾指針始終指向隊(duì)列尾元素的下一位置!空隊(duì)列:rear=front=0入隊(duì):rear=rear+1出隊(duì):front=front+1隊(duì)列空:front=reara2a1frontrear第44頁，共160頁，2023年，2月20日，星期五EDCBAEJIHGF

Q.rear

Q.frontABCDE相繼入隊(duì)列Q.RearQ.front

(a)空隊(duì)列0123

Q.rear

Q.rear

Q.front

Q.frontABCD相繼被刪除FGHIJ相繼入隊(duì)列E被刪除特點(diǎn):簡單,方便,但易產(chǎn)生假溢出第45頁，共160頁，2023年，2月20日，星期五JIHGF

q.rear

q.front可以看出:當(dāng)入隊(duì)一個(gè)元素時(shí),可能會(huì)出現(xiàn)假溢出現(xiàn)象即:不能入隊(duì),但空間并沒有使用完!解決的辦法:平移,一旦發(fā)生假溢出,把隊(duì)列中所有元素移到隊(duì)列開頭,但是效率低2.使用環(huán)數(shù)組,即將順序存儲(chǔ)空間視為一個(gè)環(huán)空間第46頁，共160頁，2023年，2月20日，星期五1.方式:將順序隊(duì)列臆造為一個(gè)環(huán)狀的空間,如下圖所示,循環(huán)隊(duì)列指針和隊(duì)列元素之間的關(guān)系不變.HGF

q.front

q.rearMaxsize-10

Q.front

Q.rear這種循環(huán)的圈只是一種邏輯上的圈,在物理上還是一組連續(xù)存儲(chǔ)單元,仍可利用數(shù)組實(shí)現(xiàn)第47頁，共160頁，2023年，2月20日，星期五循環(huán)隊(duì)列可充分利用空間,但是仍存在問題:我們知道:隊(duì)列為空時(shí)front=

=rear。如右圖繼續(xù)入隊(duì)a7a8,front=

=rear也就是說，僅根據(jù)等式front=

=rear無法有效判別是“隊(duì)滿”還是“隊(duì)空”。解決方法：少用一個(gè)元素空間,規(guī)定：當(dāng)front==rear，表示循環(huán)隊(duì)列為空；當(dāng)front==（rear+1）%MAXLEN，表示循環(huán)隊(duì)列為滿。第48頁，共160頁，2023年，2月20日，星期五鏈隊(duì)列1．鏈隊(duì)列的結(jié)構(gòu)

隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為鏈隊(duì)列（或鏈隊(duì)），同一般的線性表的單鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)完全相同.但是由于插入,刪除在兩端進(jìn)行,需要兩個(gè)指針:頭指針（front）和尾指針（rear）指向隊(duì)列的兩端單鏈表。有兩種不同的鏈法:第49頁，共160頁，2023年，2月20日，星期五為了處理方便，也可以給鏈隊(duì)列附加一個(gè)頭結(jié)點(diǎn)。鏈隊(duì)列為空的條件是front=rear，即隊(duì)列的頭指針和尾指針均指向表頭結(jié)點(diǎn)，如下圖所示:鏈隊(duì)列的入隊(duì)、出隊(duì)(a)

^

a1^

a1

a2^

a1

a2^

front

front

front

front

rearrear

rear

rear(b)(c)(d)第50頁，共160頁，2023年，2月20日，星期五1.若in、out分別表示入、出隊(duì)操作，初始隊(duì)列為空且元素a、b、c依次入隊(duì)，則經(jīng)過操作序列in、in、out、out、in、out之后，得到的出隊(duì)序列為()。

A．cba

B．bac

C．bca

D．Abc2.在以下情形中，___(35)___適合于采用隊(duì)列數(shù)據(jù)結(jié)構(gòu)。A．監(jiān)視一個(gè)火車票售票窗口等待服務(wù)的客戶B．描述一個(gè)組織中的管理機(jī)構(gòu)C．統(tǒng)計(jì)一個(gè)商場中的顧客數(shù)D．監(jiān)視進(jìn)入某住宅樓的訪客第51頁，共160頁，2023年，2月20日，星期五3.某循環(huán)隊(duì)列的容量為M，隊(duì)頭指針指向隊(duì)頭元素，隊(duì)尾指針指向隊(duì)尾元素之后，如下圖所示（M=8），則隊(duì)列中的元素?cái)?shù)目為（）（MOD表示整除取余運(yùn)算）。A．rear–front

B．front–rear

C．(rear–front+M)MODM

D．(front–rear+M)MODM第52頁，共160頁，2023年，2月20日，星期五一維數(shù)組存儲(chǔ)方式352749186054778341020123456789llllllllllLOC(i)=LOC(i-1)+l=a+i*lLOC(i)=LOC(i-1)+l=a+i*l,i>0

a,i=0a為基地址

a+i*la第53頁，共160頁，2023年，2月20日，星期五n行m列的二維數(shù)組

行優(yōu)先存放：設(shè)數(shù)組開始存放位置LOC(0,0)=a,每一行數(shù)據(jù)元素個(gè)數(shù)為m個(gè)每個(gè)元素占用l個(gè)存儲(chǔ)單元

LOC(i,j)=a+(i*m+j)*l第54頁，共160頁，2023年，2月20日，星期五對(duì)稱矩陣的壓縮存儲(chǔ)設(shè)有一個(gè)nn的對(duì)稱矩陣A。在矩陣中，aij=aji第55頁，共160頁，2023年，2月20日，星期五為節(jié)約存儲(chǔ)空間，只存對(duì)角線及對(duì)角線以上的元素，或者只存對(duì)角線及對(duì)角線以下的元素。把它們按行存放于一個(gè)一維數(shù)組B中，稱之為對(duì)稱矩陣A的壓縮存儲(chǔ)方式。數(shù)組B共有n+(n-1)++1=n*(n+1)/2個(gè)元素。第56頁，共160頁，2023年，2月20日，星期五三角矩陣上三角矩陣：主對(duì)角線以上均為同一個(gè)常數(shù)c。下三角矩陣：主對(duì)角線以下均為同一個(gè)常數(shù)c。存儲(chǔ)方式：將重復(fù)元素c可共享一個(gè)存儲(chǔ)空間，其余的元素正好有n*（n-1）/2，和我們的對(duì)稱矩陣存儲(chǔ)一樣。第57頁，共160頁，2023年，2月20日，星期五三對(duì)角矩陣的壓縮存儲(chǔ)Ba00a01a10a11a12a21a22a23…

an-1n-2an-1n-1

012345678910第58頁，共160頁，2023年，2月20日，星期五三對(duì)角矩陣中除主對(duì)角線及在主對(duì)角線上下最臨近的兩條對(duì)角線上的元素外，所有其它元素均為0。總共有3n-2個(gè)非零元素。將三對(duì)角矩陣A中三條對(duì)角線上的元素按行存放在一維數(shù)組B中，且a00存放于B[0]。在三條對(duì)角線上的元素aij滿足:

0in-1,i-1ji+1在一維數(shù)組B中A[i][j]在第i行，它前面有3*i-1個(gè)非零元素,在本行中第j列前面有j-i+1個(gè)，所以元素A[i][j]在B中位置為k=2*i+j。第59頁，共160頁，2023年，2月20日，星期五1

對(duì)于二維數(shù)組a[1..4，3..6]，設(shè)每個(gè)元素占兩個(gè)存儲(chǔ)單元，若分別以行和列為主序存儲(chǔ)，則元素a[3，4]相對(duì)于數(shù)組空間起始地址的偏移量分別是(1)和_(2)_。

A.12

B.14

C.16

D.18

A.12

B.14

C.16

D.182

數(shù)組是一種數(shù)據(jù)結(jié)構(gòu)，對(duì)數(shù)組通常進(jìn)行的兩種基本操作是___(40)___。A.插入和刪除B.插入和賦值

C.查找和修改D.查找和刪除

3.設(shè)數(shù)組a[1…10,5…]的元素以行為主序存放，每個(gè)元素占用4個(gè)存儲(chǔ)單元，則數(shù)組元素a[i,j](1≤i≤10，5≤j≤15)的地址計(jì)算公式為()。

A.a-204+2i+j

B.a-204+40i+4j

C.a-84+i+j

D.a-64+44+4j第60頁，共160頁，2023年，2月20日，星期五字符串串一種特殊的線性表,它的特殊在:1.數(shù)據(jù)元素都是來自字符集.2.由于數(shù)據(jù)元素特殊,它的操作有些不同與一般線性表例如:操作的對(duì)象一般是對(duì)子串(即一組數(shù)據(jù)元素)而不是單個(gè)數(shù)據(jù)元素.第61頁，共160頁，2023年，2月20日，星期五串的幾個(gè)術(shù)語（1）長度——串中字符的個(gè)數(shù)，稱為串的長度。（2）空串——長度為零的字符串稱為空串。

(3)空格串——由一個(gè)或多個(gè)連續(xù)空格組成的串稱為空格串。

(4)串相等——兩個(gè)串是相等的，是指兩個(gè)串的長度相等且對(duì)應(yīng)字符都相同。

(5)子串:串中任意連續(xù)的字符組成的子序列稱為該串的子串。

(6)主串:包含子串的串稱為該子串的主串。

(7)子串的位置:子串在主串第一次出現(xiàn)時(shí),該子串的第一個(gè)字母在主串中的序號(hào);(8)模式匹配——子串的定位運(yùn)算又稱為串的模式匹配，是一種求子串的第一個(gè)字符在主串中序號(hào)的運(yùn)算。被匹配的主串稱為目標(biāo)串，子串稱為模式。第62頁，共160頁，2023年，2月20日，星期五【例】字符串的長度及子串的位置。字符串字符串長度S1=＂SHANG＂5S2=＂HAI＂3S3=＂SHANGHAI＂8S4=＂SHANG□HAI＂9//□表示空格，下同

S1是S3、S4的子串，S1在S3、S4中的位置都為1。

S2也是S3、S4的子串，S2在S3中的位置為6；

S2在S4中的位置為7。第63頁，共160頁，2023年，2月20日，星期五1.字符串是一種線性表，其特殊性表現(xiàn)在()

A.它的數(shù)據(jù)元素是一個(gè)字符B.它可以鏈?zhǔn)酱鎯?chǔ)

C.它可以順序存儲(chǔ)D.它的數(shù)據(jù)元素可以是多個(gè)字符2.字符串"computer"中長度為3的子串有()個(gè)。

A．4

B．5

C．6

D．7

第64頁，共160頁，2023年，2月20日，星期五樹的定義1．樹的定義樹（Tree）是n（n≥0）個(gè)結(jié)點(diǎn)組成的有限集合T。在任意一棵非空樹T中：（1）有且僅有一個(gè)特定的稱為樹根（Root）的結(jié)點(diǎn)，根結(jié)點(diǎn)無前趨結(jié)點(diǎn)；（2）當(dāng)n>1時(shí)，除根結(jié)點(diǎn)之外的其余結(jié)點(diǎn)被分成m（m>0）個(gè)互不相交的集合T1，T2，…，Tm，其中每一個(gè)集合Ti（1≤i≤m）本身又是一棵樹，并且稱為根的子樹。樹的特點(diǎn):除根外,每個(gè)元素有且只有一個(gè)前驅(qū),有零個(gè)或者多個(gè)后繼.第65頁，共160頁，2023年，2月20日，星期五樹的術(shù)語結(jié)點(diǎn)——樹的結(jié)點(diǎn)包含一個(gè)數(shù)據(jù)及若干指向其子樹的分支。結(jié)點(diǎn)的度——結(jié)點(diǎn)所擁有的子樹數(shù)稱為該結(jié)點(diǎn)的度樹的度——樹中各結(jié)點(diǎn)度的最大值稱為該樹的度。葉子（終端結(jié)點(diǎn)）——度為零的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)。分枝結(jié)點(diǎn)——度不為零的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)。兄弟結(jié)點(diǎn)——同一父親結(jié)點(diǎn)下的子結(jié)點(diǎn)稱為兄弟結(jié)點(diǎn)。層數(shù)——樹的根結(jié)點(diǎn)的層數(shù)為1，其余結(jié)點(diǎn)的層數(shù)等于它雙親結(jié)點(diǎn)的層數(shù)加1。樹的深度——樹中結(jié)點(diǎn)的最大層數(shù)稱為樹的深度（或高度）。第66頁，共160頁，2023年，2月20日，星期五

二叉樹二叉樹的定義二叉樹是有n（n>=0）個(gè)結(jié)點(diǎn)的有限集合。（1）該集合或者為空（n=0）；（2）或者由一個(gè)根結(jié)點(diǎn)及兩個(gè)不相交的分別稱為左子樹和右子樹組成的非空樹；（3）左子樹和右子樹同樣又都是二叉樹。通俗地講：在一棵非空的二叉樹中，每個(gè)結(jié)點(diǎn)至多只有兩棵子樹，分別稱為左子樹和右子樹，且左右子樹的次序不能任意交換。所以，二叉樹是特殊的有序樹。第67頁，共160頁，2023年，2月20日，星期五二叉樹的形態(tài)根據(jù)定義，二叉樹可以有五種基本形態(tài)，如圖6-4所示。

(a)(b)(c)(d)(e)

圖6-4二叉樹的基本形態(tài)其中：（a）空二叉樹；（b）僅有根結(jié)點(diǎn)的二叉樹；（c）右子樹為空的二叉樹；（d）左子樹為空的二叉樹；

（e）左、右子樹均非空的二叉樹。

Ф

LchildLchildRchildRchild第68頁，共160頁，2023年，2月20日，星期五2.二叉樹的性質(zhì)性質(zhì)1

一棵非空二叉樹的第i層上最多有2i–1個(gè)結(jié)點(diǎn)（i≥1）。一棵非空二叉樹的第一層有1個(gè)結(jié)點(diǎn)，第二層最多有2個(gè)結(jié)點(diǎn)，第三層最多有4個(gè)結(jié)點(diǎn)……，利用歸納法即可證明第i層上最多有2i–1個(gè)結(jié)點(diǎn)。性質(zhì)2

深度為h的二叉樹中，最多具有2h－1個(gè)結(jié)點(diǎn)（h≥1）。證明：根據(jù)性質(zhì)1，當(dāng)深度為h的二叉樹每一層都達(dá)到最多結(jié)點(diǎn)數(shù)時(shí)，它的和（n）最大，即：

∴命題正確。

第69頁，共160頁，2023年，2月20日，星期五（1）滿二叉樹一棵深度為h，且有2h‐1個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹。圖6-5所示是一棵深度為4的滿二叉樹，其特點(diǎn)是每一層上的結(jié)點(diǎn)都具有最大的結(jié)點(diǎn)數(shù)。如果對(duì)滿二叉樹的結(jié)點(diǎn)進(jìn)行連續(xù)的編號(hào)，約定編號(hào)從根結(jié)點(diǎn)起，從上往下，自左向右（如圖6-5），由此可以引出完全二叉樹的定義。123876541091112131415圖6-5滿二叉樹第70頁，共160頁，2023年，2月20日，星期五（2）完全二叉樹

深度為h，有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)每一個(gè)結(jié)點(diǎn)都與深度為h的滿二叉樹中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱此二叉樹為完全二叉樹。如圖6-6（a）所示為一棵完全二叉樹。ABCHGFEDJI圖6-6（a）一棵完全二叉樹第71頁，共160頁，2023年，2月20日，星期五如圖6-6（b）所示則不是完全二叉樹。圖6-6（b）一棵非完全二叉樹完全二叉樹除最后一層外，其余各層都是滿的，并且最后一層或者為滿，或者僅在右邊缺少連續(xù)若干個(gè)結(jié)點(diǎn)。ABCGFEDH第72頁，共160頁，2023年，2月20日，星期五性質(zhì)3

對(duì)于一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹，若按滿二叉樹的同樣方法對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，（見圖6-5）則對(duì)于任意序號(hào)為i的結(jié)點(diǎn)，有：（1）若i>1，則序號(hào)為i的結(jié)點(diǎn)的父結(jié)點(diǎn)的序號(hào)為i/2；若i＝1，則序號(hào)為i的結(jié)點(diǎn)是根結(jié)點(diǎn)。（2）若2i≤n，則序號(hào)為i的結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的序號(hào)為2i；若2i>n，則序號(hào)為i的結(jié)點(diǎn)無左孩子。（3）若2i＋1≤n，則序號(hào)為i的結(jié)點(diǎn)的右孩子結(jié)點(diǎn)的序號(hào)為2i＋1；若2i＋1>n，則序號(hào)為i的結(jié)點(diǎn)無右孩子。證明略。

第73頁，共160頁，2023年，2月20日，星期五性質(zhì)4

具有n（n>0）個(gè)結(jié)點(diǎn)的完全二叉樹（包括滿二叉樹）的深度（h）為：

證明：由性質(zhì)2和完全二叉樹定義可知，當(dāng)完全二叉樹的深度為h、結(jié)點(diǎn)個(gè)數(shù)為n時(shí)有：2h－1–1<n≤2h-1

即：2h－1≤n<2h

對(duì)不等式取對(duì)數(shù)有：

h–1≤log2n<h

由于h是整數(shù)，所以有h＝。第74頁，共160頁，2023年，2月20日，星期五性質(zhì)5

對(duì)于一棵非空的二叉樹，設(shè)n0、n1、n2分別表示度為0、1、2的結(jié)點(diǎn)個(gè)數(shù)，則有:n0＝n2＋1。證明：（1）設(shè)n為二叉樹的結(jié)點(diǎn)總數(shù)，則有：

n＝n0＋n1＋n2

（6-1）（2）由二叉樹的定義可知，除根結(jié)點(diǎn)外，二叉樹其余結(jié)點(diǎn)都有唯一父結(jié)點(diǎn)，那么父結(jié)點(diǎn)的總數(shù)（F）為：

F＝n–1（6-2）（3）根據(jù)假設(shè)，各結(jié)點(diǎn)的子結(jié)點(diǎn)總數(shù)（C）為：

C＝n1＋2n2

（6-3）（4）因?yàn)楦缸雨P(guān)系是相互對(duì)應(yīng)的，即F=C，也即：

n–1＝n1+2n2（6-4）綜合（6-1）、（6-2）、（6-3）式可以得到：

n0＋n1＋n2

＝n1＋2n2

＋1n0＝n2＋1

∴命題正確。第75頁，共160頁，2023年，2月20日，星期五遍歷二叉樹先序遍歷:先訪問根結(jié)點(diǎn)，然后再分別訪問根結(jié)點(diǎn)的左子樹，右子樹中序遍歷:先訪問左子樹，然后再分別訪問根結(jié)點(diǎn)，右子樹后序遍歷:先訪問左子樹，然后再分別訪問根結(jié)點(diǎn)，右子樹性質(zhì)6：一顆二叉樹的前序遍歷和中序遍歷可以唯一確定一顆二叉樹。第76頁，共160頁，2023年，2月20日，星期五對(duì)下圖先序遍歷所得到的結(jié)點(diǎn)序列為：

ABDGCEFH按中序遍歷所得到的結(jié)點(diǎn)序列為：DGBAECHF按后序遍歷所得到的結(jié)點(diǎn)序列為：GDBEHFCA

第77頁，共160頁，2023年，2月20日，星期五二叉排序樹二叉排序樹又稱為二叉查找樹具有如下性質(zhì)：

1.若它的左子樹非空，則左子樹上所有節(jié)點(diǎn)的值均小于根結(jié)點(diǎn)

2.若它的右子樹非空，則右子樹上所有節(jié)點(diǎn)的值均大于根結(jié)點(diǎn)

3.左、右子樹本身又各是一顆二叉排序樹。根據(jù)二叉排序樹的定義可知，如果中序遍歷二叉排序樹，就能得到一個(gè)排好序的結(jié)點(diǎn)序列。第78頁，共160頁，2023年，2月20日，星期五最優(yōu)二叉樹

哈夫曼（Haffman）樹，也稱最優(yōu)二叉樹。1．幾個(gè)術(shù)語

(1)路徑：結(jié)點(diǎn)序列n1,n2,n3…nk滿足ni是ni＋1的雙親

(2)路徑長度:路徑上的分支數(shù)目，稱作路徑長度。l=k-1(3)擴(kuò)充二叉樹:在一般二叉樹中,將原來的每個(gè)空指針都指向一個(gè)特殊的結(jié)點(diǎn)---外結(jié)點(diǎn),這樣的二叉樹稱為擴(kuò)充二叉樹.（4）樹的路徑長度——從樹根到每個(gè)內(nèi)結(jié)點(diǎn)的路徑長度之和稱為樹的路徑長度。

(5)結(jié)點(diǎn)的權(quán):有時(shí)為了表示某種含義,賦予結(jié)點(diǎn)一個(gè)數(shù)值.（6）結(jié)點(diǎn)的帶權(quán)路徑長度——從該結(jié)點(diǎn)到樹根之間路徑長度與該結(jié)點(diǎn)上權(quán)的乘積。（7）樹的帶權(quán)路徑長度——假設(shè)樹的葉子有權(quán),樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和，稱為樹的帶權(quán)路徑長度。最優(yōu)二叉樹——假設(shè)有n個(gè)數(shù)據(jù)元素,它們的權(quán)值w1,w2…wn,以它們?yōu)槿~子的二叉樹,帶權(quán)路徑長度最小的二叉樹.第79頁，共160頁，2023年，2月20日，星期五2．如何求樹的帶權(quán)路徑長度？

設(shè)二叉樹具有n個(gè)帶權(quán)值的葉結(jié)點(diǎn)，那么從根結(jié)點(diǎn)到各個(gè)葉結(jié)點(diǎn)的路徑長度與相應(yīng)結(jié)點(diǎn)權(quán)值的乘積之和叫做二叉樹的帶權(quán)路徑長度（WPL），記為：

其中：

Wk——為第k個(gè)葉結(jié)點(diǎn)的權(quán)值；

Lk——為第k個(gè)葉結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑長度。【例】設(shè)給定權(quán)值分別為2，3，5，9的四個(gè)結(jié)點(diǎn)，圖6-26構(gòu)造了5個(gè)形狀不同的二叉樹。請分別計(jì)算它們的帶權(quán)路徑長度。第80頁，共160頁，2023年，2月20日，星期五第81頁，共160頁，2023年，2月20日，星期五

五棵樹的帶權(quán)路徑長度分別為：（a）WPL＝2×2＋3×2＋5×2＋9×2＝38（b）WPL＝2×3＋3×3＋5×2＋9×1＝34（c）WPL＝2×2＋3×3＋5×3＋9×1＝37（d）WPL＝9×3＋5×3＋3×2＋2×1＝50（e）WPL＝2×1＋3×3＋5×3＋9×2＝44

五個(gè)圖的葉結(jié)點(diǎn)具有相同權(quán)值，由于其構(gòu)成的二叉樹形態(tài)不同，則它們的帶權(quán)路徑長度也各不相同。其中以圖(b)的帶權(quán)路徑長度最小.特點(diǎn):權(quán)值越大的葉結(jié)點(diǎn)越靠近根結(jié)點(diǎn)，而權(quán)值越小的葉結(jié)點(diǎn)則遠(yuǎn)離根結(jié)點(diǎn)，事實(shí)上它就是一棵最優(yōu)二叉樹。由于構(gòu)成最優(yōu)二叉樹的方法是由D·

Haffman最早提出的，所以又稱為哈夫曼樹。第82頁，共160頁，2023年，2月20日，星期五2哈夫曼樹的建立1．哈夫曼樹構(gòu)成的基本思想是：選擇權(quán)值最小的葉子離根距離遠(yuǎn)些.2.算法步驟:1）由給定的n個(gè)權(quán)值{W1，W2，…，Wn}構(gòu)造n棵有一個(gè)葉結(jié)點(diǎn)的二叉樹，從而得到一個(gè)二叉樹的集合:

F＝{T1，T2，…，Tn}；（2）在F中選取根結(jié)點(diǎn)的權(quán)值最小和次小的兩棵二叉樹作為左、右子樹構(gòu)造一棵新的二叉樹，這棵新的二叉樹根結(jié)點(diǎn)的權(quán)值為其左、右子樹根結(jié)點(diǎn)權(quán)值之和；3）在集合F中刪除作為左、右子樹的兩棵二叉樹，并將新建立的二叉樹加入到集合F中；（4）重復(fù)（2）、（3）兩步，當(dāng)F中只剩下一棵二叉樹時(shí)，這棵二叉樹便是所要建立的哈夫曼樹。第83頁，共160頁，2023年，2月20日，星期五【例】的葉結(jié)點(diǎn)權(quán)值：2，3，5，9為例，介紹哈夫曼樹的構(gòu)造過程：

(a)權(quán)值之和為5(b)其權(quán)值之和為10(c)其權(quán)值之和為19圖6-27哈夫曼樹建立過程

帶權(quán)路徑長度為：WPL=9*1+5*2+3*3+2*3=34

對(duì)于同一組給定葉結(jié)點(diǎn)權(quán)值所構(gòu)造的哈夫曼樹，樹的形狀可能不同，但其帶權(quán)路徑長度值是相同的，而且必定是最小的。235105523199105523第84頁，共160頁，2023年，2月20日，星期五1.在一顆非空二叉樹中，葉子節(jié)點(diǎn)的總數(shù)比度為2的節(jié)點(diǎn)總數(shù)多（）個(gè)。

A.-1

B.0

C.1

D.22.如果要根的層次為1，具有61個(gè)結(jié)點(diǎn)的完全二叉樹的高度為___。

A.5

B.6

C.7

D.83.一棵二叉樹如下圖所示，若采用順序存儲(chǔ)結(jié)構(gòu)，即用一維數(shù)組元素存儲(chǔ)該二叉樹中的結(jié)點(diǎn)(根結(jié)點(diǎn)的下標(biāo)為1，若某結(jié)點(diǎn)的下標(biāo)為i，則其左孩子位于下標(biāo)2i處、右孩子位于下標(biāo)2i+1處)，則該數(shù)組的大小至少為___(1)___；若采用二叉鏈表存儲(chǔ)該二叉樹(各個(gè)結(jié)點(diǎn)包括結(jié)點(diǎn)的數(shù)據(jù)、左孩子指針、右孩子指針)，則該鏈表中空指針的數(shù)目為___(2)___。(1)A．6

B．10

C．12

D．15(2)A．6

B．7

C．12

D．144.數(shù)據(jù)結(jié)構(gòu)中的樹最適合用來表示（40）的情況。

A．?dāng)?shù)據(jù)元素有序

B．?dāng)?shù)據(jù)元素之間具有多對(duì)多關(guān)系

C．?dāng)?shù)據(jù)元素?zé)o序

D．?dāng)?shù)據(jù)元素之間具有一對(duì)多關(guān)系第85頁，共160頁，2023年，2月20日，星期五4.滿二叉樹的特點(diǎn)是每層上的結(jié)點(diǎn)數(shù)都達(dá)到最大值，因此對(duì)于高度為h(h>1)的滿二叉樹，其結(jié)點(diǎn)總數(shù)為（1）。對(duì)非空滿二叉樹，由根結(jié)點(diǎn)開始，按照先根后子樹、先左子樹后右子樹的次序，從1、2、3、…依次編號(hào)，則對(duì)于樹中編號(hào)為i的非葉子結(jié)點(diǎn)，其右子樹的編號(hào)為（2）（高度為3的滿二叉樹如下圖（1）A．2hB．2h-1C．2h–1D．2h-1+1（2）A．2iB．2i-1C．2i+1D．2i+2第86頁，共160頁，2023年，2月20日，星期五圖的定義和術(shù)語圖（Graph）是一種比樹形結(jié)構(gòu)更復(fù)雜的非線性結(jié)構(gòu)。在圖形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)都可以有多個(gè)直接前驅(qū)和多個(gè)直接后繼。圖的定義圖（Graph）是由非空的頂點(diǎn)（Vertices）集合和一個(gè)描述頂點(diǎn)之間關(guān)系——邊（Edges）的有限集合組成的一種數(shù)據(jù)結(jié)構(gòu)?？梢杂枚M定義為：

G＝（V，E）其中，G表示一個(gè)圖，V是圖G中頂點(diǎn)的集合，E是圖G中邊的集合。第87頁，共160頁，2023年，2月20日，星期五圖1無向圖G1圖2有向圖G2

V1V3V2V4V5V1V3V2V4

G1=（V，E）

V＝{v1,v2,v3,v4,v5}；

E＝{(v1,v2),(v1,v4),(v2,v3),(v3,v4),(v3,v5),(v2,v5)}。(vi,vj)表示頂點(diǎn)vi和頂點(diǎn)vj之間有一條無向直接連線，稱這樣的邊是無向邊，也稱為邊。G2=(V,E)V={v1,v2,v3,v4}E={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}<vi,vj>表示頂點(diǎn)vi和頂點(diǎn)vj之間有一條有向直接連線，稱這樣的邊是有向邊，也稱為弧。第88頁，共160頁，2023年，2月20日，星期五圖的相關(guān)術(shù)語無向圖：在一個(gè)圖中，如果每條邊都沒有方向（如圖1），則稱該圖為無向圖。

有向圖：在一個(gè)圖中，如果每條邊都有方向（如圖2），則稱該圖為有向圖無向完全圖(具有最大邊數(shù)的圖)：在一個(gè)無向圖中，如果任意兩頂點(diǎn)都有一條直接邊相連接，則稱該圖為無向完全圖?？梢宰C明，在一個(gè)含有n個(gè)頂點(diǎn)的無向完全圖中，有n(n-1)/2條邊。有向完全圖：在一個(gè)有向圖中，如果任意兩頂點(diǎn)之間都有方向互為相反的兩條弧相連接，則稱該圖為有向完全圖。在一個(gè)含有n個(gè)頂點(diǎn)的有向完全圖中，有n(n-1)條弧。第89頁，共160頁，2023年，2月20日，星期五圖的相關(guān)術(shù)語頂點(diǎn)的度(結(jié)點(diǎn)的度)是指和該結(jié)點(diǎn)相關(guān)聯(lián)的邊的數(shù)目。在無向圖中：一個(gè)頂點(diǎn)擁有的邊數(shù)，稱為該頂點(diǎn)的度。記為D(v)。在有向圖中：

(a)將以該結(jié)點(diǎn)結(jié)束的弧的數(shù)目，稱為該頂點(diǎn)的入度，記為ID(v)；(b)將從該結(jié)點(diǎn)出發(fā)的弧的數(shù)目，稱為該頂點(diǎn)的出度，記為OD(v)；

(c)一個(gè)頂點(diǎn)的度等于頂點(diǎn)的入度和出度之和，即：D(v)=ID(v)＋OD(v)。第90頁，共160頁，2023年，2月20日，星期五可以證明，對(duì)于具有n個(gè)頂點(diǎn)、e條邊的圖，頂點(diǎn)vi的度D(vi)與頂點(diǎn)的個(gè)數(shù)以及邊的數(shù)目滿足關(guān)系：

權(quán)：圖的邊或弧有時(shí)具有與它有關(guān)的數(shù)據(jù)信息，這個(gè)數(shù)據(jù)信息就稱為權(quán)。ACBD58697網(wǎng)——邊（或弧）上帶權(quán)的圖稱為網(wǎng)或帶權(quán)圖。如圖3所示，就是一個(gè)無向網(wǎng)（無向帶權(quán)圖）。如果邊是有方向的帶權(quán)圖，則就是一個(gè)有向網(wǎng)。3一個(gè)無向網(wǎng)第91頁，共160頁，2023年，2月20日，星期五路徑、路徑長度、簡單路徑在無向圖中，若存在一個(gè)頂點(diǎn)序列vi,vi1,vi2,…,vim,vj.，其中，（vi,vi1），(vi1,vi2)，…,(vim,.vj)分別為圖中的邊。則稱頂點(diǎn)vi到vj存在一條路徑。對(duì)于有向圖，路徑由弧組成，即<vi,vi1>,<vi1,vi2>，…,<vim,.vj>路徑上邊的數(shù)目稱為路徑長度。頂點(diǎn)不重復(fù)出現(xiàn)的路徑稱該路徑為簡單路徑。在圖1的無向圖G1中，v1→v4→v3→v5與v1→v2→v5是從頂點(diǎn)v1

到頂點(diǎn)v5

的兩條路徑，路徑長度分別為3和2。V1V3V2V4V1V3V2V4V5第92頁，共160頁，2023年，2月20日，星期五連通圖、連通分量在無向圖中，如果從一個(gè)頂點(diǎn)vi到另一個(gè)頂點(diǎn)vj(i≠j)有路徑，則稱頂點(diǎn)vi和vj是連通的。任意兩頂點(diǎn)都是連通的圖稱為連通圖。無向圖的極大連通子圖稱為連通分量。圖7-5(a)中有兩個(gè)連通分量，如圖7-5(b)所示。AEBFCDAEBFCD(a)無向圖G3(b)G3的兩個(gè)連通分量圖7-5無向圖及連通分量示意第93頁，共160頁，2023年，2月20日，星期五強(qiáng)連通圖、強(qiáng)連通分量對(duì)于有向圖來說，若圖中任意兩個(gè)頂點(diǎn)vi和vj(i≠j)都連通，即從vi到vj和從vj到vi之間都有路徑，則稱該有向圖是強(qiáng)連通圖。有向圖的極大強(qiáng)連通子圖稱為強(qiáng)連通分量。圖7-2中有兩個(gè)強(qiáng)連通分量，分別是{v1,v3,v4}和{v2}，如圖7-6所示。V1V3V2V4圖7-6有向圖G2的兩個(gè)強(qiáng)連通分量示意V1V3V2V4圖7-2連通圖只有一個(gè)連通分量,強(qiáng)連通圖只有一個(gè)強(qiáng)連通分量。第94頁，共160頁，2023年，2月20日，星期五圖的存儲(chǔ)表示

1.用連續(xù)的地址空間存儲(chǔ)圖的數(shù)據(jù)元素及元素之間的關(guān)系（鄰接關(guān)系）。用一個(gè)一維數(shù)組存儲(chǔ)頂點(diǎn)信息，用一個(gè)二維數(shù)組存儲(chǔ)頂點(diǎn)之間的關(guān)系。1.鄰接矩陣第95頁，共160頁，2023年，2月20日，星期五acbde存儲(chǔ)數(shù)據(jù)元素abcde1234501010101010101110100011001234512345存儲(chǔ)數(shù)據(jù)的鄰接關(guān)系debca1234500011001100101111100101001234512345無向圖例1：第96頁，共160頁，2023年，2月20日，星期五abcd123412341234acbd0110000000011000存儲(chǔ)數(shù)據(jù)元素存儲(chǔ)數(shù)據(jù)元素的鄰接關(guān)系例2：第97頁，共160頁，2023年，2月20日，星期五acbde存儲(chǔ)數(shù)據(jù)元素abcde12345∞6∞5∞6∞7∞8∞7∞395∞3∞∞∞89∞∞1234512345存儲(chǔ)數(shù)據(jù)的鄰接關(guān)系無向網(wǎng)例3：563879第98頁，共160頁，2023年，2月20日，星期五圖的鄰接矩陣具有以下性質(zhì)：（1）無向圖的鄰接矩陣一定是一個(gè)對(duì)稱矩陣。因此，在具體存放鄰接矩陣時(shí)只需存放上（或下）三角矩陣的元素即可。（2）對(duì)于無向圖，鄰接矩陣的第i行（或第i列）非零元素（或非∞元素）的個(gè)數(shù)正好是第i個(gè)頂點(diǎn)的度D(vi)。（3）對(duì)于有向圖，鄰接矩陣的第i行（或第i列）非零元素（或非∞元素）的個(gè)數(shù)正好是第i個(gè)頂點(diǎn)的出度OD(vi)（或入度ID(vi)）。（4）用鄰接矩陣方法存儲(chǔ)圖，很容易確定圖中任意兩個(gè)頂點(diǎn)之間是否有邊相連；但是，要確定圖中有多少條邊，則必須按行、按列對(duì)每個(gè)元素進(jìn)行檢測，所花費(fèi)的時(shí)間代價(jià)很大。這是用鄰接矩陣存儲(chǔ)圖的局限性。第99頁，共160頁，2023年，2月20日，星期五2鄰接表

1.鄰接表是圖的一種順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)結(jié)合的存儲(chǔ)方法。鄰接表表示法類似于樹的孩子鏈表表示法。用連續(xù)的地址空間存儲(chǔ)圖的數(shù)據(jù)元素，用單鏈表（非順序空間）存儲(chǔ)元素之間的鄰接關(guān)系。表頭結(jié)點(diǎn)存儲(chǔ)鄰接點(diǎn)信息vertex：存儲(chǔ)頂點(diǎn)或其它有關(guān)信息；firstedge：指向第一個(gè)鄰接點(diǎn)結(jié)點(diǎn)；adjvex：鄰接點(diǎn)的存儲(chǔ)位置；next：指向下一個(gè)鄰接點(diǎn)結(jié)點(diǎn)；vertexfirstedgeadjvexnext第100頁，共160頁，2023年，2月20日，星期五例：下圖給出無向圖對(duì)應(yīng)的鄰接表表示。

第101頁，共160頁，2023年，2月20日，星期五下圖給出有向圖對(duì)應(yīng)的鄰接表表示。

第102頁，共160頁，2023年，2月20日，星期五鄰接表特點(diǎn)：1）無向圖易求度，有向圖易求出度，入度？2）無向圖的鄰接表，第i個(gè)鏈表結(jié)點(diǎn)數(shù)等于Vi的度。3）有向圖的鄰接表，第i個(gè)鏈表結(jié)點(diǎn)數(shù)等于Vi的出度，有向圖頂點(diǎn)i的入恰好是逆鄰接表中第i個(gè)鏈表的結(jié)點(diǎn)個(gè)數(shù)。第103頁，共160頁，2023年，2月20日，星期五圖的遍歷圖的遍歷：是指從圖中的某一頂點(diǎn)出發(fā)，對(duì)圖中的所有頂點(diǎn)訪問一次，而且僅訪問一次。

圖的遍歷：有廣度優(yōu)先和深度優(yōu)先兩種方式。深度優(yōu)先遍歷類似于樹的先根遍歷，是樹的先根遍歷的推廣。假設(shè)圖G=(V,E)，從V0開始深度優(yōu)先遍歷過程：1）訪問V0，作已訪問標(biāo)志；2）任選一個(gè)與V0鄰接但未被訪問的頂點(diǎn)U訪問（如果沒有，則從V0開始的深度優(yōu)先遍歷已結(jié)束，如果有多個(gè)，選其中一個(gè)U）3）從頂點(diǎn)U開始深度優(yōu)先遍歷圖。第104頁，共160頁，2023年，2月20日，星期五V1V5V2V4V8V3V6V7

例：求下圖的深度優(yōu)先遍歷v1→v2→v4→v8→v5→v3→v6→v7深度優(yōu)先遍歷得到的頂點(diǎn)訪問序列為：從1開始：1→2→3→4→從5開始：5→6→7從5開始5→7→6→2→4→3→1第105頁，共160頁，2023年，2月20日，星期五2.廣度優(yōu)先遍歷1、遍歷方式：假設(shè)圖為G=(V,E),從V0開始廣度優(yōu)先遍歷圖。訪問V0，作已訪問標(biāo)志；依次訪問與V0鄰接但未訪問的各個(gè)頂點(diǎn)；分別從這些頂點(diǎn)開始廣度優(yōu)先遍歷圖；并使“先被訪問的頂點(diǎn)的鄰接點(diǎn)”先于“后被訪問的頂點(diǎn)的鄰接點(diǎn)”被訪問。若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖中一個(gè)未曾被訪問的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問到為止。2、特點(diǎn)：類似于樹的層次遍歷盡可能先在橫向上搜索鄰接點(diǎn)，即由近及遠(yuǎn)，依次訪問和出發(fā)點(diǎn)有路徑相通，且路徑長度為1,2...的頂點(diǎn)。第106頁，共160頁，2023年，2月20日，星期五對(duì)上面無向圖進(jìn)行廣度優(yōu)先搜索遍歷，首先訪問v1

和v1的鄰接點(diǎn)v2和v3，然后依次訪問v2

的鄰接點(diǎn)v4

和v5

及v3

的鄰接點(diǎn)v6和v7，最后訪問v4

的鄰接點(diǎn)v8。由于這些頂點(diǎn)的鄰接點(diǎn)均已被訪問，并且圖中所有頂點(diǎn)都被訪問，由些完成了圖的遍歷。得到的頂點(diǎn)訪問序列為：

v1→v2→v3→v4→v5→v6→v7→v8V1V5V2V4V8V3V6V7例1.求下圖的廣度優(yōu)先遍歷第107頁，共160頁，2023年，2月20日，星期五