線性表是一個有限序列可以為空 2 在一個長度為n的順序表中刪除第

1、1. 線性表是一個有限序列，可以為空2. 在一個長度為n的順序表中刪除第i個元素(0<=i<=n)時，需向前移動n-i個元素。3. 線性表采用鏈?zhǔn)酱鎯r，其地址連續(xù)與否均可以 4. 從一個具有n個結(jié)點的單鏈表中查找其值等于x的結(jié)點時，在查找成功的情況下，需平均比較（n+1）/2個元素結(jié)點。5. 在雙向循環(huán)鏈表中，在p所指的結(jié)點之后插入s指針?biāo)傅慕Y(jié)點，其操作是 s->prior=p; s->next=p->next;p->next->prior=s; p->next=s;6. 設(shè)單鏈表中指針p指向結(jié)點m，若要刪除m之后的結(jié)點（若存在），則需修改指

2、針的操作為p->next=p->next->next7. 在一個長度為n的順序表中向第i個元素(0< i<n+l )之前插入一個新元素時，需向后移動n-i+l個元素。8. 在一個單鏈表中，已知q結(jié)點是p結(jié)點的前趨結(jié)點，若在q和p之間插入s結(jié)點，則須執(zhí)行q->next=s; s->next=p9. 以下關(guān)于線性表的說法不正確的是線性表中的每個結(jié)點都有且只有一個直接前趨和直接后繼。  10. 線性表的順序存儲結(jié)構(gòu)是一種隨機(jī)存取的存儲結(jié)構(gòu)。  11. 在順序表中，只要知道基地址和結(jié)點大小，就可在相同時間內(nèi)求出任一結(jié)點的存儲地址。12. 在

3、等概率情況下，順序表的插入操作要移動一半結(jié)點。  13. 在根據(jù)序號查找運(yùn)算中，使用順序表比鏈表好。  14. 在一個具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并保持該表有序的時間復(fù)雜度是O(n)。  15. 設(shè)有一個棧，元素的進(jìn)棧次序為A, B, C, D, E,下列是不可能的出棧序列E, A, B, C, D。16. 在一個具有n個單元的順序棧中，假定以地址低端（即0單元）作為棧底，以top作為棧頂指針，當(dāng)做出棧處理時，top變化為 top-。17. 向一個棧頂指針為hs的鏈棧中插入一個s結(jié)點時，應(yīng)執(zhí)行s->next=hs; hs=s;。18. 在具有n個

4、單元的順序存儲的循環(huán)隊列中，假定front和rear分別為隊頭指針和隊尾指針，則判斷隊滿的條件為(rear+l)n= = front。19. 在具有n個單元的順序存儲的循環(huán)隊列中，假定front和rear分別為隊頭指針和隊尾指針，則判斷隊空的條件為rear= = front。20. 在一個鏈隊列中，假定front和rear分別為隊首和隊尾指針，則刪除一個結(jié)點的操作為front=front->next。1. 在一棵度為3的樹中，度為3的結(jié)點數(shù)為2個，度為2的結(jié)點數(shù)為1個，度為1的結(jié)點數(shù)為2個，則度為0的結(jié)點數(shù)為（6）個。2. 假設(shè)在一棵二叉樹中，雙分支結(jié)點數(shù)為15，單分支結(jié)點數(shù)為30個，則

5、葉子結(jié)點數(shù)為（16）個。3. 假定一棵三叉樹的結(jié)點數(shù)為50，則它的最小高度為（5）。4. 在一棵二叉樹上第4層的結(jié)點數(shù)最多為（8）。5. 用順序存儲的方法將完全二叉樹中的所有結(jié)點逐層存放在數(shù)組中R1.n，結(jié)點Ri若有左孩子，其左孩子的編號為結(jié)點（R2i）。6. 由權(quán)值分別為3,8,6,2,5的葉子結(jié)點生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（53）。7. 線索二叉樹是一種（物理）結(jié)構(gòu)。8. 線索二叉樹中，結(jié)點p沒有左子樹的充要條件是（p->ltag=1）。9. 設(shè)n , m 為一棵二叉樹上的兩個結(jié)點，在中序遍歷序列中n在m前的條件是（n在m 左方）。 10. 如果F是由有序樹T轉(zhuǎn)換而來的二叉

6、樹，那么T中結(jié)點的前序就是F中結(jié)點的（前序）。11. 欲實現(xiàn)任意二叉樹的后序遍歷的非遞歸算法而不必使用棧，最佳方案是二叉樹采用（三叉鏈表）存儲結(jié)構(gòu)。12. 下面敘述正確的是（二叉樹的左右子樹有次序之分）。13. 任何一棵二叉樹的葉子結(jié)點在先序、中序和后序遍歷序列中的相對次序（不發(fā)生改變）。14. 已知一棵完全二叉樹的結(jié)點總數(shù)為9個，則最后一層的結(jié)點數(shù)為（2）。15. 根據(jù)先序序列ABDC和中序序列DBAC確定對應(yīng)的二叉樹，該二叉樹（是完全二叉樹）。1. 線性表是一種典型的（線性）結(jié)構(gòu)。2. 在一個長度為n的順序表的第i個元素之前插入一個元素，需要后移（n-i+1）個元素。3. 順序表中邏輯上相

7、鄰的元素的物理位置（相鄰）。4. 要從一個順序表刪除一個元素時，被刪除元素之后的所有元素均需（前移）一個位置，移動過程是從（前）向（后）依次移動每一個元素。5. 在線性表的順序存儲中，元素之間的邏輯關(guān)系是通過（物理存儲位置）決定的；在線性表的鏈接存儲中，元素之間的邏輯關(guān)系是通過（鏈域的指針值）決定的。6. 在雙向鏈表中，每個結(jié)點含有兩個指針域，一個指向（前趨）結(jié)點，另一個指向（后繼）結(jié)點。7. 當(dāng)對一個線性表經(jīng)常進(jìn)行存取操作，而很少進(jìn)行插入和刪除操作時，則采用（順序）存儲結(jié)構(gòu)為宜。相反，當(dāng)經(jīng)常進(jìn)行的是插入和刪除操作時，則采用（鏈接）存儲結(jié)構(gòu)為宜。8. 順序表中邏輯上相鄰的元素，物理位置（一定）

8、相鄰，單鏈表中邏輯上相鄰的元素，物理位置（不一定）相鄰。9. 線性表、棧和隊列都是（線性）結(jié)構(gòu)，可以在線性表的（任何）位置插入和刪除元素；對于棧只能在（棧頂）位置插入和刪除元素；對于隊列只能在（隊尾）位置插入元素和在（隊頭）位置刪除元素。10. 根據(jù)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中每個結(jié)點所含指針的個數(shù)，鏈表可分為（單鏈表）和（雙鏈表）；而根據(jù)指針的聯(lián)接方式，鏈表又可分為（非循環(huán)鏈表）和（循環(huán)鏈表）。11. 在單鏈表中設(shè)置頭結(jié)點的作用是（使空表和非空表統(tǒng)一；算法處理一致）。12. 對于一個具有n個結(jié)點的單鏈表，在已知的結(jié)點p后插入一個新結(jié)點的時間復(fù)雜度為（ O(1)），在給定值為x的結(jié)點后插入一個新結(jié)點

9、的時間復(fù)雜度為（ O(n)）。13. 對于一個棧作進(jìn)棧運(yùn)算時，應(yīng)先判別棧是否為（棧滿），作退棧運(yùn)算時，應(yīng)先判別棧是否為（?？眨?，當(dāng)棧中元素為m時，作進(jìn)棧運(yùn)算時發(fā)生上溢，則說明棧的可用最大容量為（m ）。為了增加內(nèi)存空間的利用率和減少發(fā)生上溢的可能性，由兩個棧共享一片連續(xù)的內(nèi)存空間時，應(yīng)將兩棧的（棧底）分別設(shè)在這片內(nèi)存空間的兩端，這樣只有當(dāng)（兩個棧的棧頂在?？臻g的某一位置相遇）時才產(chǎn)生上溢。14. 設(shè)有一空棧，現(xiàn)有輸入序列1，2，3，4，5，經(jīng)過push, push, pop, push, pop, push, push后，輸出序列是（2、）。15. 無論對于順序存儲還是鏈?zhǔn)酱鎯Φ臈：完犃衼碚f，

10、進(jìn)行插入或刪除運(yùn)算的時間復(fù)雜度均相同為（ O(1)）。1. 假定一棵樹的廣義表表示為A（B（E），C（F（H，I，J），G），D），則該樹的度為 (3)，樹的深度為 (4)，終端結(jié)點的個數(shù)為 (6)，單分支結(jié)點的個數(shù)為 (1)，雙分支結(jié)點的個數(shù)為 (1)，三分支結(jié)點的個數(shù)為 (2)，C結(jié)點的雙親結(jié)點為 (A)，其孩子結(jié)點為 (F)和 (G)結(jié)點。2. 設(shè)F是一個森林，B是由F轉(zhuǎn)換得到的二叉樹，F(xiàn)中有n個非終端結(jié)點，則B中右指針域為空的結(jié)點有 (n+1)個。3. 對于一個有n個結(jié)點的二叉樹，當(dāng)它為一棵 (完全)二叉樹時具有最小高度，即為 ()，當(dāng)它為一棵單支樹具有 (最大)高度，即為 (n)。4

11、. 由帶權(quán)為3，9，6，2，5的5個葉子結(jié)點構(gòu)成一棵哈夫曼樹，則帶權(quán)路徑長度為(55)。5. 在一棵二叉排序樹上按 (中序)遍歷得到的結(jié)點序列是一個有序序列。6. 對于一棵具有n個結(jié)點的二叉樹，當(dāng)進(jìn)行鏈接存儲時，其二叉鏈表中的指針域的總數(shù)為 (2n)個，其中 (n-1)個用于鏈接孩子結(jié)點， (n+1)個空閑著。7. 在一棵二叉樹中，度為0的結(jié)點個數(shù)為n0，度為2的結(jié)點個數(shù)為n2，則n0= ( n2+1)。8. 一棵深度為k的滿二叉樹的結(jié)點總數(shù)為_(2k-1)_，一棵深度為k的完全二叉樹的結(jié)點總數(shù)的最小值為2k-1，最大值為 (2k-1)。9. 由三個結(jié)點構(gòu)成的二叉樹，共有 (5)種不同的形態(tài)。

12、10. 設(shè)高度為h的二叉樹中只有度為0和度為2的結(jié)點，則此類二叉樹中所包含的結(jié)點數(shù)至少為 (2h-1)。11. 一棵含有n個結(jié)點的k叉樹， (單支樹)形態(tài)達(dá)到最大深度， (完全二叉樹)形態(tài)達(dá)到最小深度。12. 對于一棵具有n個結(jié)點的二叉樹，若一個結(jié)點的編號為i(1in)，則它的左孩子結(jié)點的編號為 (2i)，右孩子結(jié)點的編號為 (2i+1)，雙親結(jié)點的編號為 (i/2)。13. 對于一棵具有n個結(jié)點的二叉樹，采用二叉鏈表存儲時，鏈表中指針域的總數(shù)為 (2n)個，其中 ( n-1)個用于鏈接孩子結(jié)點， (n+1)個空閑著。14. 哈夫曼樹是指 (帶權(quán)路徑長度最小) 的二叉樹。15. 空樹是指 (結(jié)

13、點數(shù)為0 )，最小的樹是指 (只有一個根結(jié)點的樹)。16. 二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)有 (二叉鏈表)和(三叉鏈表)兩種。17. 三叉鏈表比二叉鏈表多一個指向(雙親結(jié)點)的指針域。18. 線索是指 (指向結(jié)點前驅(qū)和后繼信息的指針)。19. 線索鏈表中的rtag域值為 (1)時，表示該結(jié)點無右孩子，此時 (RChild )域為指向該結(jié)點后繼線索的指針。20. 本節(jié)中我們學(xué)習(xí)的樹的存儲結(jié)構(gòu)有 (孩子表示法)、 (雙親表示法)和 (長子兄弟表示法)。1. 描述以下三個概念的區(qū)別：頭指針，頭結(jié)點，表頭結(jié)點。頭指針是指向鏈表中第一個結(jié)點（即表頭結(jié)點）的指針；在表頭結(jié)點之前附設(shè)的結(jié)點稱為頭結(jié)點；表頭結(jié)點為鏈表中

14、存儲線性表中第一個數(shù)據(jù)元素的結(jié)點。若鏈表中附設(shè)頭結(jié)點，則不管線性表是否為空表，頭指針均不為空，否則表示空表的鏈表的頭指針為空。2. 線性表的兩種存儲結(jié)構(gòu)各有哪些優(yōu)缺點？線性表具有兩種存儲結(jié)構(gòu)即順序存儲結(jié)構(gòu)和鏈接存儲結(jié)構(gòu)。線性表的順序存儲結(jié)構(gòu)可以直接存取數(shù)據(jù)元素，方便靈活、效率高，但插入、刪除操作時將會引起元素的大量移動，因而降低效率：而在鏈接存儲結(jié)構(gòu)中內(nèi)存采用動態(tài)分配，利用率高，但需增設(shè)指示結(jié)點之間關(guān)系的指針域，存取數(shù)據(jù)元素不如順序存儲方便，但結(jié)點的插入、刪除操作較簡單。3. 對于線性表的兩種存儲結(jié)構(gòu)，如果有n個線性表同時并存，而且在處理過程中各表的長度會動態(tài)發(fā)生變化，線性表的總數(shù)也會自動改變

15、，在此情況下，應(yīng)選用哪一種存儲結(jié)構(gòu)？為什么？應(yīng)選用鏈接存儲結(jié)構(gòu)，因為鏈?zhǔn)酱鎯Y(jié)構(gòu)是用一組任意的存儲單元依次存儲線性表中的各元素，這里存儲單元可以是連續(xù)的，也可以是不連續(xù)的：這種存儲結(jié)構(gòu)對于元素的刪除或插入運(yùn)算是不需要移動元素的，只需修改指針即可，所以很容易實現(xiàn)表的容量的擴(kuò)充。4. 對于線性表的兩種存儲結(jié)構(gòu)，若線性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表中的元素，應(yīng)選用何種存儲結(jié)構(gòu)？試說明理由。應(yīng)選用順序存儲結(jié)構(gòu)，因為每個數(shù)據(jù)元素的存儲位置和線性表的起始位置相差一個和數(shù)據(jù)元素在線性表中的序號成正比的常數(shù)。因此，只要確定了其起始位置，線性表中的任一個數(shù)據(jù)元素都可隨機(jī)

16、存取，因此，線性表的順序存儲結(jié)構(gòu)是一種隨機(jī)存取的存儲結(jié)構(gòu)，而鏈表則是一種順序存取的存儲結(jié)構(gòu)。5. 在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置頭指針好嗎？為什么?設(shè)尾指針比設(shè)頭指針好。尾指針是指向終端結(jié)點的指針，用它來表示單循環(huán)鏈表可以使得查找鏈表的開始結(jié)點和終端結(jié)點都很方便，設(shè)一帶頭結(jié)點的單循環(huán)鏈表，其尾指針為rear，則開始結(jié)點和終端結(jié)點的位置分別是rear->next->next 和 rear, 查找時間都是O(1)。若用頭指針來表示該鏈表，則查找終端結(jié)點的時間為O(n)。6. 假定有四個元素A, B, C, D依次進(jìn)棧，進(jìn)棧過程中允許出棧，試寫出所有可能的出棧序列。共有14種可能的出棧序

17、列，即為：ABCD, ABDC，ACBD, ACDB，BACD，ADCB，BADC，BCAD, BCDA，BDCA,CBAD, CBDA，CDBA, DCBA7. 什么是隊列的上溢現(xiàn)象？一般有幾種解決方法，試簡述之。在隊列的順序存儲結(jié)構(gòu)中，設(shè)隊頭指針為front，隊尾指針為rear，隊列的容量（即存儲的空間大小）為maxnum。當(dāng)有元素要加入隊列（即入隊）時，若rear=maxnum，則會發(fā)生隊列的上溢現(xiàn)象，此時就不能將該元素加入隊列。對于隊列，還有一種“假溢出”現(xiàn)象，隊列中尚余有足夠的空間，但元素卻不能入隊，一般是由于隊列的存儲結(jié)構(gòu)或操作方式的選擇不當(dāng)所致，可以用循環(huán)隊列解決。一般地，要解決

18、隊列的上溢現(xiàn)象可有以下幾種方法：（1）可建立一個足夠大的存儲空間以避免溢出，但這樣做往往會造成空間使用率低，浪費存儲空間。（2）要避免出現(xiàn)“假溢出”現(xiàn)象可用以下方法解決：第一種：采用移動元素的方法。每當(dāng)有一個新元素入隊，就將隊列中已有的元素向隊頭移動一個位置，假定空余空間足夠。第二種：每當(dāng)刪去一個隊頭元素，則可依次移動隊列中的元素總是使front指針指向隊列中的第一個位置。第三種：采用循環(huán)隊列方式。將隊頭、隊尾看作是一個首尾相接的循環(huán)隊列，即用循環(huán)數(shù)組實現(xiàn)，此時隊首仍在隊尾之前，作插入和刪除運(yùn)算時仍遵循“先進(jìn)先出”的原則。8. 下述算法的功能是什么?LinkList *Demo(LinkLis

19、t *L) / L是無頭結(jié)點的單鏈表LinkList *q,*p;if(L&&L->next) q=L; L=L->next; p=L;while (p->next) p=p->next; p->next=q; q->next=NULL;return (L);將開始結(jié)點摘下鏈接到終端結(jié)點之后成為新的終端結(jié)點，而原來的第二個結(jié)點成為新的開始結(jié)點，返回新鏈表的頭指針。1. 設(shè)計在無頭結(jié)點的單鏈表中刪除第i個結(jié)點的算法。delete(LinkList *q,int i) /在無頭結(jié)點的單鏈表中刪除第i個結(jié)點 LinkList *p,*s; int

20、j; if(i<0) printf("Can't delete"); else if(i= =0) s=q; q=q->next; free(s); else j=0; s=q; while(j<i) && (s! = NULL) p=s; s=s->next;j+;if (s= =NULL) printf("Cant't delete"); else p->next=s->next; free(s); 2. 在單鏈表上實現(xiàn)線性表的求表長ListLength(L)運(yùn)算。int ListL

21、ength ( LinkList *L ) /求帶頭結(jié)點的單鏈表的表長 int len=0; ListList *p; p=L; while ( p->next!=NULL ) p=p->next;len+; return (len);3. 設(shè)計將帶表頭的鏈表逆置算法。void invert(LinkList *head) /逆置head指針?biāo)赶虻膯窝h(huán)鏈表linklist *p, *q, *s; q=head; p=head->next; while (p!=head) /當(dāng)表不為空時，逐個結(jié)點逆置 s=q; q=p; p=p->next; q->next=s

22、; p->next=q; 4. 假設(shè)有一個帶表頭結(jié)點的鏈表，表頭指針為head，每個結(jié)點含三個域：data, next和prior。其中data為整型數(shù)域，next和prior均為指針域?，F(xiàn)在所有結(jié)點已經(jīng)由next域連接起來，試編一個算法，利用prior域（此域初值為NULL）把所有結(jié)點按照其值從小到大的順序鏈接起來。insert (LinkList *head) LinkList *p,*s,*q; p=head->next; /p指向待插入的結(jié)點，初始時指向第一個結(jié)點 while(p!=NULL) s=head; / s指向q結(jié)點的前趨結(jié)點 q=head->prior;

23、/q指向由prior域構(gòu)成的鏈表中待比較的結(jié)點 while(q!=NULL) && (p->data>q->data) /查找插入結(jié)點p的合適的插入位置 s=q; q=q->prior; s->prior=p; p->prior=q; /結(jié)點p插入到結(jié)點s和結(jié)點q之間 p=p->next;5. 已知線性表的元素按遞增順序排列，并以帶頭結(jié)點的單鏈表作存儲結(jié)構(gòu)。試編寫一個刪除表中所有值大于min且小于max的元素（若表中存在這樣的元素）的算法。delete(LinkList *head, int max, int min) linklist

24、 *p, *q; if (head!=NULL) q=head; p=head->next; while(p!=NULL) && (p->data<=min) q=p;p=p->next;while(p!=NULL) && (p->data<max) p=p->next; q->next=p;6. 已知線性表的元素是無序的，且以帶頭結(jié)點的單鏈表作為存儲結(jié)構(gòu)。設(shè)計一個刪除表中所有值小于max但大于min的元素的算法。delete(LinkList *head, int max, int min) LinkList *

25、p,*q; q=head; p=head->next; while (p!=NULL) if(p->data<=min) | (p->data>=max) q=p; p=p->next; else q->next=p->next;free(p);p=q->next; 7. 假定用一個單循環(huán)鏈表來表示隊列（也稱為循環(huán)隊列），該隊列只設(shè)一個隊尾指針，不設(shè)隊首指針，試編寫下列各種運(yùn)算的算法：（1）向循環(huán)鏈隊列插入一個元素值為x的結(jié)點；insert(LinkList *rear, elemtype x) /設(shè)循環(huán)鏈隊列的隊尾指針為rear,x為待插

26、入的元素 LinkList *p;p=(LinkList *)malloc(sizeof(LinkList);if(rear= =NULL) /如為空隊，建立循環(huán)鏈隊列的第一個結(jié)點 rear=p;rear->next=p; /鏈接成循環(huán)鏈表else /否則在隊尾插入p結(jié)點 p->next=rear->next;rear->next=p; rear=p;（2）從循環(huán)鏈隊列中刪除一個結(jié)點。delete(LinkList *rear) /設(shè)循環(huán)鏈隊列的隊尾指針為rearif (rear= =NULL) /空隊 printf("underflown"); i

27、f(rear->next= =rear) /隊中只有一個結(jié)點rear=NULL;elserear->next=rear->next->next; /rear->next指向的結(jié)點為循環(huán)鏈隊列的隊頭結(jié)點8. 設(shè)順序表L是一個遞減有序表，試寫一算法，將x插入其后仍保持L的有序性。int InsertDecreaseList( SqList *L, elemtype x ) int i;if ( (*L).len>= maxlen) printf(“overflow");return(0);for ( i=(*L).len ; i>0 &&

28、amp; (*L).elem i-1 < x ; i-) (*L).elem i =(*L).elem i-1 ; / 比較并移動元素 (*L).elem i =x; (*L).len+;return(1);1. 二叉樹中每個結(jié)點的度不能超過2，所以二叉樹是一種特殊的樹。（×）2. 二叉樹的前序遍歷中，任意結(jié)點均處在其子女結(jié)點之前。（）3. 線索二叉樹是一種邏輯結(jié)構(gòu)。（×）4. 哈夫曼樹的總結(jié)點個數(shù)（多于1時）不能為偶數(shù)。（）5. 由二叉樹的先序序列和后序序列可以唯一確定一顆二叉樹。（×）6. 樹的后序遍歷與其對應(yīng)的二叉樹的后序遍歷序列相同。（）7. 根據(jù)任

29、意一種遍歷序列即可唯一確定對應(yīng)的二叉樹。（）8. 滿二叉樹也是完全二叉樹。（）9. 哈夫曼樹一定是完全二叉樹。（×）10. 樹的子樹是無序的。（×）1. 已知一棵樹邊的集合為<i，m>，<i，n>，<e，i>，<b，e>，<b，d>，<a，b>，<g，j>，<g，k>，<c，g>，<c，f>，<h，l>，<c，h>，<a，c>，請畫出這棵樹，并回答下列問題：（1）哪個是根結(jié)點？a（2）哪些是葉子結(jié)點？d、m、n、j、k、

30、f、l（3）哪個是結(jié)點g的雙親？c是結(jié)點g的雙親（4）哪些是結(jié)點g的祖先？a、c是結(jié)點g的祖先（5）哪些是結(jié)點g的孩子？j、k是結(jié)點g的孩子（6）哪些是結(jié)點e的孩子？m、n是結(jié)點e的子孫（7）哪些是結(jié)點e的兄弟？哪些是結(jié)點f的兄弟？e是結(jié)點d的兄弟；g、h是結(jié)點f的兄弟（8）結(jié)點b和n的層次號分別是什么？2和5（9）樹的深度是多少？5（10）以結(jié)點c為根的子樹深度是多少？32. 一棵度為2的樹與一棵二叉樹有何區(qū)別。度為2的樹有兩個分支，但分支沒有左右之分；一棵二叉樹也有兩個分支，但有左右之分，左右子樹不能交換。4. 已知用一維數(shù)組存放的一棵完全二叉樹：ABCDEFGHIJKL，寫出該二叉樹的先

31、序、中序和后序遍歷序列。先序序列：ABDHIEJKCFLG中序序列：HDIBJEKALFCG后序序列：HIDJKEBLFGCA5. 一棵深度為H的滿k叉樹有如下性質(zhì)：第H層上的結(jié)點都是葉子結(jié)點，其余各層上每個結(jié)點都有k棵非空子樹，如果按層次自上至下，從左到右順序從1開始對全部結(jié)點編號，回答下列問題：（1）各層的結(jié)點數(shù)目是多少？第i層上的結(jié)點數(shù)目是mi-1（2）編號為n的結(jié)點的父結(jié)點如果存在，編號是多少？編號為n的結(jié)點的父結(jié)點如果存在，編號是(n-2)/m)+1（3）編號為n的結(jié)點的第i個孩子結(jié)點如果存在，編號是多少？編號為n的結(jié)點的第i個孩子結(jié)點如果存在，編號是(n-1)*m+i+1（4）編號

32、為n的結(jié)點有右兄弟的條件是什么？其右兄弟的編號是多少？編號為n的結(jié)點有右兄弟的條件是(n-1)%m0。其右兄弟的編號是n+16. 找出所有滿足下列條件的二叉樹：（1）它們在先序遍歷和中序遍歷時，得到的遍歷序列相同；（2）它們在后序遍歷和中序遍歷時，得到的遍歷序列相同；（3）它們在先序遍歷和后序遍歷時，得到的遍歷序列相同；（1）先序序列和中序序列相同的二叉樹為：空樹或者任一結(jié)點均無左孩子的非空二叉樹；（2）中序序列和后序序列相同的二叉樹為：空樹或者任一結(jié)點均無右孩子的非空二叉樹；（3）先序序列和后序序列相同的二叉樹為：空樹或僅有一個結(jié)點的二叉樹。7. 假設(shè)一棵二叉樹的先序序列為EBADCFHGI

33、KJ，中序序列為ABCDEFGHIJK，請寫出該二叉樹的后序遍歷序列。后序序列：ACDBGJKIHFE8. 假設(shè)一棵二叉樹的后序序列為DCEGBFHKJIA，中序序列為DCBGEAHFIJK，請寫出該二叉樹的后序遍歷序列。先序序列：ABCDGEIHFJKBGDCHKEIFJLMNOA圖5-169. 給出如圖5-14所示的森林的先根、后根遍歷結(jié)點序列，然后畫出該森林對應(yīng)的二叉樹。先根遍歷：ABCDEFGHIJKLMNO后根遍歷：BDEFCAHJIGKNOML10給定一組權(quán)值（5，9，11，2，7，16），試設(shè)計相應(yīng)的哈夫曼樹。ABDEFCGHJIKNOML圖5-1450 92030111614

34、7 7 2 5圖5-17答：五、算法設(shè)計題1. 一棵具有n個結(jié)點的完全二叉樹以一維數(shù)組作為存儲結(jié)構(gòu)，試設(shè)計一個對該完全二叉樹進(jìn)行先序遍歷的算法。preorder (R) /先序遍歷二叉樹Rint Rn; int root;SqStack *s; /s為一個指針棧，類型為seqstack，其中包含top域和數(shù)組datas->top= -1; /s棧置空root=1;while (root<=n) && (s->top>-1) while (root<=n) printf(Rroot); s->top+;s->datas->top=r

35、oot;root=2*root; if (s->top>-1) /棧非空訪問，遍歷右子樹 root=s->datas->top*2+1; s->top-;2. 給定一棵用二叉鏈表表示的二叉樹，其中的指針t指向根結(jié)點，試寫出從根開始，按層次遍歷二叉樹的算法，同層的結(jié)點按從左至右的次序訪問。1開始，同層結(jié)點從左到右存放。算法中的front為隊頭指針，rear為隊尾指針。levelorder (BiTree *t) /按層次遍歷二叉樹t BiTree *quemaxnum;int rear,front;if (t!=NULL) front=0; /置空隊列rear=1;que1=t;do front=front%maxsize+1; /出隊 t=quefront; printf(t->data); if (t->lchild!=NULL) /左子樹的根結(jié)點入隊 rear=rear%maxsize+1; querear=t->lchild; if (t-&