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

1、【考查目標(biāo)】 1. 理解數(shù)據(jù)結(jié)構(gòu)的基本概念；掌握數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其差異，以及各種基本操作的實(shí)現(xiàn)。 2. 掌握基本的數(shù)據(jù)處理原理和方法的基礎(chǔ)上，能夠?qū)λ惴ㄟM(jìn)行設(shè)計(jì)與分析。 3. 能夠選擇合適的數(shù)據(jù)結(jié)構(gòu)和方法進(jìn)行問題求解。 一、線性表大綱要求：（一） 線性表的定義和基本操作 （二） 線性表的實(shí)現(xiàn) 1. 順序存儲結(jié)構(gòu) 2. 鏈?zhǔn)酱鎯Y(jié)構(gòu) 3. 線性表的應(yīng)用 知識點(diǎn)：1 深刻理解數(shù)據(jù)結(jié)構(gòu)的概念，掌握數(shù)據(jù)結(jié)構(gòu)的“三要素”：邏輯結(jié)構(gòu)、物理（存儲）結(jié)構(gòu)及在這種結(jié)構(gòu)上所定義的操作“運(yùn)算”。2 時(shí)間復(fù)雜度和空間復(fù)雜度的定義，常用計(jì)算語句頻度來估算算法的時(shí)間復(fù)雜度。以下六種計(jì)算算法時(shí)間的多項(xiàng)式是最常用的

2、。其關(guān)系為：O(1)O(logn)O(n)O(nlogn) O(n2)O(n3)指數(shù)時(shí)間的關(guān)系為： O(2n)O(n!)link=plink；plink=sBqlink=s；slink=pCplink=slink；slink=pDplink=s；slink=q10. 在一個(gè)長度為n的順序表的表尾插入一個(gè)新元素的漸進(jìn)時(shí)間復(fù)雜度為（ B ）。AO（n） BO（1） CO（n2） DO（log2n）11. 表長為n的順序存儲的線性表，當(dāng)在任何位置上插入一個(gè)元素的概率相等時(shí)，插入一個(gè)元素所需移動(dòng)元素的平均個(gè)數(shù)為（ B ）An B. n/2C. (n-1)/2 D. (n+1)/212. 循環(huán)鏈表的主要

3、優(yōu)點(diǎn)是（ D ）A不再需要頭指針了。B已知某個(gè)結(jié)點(diǎn)的位置后，能很容易找到它的直接前驅(qū)結(jié)點(diǎn)。C在進(jìn)行刪除操作后，能保證鏈表不斷開。D從表中任一結(jié)點(diǎn)出發(fā)都能遍歷整個(gè)鏈表。（二）應(yīng)用題1、按增長率由小至大排列以下7個(gè)函數(shù)。答：2、數(shù)據(jù)的存儲結(jié)構(gòu)由哪四種基本的存儲方法實(shí)現(xiàn)，并做以簡要說明？答：四種表示方法（1）順序存儲方式。數(shù)據(jù)元素順序存放，每個(gè)存儲結(jié)點(diǎn)只含一個(gè)元素。存儲位置反映數(shù)據(jù)元素間的邏輯關(guān)系。存儲密度大，但有些操作（如插入、刪除）效率較差。（2）鏈?zhǔn)酱鎯Ψ绞?。每個(gè)存儲結(jié)點(diǎn)除包含數(shù)據(jù)元素信息外還包含一組（至少一個(gè)）指針。指針反映數(shù)據(jù)元素間的邏輯關(guān)系。這種方式不要求存儲空間連續(xù)，便于動(dòng)態(tài)操作（如插

4、入、刪除等），但存儲空間開銷大（用于指針），另外不能折半查找等。（3）索引存儲方式。除數(shù)據(jù)元素存儲在一地址連續(xù)的內(nèi)存空間外，尚需建立一個(gè)索引表，索引表中索引指示存儲結(jié)點(diǎn)的存儲位置（下標(biāo)）或存儲區(qū)間端點(diǎn)（下標(biāo)），兼有靜態(tài)和動(dòng)態(tài)特性。（4）散列存儲方式。通過散列函數(shù)和解決沖突的方法，將關(guān)鍵字散列在連續(xù)的有限的地址空間內(nèi)，并將散列函數(shù)的值解釋成關(guān)鍵字所在元素的存儲地址，這種存儲方式稱為散列存儲。其特點(diǎn)是存取速度快，只能按關(guān)鍵字隨機(jī)存取，不能順序存取，也不能折半存取。3. 線性表有兩種存儲結(jié)構(gòu)：一是順序表，二是鏈表。試問：（1）如果有 n個(gè)線性表同時(shí)并存，并且在處理過程中各表的長度會動(dòng)態(tài)變化，線性表的

5、總數(shù)也會自動(dòng)地改變。在此情況下，應(yīng)選用哪種存儲結(jié)構(gòu)？ 為什么？（2）若線性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除，但要求以最快的速度存取線性表中的元素，那么應(yīng)采用哪種存儲結(jié)構(gòu)？為什么？答：（1）選鏈?zhǔn)酱鎯Y(jié)構(gòu)。它可動(dòng)態(tài)申請內(nèi)存空間，不受表長度（即表中元素個(gè)數(shù)）的影響，插入、刪除時(shí)間復(fù)雜度為O（1）。（2）選順序存儲結(jié)構(gòu)。順序表可以隨機(jī)存取，時(shí)間復(fù)雜度為O（1）。（三）算法設(shè)計(jì)題1設(shè)計(jì)算法，求帶表頭的單循環(huán)鏈表的表長。解：int length(Linklist L) int I; listnode *p; I=0; P=L; while (p-next!=L) p=p-next; I+; ret

6、urn I;2.已知單鏈表L，寫一算法，刪除其重復(fù)結(jié)點(diǎn)。算法思路：用指針p指向第一個(gè)數(shù)據(jù)結(jié)點(diǎn)，從它的后繼結(jié)點(diǎn)開始到表的結(jié)束，找與其值相同的結(jié)點(diǎn)并刪除之；p指向下一個(gè)；依此類推，p指向最后結(jié)點(diǎn)時(shí)算法結(jié)束。算法如下：解：void pur_LinkList(LinkList H) LNode *p,*q,*r; p=H-next; /*p指向第一個(gè)結(jié)點(diǎn)*/ if(p=NULL) return; while (p-next) q=p; while (q-next) /* 從*p的后繼開始找重復(fù)結(jié)點(diǎn)*/ if (q-next-data=p-data) r=q-next; /*找到重復(fù)結(jié)點(diǎn)，用r指向，刪除

7、*r */ q-next=r-next; free(r); /*if*/ else q=q-next; /*while(q-next)*/ p=p-next; /*p指向下一個(gè)，繼續(xù)*/ /*while(p-next)*/該算法的時(shí)間性能為O(n2)。3.已知指針la和lb分別指向兩個(gè)無頭結(jié)點(diǎn)的單鏈表中的首結(jié)點(diǎn)。請編寫函數(shù)完成從表la中刪除自第i個(gè)元素開始的共len個(gè)元素并將它們插入到表lb中第j個(gè)元素之前，若lb中只有j-1個(gè)元素，則插在表尾。函數(shù)原型如下：int DeleteAndInsertSub(LinkList &la,LinkList &lb,int i,int j,int len

8、)；答：int DeleteAndInsertSub(LinkList &la,LinkList &lb,int i,int j,int len)int k; LinkList p,q,prev,s;if(i0|j0|len0)return -1;p=la;k=1;prev=NULL;while(p&knext;k+;if(!p)return -1;q=p;k=1;while(q&knext;k+;if(!q)return -1;if(!prev)la=q-next;elseprev-next=q-next;if(j=1)q-next=lb;lb=q;elses=lb;k=1;while(s&

9、knext;k+;if(!s)return -1;q-next=s-next;s-next=p;return 1;4寫一算法，將一帶有頭結(jié)點(diǎn)的單鏈表就地逆置，即要求逆置在原鏈表上進(jìn)行，不允許重新構(gòu)造新鏈表。圖 單鏈表的倒置254525187629L297625184525L(a)(b)函數(shù)原型如下：void LinkList_reverse(LinkList &L)；答：void LinkList_reverse(LinkList &L)LinkList p,q,s;p=L-next;q=p-next;s=q-next;p-next=NULL;while(s-next)q-next=p;p=q

10、;q=s;s=s-next;q-next=p;s-next=q;L-next=s;5寫一算法，將帶有頭結(jié)點(diǎn)的非空單鏈表中數(shù)據(jù)域值最小的那個(gè)結(jié)點(diǎn)移到鏈表的最前面。要求：不得額外申請新的鏈結(jié)點(diǎn)。函數(shù)原型如下：void delinsert(LinkList &L)；答：void delinsert(LinkList &L)p=L-next;/p是鏈表的工作指針pre=L;/pre指向鏈表中數(shù)據(jù)域最小值結(jié)點(diǎn)的前驅(qū)q=p;/q指向數(shù)據(jù)域最小值結(jié)點(diǎn)，初始假定是第一結(jié)點(diǎn)while(p-next!=NULL)if(p-next-datadata)/找到新的最小值結(jié)點(diǎn)pre=p;q=p-next; p=p-ne

11、xt;if(q!=L-next)/若最小值是第一元素結(jié)點(diǎn)，則不需再操作pre-next=q-next;/將最小值結(jié)點(diǎn)從鏈表上摘下q-next=L-next;/將q結(jié)點(diǎn)插到鏈表最前面L-next=q;6編寫一個(gè)算法來交換單鏈表中指針P所指結(jié)點(diǎn)與其后繼結(jié)點(diǎn)，HEAD是該鏈表的頭指針，P指向該鏈表中某一結(jié)點(diǎn)。答：單鏈表中查找任何結(jié)點(diǎn)，都必須從頭指針開始。本題要求將指針p所指結(jié)點(diǎn)與其后繼結(jié)點(diǎn)交換，這不僅要求知道p結(jié)點(diǎn)，還應(yīng)知道p的前驅(qū)結(jié)點(diǎn)。這樣才能在p與其后繼結(jié)點(diǎn)交換后，由原p結(jié)點(diǎn)的前驅(qū)來指向原p結(jié)點(diǎn)的后繼結(jié)點(diǎn)。LinkedList Exchange（LinkedList HEAD，p）HEAD是單鏈

12、表頭結(jié)點(diǎn)的指針，p是鏈表中的一個(gè)結(jié)點(diǎn)。本算法將p所指結(jié)點(diǎn)與其后繼結(jié)點(diǎn)交換。q=head-next； q是工作指針，指向鏈表中當(dāng)前待處理結(jié)點(diǎn)。pre=head； pre是前驅(qū)結(jié)點(diǎn)指針，指向q的前驅(qū)。while（q!=null & q!=p）pre=q；q=q-next； 未找到p結(jié)點(diǎn)，后移指針。if（p-next=null）printf（“p無后繼結(jié)點(diǎn)n”）; p是鏈表中最后一個(gè)結(jié)點(diǎn)，無后繼。Else處理p和后繼結(jié)點(diǎn)交換 q=p-next； 暫存p的后繼。 pre-next=q； p前驅(qū)結(jié)點(diǎn)的后繼指向p的后繼。 p-next=q-next；p的后繼指向原p后繼的后繼。 q-next=p ；原p后

13、繼的后繼指針指向p。 算法結(jié)束。7已知線性鏈表第一個(gè)鏈結(jié)點(diǎn)指針為list，請寫一算法，將該鏈表分解為兩個(gè)帶有頭結(jié)點(diǎn)的循環(huán)鏈表，并將兩個(gè)循環(huán)鏈表的長度分別存放在各自頭結(jié)點(diǎn)的數(shù)據(jù)域中。其中,線性表中序號為偶數(shù)的元素分解到第一個(gè)循環(huán)鏈表中,序號為奇數(shù)的元素分解到第二個(gè)循環(huán)鏈表中。答：算法如下：voidsplit(ListNode *List, ListNode *&list1, ListNode *&list2)list1=(ListNode *)malloc(sizeof(ListNode )；list2=(ListNode *)malloc(sizeof(ListNode )；p=list;；q

14、=list1；r=list2；len1=0；len2=0；mark=1；while (p!=null)if(mark=1)q-next=p;q=q-next;len1+;mark=2;elser-next=p;r=r-next;len2+;mark=1;list1-data=len1;list2-data=len2;q-next=list1;r-next=list2;8. 設(shè)A和B是兩個(gè)單鏈表，其表中元素遞增有序。試寫一算法將A和B歸并成一個(gè)按元素值遞減有序的單鏈表C，并要求輔助空間為O(1)。答：Linklist merge(Linklist A,Linklist B)Linklist C;

15、Listnode *p;C=null;while (A&B) if(A-datadata) p=A-next;A-next=C;C=A;A=p; else p=B-next;B-next=C;C=B;B=p; if (A)while(A) p=A-next;A-next=C;C=A;A=p; else while(B) p=B-next;B-next=C;C=B;B=p;return C;二、棧、隊(duì)列和數(shù)組大綱要求：（一） 棧和隊(duì)列的基本概念 （二） 棧和隊(duì)列的順序存儲結(jié)構(gòu) （三） 棧和隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu) （四） 棧和隊(duì)列的應(yīng)用 （五） 特殊矩陣的壓縮存儲 知識點(diǎn)：1 棧、隊(duì)列的定義及其相關(guān)數(shù)

16、據(jù)結(jié)構(gòu)的概念，包括：順序棧、鏈棧、循環(huán)隊(duì)列、鏈隊(duì)列等。棧與隊(duì)列存取數(shù)據(jù)（請注意包括：存和取兩部分）的特點(diǎn)。2 掌握順序棧和鏈棧上的進(jìn)棧和退棧的算法，并弄清?？蘸蜅M的條件。注意因棧在一端操作，故通常鏈棧不設(shè)頭結(jié)點(diǎn)。3 如何將中綴表達(dá)式轉(zhuǎn)換成前綴、后綴表達(dá)式，了解對兩種表達(dá)式求值的方法。4 棧與遞歸的關(guān)系。用遞歸解決的幾類問題：問題的定義是遞歸的，數(shù)據(jù)結(jié)構(gòu)是遞歸的，以及問題的解法是遞歸的。掌握典型問題的算法以及將遞歸算法轉(zhuǎn)換為非遞歸算法，如n!階乘問題，fib數(shù)列問題，hanoi問題。了解在數(shù)值表達(dá)式的求解、括號的配對等問題中應(yīng)用棧的工作原理。5 掌握在鏈隊(duì)列上實(shí)現(xiàn)入隊(duì)和出隊(duì)的算法。注意對僅剩一

17、個(gè)元素的鏈隊(duì)列刪除元素時(shí)的處理（令隊(duì)尾指針指向隊(duì)頭）。還需特別注意僅設(shè)尾指針的循環(huán)鏈隊(duì)列的各種操作的實(shí)現(xiàn)。6 循環(huán)隊(duì)列隊(duì)空及隊(duì)滿的條件。隊(duì)空定義為隊(duì)頭指針等于隊(duì)尾指針，隊(duì)滿則可用犧牲一個(gè)單元或是設(shè)標(biāo)記的方法，這里特別注意取模運(yùn)算。掌握循環(huán)隊(duì)列中入隊(duì)與出隊(duì)算法。7 在后續(xù)章節(jié)中多處有棧和隊(duì)列的應(yīng)用，如二叉樹遍歷的遞歸和非遞歸算法、圖的深度優(yōu)先遍歷等都用到棧，而樹的層次遍歷、圖的廣度優(yōu)先遍歷等則用到隊(duì)列。這些方面的應(yīng)用應(yīng)重點(diǎn)掌握。8 數(shù)組在機(jī)器（內(nèi)存）級上采用順序存儲結(jié)構(gòu)。掌握數(shù)組（主要是二維）在以行序?yàn)橹骱土行驗(yàn)橹鞯拇鎯χ械牡刂酚?jì)算方法。9 特殊矩陣（對稱矩陣、對角矩陣、三角矩陣）在壓縮存儲是的

18、下標(biāo)變換公式。練習(xí)題：（一）選擇題：1. 一個(gè)棧的輸入序列為1 2 3 4，則（D）不可能是其出棧序列。A. 1 2 4 3B. 2 1 3 4C. 1 4 3 2D. 4 3 1 22. 一個(gè)遞歸算法必須包括（ B ）。A. 遞歸部分 B. 終止條件和遞歸部分 C. 迭代部分 D.終止條件和迭代部分3. 一個(gè)遞歸的定義可以用遞歸過程求解，也可以用非遞歸過程求解，但單從運(yùn)行時(shí)間來看，通常遞歸過程比非遞歸過程（B）。A較快B較慢 C相同 D以上答案都不對4. 棧和隊(duì)列都是（C）A順序存儲的線性表B鏈?zhǔn)酱鎯Φ木€性表C限制存儲的線性表D限制存儲的非線性結(jié)構(gòu)5. 二維數(shù)組N的元素是4個(gè)字符（每個(gè)字符占

19、一個(gè)存儲單元）組成的串，行下標(biāo)i的范圍從0到4，列下標(biāo)j的范圍從0到5，N按行存儲時(shí)元素N35的起始地址與N按列存儲時(shí)元素（B）的起始地址相同。A. N24 B. N34C. N35 D. N446. 設(shè)有數(shù)組Ai,j，數(shù)組的每個(gè)元素長度為3字節(jié)，i的值為1到8，j的值為1到10，數(shù)組從內(nèi)存首地址BA開始順序存放，當(dāng)以列為主序存放時(shí)，元素A5,8的存儲首地址是（B）A. BA+141 B. BA+180C. BA+222 D. BA+2257. 遞歸過程或函數(shù)調(diào)用時(shí)，處理參數(shù)及返回地址，要用一種稱為（ C ）的數(shù)據(jù)結(jié)構(gòu)。A隊(duì)列 B多維數(shù)組 C棧 D. 線性表8. 對于單鏈表形式的隊(duì)列，隊(duì)空的條

20、件是（A ）AFRnilBFRCFnil且RnilDRF19. 若循環(huán)隊(duì)列以數(shù)組Q0.m-1作為其存儲結(jié)構(gòu)，變量rear表示循環(huán)隊(duì)列中的隊(duì)尾元素的實(shí)際位置，其移動(dòng)按 rear=(rear+1) Mod m 進(jìn)行，變量length表示當(dāng)前循環(huán)隊(duì)列中的元素個(gè)數(shù)，則循環(huán)隊(duì)列的隊(duì)首元素的實(shí)際位置是（ C ）Arear-lengthB(rear-length+m) Mod mC(1+rear+m-length) Mod mDM-length（二）應(yīng)用題1、（10分）假設(shè)一個(gè)準(zhǔn)對角矩陣按以下方式存儲于一維數(shù)組B4m中：01234k4m24m1.寫出由一對下標(biāo)（i，j）表示的k的轉(zhuǎn)換公式。答：i為奇數(shù)時(shí) k

21、=i+j-2i為偶數(shù)時(shí) k=i+j-1合并后可寫成 k=i+j-(i%2)-1 或 k=2(i/2)+j-12、特殊矩陣和稀疏矩陣哪一種壓縮存儲后失去隨機(jī)存取的功能？為什么？答：特殊矩陣指值相同的元素或零元素在矩陣中的分布有一定規(guī)律，因此可以對非零元素分配單元（對值相同元素只分配一個(gè)單元），將非零元素存儲在向量中，元素的下標(biāo)i和j和該元素在向量中的下標(biāo)有一定規(guī)律，可以用簡單公式表示，仍具有隨機(jī)存取功能。而稀疏矩陣是指非零元素和矩陣容量相比很小（tm*n），且分布沒有規(guī)律。用十字鏈表作存儲結(jié)構(gòu)自然失去了隨機(jī)存取的功能。即使用三元組表的順序存儲結(jié)構(gòu)，存取下標(biāo)為i和j的元素時(shí)，要掃描三元組表，下標(biāo)不

22、同的元素，存取時(shí)間也不同，最好情況下存取時(shí)間為O(1)，最差情況下是O(n)，因此也失去了隨機(jī)存取的功能。3、有人說，采用循環(huán)鏈表作為存儲結(jié)構(gòu)的隊(duì)列就是循環(huán)隊(duì)列，你認(rèn)為這種說法對嗎？說明你的理由。答：這種說法是錯(cuò)誤的。隊(duì)列（包括循環(huán)隊(duì)列）是一個(gè)邏輯概念，而鏈表是一個(gè)存儲概念，一個(gè)隊(duì)列是否是循環(huán)隊(duì)列。不取決于它將采用何種存儲結(jié)構(gòu)。根據(jù)實(shí)際的需要，循環(huán)隊(duì)列可以采用順序存儲結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，包括采用循環(huán)鏈表作為存儲結(jié)構(gòu)。4、指出下列程序段的功能是什么？ (1) void demo1(seqstack *s) int I;arr64;n=0; while (!stackempty(s) a

23、rrn+=pop(s); for(I=0;n;I+) push(s,arrI); (2) void demo2(seqstack *s,int m) seqstack t; int i; initstack(t);while(! Stackempty(s) if(I=pop(s)!=m) push(t,I);while(! Stackempty(t) i=pop(t); push(s,I);（三）算法設(shè)計(jì)題1 試?yán)醚h(huán)隊(duì)列編寫求k階斐波那契序列中前n+1項(xiàng)（）的算法，要求滿足且，其中max為某個(gè)約定的常數(shù)。循環(huán)隊(duì)列的容量為k，因此，在算法執(zhí)行結(jié)束時(shí)，留在循環(huán)隊(duì)列中的元素應(yīng)是所求k階斐波那契序

24、列中的最后k項(xiàng)。答：void GetFib(int k,int n)InitQueue(Q);for(i=0;kk-1;i+)Q.basei=0;Q.basek-1=1;for(i=0;ik;i+)printf(“%d”,Q.basei);for(i=k;i=n;i+)m=i%k;sum=0;for(j=0;jk;j+)sum+=Q.base(m+j)%k;Q.basem=sum;printf(“%d”,sum);2. 已知num為無符號十進(jìn)制整數(shù)，請寫一非遞歸算法，該算法輸出num對應(yīng)的r進(jìn)制的各位數(shù)字。要求算法中用到的棧采用線性鏈表存儲結(jié)構(gòu)（1r0) n=num%r; s=(link *)

25、malloc(sizeof(link); s-data=n; s-next=head;head=s; num=num/r; printf(“輸出r進(jìn)制的各位數(shù)字：”)； s=head;while (s!=NULL) printf(“%d”,s-data); s=s-next; 三、樹與二叉樹大綱要求：（一） 樹的概念 （二） 二叉樹 1. 二叉樹的定義及其主要特征 2. 二叉樹的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu) 3. 二叉樹的遍歷 4. 線索二叉樹的基本概念和構(gòu)造 5. 二叉排序樹 6. 平衡二叉樹 （三） 樹、森林 1. 樹的存儲結(jié)構(gòu) 2. 森林與二叉樹的轉(zhuǎn)換 3. 樹和森林的遍歷 （四） 樹的應(yīng)

26、用 1. 等價(jià)類問題 2. 哈夫曼（Huffman）樹和哈夫曼編碼 知識點(diǎn)：1. 二叉樹的概念、性質(zhì)（1）掌握樹和二叉樹的定義。（2）理解二叉樹與普通雙分支樹的區(qū)別。二叉樹是一種特殊的樹，這種特殊不僅僅在于其分支最多為2以及其它特征，一個(gè)最重要的特殊之處是在于：二叉樹是有序的。即二叉樹的左右孩子是不可交換的，如果交換了就成了另外一棵二叉樹，這樣交換之后的二叉樹與原二叉樹是不相同的兩棵二叉樹。但是，對于普通的雙分支樹而言，不具有這種性質(zhì)。（3）滿二叉樹和完全二叉樹的概念。（4）重點(diǎn)掌握二叉樹的五個(gè)性質(zhì)及證明方法，并把這種方法推廣到K叉樹。普通二叉樹的五個(gè)性質(zhì)：第i層的最多結(jié)點(diǎn)數(shù)，深度為k的二叉樹

27、的最多結(jié)點(diǎn)數(shù)，n0=n2+1的性質(zhì)，n個(gè)結(jié)點(diǎn)的完全二叉樹的深度，順序存儲二叉樹時(shí)孩子結(jié)點(diǎn)與父結(jié)點(diǎn)之間的換算關(guān)系（序號i結(jié)點(diǎn)的左孩子為：2*i，右孩子為：2*i+1）。2. 掌握二叉樹的順序存儲結(jié)構(gòu)和二叉鏈表、三叉鏈表存儲結(jié)構(gòu)的各自優(yōu)缺點(diǎn)及適用場合，以及二叉樹的順序存儲結(jié)構(gòu)和二叉鏈表存儲結(jié)構(gòu)的相互轉(zhuǎn)換的算法。3. 熟練掌握二叉樹的先序，中序和后序遍歷算法以及按層次遍歷二叉樹的先序、中序和后序三種遍歷算法，劃分的依據(jù)是視其每個(gè)算法中對根結(jié)點(diǎn)數(shù)據(jù)的訪問順序而定。不僅要熟練掌握這三種遍歷的遞歸算法，理解其執(zhí)行的實(shí)際步驟，并且應(yīng)該熟練掌握三種遍歷的非遞歸算法。按層次遍歷二叉樹void LayerOrde

28、r(Bitree T)/層序遍歷二叉樹InitQueue(Q); /建立工作隊(duì)列EnQueue(Q,T);while(!QueueEmpty(Q)DeQueue(Q,p);visit(p);if(p-lchild) EnQueue(Q,p-lchild);if(p-rchild) EnQueue(Q,p-rchild);/LayerOrder 4. 遍歷是基礎(chǔ)，重點(diǎn)掌握在三種基本遍歷算法的基礎(chǔ)上實(shí)現(xiàn)二叉樹的其它算法如求二叉樹葉子結(jié)點(diǎn)總數(shù)，求二叉樹結(jié)點(diǎn)總數(shù)，求度為1或度為2的結(jié)點(diǎn)總數(shù)，復(fù)制二叉樹，建立二叉樹，交換左右子樹，查找值為n的某個(gè)指定結(jié)點(diǎn)，刪除值為n的某個(gè)指定結(jié)點(diǎn)等等。5. 線索二叉樹的

29、引出，是為避免如二叉樹遍歷時(shí)的遞歸求解。遞歸雖然形式上比較好理解，但是消耗了大量的內(nèi)存資源，如果遞歸層次一多，勢必帶來資源耗盡的危險(xiǎn)。二叉樹線索化的實(shí)質(zhì)是建立結(jié)點(diǎn)在相應(yīng)序列中與其前驅(qū)和后繼之間的直接聯(lián)系。對于線索二叉樹，應(yīng)該掌握：線索化的實(shí)質(zhì)，三種線索化的算法，線索化后二叉樹的遍歷算法，基本線索二叉樹的其它算法問題（如：查找某一類線索二叉樹中指定結(jié)點(diǎn)的前驅(qū)或后繼結(jié)點(diǎn)）。6. 二叉排序樹的中序遍歷結(jié)果是一個(gè)遞增的有序序列。二叉排序樹的形態(tài)取決于元素的輸入順序，二叉排序樹在最差情況下形成單支樹。熟練掌握其建立、查找、插入和刪除算法，以及判斷某棵二叉樹是否二叉排序樹這一問題的遞歸與非遞歸算法。7.

30、平衡二叉樹是二叉排序樹的優(yōu)化，平衡二叉樹對左右子樹的深度有了限定：深度之差的絕對值不得大于1。掌握平衡二叉樹的四種調(diào)整算法。8. 樹與森林的遍歷，只有兩種遍歷算法：先根與后根（對于森林而言稱作：先序與中序遍歷）。二者的先根與后根遍歷與二叉樹中的遍歷算法是有對應(yīng)關(guān)系的：先根遍歷對應(yīng)二叉樹的先序遍歷，而后根遍歷對應(yīng)二叉樹的中序遍歷。二叉樹使用二叉鏈表分別存放它的左右孩子，樹利用二叉鏈表存儲孩子及兄弟（稱孩子兄弟鏈表），而森林也是利用二叉鏈表存儲孩子及兄弟。掌握樹、森林和二叉樹間的相互轉(zhuǎn)換。9. 簡單掌握等價(jià)類的生成算法。10. 哈夫曼樹為了解決特定問題引出的特殊二叉樹結(jié)構(gòu)，它的前提是給二叉樹的每條

31、邊賦予了權(quán)值，這樣形成的二叉樹按權(quán)相加之和是最小的，一般來說，哈夫曼樹的形態(tài)不是唯一的。理解哈夫曼編碼的基本原理，掌握基于哈夫曼樹生成哈夫曼編碼的方法。練習(xí)題：（一）選擇題：1. 一棵二叉樹的前序遍歷結(jié)果為ABCDEF，中序遍歷結(jié)果為CBAEDF，則后序遍歷結(jié)果為（A）A. CBEFDAB. FEDCBAC. CBEDFAD. 不確定2. 某二叉樹的后序遍歷序列為dabec，中序遍歷序列為debac，則前序遍歷序列為（D）。AacbedBdecabCdeabc Dcedba3. 具有10個(gè)葉子結(jié)點(diǎn)的二叉樹中有（B）個(gè)度為2的結(jié)點(diǎn)。A. 8 B. 9C. 10 D. 114. 樹中所有結(jié)點(diǎn)的度等

32、于所有結(jié)點(diǎn)數(shù)加（ C ）。A0 B1 C1 D25. 設(shè)n，m為一棵二叉樹的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)，n在m前的條件是（ C ）A. n在m的右方B. n是m的祖先C. n在m的左方D. n是m的子孫6. 利用逐點(diǎn)插入建立序列（50，72，43，85，75，20，35，45，65，30）對應(yīng)的二叉排序樹以后，要查找元素30要進(jìn)行（ B ）次元素間的比較。A4 B. 5C6 D. 77. 在平衡二叉樹中，（ C ）。A任意結(jié)點(diǎn)的左、右子樹結(jié)點(diǎn)數(shù)目相同B任意結(jié)點(diǎn)的左、右子樹高度相同C任意結(jié)點(diǎn)的左右子樹高度之差的絕對值不大于1D不存在度為1的結(jié)點(diǎn)8. 由元素序列（27，16，75，38，51）構(gòu)造平衡

33、二叉樹，則首次出現(xiàn)的最小不平衡子樹的根（即離插入結(jié)點(diǎn)最近且平衡因子的絕對值為2的結(jié)點(diǎn)）為（ D ）A27 B38C51 D. 759. 在二叉樹的順序存儲中，每個(gè)結(jié)點(diǎn)的存儲位置與其父結(jié)點(diǎn)、左右子樹結(jié)點(diǎn)的位置都存在一個(gè)簡單的映射關(guān)系，因此可與三叉鏈表對應(yīng)。若某二叉樹共有n個(gè)結(jié)點(diǎn)，采用三叉鏈表存儲時(shí)，每個(gè)結(jié)點(diǎn)的數(shù)據(jù)域需要d個(gè)字節(jié)，每個(gè)指針域占用4個(gè)字節(jié)，若采用順序存儲，則最后一個(gè)結(jié)點(diǎn)下標(biāo)為k（起始下標(biāo)為1），那么（ A ）時(shí)采用順序存儲更節(jié)省空間。Ad12n/(k-n)C. d12n/(k+n)10. 在常用的描述二叉排序樹的存儲結(jié)構(gòu)中，關(guān)鍵字值最大的結(jié)點(diǎn)（ B ）A左指針一定為空 B. 右指針一

34、定為空C左右指針均為空 D. 左右指針均不為空（二）應(yīng)用題1、一棵滿k叉樹，按層次遍歷（從1開始對全部結(jié)點(diǎn)進(jìn)行編號）存儲在一維數(shù)組中，試計(jì)算編號為u的結(jié)點(diǎn)的第i個(gè)孩子（若存在）的下標(biāo)以及編號為v的結(jié)點(diǎn)的雙親結(jié)點(diǎn)（若存在）的下標(biāo)。答：結(jié)點(diǎn)下標(biāo)為u的結(jié)點(diǎn)的第i個(gè)孩子的下標(biāo)：結(jié)點(diǎn)下標(biāo)為v的結(jié)點(diǎn)的父母結(jié)點(diǎn)的下標(biāo)：2、試求有n個(gè)葉結(jié)點(diǎn)的非滿的完全二叉樹的高度.答：完全二叉樹中葉子結(jié)點(diǎn)數(shù)為n，則根據(jù)完全二叉樹的性質(zhì)，度為2的結(jié)點(diǎn)數(shù)是n-1，而完全二叉樹中，度為1的結(jié)點(diǎn)數(shù)至多為1，所以具有n個(gè)葉子結(jié)點(diǎn)的完全二叉樹結(jié)點(diǎn)數(shù)是n+(n-1)+1=2n或2n-1（有或無度為1的結(jié)點(diǎn)）。由于具有2n(或2n-1)個(gè)結(jié)

35、點(diǎn)的完全二叉樹的深度是log2(2n)+1( 或log2(2n-1)+1)，即log2n+1,故n個(gè)葉結(jié)點(diǎn)的非滿的完全二叉樹的高度是log2n+1。（最下層結(jié)點(diǎn)數(shù)=2）。3、已知一棵度為m的樹中有N1個(gè)度為1的結(jié)點(diǎn)，N2個(gè)度為2的結(jié)點(diǎn)，Nm個(gè)度為m的結(jié)點(diǎn)，問該樹中有多少個(gè)葉子結(jié)點(diǎn)。請寫出推導(dǎo)過程。答：設(shè)N為總結(jié)點(diǎn)數(shù)，N0為葉子結(jié)點(diǎn)數(shù)則：N=N0+N1+N2+Nm又有：N-1=度的總數(shù)，則：N-1=N1*1+N2*2+Nm*m則有：N0=1+N2+2N3+(m-1)Nm4有七個(gè)帶權(quán)結(jié)點(diǎn)，其權(quán)值分別為3,7,8,2,6,10,14，試以它們?yōu)槿~子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹，并計(jì)算出帶權(quán)路徑長度WPL。答

36、：WPL = 3*4+7*3+8*3+2*4+6*3+10*2+14*2 = 1315、給定字母a,b,c,d,e的使用頻率為0.09,0.17,0.2,0.23,0.31。設(shè)計(jì)以該權(quán)值為基礎(chǔ)的哈夫曼樹，并給出哈夫曼編碼？平均長度是多少？答：構(gòu)造的哈夫曼樹如下：cc d e a b哈夫曼編碼如下：c(00)d(01)a(100)b(101)e(11)平均長度=0.09*3+0.17*3+0.2*2+0.23*2+0.31*2=2.266.從概念上講，樹，森林和二叉樹是三種不同的數(shù)據(jù)結(jié)構(gòu)，將樹，森林轉(zhuǎn)化為二叉樹的基本目的是什么，并指出樹和二叉樹的主要區(qū)別。 解：樹的孩子兄弟鏈表表示法和二叉樹二叉

37、鏈表表示法，本質(zhì)是一樣的，只是解釋不同，也就是說樹（樹是森林的特例，即森林中只有一棵樹的特殊情況）可用二叉樹唯一表示，并可使用二叉樹的一些算法去解決樹和森林中的問題。樹和二叉樹的區(qū)別有：一是二叉樹的度至多為2，樹無此限制；二是二叉樹有左右子樹之分，即使在只有一個(gè)分枝的情況下， 也必須指出是左子樹還是右子樹，樹無此限制；7.如果給出了一個(gè)二叉樹結(jié)點(diǎn)的前序序列和中序序列，能否構(gòu)造出此二叉樹?若能，請證明之。若不能，請給出反例。如果給出了一個(gè)二叉樹結(jié)點(diǎn)的前序序列和后序序列，能否構(gòu)造出此二叉樹?若能，請證明之。若不能，請給出反例。解：給定二叉樹前序序列和中序序列，可以唯一確定該二叉樹。因?yàn)榍靶蛐蛄械牡?/p>

38、一個(gè)元素是根結(jié)點(diǎn)，該元素將二叉樹中序序列分成兩部分，左邊（設(shè)l個(gè)元素）表示左子樹，若左邊無元素，則說明左子樹為空；右邊（設(shè)r個(gè)元素）是右子樹，若為空，則右子樹為空。根據(jù)前序遍歷中“根左子樹右子樹”的順序，則由從第二元素開始的l個(gè)結(jié)點(diǎn)序列和中序序列根左邊的l個(gè)結(jié)點(diǎn)序列構(gòu)造左子樹，由前序序列最后r個(gè)元素序列與中序序列根右邊的r個(gè)元素序列構(gòu)造右子樹。由二叉樹的前序序列和后序序列不能唯一確定一棵二叉樹，因無法確定左右子樹兩部分。例如，任何結(jié)點(diǎn)只有左子樹的二叉樹和任何結(jié)點(diǎn)只有右子樹的二叉樹，其前序序列相同，后序序列相同，但卻是兩棵不同的二叉樹。（三）算法設(shè)計(jì)題1請利用棧的基本操作寫出先序遍歷二叉樹的非遞

39、歸形式的算法。要求以二叉鏈表作為二叉樹的存儲結(jié)構(gòu)。函數(shù)原型如下：void PreOrder(Bitree T)；答：void PreOrder(Bitree T)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-rchlid);2試寫一個(gè)判別給定二叉樹是否為二叉排序樹的遞歸算法，設(shè)此二叉樹以二叉鏈表作存儲結(jié)構(gòu)，且樹中結(jié)點(diǎn)的關(guān)鍵字均不同。函數(shù)原型如下：int Is_BSTr

40、ee（BiTree T）；答：int last=0,flag=1;int Is_BSTree（BiTree T）if(T-lchild&flag)Is_BSTree(T-lchild);if(T-datadata;if(T-rchild&flag)Is_BSTree(T-rchild);return flag;3假設(shè)一個(gè)僅包含二元運(yùn)算符的算術(shù)表達(dá)式以鏈表形式存儲在二叉樹BT中，寫出計(jì)算該算術(shù)表達(dá)式值的算法。答：以二叉樹表示算術(shù)表達(dá)式，根結(jié)點(diǎn)用于存儲運(yùn)算符。若能先分別求出左子樹和右子樹表示的子表達(dá)式的值，最后就可以根據(jù)根結(jié)點(diǎn)的運(yùn)算符的要求，計(jì)算出表達(dá)式的最后結(jié)果。typedef struct n

41、ode ElemType data; float val;char optr; /只取+， -， *，/struct node *lchild，*rchild BiNode,*BiTree;float PostEval(BiTree bt) / 以后序遍歷算法求以二叉樹表示的算術(shù)表達(dá)式的值float lv,rv;if(bt!=null)lv=PostEval(bt-lchild); / 求左子樹表示的子表達(dá)式的值rv=PostEval(bt-rchild); / 求右子樹表示的子表達(dá)式的值switch(bt-optr)case +: value=lv+rv; break;case -: val

42、ue=lv-rv;break;case *: value=lv*rv;break;case /: value=lv/rv; return(value); 4設(shè)計(jì)算法，已知一棵以二叉鏈表存儲的二叉樹，root指向根結(jié)點(diǎn)，p指向二叉樹中任一結(jié)點(diǎn)，編寫算法求從根結(jié)點(diǎn)到p所指結(jié)點(diǎn)之間的路徑（要求輸出該路徑上每個(gè)結(jié)點(diǎn)的數(shù)據(jù)）。答：void path(Bintree T, Bintree p)Bintree stackmax,q;int tagmax,top=0,find=0;q=T;while (q|top)& find=0)while (q)stacktop=q; tagtop+=0; q=q-lchild;if (top0) q=stacktop-1; if (tagtop-1=1) if (q=p) for (i=0;idata);find=1; else top-; if (top0&!find) q=q-rchild