數(shù)據(jù)結(jié)構(gòu)考點解析課件

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

考點解析湖北科技學(xué)院計算機學(xué)院陳博數(shù)據(jù)結(jié)構(gòu)輔導(dǎo)數(shù)據(jù)結(jié)構(gòu)

考點解析湖北科技學(xué)院計算機學(xué)院數(shù)據(jù)2數(shù)據(jù)結(jié)構(gòu)考點解析概述第一章知識點第二章知識點第三章知識點第四章知識點第五章知識點第六章知識點2數(shù)據(jù)結(jié)構(gòu)考點解析概述3考試的要求考試主要從兩個方面進(jìn)行考查：知識和技能。知識方面 從數(shù)據(jù)結(jié)構(gòu)的結(jié)構(gòu)定義和使用，以及存儲表示和操作的實現(xiàn)兩個層次，系統(tǒng)地考查：掌握常用的基本數(shù)據(jù)結(jié)構(gòu)（包括順序表、鏈接表、棧與隊列、數(shù)組、二叉樹、堆、樹與森林、圖、查找結(jié)構(gòu)、索引結(jié)構(gòu)、散列結(jié)構(gòu)）及其不同的實現(xiàn)。3考試的要求考試主要從兩個方面進(jìn)行考查：知識和技能。42) 掌握分析、比較和選擇不同數(shù)據(jù)結(jié)構(gòu)、不同存儲結(jié)構(gòu)、不同算法的原則和方法。技能方面系統(tǒng)地掌握基本數(shù)據(jù)結(jié)構(gòu)的設(shè)計方法;掌握選擇結(jié)構(gòu)的方法和算法設(shè)計的思考方式及技巧；提高分析問題和解決問題的能力。42) 掌握分析、比較和選擇不同數(shù)據(jù)結(jié)構(gòu)、不同存儲結(jié)構(gòu)、不5本章“線性表”的知識點有5個：線性表的定義和特點：由數(shù)據(jù)元素組成，惟一直接前驅(qū)與后繼。線性表的基本操作：查找、定位、遍歷、插入、刪除。線性表的存儲表示：順序存儲、鏈表存儲。循環(huán)鏈表和雙向鏈表：定義和基本運算。線性表的應(yīng)用：掌握使用線性表基本操作實現(xiàn)應(yīng)用算法第一章知識點解析5本章“線性表”的知識點有5個：第一章知識點解析6線性表的定義和特點問題1.

如果一個元素集合中每個元素都有1個且僅有1個直接前驅(qū)和1個直接后繼，它是線性表嗎？解析：答案“否”，該元素集合是一個回路（環(huán)）。引伸：循環(huán)鏈表是一個“環(huán)”，它符合線性表的定義嗎？問題的關(guān)鍵是：線性表是邏輯結(jié)構(gòu)，線性表和非線性表是從邏輯上劃分的。而循環(huán)鏈表是存儲結(jié)構(gòu)，是線性表的一種特殊的表示，是線性鏈表的一種擴展。它在形態(tài)上有線性的特征，在行為上有線性表的循序訪問的特點。6線性表的定義和特點問題1.如果一個元素集合中每個元素都7問題2.

如果一個元素集合有一個元素僅有1個直接后繼而沒有直接前驅(qū)，另一個元素僅有1個直接前驅(qū)而沒有直接后繼，其他每個元素都僅有1個直接前驅(qū)和1個直接后繼，但其中各個元素可能數(shù)據(jù)類型不同，該元素集合是線性表嗎？解析：答案“是”，它符合線性表的定義和特性，只要把元素定義為Union類型即可。因為線性表的定義只規(guī)定了元素間的關(guān)系及每個表元素是原子類型，并未規(guī)定每個表元素的類型必須相同。Union是一種等價類型，它允許不同類型數(shù)據(jù)共享同一存儲空間，可保證每個表元素所占空間相同。7問題2.如果一個元素集合有一個元素僅有1個直接后繼8線性表的基本操作問題3.

我們可以為線性表定義查找、插入、刪除等操作嗎？它們?nèi)绾螌崿F(xiàn)？解析：可以為線性表定義這些操作，也可以在程序中直接使用這些操作。但它們的實現(xiàn)與線性表選用何種存儲結(jié)構(gòu)有關(guān)。在定義了線性表的存儲表示之后，必須為相關(guān)操作定義它們的實現(xiàn)代碼。具體的線性表實例一定與某一存儲表示相聯(lián)系，因此，要使用相應(yīng)的基于該存儲結(jié)構(gòu)實現(xiàn)的操作。8線性表的基本操作問題3.我們可以為線性表定義查找、插入9線性表的存儲表示問題4.

線性表的順序存儲表示是一維數(shù)組嗎？解析：答案“否”，應(yīng)是順序表，其區(qū)別在順序表中元素是相繼連續(xù)存放的。而一維數(shù)組只能有兩個操作“按下標(biāo)存”“按下標(biāo)取”，它不一定是相繼存放，不適宜存儲順序的、連續(xù)的序列元素。問題5.

想要以O(shè)(1)的時間代價存取第i

個表元素，線性表應(yīng)采用順序表還是單鏈表？解析：“順序表”，因為單鏈表只能順序地逐個訪問，順序表可以直接訪問第i個元素。9線性表的存儲表示問題4.線性表的順序存儲表示是一維數(shù)組10問題6.

為了統(tǒng)一空鏈表和非空鏈表的操作，簡化鏈表的插入刪除操作，需要給鏈表增加點什么？解析：“增加表頭結(jié)點”。問題7.在何種場合選用順序表？鏈表呢？解析：從時間角度來看，需要經(jīng)常查看不需經(jīng)常增刪的場合使用順序表，因它可直接存取，但增刪要大量移動存儲塊；反之，選擇鏈表，因它在增刪元素時不需移動存儲，修改指針即可，但只能順序訪問，存取速度慢。從空間角度來看，順序表存儲密度（有效存儲/總存儲）高，空間利用率好；鏈表存儲密度較低，空間利用率差一些。10問題6.為了統(tǒng)一空鏈表和非空鏈表的操作，簡化鏈表的插11循環(huán)鏈表和雙向鏈表問題8.

想要以O(shè)(1)的時間代價把兩個鏈表連接起來可采用何種鏈表結(jié)構(gòu)？解析：“循環(huán)鏈表”，若設(shè)兩個循環(huán)鏈表頭指針為p和q，用r=p->link;p->link=q->link;q->link=r;即可把這兩個連接起來。pqr11循環(huán)鏈表和雙向鏈表問題8.想要以O(shè)(1)的時間代價把12問題9.

想要判斷一個帶表頭結(jié)點的循環(huán)鏈表L是否為空，應(yīng)采用何種語句？解析：

“L->link==L”?？毡磉€需保留一個表頭結(jié)點，它的下一個結(jié)點還是它自己。問題10.

想要以O(shè)(1)的時間代價訪問第i個表元素的直接前驅(qū)和／或直接后繼，應(yīng)采用何種鏈表結(jié)構(gòu)？解析：“雙向鏈表”。只要事先定位于該表結(jié)點，通過該結(jié)點的前驅(qū)指針和后繼指針，直接能夠找到該元素的直接前驅(qū)或直接后繼。12問題9.想要判斷一個帶表頭結(jié)點的循環(huán)鏈表L是否為空，13例1：在一個單鏈表中，已知q結(jié)點是p結(jié)點的前趨結(jié)點，若在q和p之間插入s結(jié)點，則須執(zhí)行()A．s->next=p->next;p->next=sB．q->next=s;s->next=pC．p->next=s->next;s->next=pD．p->next=s;s->next=q13例1：14例2：假設(shè)有一個帶表頭結(jié)點的鏈表，表頭指針為head，每個結(jié)點含三個域：data,next和prior。其中data為整型數(shù)域，next和prior均為指針域。現(xiàn)在所有結(jié)點已經(jīng)由next域連接起來，試編一個算法，利用prior域（此域初值為NULL）把所有結(jié)點按照其值從小到大的順序鏈接起來。定義類型LinkList如下：typedefstructnode{intdata;structnode*next,*prior;}LinkList;14例2：15例3：設(shè)順序表L是一個遞減有序表，試寫一算法，將x插入其后仍保持L的有序性。//-----線性表的動態(tài)分配順序存儲結(jié)構(gòu)-----#definemaxlen100//線性表存儲空間最大容量typedefstruct{ElemType*elem;//存儲空間基址

intlen;//當(dāng)前長度}SqList;15例3：16例4：完成以下算法，對單鏈表實現(xiàn)就地逆置。voidLinkList_reverse(Linklist&L){//鏈表的就地逆置;為簡化算法,假設(shè)表長大于2Linklistp,q,s;p=L->next;q=p->next;s=q->next;p->next=NULL;16例4：17例5：循環(huán)鏈表存儲結(jié)構(gòu)示意圖如下，請?zhí)羁眨簍ypedefstructLNode//結(jié)點類型{ElemTypedata;//數(shù)據(jù)單元LNode*next;//指針單元}*Link,*Position;//定義兩個結(jié)點指針別名，用于操作函數(shù)typedefLNode*LinkList;//簡單鏈表類型元素1…元素n頭結(jié)點17例5：元素1…元素n頭結(jié)點18循環(huán)鏈表初始化函數(shù)InitList的參考代碼，一個空的循環(huán)鏈表至少要包含一個頭結(jié)點。voidInitList(LinkList&L){//操作結(jié)果：構(gòu)造一個空的循環(huán)鏈表L。L=(1);//產(chǎn)生頭結(jié)點，使L指向此頭結(jié)點if(!L)//存儲分配失敗{exit(OVERFLOW);}

（2）;//指針域指向頭結(jié)點}18循環(huán)鏈表初始化函數(shù)InitList的參考代碼，一個空的19循環(huán)鏈表銷毀函數(shù)DestroyList的參考代碼（循環(huán)鏈表L尾結(jié)點的next指針指向L）voidDestroyList(LinkList&L){//操作結(jié)果：銷毀循環(huán)鏈表L。

LinkListq,p=L->next;//p指向第一個結(jié)點while((3))//沒到表尾{q=p->next;free(p);p=q;}

（4）;L=NULL;}19循環(huán)鏈表銷毀函數(shù)DestroyList的參考代碼20第二章知識點解析本章“棧、隊列與數(shù)組”的知識點有8個：棧和隊列的定義及其特點棧的存儲表示及其基本運算的實現(xiàn)隊列的存儲表示及其基本運算的實現(xiàn)棧的應(yīng)用隊列的應(yīng)用多維數(shù)組特殊矩陣稀疏矩陣20第二章知識點解析本章“棧、隊列與數(shù)組”的知識點有8個21棧和隊列的定義及其特點問題1.

元素1,2,3,4依次進(jìn)棧，可能的出棧序列有多少種？隊列呢？解析：用catalan函數(shù)計算有8!/4!/4!/5=14種，用隊列是1種。因棧有FILO，隊列有FIFO特性。問題2.

當(dāng)元素以A,B,C,D,E順序進(jìn)棧，D,B,C,E,A是可能的出棧順序嗎？解析：“否”，因序列的進(jìn)出棧順序為IAIBICIDOD,當(dāng)D出棧后，棧頂為C，不能讓B先出來。所以D,B,C,E,A不是可能的出棧順序。21棧和隊列的定義及其特點問題1.元素1,2,3,422問題3.

可否用兩個棧模擬一個隊列？反過來呢？解析：“可以”，一個棧把全部數(shù)據(jù)反過來，另一個棧再把這些數(shù)據(jù)反過去即可。而隊列不能。問題4.棧、隊列對線性表加了什么限制？解析：“限制了存取位置”。棧要求只能在表的一端（棧頂）訪問、插入和刪除，隊列要求只能在表的一端（隊尾）插入，在另一端（隊頭）訪問和刪除，不能在表的中間做上述運算。這決定了在棧和隊列上只能順序訪問，不能直接存取，無論采用何種存儲表示。這表現(xiàn)了它們優(yōu)秀的“結(jié)構(gòu)化”特性。22問題3.可否用兩個棧模擬一個隊列？反過來呢？23棧的存儲表示及其基本運算的實現(xiàn)問題5.

當(dāng)棧空時順序棧的棧頂指針top=-1，當(dāng)棧非空時top是否指示最后元素加入的位置？解析：“是”，每當(dāng)新元素進(jìn)棧時讓棧頂指針top先加1，再按top指示位置把新元素加入，所以棧非空時棧頂指針總是指示最后加入元素的位置。問題6.

順序棧的進(jìn)棧、出棧的先決條件是什么？解析：進(jìn)棧的先決條件是棧未滿，棧滿再進(jìn)棧就會產(chǎn)生溢出；出棧的先決條件是棧不空，?？赵偻藯？蓤蟾娌僮魇?。23棧的存儲表示及其基本運算的實現(xiàn)問題5.當(dāng)?？諘r順序棧的24問題7.

當(dāng)兩個棧共享同一個存儲空間V[m]時，可設(shè)棧頂指針數(shù)組t[2]和棧底指針數(shù)組b[2]。如果進(jìn)棧采用兩個棧相向前行的方式，則任一棧的棧滿條件是什么？解析：“t[0]+1==t[1]”。設(shè)0號棧正向進(jìn)棧，1號棧反向進(jìn)棧，t[0]與t[1]碰頭即棧滿。問題8.

鏈?zhǔn)綏５臈ｍ斨羔樖侵冈阪滎^還是鏈尾？解析：“鏈頭”，鏈?zhǔn)綏Ｒ话悴捎脝捂湵?，棧頂指針即為鏈頭指針。進(jìn)棧出棧均在鏈頭進(jìn)行，每次都要修改棧頂指針。鏈空即?？眨瑃op==NULL。24問題7.當(dāng)兩個棧共享同一個存儲空間V[m]時，可設(shè)25問題9.鏈?zhǔn)綏Ｖ荒茼樞虼嫒?，而順序棧不但能順序存取，還能直接存取，這話對嗎？

解析：

“不對”，順序棧不能直接存取。問題10.理論上鏈?zhǔn)綏]有棧滿問題，但在進(jìn)棧操作實現(xiàn)時，還要判斷一個先決條件，是何條件？解析：每創(chuàng)建新的棧結(jié)點時還要判斷是否動態(tài)分配成功。若不成功則進(jìn)棧操作失敗。

StackNode*s=newStackNode; if(s==NULL){ cerr<<“結(jié)點存儲分配失??！”<<endl; exit(0); }25問題9.鏈?zhǔn)綏Ｖ荒茼樞虼嫒。樞驐２坏茼樞虼嫒?，還26隊列的存儲表示及其基本運算的實現(xiàn)問題11.當(dāng)用犧牲一個單元的方式組織循環(huán)隊列時，隊空和隊滿的條件是什么？進(jìn)隊、出隊的策略是什么？解析：隊空條件“Q.front==Q.rear”隊滿條件“(Q.rear+1)%maxSize==Q.front”

進(jìn)隊：Q.rear=(Q.rear+1)%m;

Q.elem[Q.rear]=x;

出隊：x=Q.elem[Q.front]; Q.front=(Q.front+1)%m;26隊列的存儲表示及其基本運算的實現(xiàn)問題11.當(dāng)用犧牲一個27問題12.

當(dāng)用隊頭指針front和長度length組織循環(huán)隊列時，隊空和隊滿的條件是什么？進(jìn)隊和出隊的策略是什么？（設(shè)表長度為m）解析：隊空條件“Q.length==0” 隊滿條件“Q.length==maxSize” 進(jìn)隊：Q.elem[(Q.front+Q.length)%m]=x; Q.length++; 出隊：Q.length--; x=Q.elem[(Q.front+Q.length)%m];問題13.鏈?zhǔn)疥犃械年狀^和隊尾在鏈表的什么地方？27問題12.當(dāng)用隊頭指針front和長度lengt28解析：“鏈?zhǔn)疥犃械年狀^在鏈頭，隊尾在鏈尾”。問題14.鏈?zhǔn)疥犃械年牽諚l件是什么？

解析：“隊空條件Q.front==NULL”，因隊頭指針為空則說明鏈表為空。用“Q.front==Q.rear”是不對的。問題15.

同時使用多個隊列時需采用何種隊列結(jié)構(gòu)？如何組織？解析：采用多個鏈?zhǔn)疥犃校⒃O(shè)置隊頭指針數(shù)組fr[n]和隊尾指針數(shù)組re[n]，分別指示各隊列的隊頭和鏈尾，其中n是隊列個數(shù)。28解析：“鏈?zhǔn)疥犃械年狀^在鏈頭，隊尾在鏈尾”。29問題16.鏈?zhǔn)疥犃械拿總€結(jié)點是否還可是隊列？

解析：“可以”，如果每個結(jié)點是順序（循環(huán)）隊列則是簡單的情形；如果每個結(jié)點又鏈接出一個鏈?zhǔn)疥犃?，則出現(xiàn)“表中套表”，是廣義表了。例題17.當(dāng)一個循環(huán)隊列已滿，如何才能擴充隊列長度，使得客戶程序能夠繼續(xù)使用這個隊列？解析：用指針動態(tài)定義存放隊列元素的數(shù)組，當(dāng)隊列已滿時，可創(chuàng)建一個更大的同類型的新數(shù)組，把隊列元素全部復(fù)制到新數(shù)組，然后修改隊列指針，釋放老數(shù)組。注意區(qū)分Q.rear<Q.front和Q.front<Q.rear的情形。29問題16.鏈?zhǔn)疥犃械拿總€結(jié)點是否還可是隊列？30棧的應(yīng)用問題18.

在后綴表達(dá)式求值過程中用棧存放什么？在中綴表達(dá)式求值過程中又用棧存放什么？解析：后綴表達(dá)式求值時用棧存放操作數(shù)或運算結(jié)果，中綴表達(dá)式求值時用OPND棧存放操作數(shù)或運算結(jié)果，用OPTR棧存放操作符。問題19.

在遞歸算法中采用何種結(jié)構(gòu)來存放遞歸過程每層的局部變量、返回地址和實參副本？解析：“?！保蜻f歸調(diào)用時需為每層分配，在退出時逐層釋放，這正是后進(jìn)先出的機制，可用棧來組織。30棧的應(yīng)用問題18.在后綴表達(dá)式求值過程中用棧存放什么？31問題20.

為判斷表達(dá)式中的括號是否配對，可采用何種結(jié)構(gòu)輔助進(jìn)行判斷？解析：“?！保瑨呙璞磉_(dá)式，每當(dāng)遇到左括號進(jìn)棧，遇到右括號再判斷棧頂所存括號是否配對，確定是否有錯。問題21.

在回溯法中采用何種結(jié)構(gòu)來記錄回退路徑?解析：“?！?，在沿某條路徑前進(jìn)時用棧記下回退路徑以便回溯之用，比在路徑上各個結(jié)點中增加訪問標(biāo)識更方便。例如圖的深度優(yōu)先搜索，采用在每個邊結(jié)點中增加標(biāo)志域的非遞歸算法比用棧的遞歸算法更復(fù)雜。31問題20.為判斷表達(dá)式中的括號是否配對，可采用何種結(jié)構(gòu)32問題22.若進(jìn)棧序列為1,2,3,4,5,6，出棧序列為2,4,3,6,5,1，問棧容量至少多大？解析：“3”。可實驗畫圖得出。問題23.常用的一種鏈?zhǔn)綏Ｊ腔陟o態(tài)鏈表的。用一個整數(shù)數(shù)組S[n]存放鏈接指針（游標(biāo)），設(shè)初始時top=-1，表示?？?，則其進(jìn)棧、出棧、判?？盏炔僮魅绾螌崿F(xiàn)？解析：判?？眨簍op==-1;

設(shè)表中第k個元素進(jìn)棧：S[k]=top;top=k; 設(shè)出棧元素是第k個元素：k=top;top=S[top];32問題22.若進(jìn)棧序列為1,2,3,4,5,633隊列的應(yīng)用問題24.

在逐層處理一個分層結(jié)構(gòu)的數(shù)據(jù)時，需采用何種輔助結(jié)構(gòu)來組織數(shù)據(jù)？解析：“隊列”，在從隊列中退出當(dāng)前層元素（頭）時把相關(guān)下層元素進(jìn)隊（尾），在當(dāng)前層元素處理完后下一層元素已經(jīng)在隊頭了。問題25.

為實現(xiàn)輸入-處理-輸出并行操作需建立多個輸入緩沖區(qū)隊列，這些隊列是按數(shù)組方式組織的還是按鏈表方式組織的？解析：“按鏈表方式組織的”，各個隊列的增長速度不一，按鏈表組織可以自由增長。33隊列的應(yīng)用問題24.在逐層處理一個分層結(jié)構(gòu)的數(shù)據(jù)時，需34問題26.

在操作系統(tǒng)中一種進(jìn)程調(diào)度策略是先來先服務(wù)，為此使用了何種輔助結(jié)構(gòu)？解析：“隊列”，其特性是先進(jìn)先出。問題27.

在對一個無序單鏈表進(jìn)行排序時，可先把鏈表截出一段段有序的子鏈表，再對它們做兩路歸并排序。為此定義隊列來輔助排序，此隊列的元素的數(shù)據(jù)類型是什么？解析：“鏈表結(jié)點指針”，存放各有序子鏈表的頭指針。每次從隊列中退出兩個子鏈表的頭指針，歸并后把結(jié)果子鏈表的頭指針進(jìn)隊列。如此重復(fù)，直到隊列中只剩下一個鏈表指針為止。34問題26.在操作系統(tǒng)中一種進(jìn)程調(diào)度策略是先來先服務(wù)，為35多維數(shù)組問題28.

二維數(shù)組可以視為數(shù)組元素為一維數(shù)組的一維數(shù)組，因此二維數(shù)組是線性結(jié)構(gòu)嗎？解析：“否”，二維數(shù)組是一維數(shù)組的擴展，每個元素最多有兩個直接前驅(qū)和兩個直接后繼，不符合線性表的特性。問題29.

二維數(shù)組每個元素的存取時間都相同嗎？解析：“是”，按照下標(biāo)確定每個元素存儲地址的計算時間都相同，按地址存取任一元素的時間也相同。35多維數(shù)組問題28.二維數(shù)組可以視為數(shù)組元素為一維數(shù)組的36問題30.數(shù)組是邏輯結(jié)構(gòu)還是物理結(jié)構(gòu)？解析：既是邏輯結(jié)構(gòu)也是物理結(jié)構(gòu)。問題31.

動態(tài)數(shù)組用指針來定義。假定數(shù)組指針為a，可否用*a取出數(shù)組元素的值？可否用a++進(jìn)到下一數(shù)組元素？解析：“可以”，這是C/C++語法文本明確定義的。例如，定義inta[5]={1,3,5,7,9};int*data=a;

有int*elem=newint[5];while(data!=0){*elem=*data;elem++;data++;} for(intk=0;k<n;k++)cout<<elem[k];36問題30.數(shù)組是邏輯結(jié)構(gòu)還是物理結(jié)構(gòu)？37問題32.鏈表也是動態(tài)結(jié)構(gòu)。假定鏈表指針為*a，可否用*a取出鏈表結(jié)點的值？可否用a++進(jìn)到下一鏈表結(jié)點？解析：

“不可以”，因為a所指結(jié)點有兩個域，*a不能取出結(jié)點內(nèi)的數(shù)據(jù)，只能用a->data取出結(jié)點數(shù)據(jù)。同樣不能用a++進(jìn)到下一結(jié)點，因為a++是進(jìn)到物理上的下一個結(jié)點，而鏈表中邏輯上的下一個不見得是物理上的下一個，所以要進(jìn)到邏輯上的下一個，只能用a=a->link。37問題32.鏈表也是動態(tài)結(jié)構(gòu)。假定鏈表指針為*a，可否用38特殊矩陣問題33.

如果用下三角壓縮存儲對稱矩陣，B[0]存放A[0][0]，如何存取A[i][j]？解析：當(dāng)i≥j時，A[i][j]在B[]中的位置是i*(i+1)/2++j。當(dāng)i＜j時，A[i][j]在B[]中不存在。問題34.

兩個對稱矩陣相加，結(jié)果矩陣還對稱嗎？兩個對稱矩陣相乘，結(jié)果矩陣還對稱嗎？解析：兩個對稱矩陣相加的結(jié)果矩陣是對稱矩陣。相乘的結(jié)果矩陣一般不對稱，除非二個對稱矩陣是相同的。38特殊矩陣問題33.如果用下三角壓縮存儲對稱矩陣，B[039問題35.兩個三對角矩陣相加，結(jié)果矩陣還是三對角矩陣嗎？相乘的情況又如何？解析：相加的結(jié)果矩陣還是三對角矩陣。相乘的結(jié)果矩陣一般不是。39問題35.兩個三對角矩陣相加，結(jié)果矩陣還是三對角矩陣嗎40稀疏矩陣問題36.

三對角矩陣是否稀疏矩陣？解析：“否”，三對角矩陣也有大量零元素，但其分布有規(guī)律，不符合稀疏矩陣定義。問題37.

兩個稀疏矩陣相加，結(jié)果矩陣還是稀疏矩陣嗎？兩個稀疏矩陣相乘，結(jié)果矩陣又如何？解析：相加的結(jié)果矩陣不一定是稀疏矩陣，相乘的結(jié)果矩陣肯定不是稀疏矩陣。問題38.用三元組表存儲稀疏矩陣的非零元素，是否失去了直接存取的特性？如何改進(jìn)？40稀疏矩陣問題36.三對角矩陣是否稀疏矩陣？41解析：是，原稀疏矩陣的元素可通過行列下標(biāo)直接存取，而三元組表只能順序存取。改進(jìn)的方法是采用帶行指針的二元組表，可以直接找到某行，且消除了三元組表中冗余的行號。在二元組表內(nèi)搜索某列元素還需順序查找，但個數(shù)少得多。列號值13573-1122449行號1344641解析：是，原稀疏矩陣的元素可通過行列下標(biāo)直接存取，而三元42設(shè)有一個棧，元素的進(jìn)棧次序為A,B,C,D,E,下列是不可能的出棧序列__________。A．A,B,C,D,E B．B,C,D,E,AC．E,A,B,C,D D．E,D,C,B,A42設(shè)有一個棧，元素的進(jìn)棧次序為A,B,43設(shè)棧S和隊列Q的初始狀態(tài)均為空，元素a,b,c,d,e,f,g依次進(jìn)入棧S。若每個元素出棧后立即進(jìn)入隊列Q，且7個元素出隊的順序是b,d,c,f,e,a,g,則棧S的容量至少是

。A.1B.2C.3D.443設(shè)棧S和隊列Q的初始狀態(tài)均為空，元素44稀疏矩陣一般的壓縮存儲方法有兩種，即（）。A.二維數(shù)組和三維數(shù)組B.三元組和散列C.三元組和十字鏈表D.散列和十字鏈表44稀疏矩陣一般的壓縮存儲方法有兩種，即（）。45一個稀疏矩陣如下圖所示，則對應(yīng)的三元組線性表為_____________。45一個稀疏矩陣如下圖所示，則對應(yīng)的三元組線46由兩個棧共享一個向量空間的好處是：（）

A．減少存取時間，降低下溢發(fā)生的機率

B．節(jié)省存儲空間，降低上溢發(fā)生的機率

C．減少存取時間，降低上溢發(fā)生的機率

D．節(jié)省存儲空間，降低下溢發(fā)生的機率46由兩個棧共享一個向量空間的好處是：（）47第三章知識點解析本章“樹與二叉樹”的知識點有10個：樹與二叉樹的定義和性質(zhì)二叉樹的存儲結(jié)構(gòu)二叉樹的遍歷線索二叉樹樹與森林二叉樹的應(yīng)用（二叉排序樹、平衡二叉樹、并查集、Huffman樹、堆）47第三章知識點解析本章“樹與二叉樹”的知識點有10個：48樹與二叉樹的定義和性質(zhì)問題1.二叉樹是樹嗎？解析：“否”，樹的定義是從圖來的，要求結(jié)點至少有1個，二叉樹則可以是空樹；另外二叉樹必為有序樹，樹可有序，也可無序。問題2.樹的葉結(jié)點無子女，是否可稱它無子樹？解析：“是”，樹的定義是遞歸的，遞歸結(jié)束于只有一個結(jié)點的樹。問題3.二叉樹的葉結(jié)點無子女，它是否無子樹？解析：“否”，二叉樹的定義是遞歸的，遞歸到空樹為止，所以結(jié)點無子女，應(yīng)稱它子樹為空。48樹與二叉樹的定義和性質(zhì)問題1.二叉樹是樹嗎？49問題4.樹和二叉樹的高度與深度如何理解？解析：樹的高度與深度的值相等；但樹中某個結(jié)點的高度與深度的值可能不同：深度是從上向下計算的，高度是從下向上計算的。問題5.一棵二叉樹有1024個結(jié)點，其中465個是葉結(jié)點，那么樹中度為2和度為1的結(jié)點各有多少？解析：由n0=n2+1的性質(zhì)，度為2的結(jié)點有465-1=464個，度為1的結(jié)點有1024-465-464=95個。問題6.計算深度的公式

log2(n+1)是針對何種二叉樹的？解析：針對完全二叉樹。但對理想平衡樹也可用。49問題4.樹和二叉樹的高度與深度如何理解？50問題7.二叉樹求深度的公式

log2(n+1)與

log2n+1有何不同？解析：推導(dǎo)有些差異，都可計算二叉樹深度，只不過后者對于n=0不適用。問題8.完全二叉樹有何用處？解析：后續(xù)討論可知，堆、勝者樹、敗者樹等都按完全二叉樹組織。何況完全二叉樹最省存儲。問題9.n0=n2+1公式有何用途？解析：對于完全二叉樹最有用。例如組織對抗賽可用勝者樹，已知選手有n個人，取n0=n,直接可求得比賽場次n2=n0-1，是否有人輪空。50問題7.二叉樹求深度的公式log2(n+1)與51二叉樹的存儲問題10.順序存儲適用于何種二叉樹？解析：適用于完全二叉樹，可充分利用存儲，并可方便地找到某結(jié)點的雙親、兄弟和子女。問題11.完全二叉樹的結(jié)點從1開始編號和從0開始編號有何不同？解析：C/C++與Pascal不同，數(shù)組下標(biāo)從0開始，完全二叉樹從0開始編號是合理的，這時某結(jié)點i的雙親是

(i-1)/2，左子女是2i+1，右子女是2i+2。完全二叉樹結(jié)點從1開始編號是傳承了Pascal的做法。51二叉樹的存儲問題10.順序存儲適用于何種二叉樹？52問題12.通常使用二叉鏈表存儲二叉樹，為何還選用三叉鏈表？解析：使用二叉鏈表找某結(jié)點的左子女和右子女比較方便，找雙親比較麻煩，三叉鏈表每個結(jié)點增設(shè)一個父指針，可方便地找雙親。當(dāng)然，如果結(jié)點數(shù)n很大，不如使用二叉鏈表加一個棧，用棧也可記憶結(jié)點的雙親，所需空間僅O(log2n)。問題13.使用二叉鏈表存儲有n個結(jié)點的二叉樹，空的指針域有多少？解析：n個結(jié)點的二叉樹有2n個指針域，其中n-1個指針域被使用，有n+1個空指針域。52問題12.通常使用二叉鏈表存儲二叉樹，為何還選用三叉鏈53二叉樹的遍歷問題14.已知二叉樹的前序序列abdcef，中序序列dbaecf，其后序序列是什么？解析：由二叉樹的前序序列和中序序 列可唯一確定此二叉樹，根據(jù)問 題要求構(gòu)造出的二叉樹如右圖， 后序序列為dbefca。問題15.前序序列與中序序列相同的是什么二叉樹?解析：要求VLR=LVR，應(yīng)是左子樹均 為空的單支樹，或空樹。abdcef12353二叉樹的遍歷問題14.已知二叉樹的前序序列abdcef54問題16.前序序列與后序序列相同的是什么二叉樹?解析：要求VLR=LRV，應(yīng)是只有根結(jié)點的二叉樹或空樹。問題17.前序序列與層次序序列相同的又是什么二叉樹?解析：應(yīng)是右子樹均為空的單支 樹，或左子樹均為空的單支 樹，或空樹。問題18.后序序列與層次序序列相同的是何二叉樹?解析：只有根結(jié)點的二叉樹或空樹。12312354問題16.前序序列與后序序列相同的是什么二叉樹?12355問題19.前序序列與中序序列正好相反的是什么二叉樹？解析：要求VLR與LVR 相反，即 ，當(dāng)右子樹均為空時，

，或空樹時滿足要求。 問題20.前序序列與后序序列正好相反的是什么二叉樹？解析：要求VLR與LRV 相反，即，當(dāng)右子樹都空時,或左 子樹都空時,或空樹 時滿足要求。12312312355問題19.前序序列與中序序列正好相反的是什么二叉樹？156問題21.一棵二叉樹的前序序列的最后一個結(jié)點是否是它中序序列的最后一個結(jié)點？解析：“不一定是”，右圖即反例，二叉 樹前序序列abdce，中序序列dbaec。問題22.一棵二叉樹的前序序列的最后一個結(jié)點是否是它層次序序列的最后一個結(jié)點？解析：“是”。問題23.一棵有n個結(jié)點的二叉樹的前序序列固定，可能的不同二叉樹有多少種？解析：用catalan函數(shù)求：abdce56問題21.一棵二叉樹的前序序列的最后一個結(jié)點是否是它中57問題24.二叉樹的前序、中序、后序遍歷所走的路線都相同，只是訪問時機不同，這種說法對嗎？解析：“對”，從給出的二叉樹的前序、中序、后序的遞歸遍歷算法就可以清楚看到。問題25.二叉樹的層次序遍歷是按二叉樹層次進(jìn)行逐層訪問，其遍歷算法需要使用何種輔助結(jié)構(gòu)？解析：“隊列”，使用隊列，在逐層訪問過程中一旦當(dāng)前層次的結(jié)點出隊進(jìn)行處理，就需把它下一層的結(jié)點進(jìn)隊列。當(dāng)當(dāng)前層的結(jié)點全部退出隊列并處理完后下一層結(jié)點已經(jīng)在隊頭了。57問題24.二叉樹的前序、中序、后序遍歷所走的路線都相同58線索二叉樹問題26.如何構(gòu)造一棵中序線索二叉樹？解析：通過中序遍歷，把二叉樹改造為中序線索二叉樹

voidcrt-inthtree(ThreadNode*p, ThreadNode*&pre){ if(p){ crt-inthtree(p->left,pre); if(!p->left) {p->left=pre;p->ltag=1;} if(pre&&!pre->right) {pre->right=p;pre->rtag=1;}abdcefg58線索二叉樹問題26.如何構(gòu)造一棵中序線索二叉樹？abd59

pre=p; crt-inthtree(p->right,pre); } };

在主程序中

pre=NULL; crt-inthtree(root,pre); pre->right=NULL;pre->rtag=1;問題27.如何在一棵中序線索二叉樹中尋找某結(jié)點p為根的子樹上的中序第一個結(jié)點？解析：沿結(jié)點p的左子樹鏈一直走下去，直到遇到其左指針為左線索的結(jié)點為止，該結(jié)點即所求。59 pre=p;60

ThreadNode*inFirst(ThreadNode*p){

ThreadNode*q=p; while(q&&!q->ltag)q=q->left; returnq; };問題28.如何在一棵中序線索二叉樹中尋找某結(jié)點p為根的子樹上的中序最后一個結(jié)點？解析：沿結(jié)點p的右子樹鏈一直走下去，直到遇到其右指針為右線索的結(jié)點為止，該結(jié)點即所求。 ThreadNode*inLast(ThreadNode*p){

ThreadNode*q=p; while(q&&!q->rtag)q=q->right;60 ThreadNode*inFirst(Thread61

returnq; };問題29.如何在一棵中序線索二叉樹中尋找某結(jié)點p的中序下的后繼？解析：若結(jié)點p有右線索，則其右線索所指結(jié)點即為其中序后繼；若無右線索，則其右子樹中中序第一個結(jié)點即為它的中序后繼。

ThreadNode*inNext(ThreadNode*p){

ThreadNode*q=p->right; if(q&&!p->rtag)q=inFirst(q); returnq; };abdcefg61 returnq;abdcefg62問題30.如何在一棵中序線索二叉樹中尋找某結(jié)點p的中序下的前驅(qū)？解析：鏡像情況。若結(jié)點p有左線索，則其左線索所指結(jié)點即為其中序前驅(qū)；若無左線索，則其左子樹中中序最后一個結(jié)點即為它的中序前驅(qū)。

ThreadNode*inPrior(ThreadNode*p){

ThreadNode*q=p->left; if(q&&!p->ltag)q=inLast(q); returnq; };abdcefg62問題30.如何在一棵中序線索二叉樹中尋找某結(jié)點p的中63問題31.如何在一棵中序線索二叉樹中尋找某結(jié)點p的前序下的后繼？解析：右圖二叉樹前序遍歷的結(jié)果是abdgcef。分析這個事例可知：a有左子女b，a的前序后繼為b；d無左子女但有右子女g，d 的前序后繼是g；g既無左子女又無右子女，g的前序后繼為c,c可從g沿右線索鏈到a，a的右子女即為g的前序后繼。 abdcefg63問題31.如何在一棵中序線索二叉樹中尋找某結(jié)點p的前序64

ThreadNode*preNext(ThreadNode*p){ ThreadNode*q; if(!p->ltag)q=p->left; elseif(!p->rtag)q=p->right; else{ q=p; while(q&&q->rtag)q=q->right; if(q)q=q->right; } returnq; };abdcefg64 ThreadNode*preNext(ThreadN65問題32.如何在一棵中序線索二叉樹中尋找某結(jié)點p的前序下的前驅(qū)？解析：右圖二叉樹前序遍歷的結(jié)果是abdgcef。為尋找p的前驅(qū)，需找p的雙親q，確定雙親原則:若p是q的左子女，則q是p

右子樹中序最后一個結(jié)點的右 線索；若p是q的右子女，則q是p

左子樹中序第一個結(jié)點的左線索。

ThreadNode*inParent(ThreadNode*p){ if(p){abdcefg65問題32.如何在一棵中序線索二叉樹中尋找某結(jié)點p的前序66

ThreadNode*q=inLast(p->right); if(q)returnq->right;

else{ q=inFirst(p->left); if(q)returnq->left;

} }

returnNULL;

}; 找到b的雙親a后，判斷:若b是a的左子女，則b的前序前驅(qū)是a；否則若c是a的右子女，則c的前序前驅(qū)是

abdcefg66 ThreadNode*q=inLas67a（a的左子樹空）或a的左子樹（非空）前序最后一個結(jié)點。 ThreadNode*prePrior(ThreadNode*p){ ThreadNode*q=inParent(p); if(p==q->left)returnq;//p是q的左子女 if(!q->left)returnq; //p是q的右子女

while(!q->ltag||!q->rtag){ while(!q->rtag)q=q->right; while(!q->ltag)q=q->left; }; returnq; };abdcefg67a（a的左子樹空）或abdcefg68問題33.如何構(gòu)造一棵前序線索二叉樹？解析：類似于構(gòu)造中序線索二叉樹，可通過前序遍歷，把二叉樹改造為前序線索二叉樹：

voidcrt-prethtree(ThreadNode*p, ThreadNode*&pre){ if(p){ if(!p->left) {p->left=pre;p->ltag=1;} if(pre&&!pre->right) {pre->right=p;pre->rtag=1;} pre=p; crt-prethtree(p->left,pre);abdcefgh68問題33.如何構(gòu)造一棵前序線索二叉樹？abdcefgh69

crt-prethtree(p->right,pre); } }; 在主程序中

pre=NULL; crt-prethtree(root,pre); pre->right=NULL;pre->rtag=1;問題34.如何在一棵前序線索二叉樹中尋找某結(jié)點p為根的子樹上的前序第一個結(jié)點？解析：以結(jié)點p為根的子樹上前序的第一個結(jié)點就是它自己。abdcefgh69 crt-prethtree(p->right70 ThreadNode*preFirst(ThreadNode*p){

returnp; };問題35.如何在一棵前序線索二叉樹 中尋找某結(jié)點p的前序最后一個結(jié)點？解析：若結(jié)點p有右子樹，則其前序最后一個結(jié)點一定是其右子樹上前序最后一個結(jié)點；若其右子樹為空，則其前序最后一個結(jié)點一定是其左子樹上前序最后一個結(jié)點；若其左、右子樹都為空，則其前序最后一個結(jié)點即為它自己。

ThreadNode*preLast(ThreadNode*p){abdcefgh70 ThreadNode*preFirst(Threa71

if(p) if(!p->rtag)returnpreLast(p->right); elseif(!p->ltag)returnpreLast(p->left); elsereturnp; };問題36.如何在一棵前序線索二叉樹中尋找某結(jié)點p的前序下的后繼？解析：若結(jié)點p有右線索，則其前序 后繼即為右線索所指結(jié)點；否則 若結(jié)點p有左子女，則前序后繼即 為其左子女指針?biāo)附Y(jié)點,否則為abdcefgh71 if(p)abdcefgh72 其右子女指針?biāo)附Y(jié)點。

ThreadNode*preNext(ThreadNode*p){

if(p) if(!p->ltag)returnp->left; elsereturnp->right; };問題37.如何在一棵前序線索二叉樹中尋找某結(jié)點p的前序下的前驅(qū)？解析：若結(jié)點p有左線索，則其前序下的前驅(qū)即其左線索所指結(jié)點；否則需要找到它的雙親q，若p是q的左子女，則其前序下的前驅(qū)即為q，否則到abdcefgh72 其右子女指針?biāo)附Y(jié)點。abdcefgh73

q的左子樹中尋找其前序下最后一個結(jié)點，它就是結(jié)點p前序下的前驅(qū)。

ThreadNode*prePrior(ThreadNode*p){

if(p) if(p->ltag)returnp->left; else{ ThreadNode*q=preParent(p); if(q->left==p)returnq; elsereturnpreLast(q->left); } };

如何找雙親留給大家自己考慮。abdcefgh73 q的左子樹中尋找其前序下最后一個結(jié)點，它就是結(jié)點p前序74樹與森林問題38.在一棵m叉樹，設(shè)根在第1層，并從0開始自上向下分層給各個結(jié)點編號。問

(1)第i層最多有多少結(jié)點？

(2)高度為h的m叉樹最多有多少結(jié)點？

(3)編號為k的結(jié)點的父結(jié)點編號是多少？

(4)編號為k的結(jié)點的第1個子結(jié)點編號是多少？ (5)編號為k的結(jié)點在第幾層？解析：(1)第i層最多有mi-1個結(jié)點。(2)高度為h的m叉樹最多有(mh-1)/(m-1)個結(jié)點。(3)當(dāng)k=0時結(jié)點k是根，沒有父結(jié)點；當(dāng)k>0時結(jié)點k74樹與森林問題38.在一棵m叉樹，設(shè)根在第1層，并75 的父結(jié)點是

(k-1)/m。(4)結(jié)點k的第1個子女是k*m+1。(5)設(shè)結(jié)點k在第i層，到第i層為止的m叉樹最多有(mi-1)/(m-1)個結(jié)點，第i層最后一個結(jié)點編號k=(mi-1)/(m-1)-1，由此可得層次號i=logm((k+1)*(m-1)+1)。問題39.使用樹的雙親表示，尋找某結(jié)點i的雙親、所有子女、兄弟的時間復(fù)雜性是多少？0123456789

10

11

1213141516171819201層2層3層75 的父結(jié)點是(k-1)/m。(4)結(jié)點k的第76解析：使用樹的雙親表示，尋找某結(jié)點i的雙親的時間復(fù)雜度為O(1)，而尋找其他要看結(jié)點存放的順序。如果所有結(jié)點按層次序存放，尋找所有兄弟的時間為O(1)，尋找所有子女的時間為O(n);如果所有結(jié)點按先根序存放，尋找所有子女和兄弟的時間都是O(n)，其中n是結(jié)點個數(shù)。問題40.樹的先根次序序列的特性是什么？解析：在樹的先根次序序列中，第一個元素一定是樹的根，如果樹的結(jié)點個數(shù)大于1，它后面緊跟的一定是第一棵子樹的根，…...。子樹又是樹，同樣滿足上述特性。76解析：使用樹的雙親表示，尋找某結(jié)點i的雙親的時間復(fù)雜77問題41.n個結(jié)點的樹有多少種？解析：可通過樹的二叉樹表示來估計。在樹的二叉樹表示中，根的右指針一定是空的，因此，估計有多少種形態(tài)看根的左子樹的n-1個結(jié)點能構(gòu)成多少種二叉樹。根據(jù)在二叉樹中的分析可知，它服從catalan函數(shù)，等于問題42.森林中樹T1、T2、T3的結(jié)點數(shù)為m1、m2、m3，在該森林的二叉樹表示中，根的左子樹和右子樹各有多少結(jié)點？二叉樹表示77問題41.n個結(jié)點的樹有多少種？二叉樹表示78解析：在森林的二叉樹表示中根是T1的根，其左子樹是T1的根的子樹森林，有m1-1個結(jié)點，其右子樹是除T1外其他樹T2、T3構(gòu)成的森林，有m2+m3個結(jié)點。問題43.在一個有n個結(jié)點的森林的二叉樹表示中，左指針為空的結(jié)點有m個，那么右指針為空的結(jié)點有多少個？解析：左指針為空的都是森林中各棵樹的葉結(jié)點，非葉結(jié)點有n-m個。每個非葉結(jié)點的子女-兄弟鏈都有一個右指針為空的結(jié)點，加上根結(jié)點的右指針為空，故右指針為空的結(jié)點有n-m+1個。78解析：在森林的二叉樹表示中根是T1的根，其左子樹是T1的79二叉排序樹問題44.一棵有n個結(jié)點的二叉排序樹有多少種不同形態(tài)？解析：二叉排序樹的中序排列一定，不同的前序序列得到不同的二叉排序樹，不同二叉排序樹的總數(shù)服從catalan函數(shù)問題45.若想把二叉排序樹上所有結(jié)點的數(shù)據(jù)從小到大排列，采用何種遍歷算法？從大到小排列，又采用何種算法？79二叉排序樹問題44.一棵有n個結(jié)點的二叉排序樹有多80解析：采用中序遍歷算法：若想得到從小到大排列的遍歷結(jié)果，采用LVR的方式，若想得到從大到小的遍歷結(jié)果，采用RVL的方式。問題46.每次插入一個新元素到二叉排序樹中應(yīng)插入到什么地方？樹的高度最大是多少？解析：在插入之前應(yīng)先調(diào)用查找算法從根開始查找插入位置，如果查找成功，說明樹中已有要插入的元素，新元素不插入；如果查找失敗，則把新結(jié)點插入到查找失敗的位置。注意，新結(jié)點將作為葉結(jié)點插入。二叉排序樹是向下增長的，最高是單支樹情形，若樹結(jié)點數(shù)為n，最大高度為n。80解析：采用中序遍歷算法：若想得到從小到大排列的遍歷結(jié)果，81問題47.衡量一棵二叉排序樹的查找性能要計算其查找成功的平均查找長度和查找不成功的平均查找長度，此時可借助的輔助結(jié)構(gòu)是什么？解析：擴充二叉樹（或稱判定樹）。內(nèi)結(jié)點代表二叉排序樹原有的數(shù)據(jù)，查找成功時查找指針停留在內(nèi)結(jié)點上；外結(jié)點代表二叉排序樹原來沒有的數(shù)據(jù)，查找失敗時查找指針走到外結(jié)點。kicspyfkicspyfa～bd～eg～hjl～0q～rt～xz81問題47.衡量一棵二叉排序樹的查找性能要計算其查找成功82問題48.對下圖所示二叉排序樹，查找成功的平均查找長度和查找不成功的平均查找長度是多少？解析：查找成功的平均查找長度為 查找不成功的平均查找長度為 擴充二叉樹的 內(nèi)結(jié)點的度為

2,外結(jié)點的度 為0。n0=n2+1kicspyfkicspyf82問題48.對下圖所示二叉排序樹，查找成功的平均查找長度83問題49.對一棵二叉排序樹做中序遍歷，再基于得到的中序序列重新構(gòu)造二叉排序樹，這兩棵二叉排序樹是否相同？解析：一般不相同。對一棵二叉排序樹做中序遍歷得到一個有序的序列，再順序用序列中的數(shù)據(jù)構(gòu)造二叉排序樹，得到一棵單支樹，每個結(jié)點的左子樹均為空。khspykhspy中序遍歷h,k,p,s,y順序插入83問題49.對一棵二叉排序樹做中序遍歷，再基于得到的中序84平衡二叉樹問題50.二叉樹、二叉排序樹和平衡二叉樹之間是何關(guān)系？解析：二叉排序樹是二叉樹的特殊情形，平衡二叉樹又是二叉排序樹的特殊情形。平衡二叉樹是高度平衡的二叉排序樹。問題51.有n個結(jié)點的平衡二叉樹的最小高度和最大高度是多少？解析：讓平衡二叉樹每層結(jié)點達(dá)到最大數(shù)目，就得到它的最小高度：n≤2h-1

h≥

log2(n+1)

；若讓根的左右子樹的結(jié)點個數(shù)達(dá)到最少，可得84平衡二叉樹問題50.二叉樹、二叉排序樹和平衡二叉樹之間85 最大高度。設(shè)高度為h的平衡二叉樹的最少結(jié)點數(shù)為Nh，則有N0=0,N1=1,Nh=Nh-1+Nh-2+1,h>1。由此推出 N2=2,N3=4,N4=7,N5=12,… 對照斐波那契數(shù)F0=0,F1=1,F2=1,F3=2, F4=3,F5=5,F6=8,F7=13,…

有Nh=Fh+2-1。

另外，斐波那契數(shù)滿足漸進(jìn)公式： 由此可得 85 最大高度。設(shè)高度為h的平衡二叉樹的最少結(jié)點數(shù)為Nh，則86

兩邊取對數(shù)

由換底公式

log

X=log2X/log2

及

log2

=0.694

和

可得

h

1.44*log2(Nh+1)–0.33<1.44*log2(n+1)

此即平衡二叉樹的最大高度。問題52.在高度為h的平衡二叉樹中離根最近的葉結(jié)點在第幾層？解析：計算平衡二叉樹離根最近的葉結(jié)點所在層次的方法與推導(dǎo)高度為h的平衡二叉樹最少結(jié)點86 兩邊取對數(shù)87

個數(shù)的過程類似。設(shè)高度為h的平衡二叉樹的離根最近的葉結(jié)點所在層次為Lh，則有

L1=1,L2=2, Lh=min{Lh-1,Lh-2}+1=Lh-2+1,h>2

直接計算Lh=h/2+1.L1=1L2=2L3=2L4=3L5=387 個數(shù)的過程類似。設(shè)高度為h的平衡二叉樹的離根最近的88問題53.Huffman樹是一棵擴充二叉樹，外結(jié)點（葉結(jié)點）有n個，那么總共有多少結(jié)點？解析：總共有2n-1個結(jié)點，因它只有度為0和度為2的結(jié)點，由n0=n2+1，當(dāng)n0=n時，n0+n2=n+n-1=2n-1。問題54.在構(gòu)造Huffman樹的過程中，每次從森林中選根的關(guān)鍵字值最小和次小的兩棵樹合并。在合并時是最小的做左子樹還是次小的做左子樹？解析：都可以?？蓞⒖妓惴ǖ膶崿F(xiàn)代碼，但手工構(gòu)造時沒有限制。Huffman樹88問題53.Huffman樹是一棵擴充二叉樹，外結(jié)點（葉89問題55.用Huffman樹構(gòu)造最佳判定樹，內(nèi)、外結(jié)點各起什么作用？帶權(quán)路徑長度表示什么意思？解析：內(nèi)結(jié)點是比較過程中的中間結(jié)果，外結(jié)點是比較的最終結(jié)果。帶權(quán)路徑長度表明可能的比較次數(shù)，或總比較次數(shù)的期望值。問題56.用Huffman樹構(gòu)造不等長的Huffman編碼，一段報文的總（二進(jìn)制）編碼數(shù)用什么衡量？解析：首先根據(jù)報文中各字符出現(xiàn)的頻度和每個字符的Huffman編碼，計算帶權(quán)路徑長度，它就是該報文的總（二進(jìn)制）編碼數(shù)，也叫做總編碼長度。89問題55.用Huffman樹構(gòu)造最佳判定樹，內(nèi)、外結(jié)點90問題57.并查集（mfsetorUFSetsordisjoint）主要用在什么地方？解析：一是判斷和構(gòu)造等價類，二是判斷和構(gòu)造圖的連通分量。問題58.并查集有哪幾種操作？解析：并查集以雙親表示為其存儲結(jié)構(gòu)，操作有:(1)Find(S,x),尋找x所在子樹的根；(2)Union(S,s1,s2),合并以s1和s2為根的子樹（s1并入s2,還是s2并入s1,根據(jù)算法的具體實現(xiàn)而定）；(3)UFSets(S),把集合S初始化為一個森林。并查集90問題57.并查集（mfsetorUFSetsor91問題59.堆作為優(yōu)先級隊列的實現(xiàn)，插入和刪除在堆得什么位置實施？解析：插入在隊尾，即堆的最后元素的后面，刪除在隊頭，即堆頂（最前面的位置）。問題60.堆用數(shù)組作為其存儲，那么它是線性結(jié)構(gòu)還是非線性結(jié)構(gòu)？解析：即使使用數(shù)組作為存儲結(jié)構(gòu)，它也是非線性結(jié)構(gòu)。邏輯結(jié)構(gòu)才區(qū)分線性還是非線性。因為堆是用完全二叉樹組織，可以利用二叉樹性質(zhì)很容易地找某結(jié)點的雙親、子女和兄弟。堆（heap）91問題59.堆作為優(yōu)先級隊列的實現(xiàn)，插入和刪除在堆得什么92問題61.若想把數(shù)組中的100個元素調(diào)整為小根堆（或大根堆）需做多少次關(guān)鍵字比較？解析：堆按完全二叉樹組織，當(dāng)n=100為偶數(shù)時，堆有1個度為1的結(jié)點，50個葉結(jié)點，49個度為2的結(jié)點，堆的高度為h=log2(100+1)=7。 上面5層是滿的，有25-1=31個結(jié)點，第6層度為2的結(jié)點有49-31=18個結(jié)點，則形成初始堆的最大關(guān)鍵字比較次數(shù)為：第6層：18*2*1+1*1*1=37

；第5層：10*2*2+6*2*1=52；第4層：5*2*3+3*2*2=42；18/2+124-1023-592問題61.若想把數(shù)組中的100個元素調(diào)整為小根堆93第3層：22*2*4=32；第2層：21*2*5=20；第1層：20*2*6=12。 總比較次數(shù)12+20+32+42+52+37=195次，時間復(fù)雜度O(n)。如果借助公式

這是最大估計。93第3層：22*2*4=32；94已知二叉樹以二叉鏈表為存儲結(jié)構(gòu)，其結(jié)點結(jié)構(gòu)定義如下：TypedefstructBiTNode{ElemTypedata;StructBiTNode*lchile,*rchild;Intleaf;}BiTNode,*BiTree;其中l(wèi)eaf域表示該結(jié)點的子孫(含孩子結(jié)點)中所含的葉子結(jié)點的個數(shù)。開始時，leaf域值均為0,T為指向某二叉樹根結(jié)點的指針。請編寫一個算法，填寫該二叉樹中每個結(jié)點的leaf域。94已知二叉樹以二叉鏈表為存儲結(jié)構(gòu)，其結(jié)點結(jié)構(gòu)95給定一組字母(A,B,C,D,E,F)，其出現(xiàn)的頻率分別為（6，8，11，3，20，12），按權(quán)值（6，8，11，3，20，12）設(shè)計相應(yīng)的哈夫曼樹。(2)寫出每一個字母的哈夫曼編碼。(3)求哈夫曼樹的帶權(quán)路徑長度。95給定一組字母(A,B,C,D,E,F)，其出現(xiàn)的頻率分別96已知一棵哈夫曼樹的順序存儲結(jié)構(gòu)如表1所示。①畫出哈夫曼樹的邏輯結(jié)構(gòu)樹型表示；②求權(quán)值為5、7、3、9、6所對應(yīng)字符的哈夫曼編碼；③求哈夫曼樹的帶權(quán)路徑長度WPL。96已知一棵哈夫曼樹的順序存儲結(jié)構(gòu)如表1所示。97假定一個線性表為(38,52,25,74,68,16,30,54,90,72)，畫出按線性表中元素的次序生成的一棵二叉排序樹，求出其平均查找長度。97假定一個線性表為(38,52,25,74,68,16,398已知某二叉樹的中序、后序序列分別為DBAFCE、ABDCEF，則該二叉樹的層序序列為

。

A．BCDEAFB．DBACEFC．DABECFD．FDEBCA98已知某二叉樹的中序、后序序列分別為DBAFCE、99由元素序列{16,3,7,11,9,26,18,14,15}構(gòu)造平衡二叉樹，則該平衡二叉樹的根為

。

A．16B．26C．15D．1199由元素序列{16,3,7,11,9,26,18,14,1100二叉排序樹結(jié)點刪除算法二叉排序樹結(jié)點刪除算法思想：設(shè)被刪結(jié)點的指針為p，其雙親結(jié)點的指針為f，分以下三種情況處理：⑴p指示的是葉子結(jié)點(即p->lchild=NULL且p->rchild=NULL)當(dāng)*p是*f的左孩子時(即f->lchild=p)，置f->lchild=NULL；當(dāng)*p是*f的右孩子時(即f->rchild=p)，置f->rchild=NULL；⑵p指示的結(jié)點是單分支結(jié)點(即p->rchild=NULL或p->lchild=NULL)當(dāng)*p是*f的左孩子時(即f->lchild=p)：若*p結(jié)點只有左子樹，置f->lchild=p->lchild；若*p結(jié)點只有右子樹，置f->rchild=p->rchild。當(dāng)*p是*f的右孩子時(即f->rchild=p)：若*p結(jié)點只有左子樹，置f->rchild=p->lchild；若*p結(jié)點只有右子樹，置f->rchild=p->rchild。100二叉排序樹結(jié)點刪除算法101⑶p指示的結(jié)點是雙分支結(jié)點(即p->lchild≠NULL且p->rchild≠NULL)找到*p結(jié)點的中序前驅(qū)結(jié)點*q，即*p的左子樹的最右下結(jié)點，*q必為單分支結(jié)點或葉結(jié)點(其右指針為空)；把*q的值賦給*p結(jié)點的值域，將刪除*p結(jié)點的操作轉(zhuǎn)換為刪除*q結(jié)點的操作。在以下程序的空白處填上適當(dāng)?shù)膬?nèi)容，實現(xiàn)以上二叉排序樹結(jié)點刪除算法。101⑶p指示的結(jié)點是雙分支結(jié)點102#defineEQ(a,b)((a)=(b))#defineLT(a,b)((a)<(b))//二叉樹的二叉鏈表存儲表示typedefstructBiTNode{TElemTypedata;BiTNode*lchild,*rchild;//左右孩子指針}BiTNode,*BiTree;voidDelete(BiTree&p){//從二叉排序樹中刪除結(jié)點p,并重接它的左或右子樹

BiTreeq,s;if(!p->rchild){q=p;p=p->lchild;free(q);}//右子樹空,重接左子樹

elseif(!p->lchild){q=p;p=p->rchild;free(q);}//左子樹空,重接右子樹

else//左右子樹均不空

{q=p;s=p->lchild;//轉(zhuǎn)左

while(s->rchild){q=s;____(1)___;}//然后向右到盡頭，s指向被刪結(jié)點的"前驅(qū)"p->data=s->data;//s的數(shù)據(jù)域代替p的數(shù)據(jù)域

if(____(2)____)q->rchild=s->lchild;//重接*q的右子樹

elseq->lchild=s->lchild;//重接*q的左子樹

free(s);}//else}102#defineEQ(a,b)((a)=(b))103StatusDeleteBST(BiTree&T,KeyTypekey){//若二叉排序樹T中存在關(guān)鍵字等于key的數(shù)據(jù)元素時,//則刪除該數(shù)據(jù)元素結(jié)點并返回TRUE,否則返回FALSE.if(!T)//不存在關(guān)鍵字等于key的數(shù)據(jù)元素

{cout<<"表中無此數(shù)據(jù)元素!\n";returnFALSE;}Else{ifEQ(key,T->data.key)Delete(T);//找到關(guān)鍵字等于key的數(shù)據(jù)元素

elseifLT(key,T->data.key)DeleteBST(_____(3)_____,key);elseDeleteBST(T->rchild,key);returnTRUE;}//else}103StatusDe