數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)要點(diǎn)(整理版)

1、風(fēng)從水上走過，留下粼粼波紋；駱駝從沙漠上走過，留下深深的腳印 ；哨鴿從天空飛過，留下串串歡韻；歲月從樹林穿過，留下圈圈年輪。啊，朋友，我們從時(shí)代的舞臺(tái)走過，將給社會(huì)留下些什么？花從春走過，留下縷縷花香；葉從夏走過，留下片片蔭涼；風(fēng)從秋走過，留下陣陣金浪；雪從冬走過，留下種種希望。啊，朋友，我們從人生的四季走過，將給人生留下些什么第一章數(shù)據(jù)結(jié)構(gòu)概述基本概念與術(shù)語1 .數(shù)據(jù)：數(shù)據(jù)是對客觀事物的符號(hào)表示，在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序所處理的符號(hào)的總稱。2 .數(shù)據(jù)元素：數(shù)據(jù)元素是數(shù)據(jù)的基本單位，是數(shù)據(jù)這個(gè)集合中的個(gè)體，也稱之為元素，結(jié)點(diǎn),頂點(diǎn)記錄。(補(bǔ)充：一個(gè)數(shù)據(jù)元素可由若干個(gè)

2、數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。)3 .數(shù)據(jù)對象：數(shù)據(jù)對象是具有相同性質(zhì)的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。(有時(shí)候也叫做屬性。)4 .數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。(1)數(shù)據(jù)的邏輯結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間存在的固有邏輯關(guān)系，常稱為數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)是從數(shù)據(jù)元素之間存在的邏輯關(guān)系上描述數(shù)據(jù)與數(shù)據(jù)的存儲(chǔ)無關(guān)，是獨(dú)立于計(jì)算機(jī)的。依據(jù)數(shù)據(jù)元素之間的關(guān)系，可以把數(shù)據(jù)的邏輯結(jié)構(gòu)分成以下幾種：1 .集合：數(shù)據(jù)中的數(shù)據(jù)元素之間除了“同屬于一個(gè)集合的關(guān)系以外，沒有其他關(guān)系。2 .線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在“一對一“的關(guān)系。若結(jié)構(gòu)為非

3、空集合，則除了第一個(gè)元素之外，和最后一個(gè)元素之外，其他每個(gè)元素都只有一個(gè)直接前驅(qū)和一個(gè)直接后繼。3 .樹形結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在“一對多的關(guān)系。若數(shù)據(jù)為非空集，則除了第一個(gè)元素(根)之外，其它每個(gè)數(shù)據(jù)元素都只有一個(gè)直接前驅(qū)，以及多個(gè)或零個(gè)直接后繼。4 .圖狀結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素存在“多對多”的關(guān)系。若結(jié)構(gòu)為非空集，折每個(gè)數(shù)據(jù)可有多個(gè)(或零個(gè))直接后繼。(2)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)內(nèi)的表示稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。想要計(jì)算機(jī)處理數(shù)據(jù)，就必須把數(shù)據(jù)的邏輯結(jié)構(gòu)映射為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。邏輯結(jié)構(gòu)可以映射為以下兩種存儲(chǔ)結(jié)構(gòu)：1 .順序存儲(chǔ)結(jié)構(gòu)：把邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理位置也相鄰

4、的存儲(chǔ)單元中，借助元素在存儲(chǔ)器中的相對位置來表示數(shù)據(jù)之間的邏輯關(guān)系。2 .鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：借助指針表達(dá)數(shù)據(jù)元素之間的邏輯關(guān)系。不要求邏輯上相鄰的數(shù)據(jù)元素物理位置上也相鄰。5.時(shí)間復(fù)雜度分析：1.常量階：算法的時(shí)間復(fù)雜度與問題規(guī)模n無關(guān)系T(n)=O(1)2 .線性階：算法的時(shí)間復(fù)雜度與問題規(guī)模n成線性關(guān)系T(n)=O(n)3 .平方階和立方階：一般為循環(huán)的嵌套，循環(huán)體最后條件為i+時(shí)間復(fù)雜度的大小比較：O(1)O(log2n)O(n)O(nlog2n)O(n2)O(n3)O(2n)O(n!)next=head-next;head-next=p;輸出：printf(%d”,p-data);刪除：q

5、=p-next;p-next=q-next;free(q);結(jié)點(diǎn)遍歷：for(p=head;p;p=p-next);補(bǔ)充內(nèi)容：1、線性表中，第一個(gè)元素沒有直接前驅(qū)，最后一個(gè)元素沒有直接后驅(qū)。2、在一個(gè)單鏈表中，若p所指結(jié)點(diǎn)是q所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，則刪除結(jié)點(diǎn)q的操作語句為P-next=q-next;free（q）;3、在長度為N的順序表中，插入一個(gè)新元素平均需要移動(dòng)表中N/2個(gè)元素，刪除一個(gè)元素平均需要移動(dòng)（N-1）/2個(gè)元素。4、若線性表的主要操作是在最后一個(gè)元素之后插入一個(gè)元素或刪除最后一個(gè)元素，則采用順序表存儲(chǔ)結(jié)構(gòu)最節(jié)省運(yùn)算時(shí)間。5、已知順序表中每個(gè)元素占用3個(gè)存儲(chǔ)單元，第13個(gè)元素的存儲(chǔ)

6、地址為336,則順序表的首地址為300。（第n個(gè)元素的地址即首地址+（n-1）*每個(gè)元素的存儲(chǔ)空間，如a12（第13個(gè)元素）的地址=a0+12*3）6、設(shè)有一帶頭結(jié)點(diǎn)單鏈表L,請編寫該單鏈表的初始化，插入、輸出和刪除函數(shù)。（函數(shù)名自定義）結(jié)點(diǎn)定義：typedefintdatatype;結(jié)點(diǎn)數(shù)據(jù)類型，假設(shè)為inttypedefstructnode結(jié)點(diǎn)結(jié)構(gòu)datatypedata;structnode*next;/雙向鏈表還應(yīng)加上previousLnode,*pointer;/結(jié)點(diǎn)類型，結(jié)點(diǎn)指針類型typedefpointerIklist;單鏈表類型，即頭指針類型1 .初始化：Iklistinit

7、list()pointerhead;head=newnode;這是C+做法/head=(pointer)malloc(sizeof(Lnode);這是C語言做法head-next=NULL;循環(huán)鏈表則是head-next=head;/雙向鏈表應(yīng)力口上head-previos=NULL;returnhead;2 .插入：(C語言中需要把head轉(zhuǎn)化為全局變量才能實(shí)現(xiàn)此程序)intinsert(lklisthead,datatypex,inti)pointerq,s;q=get(head,i-1);找第i-1個(gè)點(diǎn)if(q=NULL)無第i-1點(diǎn)，即in+1時(shí)coutdata=x;s-next=q-

8、next;新點(diǎn)的后繼是原第i個(gè)點(diǎn)q-next=s;原第i-1個(gè)點(diǎn)的后繼是新點(diǎn)return1;插入成功3 .刪除：(C語言中需要把head轉(zhuǎn)化為全局變量才能實(shí)現(xiàn)此程序)intdelete(lklisthead,inti)pointerp,q;q=get(head,i-1);找待刪點(diǎn)的直接前趨if(q=NULL|q-next=NULL)即in時(shí)coutnext;保存待刪點(diǎn)地址q-next=p-next;修改前趨的后繼指針deletep;釋放結(jié)點(diǎn)即C語言中的free(p);return1;刪除成1 .不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是(A)A.head=NULLB.head-next=NUL

9、LC.head-next=headD.head!=NULL2 .帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是(B)A.head=NULLB.head-next=NULLC.head-next=headD.head!=NULL3 .在一個(gè)單鏈表中，若p所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在p之后插入s所指結(jié)點(diǎn)，則執(zhí)行(B)A.s-next=p;p-next=s;B.s-next=p-next;p-next=s;C.s-next=p-next;p=s;D.p-next=s;s-next=p;4 .在一個(gè)單鏈表中，若刪除p所指結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則執(zhí)行(A)A.p-next=p-next-next;B. p=p-next

10、;p-next=p-next-next;C. p-next=p-nextD. p=p-next-next5 .從一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中查找其值等于x結(jié)點(diǎn)時(shí)，在查找成功的情況下，需平均比較(B)個(gè)結(jié)點(diǎn)。A.nB.n/2C.(n-1)/2D.O(nlog2n)6 .給定有n個(gè)元素的向量，建立一個(gè)有序單鏈表的時(shí)間復(fù)雜度(B)A.O(1)B.O(n)C.O(n2)D.O(nlog2n)7 .在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然有序的時(shí)間復(fù)雜度是(B)A.O(1)B.O(n)C.O(n2)D.O(nlog2n)8 .在一個(gè)單鏈表中刪除q所指結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行如下操作：q=p-next

11、;p-next=(p-next-next);free(q);/這種題目靠一根指針是沒有辦法完成的，必須要借助第二根指針。9 .在一個(gè)單鏈表中p所指結(jié)點(diǎn)之后插入一個(gè)s所指結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行：s-next=(p-next)p-next=(s)操作。10 .對于一個(gè)具有n個(gè)節(jié)點(diǎn)的單鏈表，在已知所指結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度是(O(1);在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度是(O(n)。11 .問答題線性表可用順序表或鏈表存儲(chǔ)。試問：(1)兩種存儲(chǔ)表示各有哪些主要優(yōu)缺點(diǎn)？順序表的存儲(chǔ)效率高，存取速度快。但它的空間大小一經(jīng)定義，在程序整個(gè)運(yùn)行期間不會(huì)發(fā)生改變，因此，不易擴(kuò)充。同時(shí)，由于在插入

12、或刪除時(shí)，為保持原有次序，平均需要移動(dòng)一半(或近一半)元素，修改效率不高。鏈接存儲(chǔ)表示的存儲(chǔ)空間一般在程序的運(yùn)行過程中動(dòng)態(tài)分配和釋放，且只要存儲(chǔ)器中還有空間，就不會(huì)產(chǎn)生存儲(chǔ)溢出的問題。同時(shí)在插入和刪除時(shí)不需要保持?jǐn)?shù)據(jù)元素原來的物理順序，只需要保持原來的邏輯順序，因此不必移動(dòng)數(shù)據(jù)，只需修改它們的鏈接指針，修改效率較高。但存取表中的數(shù)據(jù)元素時(shí)，只能循鏈順序訪問，因此存取效率不高。(2)若表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除，但要求以最快的速度存取表中的元素，這時(shí)，應(yīng)采用哪種存儲(chǔ)表示？為什么？應(yīng)采用順序存儲(chǔ)表示。因?yàn)轫樞虼鎯?chǔ)表示的存取速度快，但修改效率低。若表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除，

13、但要求以最快的速度存取表中的元素，這時(shí)采用順序存儲(chǔ)表示較好。第三章棧和隊(duì)列1 .棧(1) 棧的結(jié)構(gòu)與定義定義：限定僅在表尾進(jìn)行插入或刪除操作的線性表。結(jié)構(gòu)：typedefstructlistintlistsize;棧的容量structlist*head;棧頂指針structlist*base;棧底指針(2) 順序棧操作算法：入棧、出棧、判斷?？盏?這個(gè)是使用數(shù)組進(jìn)行操作的，具體內(nèi)容參照書本P46-47)(3) 鏈棧的結(jié)構(gòu)與定義2 .隊(duì)列（1） 隊(duì)列的定義定義：只允許在表的一端進(jìn)行插入，而在另一端刪除元素。補(bǔ)充內(nèi)容：1、一個(gè)棧的入棧序列為“ABCDE，則以下不可能的出棧序列是（B）A.BCDAE

14、B.EDACBC.BCADED.AEDCB2、棧的順序表示中，用TOP表示棧頂元素，那么?？盏臈l件是（D）A.TOP=STACKSIZEB.TOP=1C.TOP=0D.TOP=-13、允許在一端插入，在另一端刪除的線性表稱為隊(duì)列。插入的一端為表頭，刪除的一端為表尾。4、棧的特點(diǎn)是先進(jìn)后出，隊(duì)列的特點(diǎn)是先進(jìn)先出。5、對于棧和隊(duì)列，無論他們采用順序存儲(chǔ)結(jié)構(gòu)還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，進(jìn)行插入和刪除操作的時(shí)間復(fù)雜度都是0（1）（即與已有元素N無關(guān)）。6、已知鏈棧Q,編寫函數(shù)判斷?？?，如果?？談t進(jìn)行入棧操作，否則出棧并輸出。（要求判斷棧空、出棧、入棧用函數(shù)實(shí)現(xiàn)）（詳看考點(diǎn)2）7 .出隊(duì)與取隊(duì)頭元素的區(qū)別：出隊(duì)就

15、是刪除對頭的數(shù)據(jù)元素，取隊(duì)頭元素是獲取對頭的數(shù)據(jù)元素值，不需要?jiǎng)h除。8 .鏈棧與順序棧相比，比較明顯的優(yōu)點(diǎn)是：（D）A.插入操作比較容易B.刪除操作比較容易C.不會(huì)出現(xiàn)?？盏那闆rD.不會(huì)出現(xiàn)棧滿的情況考點(diǎn)1:隊(duì)列的編程：結(jié)構(gòu)：typedefstructQNodeintdate;structQNode*next;QNode,*QueuePtr;typedefstructQueuePtrfront;QueuePtrrear;LinkQueue;創(chuàng)建：LinkQueueInitQueue(LinkQueueQ)Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)

16、;Q.front-next=NULL;return(Q);入隊(duì)：LinkQueueEnQueue(LinkQueueQ,inte)QueuePtrp;p=(QueuePtr)malloc(sizeof(QNode);p-date=e;p-next=NULL;Q.rear-next=p;Q.rear=p;return(Q);出隊(duì)：LinkQueueDeQueue(LinkQueueQ)inte;QueuePtrp;p=Q.front-next;e=p-date;Q.front=p-next;printf(%d,e);if(Q.rear=p)Q.rear=Q.front=NULL;free(p);

17、return(Q);考點(diǎn)2:棧的編程：創(chuàng)建：structlist*creat()structlist*p;p=(structlist*)malloc(LEN);p-next=NULL;return(p);入棧：structlist*push(structlist*head,inta)structlist*p;p=(structlist*)malloc(LEN);p-num=a;p-next=head;return(p);出棧：structlist*pop(structlist*head)structlist*p;p=head-next;free(head);return(p);判斷?？眨篿nt

18、listempty(structlist*head)if(head-next)return0;elsereturn1;第四章串(不是重點(diǎn)內(nèi)容)1 .串是由零個(gè)或多個(gè)字符組成的有限序列2 .串的賦值：x=abc;或x=abc;第五章數(shù)組和廣義表(不是重點(diǎn)內(nèi)容)1 .多維數(shù)組中某數(shù)組元素的position求解。一般是給出數(shù)組元素的首元素地址和每個(gè)元素占用的地址空間并組給出多維數(shù)組的維數(shù)，然后要求你求出該數(shù)組中的某個(gè)元素所在的位置。2 .明確按行存儲(chǔ)和按列存儲(chǔ)的區(qū)別和聯(lián)系，并能夠按照這兩種不同的存儲(chǔ)方式求解1中類型的題。3 .將特殊矩陣中的元素按相應(yīng)的換算方式存入數(shù)組中。這些矩陣包括：對稱矩陣，三角

19、矩陣，具有某種特點(diǎn)的稀疏矩陣等。熟悉稀疏矩陣的三種不同存儲(chǔ)方式：三元組，帶輔助行向量的二元組，十字鏈表存儲(chǔ)。掌握將稀疏矩陣的三元組或二元組向十字鏈表進(jìn)行轉(zhuǎn)換的算法。補(bǔ)充內(nèi)容：三元組：結(jié)構(gòu)：typedefstructinti,j;元素行下標(biāo)及列下標(biāo)inte;元素值Triple;typedefstructintmu,nu,tu;矩陣的行數(shù)、列數(shù)、非零元素個(gè)數(shù)TripledataMAXSIZE+1;矩陣包含的三元組表，data0未用TSMatrix;十字鏈表：typedefstructOLNodeinti,j;元素行下標(biāo)及列下標(biāo)inte;元素值structOLNode*right,*down;行的后

20、繼以及列的后繼OLNode,*OLink;typedefstructintmu,nu,tu;矩陣的行數(shù)、列數(shù)、非零元素個(gè)數(shù)OLink*rhead,*chead;行和列的表頭指針組的首地址CrossList;CrossListCreat(CrossListM)intm,n,t;scanf(%d%d%d”,&m,&n,&t);M.mu=m;M.nu=n;M.tu=t;M.rhead=(OLink*)malloc(m+1)*sizeof(OLink);開辟行表頭指針組M.chead=(OLink*)malloc(n+1)*sizeof(OLink);開辟行列頭指針組M.rhead=M.chead=N

21、ULL;初始化接下來就是賦值和入鏈第六章樹和二叉樹1 .樹(1) 樹的概念及術(shù)語樹：n(n0)個(gè)結(jié)點(diǎn)的有限集合。當(dāng)n=0時(shí)，稱為空樹；任意一棵非空樹滿足以下條件：有且僅有一個(gè)特定的稱為根的結(jié)點(diǎn)；當(dāng)n1時(shí)，除根結(jié)點(diǎn)之外的其余結(jié)點(diǎn)被分成m(m0)個(gè)互不相交的有限集合T1,T2,，Tm,其中每個(gè)集合又是一棵樹，并稱為這個(gè)根結(jié)點(diǎn)的子樹。(2) 結(jié)點(diǎn)的度：結(jié)點(diǎn)所擁有的子樹的個(gè)數(shù)。樹的度：樹中所有結(jié)點(diǎn)的度的最大值。(3) 葉子結(jié)點(diǎn)：度為0的結(jié)點(diǎn)，也稱為終端結(jié)點(diǎn)。分支結(jié)點(diǎn)：度不為。的結(jié)點(diǎn)，也稱為非終端結(jié)點(diǎn)。(4)孩子、雙親：樹中某結(jié)點(diǎn)的子樹的根結(jié)點(diǎn)稱為這個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)，這個(gè)結(jié)點(diǎn)稱為它孩子結(jié)點(diǎn)的雙親結(jié)點(diǎn)；兄

22、弟：具有同一個(gè)雙親的孩子結(jié)點(diǎn)互稱為兄弟。(5)路徑：如果樹的結(jié)點(diǎn)序列n1,n2,，nk有如下關(guān)系：結(jié)點(diǎn)ni是ni+1的雙親(1=i0)個(gè)結(jié)點(diǎn)的有限集合，該集合或者為空集(稱為空二叉樹)，或者由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的、分別稱為根結(jié)點(diǎn)的左子樹和右子樹的二叉樹組成。滿二叉樹：在一棵二叉樹中，如果所有分支結(jié)點(diǎn)都存在左子樹和右子樹，并且所有葉子都在同一層上。(滿二叉樹的特點(diǎn)：葉子只能出現(xiàn)在最下一層；只有度為0和度為2的結(jié)點(diǎn)。)完全二叉樹：對一棵具有n個(gè)結(jié)點(diǎn)的二叉樹按層序編號(hào)，如果編號(hào)為i(1wiwn)的結(jié)點(diǎn)與同樣深度的滿二叉樹中編號(hào)為i的結(jié)點(diǎn)在二叉樹中的位置完全相同。完全二叉樹的特點(diǎn)：1 .在滿二叉

23、樹中，從最后一個(gè)結(jié)點(diǎn)開始，連續(xù)去掉任意個(gè)結(jié)點(diǎn)，即是一棵完全二叉樹。2 .葉子結(jié)點(diǎn)只能出現(xiàn)在最下兩層，且最下層的葉子結(jié)點(diǎn)都集中在二叉樹的左部；3 .完全二叉樹中如果有度為1的結(jié)點(diǎn)，只可能有一個(gè)，且該結(jié)點(diǎn)只有左孩子。4 .深度為k的完全二叉樹在k-1層上一定是滿二叉樹。(3)二叉樹的性質(zhì):性質(zhì)1:二叉樹的第i層上最多有2i-1個(gè)結(jié)點(diǎn)(i1)o性質(zhì)2：一棵深度為k的二叉樹中，最多有2k-1個(gè)結(jié)點(diǎn)，最少有k個(gè)結(jié)點(diǎn)。深度為k且具有2k-1個(gè)結(jié)點(diǎn)的二叉樹一定是滿二叉樹性質(zhì)3:在一棵二叉樹中，如果葉子結(jié)點(diǎn)數(shù)為n0,度為2的結(jié)點(diǎn)數(shù)為n2,則有：n0=n2+1。(一個(gè)結(jié)點(diǎn)的度就是指它放出的射線)性質(zhì)4：具有n個(gè)

24、結(jié)點(diǎn)的完全二叉樹的深度為log2n+1。性質(zhì)5:對一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹中從1開始按層序編號(hào)，則對于任意的序號(hào)為i(1wiwn)的結(jié)點(diǎn)(簡稱為結(jié)點(diǎn)i),有：(1)如果i1,則結(jié)點(diǎn)i的雙親結(jié)點(diǎn)的序號(hào)為i/2;如果i=1,則結(jié)點(diǎn)i是根結(jié)點(diǎn)，無雙殺結(jié)點(diǎn)O(2)如果2in,則結(jié)點(diǎn)i無左孩子。(3)如果2i+1wn,則結(jié)點(diǎn)i的右孩子的序號(hào)為2i+1;如果2i+1n,則結(jié)點(diǎn)i無右孩子。3 .二叉樹的遍歷(遞歸調(diào)用與訪問的順序不同而產(chǎn)生不同的遍歷方法)(1) 先序遍歷voidXianXu(BiTreeT)if(T)printf(%c,T-data);先訪問XianXu(T-lchild);再繼續(xù)遍歷X

25、ianXu(T-rchild);(2) 中序遍歷(3) 后序遍歷4 .森林與二叉樹的轉(zhuǎn)換(1)同級(jí)以左為親，即左一結(jié)點(diǎn)的右孩子是與它同級(jí)的右一結(jié)點(diǎn)(2)只認(rèn)最左路線為親子路線，即結(jié)點(diǎn)的左孩子是它下一級(jí)結(jié)點(diǎn)的最左的元素5.哈夫曼樹(1)哈夫曼樹的基本概念：哈夫曼樹：給定一組具有確定權(quán)值的葉子結(jié)點(diǎn)，帶權(quán)路徑長度最小的二叉樹。(2)哈夫曼樹的特點(diǎn)：1 .權(quán)值越大的葉子結(jié)點(diǎn)越靠近根結(jié)點(diǎn)，而權(quán)值越小的葉子結(jié)點(diǎn)越遠(yuǎn)離根結(jié)點(diǎn)。2 .只有度為0(葉子結(jié)點(diǎn))和度為2(分支結(jié)點(diǎn))的結(jié)點(diǎn)，不存在度為1的結(jié)點(diǎn).(3)哈夫曼樹的構(gòu)造算法思想及構(gòu)造過程(森林與哈夫曼編碼)就是求各權(quán)值和路徑相乘之后疊加的最小值。1、已知一

26、棵完全二叉樹有A. 6 B. 12 C. 24 解法如下： 1+2+4+8+16=31 47-31=16 16-16/2=847個(gè)結(jié)點(diǎn)，則該二叉樹有(C)個(gè)葉子結(jié)點(diǎn)。D.48計(jì)算從第一層到n-1層的結(jié)點(diǎn)個(gè)數(shù)計(jì)算第n層的葉子結(jié)點(diǎn)個(gè)數(shù)計(jì)算第n-1層的葉子結(jié)點(diǎn)個(gè)數(shù)所以，葉子結(jié)點(diǎn)數(shù)=16+8=24計(jì)算第n層和第n-1層的總?cè)~子結(jié)點(diǎn)數(shù)2、已知遍歷一棵二叉樹的前序序列ABCDEFG和中序序列CBEDAFG,那么是下面哪棵樹(C)。C圖如下:ACDG/E4、完全二叉樹必須滿足的條件為：一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，它的結(jié)構(gòu)與滿二叉樹的前n個(gè)結(jié)點(diǎn)的的結(jié)構(gòu)相同。5、哈夫曼樹不存在度為1的結(jié)點(diǎn)。6、有5個(gè)帶權(quán)結(jié)點(diǎn)，其

27、權(quán)值分別為2,5,3,7,11,根據(jù)哈夫曼算法構(gòu)建該樹，并計(jì)算該樹的帶權(quán)路徑長度。(構(gòu)建哈夫曼樹，很簡單，從小開始，計(jì)算相加，然后把所有葉子結(jié)點(diǎn)乘以等級(jí)數(shù)字然后相加。也即是：帶權(quán)路徑長度=葉結(jié)點(diǎn)的權(quán)值*路徑長度)7.試找出分別滿足下列條件的所有二叉樹：前序序列和中序序列相同：只有右子樹中序序列和后序序列相同：只有左子樹前序序列和后序序列相同：只有根，空二叉樹第七章圖1 .圖的基本概念：圖的基本術(shù)語及推論圖的結(jié)點(diǎn)之間的關(guān)系可以是任意的，圖中任意兩個(gè)數(shù)據(jù)元素之間都可能相關(guān)。設(shè)圖有n個(gè)頂點(diǎn)，則：有1/2n(n-1)條邊的無向圖稱為完全圖有n(n-1)條弧的有向圖稱為有向完全圖元素被多少條弧的箭頭所指，它的入度就為多少；反之，出度。第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑叫做回路或環(huán)頂點(diǎn)不重復(fù)出現(xiàn)的路徑叫簡單路徑若圖中任意兩個(gè)頂點(diǎn)之間存在路徑(不一定是直接相連)，則