數(shù)據(jù)結(jié)構(gòu)實(shí)用教程習(xí)題答案

1、1 緒論1.1 回答下列概念：數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)的存儲結(jié)構(gòu)，算法數(shù)據(jù)結(jié)構(gòu): 按照某種邏輯關(guān)系組織起來的一批數(shù)據(jù)，用一定的存儲方式存儲在計(jì)算機(jī)的存儲器中，并在這些數(shù)據(jù)上定義一個運(yùn)算的集合，就稱為一個數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu): 數(shù)據(jù)元素之間的邏輯關(guān)系，是根據(jù)實(shí)際問題抽象出來的數(shù)學(xué)模型。數(shù)據(jù)的存儲結(jié)構(gòu): 是指數(shù)據(jù)的邏輯結(jié)構(gòu)到計(jì)算機(jī)存儲器的映射。算法: 是指對數(shù)據(jù)元素進(jìn)行加工和處理1.2 數(shù)據(jù)結(jié)構(gòu)研究的三方面內(nèi)容是什么？它們之間有什么聯(lián)系和區(qū)別？三方面內(nèi)容: 數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)和數(shù)據(jù)運(yùn)算的集合。聯(lián)系和區(qū)別：數(shù)據(jù)的邏輯結(jié)構(gòu)是數(shù)學(xué)模型，數(shù)據(jù)的存儲結(jié)構(gòu)是指邏輯結(jié)構(gòu)到存儲區(qū)域的映射，運(yùn)

2、算是定義在邏輯結(jié)構(gòu)上，實(shí)現(xiàn)在存儲結(jié)構(gòu)上。1.3 簡述數(shù)據(jù)結(jié)構(gòu)中討論的三種經(jīng)典結(jié)構(gòu)及其邏輯特征。三種經(jīng)典結(jié)構(gòu)：線性表、樹和圖。線性表：有且僅有一個開始結(jié)點(diǎn)和一個終端結(jié)點(diǎn)，其余的內(nèi)部結(jié)點(diǎn)都有且僅有一個前趨結(jié)點(diǎn)和一個后繼結(jié)點(diǎn)，數(shù)據(jù)元素間存在著一對一的相互關(guān)系。樹：有且僅有一個開始結(jié)點(diǎn)，可有若干個終端結(jié)點(diǎn)，其余的內(nèi)部結(jié)點(diǎn)都有且僅有一個前趨結(jié)點(diǎn)，可以有若干個后繼結(jié)點(diǎn)，數(shù)據(jù)元素間存在著一對多的層次關(guān)系。圖：可有若干個開始結(jié)點(diǎn)和終端結(jié)點(diǎn)，其余的內(nèi)部結(jié)點(diǎn)可以有若干個前趨結(jié)點(diǎn)和若干個后繼結(jié)點(diǎn)，數(shù)據(jù)元素間存在著多對多的網(wǎng)狀關(guān)系。1.4 實(shí)現(xiàn)數(shù)據(jù)存儲結(jié)構(gòu)的常用存儲方法有哪幾種？簡述各種方法的基本思想。常用存儲方法有

3、四種：順序存儲、鏈接存儲、索引存儲、散列存儲。各種方法的基本思想：順序存儲：把邏輯上相鄰的數(shù)據(jù)元素存儲在物理位置上相鄰的存儲單元里。鏈接存儲：通過附加指針域表示數(shù)據(jù)元素之間的關(guān)系。索引存儲：除了存儲數(shù)據(jù)元素，還要建立附加索引表來標(biāo)識數(shù)據(jù)元素的地址。散列存儲：根據(jù)數(shù)據(jù)元素的關(guān)鍵字直接計(jì)算出該結(jié)點(diǎn)的存儲地址，稱為關(guān)鍵字地址轉(zhuǎn)換法。1.5 算法的特性是什么？如何定性的評價一個算法的優(yōu)劣？算法的特性：有窮性、確定性、可行性、輸入、輸出。算法的定性評價標(biāo)準(zhǔn)有：正確性、可讀性、健壯性、簡單性。1.6 算法的定量評價標(biāo)準(zhǔn)是什么？算法的定量評價標(biāo)準(zhǔn)有：時間復(fù)雜度和空間復(fù)雜度。時間復(fù)雜度：是一個算法運(yùn)行時所耗費(fèi)

4、的系統(tǒng)時間，也就是算法的時間效率?？臻g復(fù)雜度：是一個算法運(yùn)行時所耗費(fèi)的存儲空間，也就是算法的空間效率。1.7 寫出下列程序段中帶標(biāo)號語句的頻度，并給出執(zhí)行各程序段的時間復(fù)雜度（n為整數(shù)）。（1）i=1; （2）s=1;while（in）do for(i=1;i=n;i+) 【1】i+; 【1】s=s*i;（3）s=0; （4）i=1;for(i=l;in;i+) while(i*i=i;j-) 【1】i+; 【1】s=s+i+j; （5）i=1； （6）x=1;y=100;while（in）do do 【1】i=i*2; 【1】x+;y-; While(xy); 答：（1） n-1, O(n)

5、 （2）n,O(n) （3）(n+2)(n-1)/2, O(n2) （4） , O( ) （5）(n-1)+1,O(n) （6）50,O(1)2 線性表2.1 回答下列概念：線性結(jié)構(gòu)，線性表，順序表，單鏈表，靜態(tài)鏈表 線性結(jié)構(gòu)：設(shè)Data_Structure =（D，S），rS，相對r，D中有且僅有一個開始結(jié)點(diǎn)和一個終端結(jié)點(diǎn)，其余的內(nèi)部結(jié)點(diǎn)都有且僅有一個前趨和一個后繼，則稱Data_Structure是相對r的線性結(jié)構(gòu)。線性表：是具有相同屬性的n（n0）個數(shù)據(jù)元素的有限序列。順序表：順序表（Sequential List）是采用順序存儲結(jié)構(gòu)的線性表。單鏈表：每個結(jié)點(diǎn)只附加一個指向后繼的指針域，

6、這樣的鏈表稱為單鏈表（Single Linked List）靜態(tài)鏈表：用數(shù)組實(shí)現(xiàn)的鏈表，指針就變換為數(shù)組的下標(biāo)，結(jié)點(diǎn)即為數(shù)組中的下標(biāo)變量，由于需要預(yù)先分配一個較大的數(shù)組空間，因此這種鏈表稱之為靜態(tài)鏈表。2.2 比較順序表和鏈表這兩種線性表不同存儲結(jié)構(gòu)的特點(diǎn)。邏輯關(guān)系的表示：順序表隱含表示關(guān)系，鏈表顯示表示關(guān)系。2存儲密度：順序表的存儲密度大，而鏈表的存儲密度小。3存儲分配方式：順序表的存儲空間是預(yù)先靜態(tài)分配的一塊連續(xù)存儲空間，在程序執(zhí)行之前必須明確規(guī)定它的存儲規(guī)模。鏈表不用事先估計(jì)存儲規(guī)模，動態(tài)分配和釋放存儲空間，存儲空間可連續(xù)也可不連續(xù)。4存取方法：順序表可以隨機(jī)存取，鏈表必須順序存取。5插

7、入、刪除操作：在順序表中做插入、刪除時平均移動表中一半的元素；在鏈表中作插入、刪除時，只要修改指針域，而不需要移動元素。所以順序表的插入、刪除效率低，鏈表的插入、刪除效率高。6實(shí)現(xiàn)語言：順序表容易實(shí)現(xiàn)，任何高級語言中都有數(shù)組類型。而鏈表的操作是基于指針的，對于沒有提供指針類型的高級語言，必須采用靜態(tài)鏈表。總之，兩種存儲結(jié)構(gòu)各有長短，選擇那一種由實(shí)際問題中的主要因素決定。通常“較穩(wěn)定”的線性表選擇順序存儲，而頻繁做插入、刪除的線性表，即動態(tài)性較強(qiáng)的線性表宜選擇鏈接存儲。2.3 已知長度為n的線性表A中的元素是整數(shù)，寫算法求線性表中值大于item的元素個數(shù)。分兩種情況編寫函數(shù)：（1）線性表采用順序

8、存儲；（2）線性表采用單鏈表存儲。（1）線性表采用順序存儲#define MAX 1024typedef int DataType;typedef struct DataType dataMAX;int last; SeqList;int LocateElem (SeqList *L, DataType item)int i,j=0; for(i=0;ilast ;i+) if( L-datai item ) j+; return j;（2）線性表采用單鏈表存儲typedef int DataType;typedef struct Node DataType data; struct Node

9、 *next; LinkList;LinkList *locateElem(LinkList *L, DataType item ) LinkList *p=L-next; int i=0; while ( p ) if( p-data item) i+; p=p-next; return i ;2.4 已知長度為n的線性表A中的元素是整數(shù)，寫算法刪除線性表中所有值為item的數(shù)據(jù)元素。分兩種情況編寫函數(shù)：（1）線性表采用順序存儲；（2）線性表采用單鏈表存儲。（1）線性表采用順序存儲#define MAX 1024typedef int DataType;typedef struct Data

10、Type dataMAX;int last; SeqList; int LocateElem (SeqList *L, DataType item)int i=0; While(ilast) if( L-datai =item ) for(j=i+1;jlast;j+) L-dataj-1=L-dataj; L-last -; Else i+; （2）線性表采用單鏈表存儲typedef int DataType;typedef struct Node DataType data; struct Node *next; LinkList;int deleteDupNode(LinkList *L

11、, DataType item) LinkList *p,*q,*r; q= L; p=L-next; while (p) if (p-data=item) q-next=p-next; free(p); p=q-next;else q=p; p=p-next; 2.5 設(shè)長度為Max的順序表L中包含n個整數(shù)且遞增有序。試寫一算法，將x 插入到順序表的適當(dāng)位置上，以保持表的有序性，并且分析算法的時間復(fù)雜度。#define MAX 1024typedef int DataType;typedef struct DataType dataMAX;int last; SeqList;int inse

12、rts(SeqList *L, DataType x) int i; if (L-last =Max-1) printf(“full”); return 0; i= L-last;while(i=0& L-datai x) L-data i+1= L-data i-;/“相當(dāng)于L-data i+1= L-data i；i-；”L-data i+1=x; L-last +; return 1;2.6 設(shè)帶頭結(jié)點(diǎn)的單鏈表L中的數(shù)據(jù)元素是整型數(shù)且遞增有序。試寫一算法，將x 插入到單鏈表的適當(dāng)位置上，以保持表的有序性，并且分析算法的時間復(fù)雜度。typedef int DataType;typedef

13、struct Node DataType data; struct Node *next; LinkList;void InsertList(LinkList *L,datetype x)LinkList *p,*s;s=(LinkList *)malloc(sizeof(Linklist);s-data=x;p=L;while(p-next)&(p-next-datanext;s-next=p-next; p-next=s;2.7 試寫一算法實(shí)現(xiàn)對不帶頭結(jié)點(diǎn)的單鏈表H進(jìn)行就地逆置。 typedef int DataType;typedef struct Node DataType data;

14、 struct Node *next; LinkList;LinkList * Reverse(LinkList *H)LinkList *p,*q;if (!H) return;p=H-next; q=H-next; H-next=NULL;While(q)q=q-next; p-next= H; H =p; p=q; return H;2.8 若帶頭結(jié)點(diǎn)的單鏈表L中的數(shù)據(jù)元素是整型數(shù)，編寫算法對單鏈表L進(jìn)行排序。typedef int DataType;typedef struct Node DataType data; struct Node *next; LinkList;void I

15、nsertList(LinkList *L)LinkList *p,*q,*s;if (!L-next |！L-next-next) return;q= L-next-next; L-next-next= NULL;while(q)s=q; q=q-next;p=L;while(p-next)&(p-next-datadata ) p=p-next;s-next=p-next; p-next=s; 2.9 設(shè)單鏈表X和單鏈表Y分別存儲了兩個字符串，設(shè)計(jì)算法找出X中第一個不在Y中出現(xiàn)的字符。typedef char DataType;typedef struct Node DataType da

16、ta; struct Node *next; LinkList;linklist *search(linklist *x, linklist *y) linklist *p,*q; p=x; q=y; while(p&q) if(p-data!=q-data) q=q-next;else p=p-next; q=y; return p; 2.10 已知遞增有序的兩個單鏈表A和B各存儲了一個集合。設(shè)計(jì)算法實(shí)現(xiàn)求兩個集合的交集運(yùn)算C=AB。typedef int DataType;typedef struct Node DataType data; struct Node *next; LinkL

17、ist;LinkList *union(LinkList *A,LinkList *B) LinkList *C, *p,*q,*s*r; p=A-next;q=B-next; C=A; r=C; while (p&q) if (p-data=q-data) r-next=p; r=p; p=p-next;q=q-next;else if (p-datadata) p=p-next; else q=q-next; r-next= NULL ; free(B); return C;2.11 已知遞增有序的兩個單鏈表A和B，編寫算法將A、B歸并成一個遞增有序的單鏈表C。typedef int Da

18、taType;typedef struct Node DataType data; struct Node *next; LinkList;LinkList *union(LinkList *A,LinkList *B) LinkList *C, *p,*q,*s*r; p=A-next;q=B-next; C=A; r=C; while (p&q) if (p-datadata) s=p; p=p-next; else s=q; q=q-next; r-next=s;r=s; if (!q) r-next=q;else r-next=p; free(B); return C;3 棧和隊(duì)列3.

19、1 回答下列概念：棧，隊(duì)列，順序棧，鏈隊(duì)列棧：棧（Stack）是運(yùn)算受限的線性表，限制它的插入和刪除操作僅在表的一端進(jìn)行。隊(duì)列：只允許在表的一端進(jìn)行插入，而在表的另一端進(jìn)行刪除，將這種線性表稱為隊(duì)或隊(duì)列（Queue）。順序棧：采用順序方式存儲的棧稱為順序棧（Sequential Stack）。鏈隊(duì)列：采用鏈接方法存儲的隊(duì)列稱為鏈隊(duì)列（Linked Queue）。3.2 棧和隊(duì)列各有什么特點(diǎn)？簡述棧、隊(duì)列和線性表的差別。棧（Stack）是運(yùn)算受限的線性表，限制它的插入和刪除操作僅在表的一端進(jìn)行，又稱為后進(jìn)先出的線性表（Last In First Out），簡稱 LIFO表。只允許在表的一端進(jìn)行插

20、入，而在表的另一端進(jìn)行刪除，將這種線性表稱為隊(duì)或隊(duì)列（Queue），又叫先進(jìn)先出的線性表，簡稱為FIFO（First In First Out）表。這三種結(jié)構(gòu)有很多的相似之處，其差別主要體現(xiàn)在運(yùn)算上，具有不同的運(yùn)算特點(diǎn)。同線性表的運(yùn)算相比，棧和隊(duì)列在操做上受到限制。線性表可以在元素序列的任何位置上進(jìn)行插入、刪除操作，查找運(yùn)算往往是線性表上使用頻率最高的操作。查找、插入、刪除的時間復(fù)雜度一般為O（n）。棧和隊(duì)列的插入和刪除運(yùn)算都限制在線性表的表端完成，在棧和隊(duì)列上不需要查找運(yùn)算。棧和隊(duì)列的插入及刪除運(yùn)算時間復(fù)雜度都可以為O（1）。3.3 設(shè)有編號為1，2，3，4的四輛車，順序進(jìn)入一個棧式結(jié)構(gòu)的站

21、臺，試寫出這四輛車開出車站的所有可能的順序。1 2 3 4 2 1 3 4 3 2 1 4 4 3 2 11 2 4 3 2 1 4 3 3 2 4 1 1 3 2 4 2 3 1 4 3 4 2 11 3 4 2 2 3 4 1 1 4 3 2 2 4 3 1 3.4 若數(shù)列1、2、3、4、5、6順序進(jìn)棧，假設(shè)P表示入棧操作，S表示出棧操作，例如：操作序列PSPSPSPSPSPS，可得到出棧序列為:。依此類推，請回答：（1）能否得到出棧序列？若能，請寫出對應(yīng)的操作序列。 （2）能否得到出棧序列？若能，請寫出對應(yīng)的操作序列。（3）對應(yīng)操作序列：PPSSPPSPSPSS，得到的出棧序列是什么？（

22、4）對應(yīng)操作序列：PPPPSPSSPSSS，得到的出棧序列是什么？（5）從上面的結(jié)果中你能總結(jié)出什么結(jié)論？（1）能得到。在123依次進(jìn)棧后，3和2出棧，得部分輸出序列32；然后4，5入棧，5出棧，得部分出棧序列325；6入棧并出棧，得部分輸出序列3256；最后退棧，直到?？铡５幂敵鲂蛄?。其操作序列為PPPSSPPSPSSS。（2）不能得到輸出順序?yàn)榈男蛄?。部分合法操作序列為ADAAAADDAD，得到部分輸出序列1546后，棧中元素為23，3在棧頂，故不可能2先出棧，得不到輸出序列。（3）（4）（5）借助棧由輸入序列12n得到輸出序列p1p2pn ,則在輸出序列中不可能存在這樣的情形：存在著ij

23、k使pjpkfront=sq-rear判斷隊(duì)滿的條件是：（sq-rear+1）% MAXSIZE= = sq-front求隊(duì)列長度的公式為：m =（sq-rear - sq-front+ MAXSIZE）% MAXSIZE;3.6 通常稱正讀和反讀都相同的字符序列為“回文”，例如，“abcdeedcba”、 “abcdcba”是回文。若字符序列存儲在一個單鏈表中，編寫算法判斷此字符序列是否為回文。（提示：將一半字符先依次進(jìn)棧）#define maxsize 100typedef char datatype1;typedef struct datatype1 datamaxsize; int t

24、op; seqstack;typedef int datatype;typedef struct node datatype data; struct node *next; Linklist;Duichen(Linklist *head) int i=1;Linklist *p; seqstack *s;s=initSeqStack();p= head-next;n=0;while(p)n+; p=p-next;p=head-next;while(idata); i+; if (n%2!=0) p=p-next; while(p&p-data=pop(s) p=p-next;if (p) r

25、eturn 0 else return 1;3.7 兩個棧共享數(shù)組am空間，棧底分別設(shè)在兩端，此時?？铡M的條件是什么？試寫出兩個棧公用的算法：Top(i), Push(i,x)和Pop(i)，其中i為棧的序號0或1。 #define m 100typedef char datatype;typedef struct node datatype am; int top0 , top1; seqstack; Seqstack ss,*s=&ss;int push(int i, datatype x) if (s-top1 = s-top0+1) printf(“full”); return 0

26、; if(i=0) s-top0+; s-as-top0=x; else s-top1-; s-as-top1=x; return 1;datatype pop(int i) if(i=0) if (s-top0= -1) printf(“empty”); return 0;s-top0-; return s-as-top0+1; else if (s-top1= m) printf(“empty”); return 0;s-top1+; return s-as-top1-1;datatype top(int i) if(i=0) if (s-top0= -1) printf(“empty”)

27、; return 0; return s-as-top0; else if (s-top1=m) printf(“empty”); return 0; return s-as-top1;3.8 假設(shè)以數(shù)組am存放循環(huán)隊(duì)列的元素，同時設(shè)變量rear 和length分別作為隊(duì)尾指針和隊(duì)中元素個數(shù)，試給出判別此循環(huán)隊(duì)列的隊(duì)滿條件，并寫出相應(yīng)入隊(duì)和出隊(duì)的算法（在出隊(duì)的算法中要返回隊(duì)頭元素）。#define m 100 int enqueue(int a, int rear, int length, int x) if(length = m) printf(“queue is full”); retur

28、n 0; rear=(rear+1)% m; arear=x; length +; return length; int dequeue(int a, int rear, int length, int *x) if(length =0) printf(“queueempty”); return 0; *x= a (rear- length +m)%m; length -; return length;4 多維數(shù)組及廣義表4.1回答下列概念：三元組表、廣義表、十字鏈表三元組表：稀疏矩陣中的非零元素三元組組成的線性表。廣義表： 也稱為列表（Lists）是n（n0）個元素a1， a2， ，ai，

29、an的有限序列，元素ai可以是原子或者是子表（子表亦是廣義表）。十字鏈表：稀疏矩陣（即三元組表）的一種鏈接存儲結(jié)構(gòu)。稀疏矩陣中每個非零元素都用一個包含五個域的結(jié)點(diǎn)來表示，存儲非零元素所在行的行號域i，存儲非零元素所在列的列號域j，存儲非零元素值的值域v，以及行指針域right和列指針域down，分別指向同一行中的下一個非零元素結(jié)點(diǎn)和同一列中的下一個非零元素結(jié)點(diǎn)。4.2二維數(shù)組在采用順序存儲時，元素的排列方式有哪兩種？行優(yōu)先和列優(yōu)先。4.3 矩陣壓縮存儲的目的是什么？請寫出對稱陣壓縮存儲四種方式的地址公式。壓縮存儲的目的：節(jié)省矩陣的存儲空間。將對稱矩陣的下（上）三角存儲在數(shù)組長度為n（n+1）/

30、2的數(shù)組sa中，設(shè)矩陣中的某一個元素aij在數(shù)組中的下標(biāo)為k，則對稱陣壓縮存儲四種方式下k的計(jì)算公式如下：（1）行優(yōu)先順序存儲下三角（2）列優(yōu)先順序存儲下三角（3）行優(yōu)先順序存儲上三角（4）列優(yōu)先順序存儲上三角4.4 在特殊矩陣和稀疏矩陣中，哪一種經(jīng)過壓縮存儲后會失去隨機(jī)存取的特性？稀疏矩陣。4.5 設(shè)有一個10階的對稱矩陣A，以行優(yōu)先順序存儲下三角元素，其中a00為第一元素，其存儲地址為1，每個元素占一個字節(jié)，則a85的地址為多少？若a11為第一元素，那么a85的地址又會是多少？若a00為第一元素，則a85的地址為：41若a11為第一元素，則a85的地址為：324.6 請給出圖4.10中稀疏

31、矩陣A67的三元組順序表和十字鏈表存儲結(jié)構(gòu)圖示。矩陣A67的三元組順序表： 01234i13346j21643v11-3765矩陣A67及十字鏈表表示：4.7 廣義表分幾類？它們之間有什么關(guān)系？ 廣義表分為：線性表、純表、再入表和遞歸表四種。它們之間的關(guān)系滿足：遞歸表再入表純表線性表。4.8 分別求出下列廣義表的表頭、表尾及表長、表深。A=（a） 表頭：a表尾：()表長：1表深：1B=（a,b）,（c,d）表頭：（a,b）表尾：（c,d）表長：2表深：2C=（a,（b,c）,d,e）表頭：a表尾：(（b,c）,d,e）表長：4表深：2D=（a,b,（c,d）,（e,（f,g）表頭：a表尾：（b

32、,（c,d）,（e,（f,g）表長：4表深：44.9 請畫出下列廣義表的圖形表示。A=（a,b,c）B=（A,d）C=（x ,A , B）5 樹5.1 回答下列概念：樹、二叉樹、滿二叉樹、完全二叉樹、哈夫曼樹樹：可以用二元組或遞歸兩種方法定義樹。樹的二元組定義如下：設(shè)tree=（D，S），其中D是數(shù)據(jù)元素的集合，S是D中數(shù)據(jù)元素之間關(guān)系的集合。設(shè)關(guān)系rS，相對r，滿足下列條件： （1）D中有且僅有一個開始結(jié)點(diǎn)，該結(jié)點(diǎn)被稱為樹的根（Root）；（2）除樹根結(jié)點(diǎn)外，D中其余的結(jié)點(diǎn)有且僅有一個前趨結(jié)點(diǎn)；（3）從根到其余結(jié)點(diǎn)都有路徑。則稱tree是相對r的樹形結(jié)構(gòu)。二叉樹：二叉樹（Binary Tre

33、e）是n（n0）個結(jié)點(diǎn)的有限集合，滿足：（1）當(dāng)n=0時，為空二叉樹。（2）當(dāng)n0時，是由一個根結(jié)點(diǎn)和兩棵互不相交的分別稱作這個根的左子樹和右子樹的二叉樹組成。滿二叉樹：每層結(jié)點(diǎn)數(shù)都達(dá)到最大值的二叉樹。完全二叉樹：除最下面一層外其余各層的結(jié)點(diǎn)數(shù)都達(dá)到最大值，并且最下一層上的結(jié)點(diǎn)都集中在最左邊的若干位置上的二叉樹。哈夫曼樹：又稱最優(yōu)二叉樹，是在含有n個葉子結(jié)點(diǎn)，權(quán)值分別為w1，w2，wn的所有二叉樹中，帶權(quán)路徑長度WPL最小的二叉樹。5.2 對于圖5.37給出的樹，回答下列問題：（1）寫出它的二元組表示；（2）根結(jié)點(diǎn)、葉結(jié)點(diǎn)和分支結(jié)點(diǎn)分別都為哪些；（3）結(jié)點(diǎn)F的度數(shù)和層數(shù)分別為多少； （4）結(jié)點(diǎn)

34、B的兄弟和孩子分別為哪些？（5）從結(jié)點(diǎn)B到結(jié)點(diǎn)N是否存在路徑？若存在請寫出具體路徑。（6）從結(jié)點(diǎn)C到結(jié)點(diǎn)L是否存在路徑？若存在請寫出具體路徑。圖5.37（1）該樹采用二元組表示如下：設(shè)tree =（D，S），rSD = A， B， C， D， E， F， G， H， I，J， K， L， M，N R = ，（2）根結(jié)點(diǎn)：A 分支結(jié)點(diǎn)：B，D，F(xiàn)，G，H，I，M 葉結(jié)點(diǎn)：C，E，L，N，J，K（3）結(jié)點(diǎn)F的度數(shù)為1，層數(shù)為3。（4）結(jié)點(diǎn)B的兄弟為：C，D；孩子為E，F(xiàn)，G。（5）結(jié)點(diǎn)B到N存在路徑，路徑為：BFIMN。（6）結(jié)點(diǎn)C到L不存在路徑。5.3 畫出包含三個結(jié)點(diǎn)的樹和二叉樹的所有不同形態(tài)

35、，說明樹和二叉樹之間的區(qū)別與聯(lián)系。包含三個結(jié)點(diǎn)的樹： 包含三個結(jié)點(diǎn)的二叉樹： 5.4 判斷下列說法是否正確：（1）二叉樹是度為2的有序樹。 （）（2）二叉樹中至少有一個結(jié)點(diǎn)的度為2。 （）（3）完全二叉樹一定存在度為1的結(jié)點(diǎn)。 （）5.5 設(shè)樹T的度為4，其中度為1，2，3和4的結(jié)點(diǎn)個數(shù)分別為4，2，1，1 則T中的葉子數(shù)為多少？葉子數(shù)為8。5.6 結(jié)點(diǎn)數(shù)為n的二叉樹，高度最大是多少？最小是多少？將其擴(kuò)充成完全二叉樹時最多需要附加多少個虛點(diǎn)？結(jié)點(diǎn)數(shù)為n的二叉樹，高度最大是n，最小是或。將其擴(kuò)充成完全二叉樹時最多需要附加的虛點(diǎn)個數(shù)：2n-1-n。5.7 分別畫出圖5.38中的二叉樹的順序存儲結(jié)構(gòu)

36、和二叉鏈表存儲結(jié)構(gòu)的圖示。圖5.38順序存儲結(jié)構(gòu)的圖示：0123456789101112131415272829ABCDE#F#G#H#IJ二叉鏈表存儲結(jié)構(gòu)的圖示：5.8 分別寫出圖5.38中二叉樹的前序、中序和后序遍歷序列。前序遍歷序列：ABDEGCFHIJ中序遍歷序列：DBGEACIHJF后序遍歷序列：DGEBIJHFCA5.9 找出滿足下面條件的二叉樹：（1）前序遍歷與中序遍歷結(jié)果相同（2）前序遍歷和后序遍歷結(jié)果相同（3）中序遍歷和后序遍歷結(jié)果相同（1）只有右分支的單分支樹。（2）只有一個根結(jié)點(diǎn)的二叉樹。（3）只有左分支的單分支樹。5.10 以二叉鏈表為存儲結(jié)構(gòu)，請寫出前序遍歷的非遞歸算

37、法。#define MAXSIZE 100typedef char DataType;typedef struct Node/* 二叉鏈表存儲結(jié)構(gòu) */DataType data; struct Node *lchild,*rchild;BiTree;typedef BiTree* SElemType ;/* 棧中數(shù)據(jù)元素類型，棧中保存結(jié)點(diǎn)指針 */typedef struct SElemType dataMAXSIZE; int top;SeqStack;/* 棧的類型定義，順序棧 */* 棧的基本操作的實(shí)現(xiàn) */SeqStack *initSeqStack()/*初始化棧*/ SeqSta

38、ck *s;/*首先建立?？臻g，然后初始化棧頂指針*/ s=(SeqStack*)malloc(sizeof(SeqStack); s-top= -1; return s;int push (SeqStack *s, SElemType x) if (s-top=MAXSIZE-1) /*棧滿不能入棧*/printf(overflow); return 0; s-top+; s-datas-top=x; return 1;void pop (SeqStack *s) /*出棧，假設(shè)棧不空*/ s-top-; int empty (SeqStack *s) if (s-top= -1) retu

39、rn 1; else return 0; SElemType top (SeqStack *s) /*設(shè)棧不空*/return (s-datas-top ); void PreOrderFei(BiTree *p)/* 前序遍歷二叉樹的非遞歸算法 */SeqStack *s; s=initSeqStack(); while(1) while(p) printf(%c, p-data); push(s,p); p=p-lchild;/*先訪問結(jié)點(diǎn)，后壓棧*/ if (empty(s) break; p=top(s);pop(s); p=p-rchild; 5.11 引入線索二叉樹的目的是什么？n

40、個結(jié)點(diǎn)的線索二叉樹上含有多少條線索？有效利用空指針域，提高遍歷運(yùn)算的效率，簡化遍歷算法。n個結(jié)點(diǎn)的線索二叉樹上含有n+1條線索。5.12 設(shè)一棵二叉樹的中序、后序遍歷序列分別為： G L D H B E I A C J F K和L G H D I E B J K F C A，請回答：（1）畫出二叉樹邏輯結(jié)構(gòu)的圖示。（2）畫出上題中二叉樹的中序線索二叉樹。（3）畫出中序線索二叉鏈表存儲結(jié)構(gòu)圖示并給出C語言描述。（4）給出利用中序線索求結(jié)點(diǎn)中序后繼的算法。（1）（2）（3）（4）typedef char DataType; typedef struct NodeDataType data; str

41、uct Node *lchild,*rchild; int ltag,rtag;BiThrTree;BiThrTree * InOrderNext(BiThrTree *p)/* 求中序后繼 */if(p-rtag=1) p=p-rchild; /*分兩種情況查找結(jié)點(diǎn)后繼 */ elsep=p-rchild; while(p-ltag=0) p=p-lchild; return p;5.13 以二叉鏈表為存儲結(jié)構(gòu)，設(shè)計(jì)一個求二叉樹高度的算法。typedef char DataType;typedef struct Node/* 二叉鏈表存儲結(jié)構(gòu) */DataType data; struct

42、Node *lchild,*rchild;BiTree;int height(BiTree *T)/* 求樹高 */int i,j; if(!T) return 0; i=height(T-lchild);/*求左子樹的高度*/ j=height(T-rchild);/*求右子樹的高度*/ return ij?i+1:j+1;/*二叉樹的高度為左右子樹中較高的高度加1*/5.14 試設(shè)計(jì)一個算法，根據(jù)二叉樹的前序序列和中序序列創(chuàng)建一棵二叉樹。算法思想：（1） 確定二叉樹的根節(jié)點(diǎn)。樹根是二叉樹前序遍歷的第一個元素。（2） 求解二叉樹的左右子樹。找出根結(jié)點(diǎn)在中序遍歷中的位置，根左邊的所有元素是左子

43、樹，根右邊的所有元素是右子樹。若根結(jié)點(diǎn)左邊或右邊為空，則該方向子樹為空；若根結(jié)點(diǎn)左邊和右邊都為空，則此結(jié)點(diǎn)為葉子節(jié)點(diǎn)。（3） 遞歸求解樹。將左子樹和右子樹分別看成一棵二叉樹，重復(fù)（1）（2）（3）步，直到所有的結(jié)點(diǎn)完成定位。typedef char DataType;typedef struct Node/* 二叉鏈表存儲結(jié)構(gòu) */DataType data; struct Node *lchild,*rchild;BiTree;charpre50=ABDHLEKCFG;/全局變量-前序序列charmid50=HLDBEKAFCG;/中序序列intposition(charc)/*求解字符在中

44、序遍歷序列中的位置*/returnstrchr(mid,c)-mid;/* strchr() #include 功能：查找字符串s中首次出現(xiàn)字符c的位置（指針)，如果s中不存在c則返回NULL。*/voidpreMidCreateTree(BiTree *p,inti,intj,intlen)/* i:子樹的前序序列的首字符在pre中的下標(biāo) j:子樹的中序序列的首字符在mid中的下標(biāo)len:子樹的遍歷序列長度，即子樹中的字符數(shù)*/intm;if(lendata=prei;m=position(prei);preMidCreateTree(p-left,i+1,j,m-j);/m-j為左子樹字符

45、數(shù)preMidCreateTree(p-right,i+(m-j)+1,m+1,len-1-(m-j);/len-1-(m-j)為右子樹字符數(shù)void main()BiTree *root=NULL; preMidCreateTree(root,0,0,strlen(mid);5.15 請畫出5.37中的樹對應(yīng)的二叉樹。5.16 請畫出5.39中的各二叉樹對應(yīng)的森林。圖5.395.17 設(shè)森林F對應(yīng)的二叉樹為B，它有m個結(jié)點(diǎn)，B的根為p，p的右子樹結(jié)點(diǎn)個數(shù)為n，森林F中第一棵樹的結(jié)點(diǎn)個數(shù)是多少？m-n。5.18 假設(shè)用于通信的電文由字符集a，b，c，d，e，f，g，h中的字母構(gòu)成，這8個字母在

46、電文中出現(xiàn)的概率分別為0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。（1）為這8個字母設(shè)計(jì)Huffman編碼。（2）求出哈夫曼樹的帶權(quán)路徑長度WPL。（3）若用三位二進(jìn)制數(shù)對這8個字母進(jìn)行等長編碼，則Huffman編碼的平均碼長是等長編碼的百分之幾？（1）哈夫曼樹： 對應(yīng)的哈夫曼編碼：字符編碼a1010b00c10000d1001e11f10001g01h1011（2）帶權(quán)路徑長度為：=0.074+0.192+0.025+0.064+0.322+0.035+0.212+0.104=2.61（3）2.61/3*100%=87%6 圖6.1 回答下列概念：完全圖、子圖、連通分量、網(wǎng)絡(luò)、最小生成樹、拓?fù)湫蛄?完全圖：任意兩個頂點(diǎn)之間都有邊的圖。子 圖：設(shè)有圖G=(V,E)，若V是V的子集(VV)，E是E的子集(EE)，且E中的邊所鄰接的點(diǎn)均在V中出現(xiàn)，則G=(V,E)也是一個圖，并且稱之為G的子圖。連通分量：無向圖G的極大連通子圖。網(wǎng) 絡(luò)：邊上帶權(quán)的圖。最小生成樹：連通網(wǎng)絡(luò)的所有生成樹中邊上權(quán)值之和最小的生成樹。拓?fù)湫蛄校河邢驘o環(huán)圖中所有頂點(diǎn)按照拓?fù)渑判虻乃枷肱懦傻囊粋€線性序列。6.2 n個頂點(diǎn)的無向圖，若采用鄰接矩陣為存儲結(jié)構(gòu)，如何求邊的條數(shù)？如何求某個頂點(diǎn)的度？如果該圖為有向圖呢？無向圖的鄰接矩陣是對稱的，“1”的個數(shù)則是圖中邊的條數(shù)的2倍，第i