數(shù)據(jù)結(jié)構(gòu)課后習(xí)題答案

1、精選優(yōu)質(zhì)文檔-傾情為你奉上第 1 章 緒 論 1. 填空 在順序表中，等概率情況下，插入和刪除一個元素平均需移動（ ）個元素，具體移動元素的個數(shù)與（ ）和（ ）有關(guān)?！窘獯稹勘黹L的一半，表長，該元素在表中的位置 順序表中第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的存儲地址是（ ）。【解答】108【分析】第5個元素的存儲地址=第1個元素的存儲地址(51)×2=108 設(shè)單鏈表中指針p 指向結(jié)點A，若要刪除A的后繼結(jié)點（假設(shè)A存在后繼結(jié)點），則需修改指針的操作為（ ）?！窘獯稹縫->next=(p->next)->next 單鏈表中設(shè)置頭結(jié)點的作用是

2、（ ）。【解答】為了運算方便【分析】例如在插入和刪除操作時不必對表頭的情況進行特殊處理。 非空的單循環(huán)鏈表由頭指針head指示，則其尾結(jié)點（由指針p所指）滿足（ ）。【解答】p->next=head【分析】如圖2-8所示。 在由尾指針rear指示的單循環(huán)鏈表中，在表尾插入一個結(jié)點s的操作序列是（ ）；刪除開始結(jié)點的操作序列為（ ）?！窘獯稹縮->next =rear->next; rear->next =s; rear =s;(將S的指針域先弄成表尾指針域，而表尾指針域是代表下個結(jié)點的地址信息，所以要將指針域要用S替代，最后把表尾給S)q=rear->next-&

3、gt;next; rear->next->next=q->next; delete q;【分析】操作示意圖如圖2-9所示： 一個具有n個結(jié)點的單鏈表，在指針p所指結(jié)點后插入一個新結(jié)點的時間復(fù)雜度為（ ）；在給定值為x的結(jié)點后插入一個新結(jié)點的時間復(fù)雜度為（ ）?！窘獯稹?1)，(n)【分析】在p所指結(jié)點后插入一個新結(jié)點只需修改指針，所以時間復(fù)雜度為(1)（是表示常數(shù)計算時間）；而在給定值為x的結(jié)點后插入一個新結(jié)點需要先查找值為x的結(jié)點，所以時間復(fù)雜度為(n)。 可由一個尾指針唯一確定的鏈表有（ ）、（ ）、（ ）?！窘獯稹垦h(huán)鏈表，循環(huán)雙鏈表，雙鏈表2. 選擇題 線性表的順序存

4、儲結(jié)構(gòu)是一種（ ）的存儲結(jié)構(gòu)，線性表的鏈接存儲結(jié)構(gòu)是一種（ ）的存儲結(jié)構(gòu)。 A 隨機存取 B 順序存取 C 索引存取 D 散列存取【解答】A，B【分析】參見2.2.1。 線性表采用鏈接存儲時，其地址（ ）。A 必須是連續(xù)的 B 部分地址必須是連續(xù)的C 一定是不連續(xù)的 D 連續(xù)與否均可以【解答】D【分析】線性表的鏈接存儲是用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素，這組存儲單元可以連續(xù)，也可以不連續(xù)，甚至可以零散分布在內(nèi)存中任意位置。 單循環(huán)鏈表的主要優(yōu)點是（ ）。A 不再需要頭指針了 B 從表中任一結(jié)點出發(fā)都能掃描到整個鏈表；C 已知某個結(jié)點的位置后，能夠容易找到它的直接前驅(qū)；D 在進行插入、刪

5、除操作時，能更好地保證鏈表不斷開。【解答】B 鏈表不具有的特點是（ ）。A 可隨機訪問任一元素 B 插入、刪除不需要移動元素C 不必事先估計存儲空間 D 所需空間與線性表長度成正比【解答】A 若某線性表中最常用的操作是取第i 個元素和找第i個元素的前驅(qū)，則采用（ ）存儲方法最節(jié)省時間。A 順序表 B 單鏈表 C 雙鏈表 D 單循環(huán)鏈表【解答】A【分析】線性表中最常用的操作是取第i 個元素，所以，應(yīng)選擇隨機存取結(jié)構(gòu)即順序表，同時在順序表中查找第i個元素的前驅(qū)也很方便。單鏈表和單循環(huán)鏈表既不能實現(xiàn)隨機存取，查找第i個元素的前驅(qū)也不方便，雙鏈表雖然能快速查找第i個元素的前驅(qū)，但不能實現(xiàn)隨機存取。 若

6、鏈表中最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點和刪除第一個結(jié)點，則采用（ ）存儲方法最節(jié)省時間。A 單鏈表 B 帶頭指針的單循環(huán)鏈表 C 雙鏈表 D 帶尾指針的單循環(huán)鏈表【解答】D【分析】在鏈表中的最后一個結(jié)點之后插入一個結(jié)點需要知道終端結(jié)點的地址，所以，單鏈表、帶頭指針的單循環(huán)鏈表、雙鏈表都不合適，考慮在帶尾指針的單循環(huán)鏈表中刪除第一個結(jié)點，其時間性能是O(1)，所以，答案是D 。 若鏈表中最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點和刪除最后一個結(jié)點，則采用（ ）存儲方法最節(jié)省運算時間。A 單鏈表 B 循環(huán)雙鏈表 C單循環(huán)鏈表 D 帶尾指針的單循環(huán)鏈表【解答】B【分析】在鏈表中的最后一

7、個結(jié)點之后插入一個結(jié)點需要知道終端結(jié)點的地址，所以，單鏈表、單循環(huán)鏈表都不合適，刪除最后一個結(jié)點需要知道終端結(jié)點的前驅(qū)結(jié)點的地址，所以，帶尾指針的單循環(huán)鏈表不合適，而循環(huán)雙鏈表滿足條件。 在具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并仍然有序的時間復(fù)雜度是（ ）。A O(1) B O(n) C O(n2) D O(nlog2n)【解答】B【分析】首先應(yīng)順序查找新結(jié)點在單鏈表中的位置。 對于n個元素組成的線性表，建立一個有序單鏈表的時間復(fù)雜度是（ ）。A O(1) B O(n) C O(n2) D O(nlog2n)【解答】C【分析】該算法需要將n個元素依次插入到有序單鏈表中，而插入每個元素需O(

8、n)。 使用雙鏈表存儲線性表，其優(yōu)點是可以（ ）。A 提高查找速度 B 更方便數(shù)據(jù)的插入和刪除C 節(jié)約存儲空間 D 很快回收存儲空間【解答】B【分析】在鏈表中一般只能進行順序查找，所以，雙鏈表并不能提高查找速度，因為雙鏈表中有兩個指針域，顯然不能節(jié)約存儲空間，對于動態(tài)存儲分配，回收存儲空間的速度是一樣的。由于雙鏈表具有對稱性，所以，其插入和刪除操作更加方便。 在一個單鏈表中，已知q所指結(jié)點是p所指結(jié)點的直接前驅(qū)，若在q和p之間插入s所指結(jié)點，則執(zhí)行（ ）操作。A s->next=p->next; p->next=s; B q->next=s; s->next=p;

9、 C p->next=s->next; s->next=p; D p->next=s; s->next=q;【解答】B【分析】注意此題是在q和p之間插入新結(jié)點，所以，不用考慮修改指針的順序。 在循環(huán)雙鏈表的p所指結(jié)點后插入s所指結(jié)點的操作是（ ）。A p->next=s; s->prior=p; p->next->prior=s; s->next=p->next; B p->next=s; p->next->prior=s; s->prior=p; s->next=p->next;C s-&g

10、t;prior=p; s->next=p->next; p->next=s; p->next->prior=s;D s->prior=p; s->next=p->next; p->next->prior=s; p->next=s【解答】D【分析】在鏈表中，對指針的修改必須保持線性表的邏輯關(guān)系，否則，將違背線性表的邏輯特征，圖2-10給出備選答案C和D的圖解。3. 判斷題 線性表的邏輯順序和存儲順序總是一致的?！窘獯稹垮e。順序表的邏輯順序和存儲順序一致，鏈表的邏輯順序和存儲順序不一定一致。 線性表的順序存儲結(jié)構(gòu)優(yōu)于鏈接存儲結(jié)構(gòu)?！?/p>

11、解答】錯。兩種存儲結(jié)構(gòu)各有優(yōu)缺點。 設(shè)p，q是指針，若p=q，則*p=*q。【解答】錯。p=q只能表示p和q指向同一起始地址，而所指類型則不一定相同。 線性結(jié)構(gòu)的基本特征是：每個元素有且僅有一個直接前驅(qū)和一個直接后繼?！窘獯稹垮e。每個元素最多只有一個直接前驅(qū)和一個直接后繼，第一個元素沒有前驅(qū)，最后一個元素沒有后繼。 在單鏈表中，要取得某個元素，只要知道該元素所在結(jié)點的地址即可，因此單鏈表是隨機存取結(jié)構(gòu)。【解答】錯。要找到該結(jié)點的地址，必須從頭指針開始查找，所以單鏈表是順序存取結(jié)構(gòu)。4請說明順序表和單鏈表各有何優(yōu)缺點，并分析下列情況下，采用何種存儲結(jié)構(gòu)更好些。 若線性表的總長度基本穩(wěn)定，且很少進

12、行插入和刪除操作，但要求以最快的速度存取線性表中的元素。 如果n個線性表同時并存，并且在處理過程中各表的長度會動態(tài)發(fā)生變化。 描述一個城市的設(shè)計和規(guī)劃。【解答】順序表的優(yōu)點： 無需為表示表中元素之間的邏輯關(guān)系而增加額外的存儲空間； 可以快速地存取表中任一位置的元素（即隨機存?。?。順序表的缺點： 插入和刪除操作需移動大量元素； 表的容量難以確定； 造成存儲空間的“碎片”。單鏈表的優(yōu)點： 不必事先知道線性表的長度； 插入和刪除元素時只需修改指針，不用移動元素。單鏈表的缺點： 指針的結(jié)構(gòu)性開銷； 存取表中任意元素不方便，只能進行順序存取。 應(yīng)選用順序存儲結(jié)構(gòu)。因為順序表是隨機存取結(jié)構(gòu)，單鏈表是順序存

13、取結(jié)構(gòu)。本題很少進行插入和刪除操作，所以空間變化不大，且需要快速存取，所以應(yīng)選用順序存儲結(jié)構(gòu)。 應(yīng)選用鏈接存儲結(jié)構(gòu)。鏈表容易實現(xiàn)表容量的擴充，適合表的長度動態(tài)發(fā)生變化。 應(yīng)選用鏈接存儲結(jié)構(gòu)。因為一個城市的設(shè)計和規(guī)劃涉及活動很多，需要經(jīng)常修改、擴充和刪除各種信息，才能適應(yīng)不斷發(fā)展的需要。而順序表的插入、刪除的效率低，故不合適。5算法設(shè)計 設(shè)計一個時間復(fù)雜度為(n)的算法，實現(xiàn)將數(shù)組An中所有元素循環(huán)右移k個位置?！窘獯稹克惴ㄋ枷胝垍⒁娭鹘滩牡谝徽滤枷牖鸹?。下面給出具體算法。分析算法，第一次調(diào)用Reverse函數(shù)的時間復(fù)雜度為O(k)，第二次調(diào)用Reverse函數(shù)的時間復(fù)雜度為O(n-k)，第三次

14、調(diào)用Reverse函數(shù)的時間復(fù)雜度為O(n)，所以，總的時間復(fù)雜度為O(n)。 已知數(shù)組An中的元素為整型，設(shè)計算法將其調(diào)整為左右兩部分，左邊所有元素為奇數(shù)，右邊所有元素為偶數(shù)，并要求算法的時間復(fù)雜度為(n)?！窘獯稹繌臄?shù)組的兩端向中間比較，設(shè)置兩個變量i和j，初始時i=0，j=n-1，若Ai為偶數(shù)并且Aj為奇數(shù)，則將Ai與Aj交換。具體算法如下：分析算法，兩層循環(huán)將數(shù)組掃描一遍，所以，時間復(fù)雜度為(n)。 試編寫在無頭結(jié)點的單鏈表上實現(xiàn)線性表的插入操作的算法，并和帶頭結(jié)點的單鏈表上的插入操作的實現(xiàn)進行比較。【解答】參見2.2.3。 試分別以順序表和單鏈表作存儲結(jié)構(gòu)，各寫一實現(xiàn)線性表就地逆置的

15、算法?！窘獯稹宽樞虮淼哪嬷茫词菍ΨQ元素交換，設(shè)順序表的長度為length，則將表中第i個元素與第length-i-1個元素相交換。具體算法如下：單鏈表的逆置請參見2.2.4算法2-4和算法2-6。 假設(shè)在長度大于1的循環(huán)鏈表中，即無頭結(jié)點也無頭指針，s為指向鏈表中某個結(jié)點的指針，試編寫算法刪除結(jié)點s的前驅(qū)結(jié)點?！窘獯稹坷脝窝h(huán)鏈表的特點，通過指針s可找到其前驅(qū)結(jié)點r以及r的前驅(qū)結(jié)點p，然后將結(jié)點r刪除，如圖2-11所示，具體算法如下： 已知一單鏈表中的數(shù)據(jù)元素含有三類字符：字母、數(shù)字和其他字符。試編寫算法，構(gòu)造三個循環(huán)鏈表，使每個循環(huán)鏈表中只含同一類字符?！窘獯稹吭趩捂湵鞟中依次取元素，

16、若取出的元素是字母，把它插入到字母鏈表B 中，若取出的元素是數(shù)字，則把它插入到數(shù)字鏈表D中，直到鏈表的尾部，這樣表B，D，A中分別存放字母、數(shù)字和其他字符。具體算法如下： 設(shè)單鏈表以非遞減有序排列，設(shè)計算法實現(xiàn)在單鏈表中刪去值相同的多余結(jié)點?！窘獯稹繌念^到尾掃描單鏈表，若當(dāng)前結(jié)點的元素值與后繼結(jié)點的元素值不相等，則指針后移；否則刪除該后繼結(jié)點。具體算法如下： 判斷帶頭結(jié)點的雙循環(huán)鏈表是否對稱?！窘獯稹吭O(shè)工作指針p和q分別指向循環(huán)雙鏈表的開始結(jié)點和終端結(jié)點，若結(jié)點p和結(jié)點q的數(shù)據(jù)域相等，則工作指針p后移，工作指針q前移，直到指針p和指針q指向同一結(jié)點（循環(huán)雙鏈表中結(jié)點個數(shù)為奇數(shù)），或結(jié)點q成為結(jié)

17、點p的前驅(qū)（循環(huán)雙鏈表中結(jié)點個數(shù)為偶數(shù)）。如圖2-12所示。學(xué)習(xí)自測及答案 1. 已知一維數(shù)組A采用順序存儲結(jié)構(gòu)，每個元素占用4個存儲單元，第9個元素的地址為144，則第一個元素的地址是（ ）。A 108 B 180 C 176 D 112【解答】D2在長度為n的線性表中查找值為x的數(shù)據(jù)元素的時間復(fù)雜度為： （ ）。 A O(0) B O(1) C O(n) D O(n2)【解答】C3在一個長度為n的順序表的第i（1in+1）個元素之前插入一個元素，需向后移動（ ）個元素，刪除第i（1in）個元素時，需向前移動（ ）個元素。【解答】n-i+1，n-i 4在單鏈表中，除了頭結(jié)點以外，任一結(jié)點的存

18、儲位置由（ ）指示?！窘獯稹科淝膀?qū)結(jié)點的指針域 5當(dāng)線性表采用順序存儲結(jié)構(gòu)時，其主要特點是（ ）?！窘獯稹窟壿嫿Y(jié)構(gòu)中相鄰的結(jié)點在存儲結(jié)構(gòu)中仍相鄰6在雙鏈表中，每個結(jié)點設(shè)置了兩個指針域，其中一個指向（ ）結(jié)點，另一個指向（ ）結(jié)點。【解答】前驅(qū)，后繼7設(shè)A是一個線性表（a1, a2, , an），采用順序存儲結(jié)構(gòu)，則在等概率的前提下，平均每插入一個元素需要移動的元素個數(shù)為多少？若元素插在ai與ai+1之間（1in）的概率為 ，則平均每插入一個元素所要移動的元素個數(shù)又是多少？【解答】 ，。8線性表存放在整型數(shù)組Aarrsize的前elenum 個單元中，且遞增有序。編寫算法，將元素x插入到線性表的

19、適當(dāng)位置上，以保持線性表的有序性，并且分析算法的時間復(fù)雜度?！窘獯稹勘绢}是在一個遞增有序表中插入元素x，基本思路是從有序表的尾部開始依次取元素與x比較，若大于x，此元素后移一位，再取它前面一個元素重復(fù)上述步驟；否則，找到插入位置，將x插入。具體算法如下：9. 已知單鏈表中各結(jié)點的元素值為整型且遞增有序，設(shè)計算法刪除鏈表中所有大于mink且小于maxk的所有元素，并釋放被刪結(jié)點的存儲空間?！窘獯稹恳驗槭窃谟行騿捂湵砩系牟僮?，所以，要充分利用其有序性。在單鏈表中查找第一個大于mink的結(jié)點和第一個小于maxk的結(jié)點，再將二者間的所有結(jié)點刪除。10設(shè)單循環(huán)鏈表L1，對其遍歷的結(jié)果是：x1, x2,

20、x3, xn-1, xn。請將該循環(huán)鏈表拆成兩個單循環(huán)鏈表L1和L2，使得L1中含有原L1表中序號為奇數(shù)的結(jié)點且遍歷結(jié)果為：x1, x3, ；L2中含有原L1表中序號為偶數(shù)的結(jié)點且遍歷結(jié)果為： , x4, x2?！窘獯稹克惴ㄈ缦拢旱?3 章 特殊線性表棧、隊列和串 課后習(xí)題講解 1. 填空 設(shè)有一個空棧，棧頂指針為1000H，現(xiàn)有輸入序列為1、2、3、4、5， 經(jīng)過push，push，pop，push，pop，push，push后，輸出序列是（ ），棧頂指針為（ ）?！窘獯稹?3，1003H 棧通常采用的兩種存儲結(jié)構(gòu)是（ ）；其判定?？盏臈l件分別是（ ），判定棧滿的條件分別是（ ）?！窘獯稹宽?/p>

21、序存儲結(jié)構(gòu)和鏈接存儲結(jié)構(gòu)（或順序棧和鏈棧），棧頂指針top= -1和top=NULL，棧頂指針top等于數(shù)組的長度和內(nèi)存無可用空間（ ）可作為實現(xiàn)遞歸函數(shù)調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)?！窘獯稹織！痉治觥窟f歸函數(shù)的調(diào)用和返回正好符合后進先出性。 表達式a*(b+c)-d的后綴表達式是（ ）。【解答】abc+*d-【分析】將中綴表達式變?yōu)楹缶Y表達式有一個技巧：將操作數(shù)依次寫下來，再將算符插在它的兩個操作數(shù)的后面。 棧和隊列是兩種特殊的線性表，棧的操作特性是（ ），隊列的操作特性是（ ），棧和隊列的主要區(qū)別在于（ ）?！窘獯稹亢筮M先出，先進先出，對插入和刪除操作限定的位置不同 循環(huán)隊列的引入是為了克服（ ）。

22、【解答】假溢出 數(shù)組Qn用來表示一個循環(huán)隊列，front為隊頭元素的前一個位置，rear為隊尾元素的位置，計算隊列中元素個數(shù)的公式為（ ）?！窘獯稹浚╮ear-front+n）% n【分析】也可以是（rear-front）% n，但rear-front的結(jié)果可能是負整數(shù)，而對一個負整數(shù)求模，其結(jié)果在不同的編譯器環(huán)境下可能會有所不同。 用循環(huán)鏈表表示的隊列長度為n，若只設(shè)頭指針，則出隊和入隊的時間復(fù)雜度分別是（ ）和（ ）。【解答】(1)，(n)【分析】在帶頭指針的循環(huán)鏈表中，出隊即是刪除開始結(jié)點，這只需修改相應(yīng)指針；入隊即是在終端結(jié)點的后面插入一個結(jié)點，這需要從頭指針開始查找終端結(jié)點的地址。

23、串是一種特殊的線性表，其特殊性體現(xiàn)在（ ）?！窘獯稹繑?shù)據(jù)元素的類型是一個字符 兩個串相等的充分必要條件是（ ）。【解答】長度相同且對應(yīng)位置的字符相等【分析】例如"abc""abc "，"abc""bca"。2. 選擇題 若一個棧的輸入序列是1，2，3，n，輸出序列的第一個元素是n，則第i個輸出元素是（ ）。A 不確定 B n-i C n-i-1 D n-i+1【解答】D【分析】此時，輸出序列一定是輸入序列的逆序。 設(shè)棧S和隊列Q的初始狀態(tài)為空，元素e1、e2、e3、e4、e5、e6依次通過棧S，一個元素出棧后即進入

24、隊列Q，若6個元素出隊的順序是e2、e4、e3、e6、e5、e1，則棧S的容量至少應(yīng)該是（ ）。A 6 B 4 C 3 D 2【解答】C【分析】由于隊列具有先進先出性，所以，此題中隊列形同虛設(shè)，即出棧的順序也是e2、e4、e3、e6、e5、e1。 一個棧的入棧序列是1，2，3，4，5，則棧的不可能的輸出序列是（ ）。A 54321 B 45321 C 43512 D 12345 【解答】C【分析】此題有一個技巧：在輸出序列中任意元素后面不能出現(xiàn)比該元素小并且是升序（指的是元素的序號）的兩個元素。 設(shè)計一個判別表達式中左右括號是否配對的算法，采用（ ）數(shù)據(jù)結(jié)構(gòu)最佳A 順序表 B 棧 C 隊列 D

25、 鏈表【解答】B【分析】每個右括號與它前面的最后一個沒有匹配的左括號配對，因此具有后進先出性。 在解決計算機主機與打印機之間速度不匹配問題時通常設(shè)置一個打印緩沖區(qū)，該緩沖區(qū)應(yīng)該是一個（ ）結(jié)構(gòu)。A 棧 B隊列 C 數(shù)組 D線性表【解答】B【分析】先進入打印緩沖區(qū)的文件先被打印，因此具有先進先出性。 一個隊列的入隊順序是1，2，3，4，則隊列的輸出順序是（ ）。A 4321 B 1234 C 1432 D 3241【解答】B【分析】隊列的入隊順序和出隊順序總是一致的。 棧和隊列的主要區(qū)別在于（ ）。A 它們的邏輯結(jié)構(gòu)不一樣 B 它們的存儲結(jié)構(gòu)不一樣C 所包含的運算不一樣 D 插入、刪除運算的限定

26、不一樣【解答】D【分析】棧和隊列的邏輯結(jié)構(gòu)都是線性的，都有順序存儲和鏈接存儲，有可能包含的運算不一樣，但不是主要區(qū)別，任何數(shù)據(jù)結(jié)構(gòu)在針對具體問題時包含的運算都可能不同。 設(shè)數(shù)組Sn作為兩個棧S1和S2的存儲空間，對任何一個棧只有當(dāng)Sn全滿時才不能進行進棧操作。為這兩個棧分配空間的最佳方案是（ ）。A S1的棧底位置為0，S2的棧底位置為n-1B S1的棧底位置為0，S2的棧底位置為n/2C S1的棧底位置為0，S2的棧底位置為nD S1的棧底位置為0，S2的棧底位置為1【解答】A【分析】兩棧共享空間首先兩個棧是相向增長的，棧底應(yīng)該分別指向兩個棧中的第一個元素的位置，并注意C+中的數(shù)組下標是從0

27、開始的。 設(shè)有兩個串p和q，求q在p中首次出現(xiàn)的位置的運算稱作（ ）。A 連接 B 模式匹配 C 求子串 D 求串長【解答】B3. 判斷題 有n個元素依次進棧，則出棧序列有(n-1)/2種?！窘獯稹垮e。應(yīng)該有 種。 ?？梢宰鳛閷崿F(xiàn)過程調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)。【解答】對。只要操作滿足后進先出性，都可以采用棧作為輔助數(shù)據(jù)結(jié)構(gòu)。 在棧滿的情況下不能做進棧操作，否則將產(chǎn)生“上溢”?！窘獯稹繉Α?在循環(huán)隊列中，front指向隊頭元素的前一個位置，rear指向隊尾元素的位置，則隊滿的條件是front=rear?！窘獯稹垮e。這是隊空的判定條件，在循環(huán)隊列中要將隊空和隊滿的判定條件區(qū)別開。 空串與空格串是相同的。

28、【解答】錯?？沾拈L度為零，而空格串的長度不為0，其長度是串中空格的個數(shù)。4. 設(shè)有一個棧，元素進棧的次序為A，B，C，D，E，能否得到如下出棧序列，若能，請寫出操作序列，若不能，請說明原因。 C，E，A，B，D C，B，A，D，E【解答】不能，因為在C、E出棧的情況下，A一定在棧中，而且在B的下面，不可能先于B出棧?？梢?，設(shè)為進棧操作，為入棧操作，則其操作序列為IIIOOOIOIO。5. 舉例說明順序隊列的“假溢出”現(xiàn)象?！窘獯稹考僭O(shè)有一個順序隊列，如圖3-6所示，隊尾指針rear=4，隊頭指針front=1，如果再有元素入隊，就會產(chǎn)生“上溢”，此時的“上溢”又稱為“假溢出”，因為隊列并不是

29、真的溢出了，存儲隊列的數(shù)組中還有2個存儲單元空閑，其下標分別為0和1。6. 在操作序列push(1)、push(2)、pop、push(5)、push(7)、pop、push(6)之后，棧頂元素和棧底元素分別是什么？（push(k)表示整數(shù)k入棧，pop表示棧頂元素出棧。）【解答】棧頂元素為6，棧底元素為1。其執(zhí)行過程如圖3-7所示。7 在操作序列EnQueue(1)、 EnQueue(3)、 DeQueue、EnQueue(5)、EnQueue(7)、DeQueue、EnQueue(9)之后，隊頭元素和隊尾元素分別是什么？（EnQueue(k)表示整數(shù)k入隊，DeQueue表示隊頭元素出隊）

30、?！窘獯稹筷狀^元素為5，隊尾元素為9。其執(zhí)行過程如圖3-8所示。8空串和空格串有何區(qū)別？串中的空格符有何意義？空串在串處理中有何作用？【解答】不含任何字符的串稱為空串，其長度為零。僅含空格的串稱為空格串，它的長度為串中空格符的個數(shù)。串中的空格符可用來分隔一般的字符，便于人們識別和閱讀，但計算串長時應(yīng)包括這些空格符?？沾诖幚碇锌勺鳛槿我獯淖哟?. 算法設(shè)計 假設(shè)以不帶頭結(jié)點的循環(huán)鏈表表示隊列，并且只設(shè)一個指針指向隊尾結(jié)點，但不設(shè)頭指針。試設(shè)計相應(yīng)的入隊和出隊的算法?！窘獯稹砍鲫牪僮魇窃谘h(huán)鏈表的頭部進行，相當(dāng)于刪除開始結(jié)點，而入隊操作是在循環(huán)鏈表的尾部進行，相當(dāng)于在終端結(jié)點之后插入一個結(jié)

31、點。由于循環(huán)鏈表不帶頭結(jié)點，需要處理空表的特殊情況。入隊算法如下：出隊算法如下： 設(shè)順序棧S中有2n個元素，從棧頂?shù)綏５椎脑匾来螢閍2n，a2n-1，a1，要求通過一個循環(huán)隊列重新排列棧中元素，使得從棧頂?shù)綏５椎脑匾来螢閍2n，a2n-2，a2，a2n-1，a2n-3，a1，請設(shè)計算法實現(xiàn)該操作，要求空間復(fù)雜度和時間復(fù)雜度均為O(n)。【解答】操作步驟為： 將所有元素出棧并入隊； 依次將隊列元素出隊，如果是偶數(shù)結(jié)點，則再入隊，如果是奇數(shù)結(jié)點，則入棧； 將奇數(shù)結(jié)點出棧并入隊； 將偶數(shù)結(jié)點出隊并入棧； 將所有元素出棧并入隊； 將所有元素出隊并入棧即為所求。 用順序存儲結(jié)構(gòu)存儲串S，編寫算法刪除

32、S中第 i個字符開始的連續(xù)j個字符?！窘獯稹肯扰袛啻甋中要刪除的內(nèi)容是否存在，若存在，則將第i+j-1之后的字符前移j個位置。算法如下： 對于采用順序存儲結(jié)構(gòu)的串S，編寫一個函數(shù)刪除其值等于ch的所有字符。【解答】從后向前刪除值為ch的所有元素，這樣所有移動的元素中沒有值為ch的元素，能減少移動元素的次數(shù)，提高算法的效率。算法如下： 對串的模式匹配KMP算法設(shè)計求模式滑動位置的next函數(shù)。【解答】參見3.2.5學(xué)習(xí)自測及答案 1在一個具有n個單元的順序棧中，假定以地址低端（即下標為0的單元）作為棧底，以top作為棧頂指針，當(dāng)出棧時，top的變化為（ ）。A 不變 B top=0; C top

33、=top-1; D top=top+1;【解答】C2一個棧的入棧序列是a, b, c, d, e，則棧的不可能的出棧序列是（ ）。A edcba B cdeba C debca D abcde 【解答】C3從棧頂指針為top的鏈棧中刪除一個結(jié)點，用x保存被刪除結(jié)點的值，則執(zhí)行（ ）。A x=top; top=top->next; B x=top->data;C top=top->next; x=top->data; D x=top->data; top=top->next;【解答】D4設(shè)元素1, 2, 3, P, A依次經(jīng)過一個棧，進棧次序為123PA，在棧

34、的輸出序列中，有哪些序列可作為C+程序設(shè)計語言的變量名?！窘獯稹縋A321, P3A21, P32A1, P321A, AP3215.設(shè)S="I_ am_ a_ teacther"，其長度為（ ）?！窘獯稹?5第 4 章 廣義線性表多維數(shù)組和廣義表 課后習(xí)題講解 1. 填空 數(shù)組通常只有兩種運算：（ ）和（ ），這決定了數(shù)組通常采用（ ）結(jié)構(gòu)來實現(xiàn)存儲?！窘獯稹看嫒?，修改，順序存儲【分析】數(shù)組是一個具有固定格式和數(shù)量的數(shù)據(jù)集合，在數(shù)組上一般不能做插入、刪除元素的操作。除了初始化和銷毀之外，在數(shù)組中通常只有存取和修改兩種操作。 二維數(shù)組A中行下標從10到20，列下標從5到10

35、，按行優(yōu)先存儲，每個元素占4個存儲單元，A105的存儲地址是1000，則元素A1510的存儲地址是（ ）。【解答】1140【分析】數(shù)組A中每行共有6個元素，元素A1510的前面共存儲了(15-10)×6+5個元素，每個元素占4個存儲單元，所以，其存儲地址是1000+140=1140。 設(shè)有一個10階的對稱矩陣A采用壓縮存儲，A00為第一個元素，其存儲地址為d，每個元素占1個存儲單元，則元素A85的存儲地址為（ ）?！窘獯稹縟+41【分析】元素A85的前面共存儲了(1+2+8)+5=41個元素。 稀疏矩陣一般壓縮存儲方法有兩種，分別是（ ）和（ ）?！窘獯稹咳M順序表，十字鏈表 廣義

36、表(a), (b),c),(d)的長度是（），深度是（），表頭是（），表尾是（）。【解答】3，4，(a)，(b),c),(d) 已知廣義表LS=(a，(b，c，d)，e)，用Head和Tail函數(shù)取出LS中原子b的運算是（ ）?！窘獯稹縃ead(Head(Tail(LS)2. 選擇題 二維數(shù)組A的每個元素是由6個字符組成的串，行下標的范圍從08，列下標的范圍是從09，則存放A至少需要（）個字節(jié)，A的第8列和第5行共占（）個字節(jié)，若A按行優(yōu)先方式存儲，元素A85的起始地址與當(dāng)A按列優(yōu)先方式存儲時的（ ）元素的起始地址一致。A 90 B 180 C 240 D 540 E 108 F 114 G

37、54 H A85 I A310 J A58 K A49【解答】D，E，K【分析】數(shù)組A為9行10列，共有90個元素，所以，存放A至少需要90×6=540個存儲單元，第8列和第5行共有18個元素（注意行列有一個交叉元素），所以，共占108個字節(jié)，元素A85按行優(yōu)先存儲的起始地址為d+8×10+5=d+85，設(shè)元素Aij按列優(yōu)先存儲的起始地址與之相同，則d+j×9+i=d+85，解此方程，得i=4，j=9。 將數(shù)組稱為隨機存取結(jié)構(gòu)是因為（）A 數(shù)組元素是隨機的 B 對數(shù)組任一元素的存取時間是相等的C 隨時可以對數(shù)組進行訪問 D 數(shù)組的存儲結(jié)構(gòu)是不定【解答】B 下面的說

38、法中，不正確的是（）A 數(shù)組是一種線性結(jié)構(gòu) B 數(shù)組是一種定長的線性結(jié)構(gòu) C 除了插入與刪除操作外，數(shù)組的基本操作還有存取、修改、檢索和排序等D 數(shù)組的基本操作有存取、修改、檢索和排序等，沒有插入與刪除操【解答】C【分析】數(shù)組屬于廣義線性表，數(shù)組被創(chuàng)建以后，其維數(shù)和每維中的元素個數(shù)是確定的，所以，數(shù)組通常沒有插入和刪除操作。 對特殊矩陣采用壓縮存儲的目的主要是為了（）A 表達變得簡單 B 對矩陣元素的存取變得簡單C 去掉矩陣中的多余元素 D 減少不必要的存儲空間【解答】D【分析】在特殊矩陣中，有很多值相同的元素并且他們的分布有規(guī)律，沒有必要為值相同的元素重復(fù)存儲。 下面（）不屬于特殊矩陣。A

39、對角矩陣 B 三角矩陣 C 稀疏矩陣 D 對稱矩陣 【解答】C 若廣義表A滿足Head(A)=Tail(A)，則A為（ ）A ( ) B ( ) C ( ),( ) D( ),( ),( )【解答】B 下面的說法中，不正確的是（）A 廣義表是一種多層次的結(jié)構(gòu) B 廣義表是一種非線性結(jié)構(gòu)C 廣義表是一種共享結(jié)構(gòu) D 廣義表是一種遞歸【解答】B【分析】從各層元素各自具有的線性關(guān)系講，廣義表屬于線性結(jié)構(gòu)。 下面的說法中，不正確的是（）A 對稱矩陣只須存放包括主對角線元素在內(nèi)的下（或上）三角的元素即可。B 對角矩陣只須存放非零元素即可。C 稀疏矩陣中值為零的元素較多，因此可以采用三元組表方法存儲。D

40、稀疏矩陣中大量值為零的元素分布有規(guī)律，因此可以采用三元組表方法存儲【解答】D【分析】稀疏矩陣中大量值為零的元素分布沒有規(guī)律，因此采用三元組表存儲。如果零元素的分布有規(guī)律，就沒有必要存儲非零元素的行號和列號，而需要按其壓縮規(guī)律找出相應(yīng)的映象函數(shù)。3. 判斷題 數(shù)組是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，數(shù)組元素之間的關(guān)系既不是線性的，也不是樹形的?！窘獯稹垮e。例如二維數(shù)組可以看成是數(shù)據(jù)元素為線性表的線性表。 使用三元組表存儲稀疏矩陣的元素，有時并不能節(jié)省存儲空間?！窘獯稹繉?。因為三元組表除了存儲非零元素值外，還需要存儲其行號和列號。 稀疏矩陣壓縮存儲后，必會失去隨機存取功能?！窘獯稹繉?。因為壓縮存儲后，非零元素的

41、存儲位置和行號、列號之間失去了確定的關(guān)系。 線性表可以看成是廣義表的特例，如果廣義表中的每個元素都是單元素，則廣義表便成為線性表?！窘獯稹繉Α?若一個廣義表的表頭為空表，則此廣義表亦為空表?！窘獯稹垮e。如廣義表L=( )，(a，b)的表頭為空表，但L不是空表。4一個稀疏矩陣如圖4-4所示，寫出對應(yīng)的三元組順序表和十字鏈表存儲表示。【解答】對應(yīng)的三元組順序表如圖4-5所示，十字鏈表如圖4-6所示。5已知A為稀疏矩陣，試從空間和時間角度比較采用二維數(shù)組和三元組順序表兩種不同的存儲結(jié)構(gòu)完成求 運算的優(yōu)缺點?！窘獯稹吭O(shè)稀疏矩陣為m行n列，如果采用二維數(shù)組存儲，其空間復(fù)雜度為(m×n)；因為要

42、將所有的矩陣元素累加起來，所以，需要用一個兩層的嵌套循環(huán)，其時間復(fù)雜度亦為(m×n)。如果采用三元組順序表進行壓縮存儲，假設(shè)矩陣中有t個非零元素，其空間復(fù)雜度為(t)，將所有的矩陣元素累加起來只需將三元組順序表掃描一遍，其時間復(fù)雜度亦為(t)。當(dāng)t << m×n時，采用三元組順序表存儲可獲得較好的時、空性能。6設(shè)某單位職工工資表ST由“工資”、“扣除”和“實發(fā)金額”三項組成，其中工資項包括“基本工資”、“津貼”和“獎金”，扣除項包括“水”、“電”和“煤氣” 。 請用廣義表形式表示所描述的工資表ST，并用表頭和表尾求表中的“獎金”項； 畫出該工資表ST的存儲結(jié)構(gòu)。

43、【解答】 ST=(基本工資，津貼，獎金)，(水，電，煤氣)，實發(fā)金額)Head(Tail(Tail(Head(ST)=獎金 工資表ST的頭尾表示法如圖4-7所示。7若在矩陣A中存在一個元素ai,j（0in-1，0jm-1），該元素是第i行元素中最小值且又是第j列元素中最大值，則稱此元素為該矩陣的一個馬鞍點。假設(shè)以二維數(shù)組存儲矩陣A，試設(shè)計一個求該矩陣所有馬鞍點的算法，并分析最壞情況下的時間復(fù)雜度?！窘獯稹吭诰仃囍兄鹦袑ふ以撔兄械淖钚≈担缓髮ζ渌诘牧袑ふ易畲笾?，如果該列上的最大值與該行上的最小值相等，則說明該元素是鞍點，將它所在行號和列號輸出。具體算法如下：分析算法，外層for循環(huán)共執(zhí)行n次

44、，內(nèi)層第一個for循環(huán)執(zhí)行m次，第二個for循環(huán)最壞情況下執(zhí)行n次，所以，最壞情況下的時間復(fù)雜度為(mn+n2)。 學(xué)習(xí)自測及答案 (沒看)1二維數(shù)組M中每個元素的長度是3個字節(jié)，行下標從0到7，列下標從0到9，從首地址d開始存儲。若按行優(yōu)先方式存儲，元素M75的起始地址為（ ），若按列優(yōu)先方式存儲，元素M75的起始地址為（ ）?！窘獯稹縟+22，d+1412一個n×n的對稱矩陣，按行優(yōu)先或列優(yōu)先進行壓縮存儲，則其存儲容量為（ ）?！窘獯稹縩(n+1)/23設(shè)n行n列的下三角矩陣A（行列下標均從1開始）已壓縮到一維數(shù)組S1Sn(n+1)/2中，若按行優(yōu)先存儲，則Aij在數(shù)組S中的存儲

45、位置是（ ）?！窘獯稹縤×(i-1)/2+j4已知廣義表LS=(a, (b, c), (d, e, a)，運用Head函數(shù)和Tail函數(shù)取出LS中原子d的運算是（ ）。【解答】Head(Head(Tail(Tail(LS)5廣義表(a, b, (c, (d)的表尾是（ ）。A (d) B (c,(d) C b,(c,(d) D (b,(c,(d)【解答】D6設(shè)有三對角矩陣An×n（行、列下標均從0開始），將其三條對角線上的元素逐行存于數(shù)組B3n-2中，使得Bk=aij求： 用i, j表示k的下標變換公式； 用k表示i, j的下標變換公式。【解答】 要求i, j表示k的下標變

46、換公式，就是要求在k之前已經(jīng)存儲了多少個非零元素，這些非零元素的個數(shù)就是k的值。元素aij求所在的行為i，列為j，則在其前面的非零元素的個數(shù)是；k=2 + 3(i1)+( ji + 1)= 2i+ j。 因為k和i, j之間是一一對應(yīng)的關(guān)系，k+1是當(dāng)前非零元素的個數(shù)，整除即為其所在行號，取余表示當(dāng)前行中第幾個非零元素，加上前面零元素所在列數(shù)就是當(dāng)前列號，即：7已知兩個n×n的對稱矩陣按壓縮存儲方法存儲在已維數(shù)組A和B中，編寫算法計算對稱矩陣的乘積?！窘獯稹繉ΨQ矩陣采用壓縮存儲，乘積矩陣也采用壓縮存儲。注意矩陣元素的表示方法。第 5 章 樹和二叉樹課后習(xí)題講解1. 填空題 樹是n（n

47、0）結(jié)點的有限集合，在一棵非空樹中，有（ ）個根結(jié)點，其余的結(jié)點分成m（m0）個（ ）的集合，每個集合都是根結(jié)點的子樹?！窘獯稹坑星覂H有一個，互不相交 樹中某結(jié)點的子樹的個數(shù)稱為該結(jié)點的（ ），子樹的根結(jié)點稱為該結(jié)點的（ ），該結(jié)點稱為其子樹根結(jié)點的（ ）?！窘獯稹慷?，孩子，雙親 一棵二叉樹的第i（i1）層最多有（ ）個結(jié)點；一棵有n（n>0）個結(jié)點的滿二叉樹共有（ ）個葉子結(jié)點和（ ）個非終端結(jié)點。【解答】2i-1，(n+1)/2，(n-1)/2【分析】設(shè)滿二叉樹中葉子結(jié)點的個數(shù)為n0，度為2的結(jié)點個數(shù)為n2，由于滿二叉樹中不存在度為1的結(jié)點，所以n=n0+n2；由二叉樹的性質(zhì)n0=n

48、2+1，得n0=(n+1)/2，n2=(n-1)/2。 設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點，該二叉樹的結(jié)點數(shù)可能達到的最大值是（ ），最小值是（ ）?！窘獯稹?h -1，2h-1【分析】最小結(jié)點個數(shù)的情況是第1層有1個結(jié)點，其他層上都只有2個結(jié)點。 深度為k的二叉樹中，所含葉子的個數(shù)最多為（ ）?！窘獯稹?k-1【分析】在滿二叉樹中葉子結(jié)點的個數(shù)達到最多。 具有100個結(jié)點的完全二叉樹的葉子結(jié)點數(shù)為（ ）。【解答】50【分析】100個結(jié)點的完全二叉樹中最后一個結(jié)點的編號為100，其雙親即最后一個分支結(jié)點的編號為50，也就是說，從編號51開始均為葉子。 已知一棵度為3的樹有2個度為1的

49、結(jié)點，3個度為2的結(jié)點，4個度為3的結(jié)點。則該樹中有（ ）個葉子結(jié)點?！窘獯稹?2【分析】根據(jù)二叉樹性質(zhì)3的證明過程，有n0=n2+2n3+1（n0、n2、n3分別為葉子結(jié)點、度為2的結(jié)點和度為3的結(jié)點的個數(shù)）。 某二叉樹的前序遍歷序列是ABCDEFG，中序遍歷序列是CBDAFGE，則其后序遍歷序列是（ ）?！窘獯稹緾DBGFEA【分析】根據(jù)前序遍歷序列和后序遍歷序列將該二叉樹構(gòu)造出來。 在具有n個結(jié)點的二叉鏈表中，共有（ ）個指針域，其中（ ）個指針域用于指向其左右孩子，剩下的（ ）個指針域則是空的?！窘獯稹?n，n-1，n+1 在有n個葉子的哈夫曼樹中，葉子結(jié)點總數(shù)為（ ），分支結(jié)點總數(shù)為

50、（ ）?！窘獯稹縩，n-1【分析】n-1個分支結(jié)點是經(jīng)過n-1次合并后得到的。2. 選擇題 如果結(jié)點A有3個兄弟，B是A的雙親，則結(jié)點B的度是（）。A 1 B 2 C 3 D 4【解答】D 設(shè)二叉樹有n個結(jié)點，則其深度為（ ）。A n-1 B n C +1 D 不能確定【解答】D【分析】此題并沒有指明是完全二叉樹，則其深度最多是n，最少是 +1。 二叉樹的前序序列和后序序列正好相反，則該二叉樹一定是（ ）的二叉樹。A 空或只有一個結(jié)點 B 高度等于其結(jié)點數(shù)C 任一結(jié)點無左孩子 D 任一結(jié)點無右孩子【解答】B【分析】此題注意是序列正好相反，則左斜樹和右斜樹均滿足條件。 線索二叉樹中某結(jié)點R沒有左

51、孩子的充要條件是（ ）。A R.lchild=NULL B R.ltag=0 C R.ltag=1 D R.rchild=NULL【解答】C【分析】線索二叉樹中某結(jié)點是否有左孩子，不能通過左指針域是否為空來判斷，而要判斷左標志是否為1。 深度為k的完全二叉樹至少有（ ）個結(jié)點，至多有（ ）個結(jié)點，具有n個結(jié)點的完全二叉樹按層序從1開始編號，則編號最小的葉子的序號是（ ）。A 2k-2+1 B 2k-1 C 2k -1 D 2k1 -1 E 2k+1 F 2k+1 -1 G 2k -1+1 H 2k【解答】B，C，A【分析】深度為k的完全二叉樹最少結(jié)點數(shù)的情況應(yīng)是第k層上只有1個結(jié)點，最多的情況

52、是滿二叉樹，編號最小的葉子應(yīng)該是在結(jié)點數(shù)最少的情況下，葉子結(jié)點的編號。 一個高度為h的滿二叉樹共有n個結(jié)點，其中有m個葉子結(jié)點，則有（ ）成立。A n=h+m B h+m=2n C m=h-1 D n=2m-1【解答】D【分析】滿二叉樹中沒有度為1的結(jié)點，所以有m個葉子結(jié)點，則度為2的結(jié)點個數(shù)為m-1。 任何一棵二叉樹的葉子結(jié)點在前序、中序、后序遍歷序列中的相對次序（ ）。A 肯定不發(fā)生改變 B 肯定發(fā)生改變 C 不能確定 D 有時發(fā)生變化【解答】A【分析】三種遍歷次序均是先左子樹后右子樹。 如果T' 是由有序樹T轉(zhuǎn)換而來的二叉樹，那么T中結(jié)點的前序序列就是T' 中結(jié)點的（ ）

53、序列，T中結(jié)點的后序序列就是 T' 中結(jié)點的（）序列。A 前序 B 中序 C 后序 D 層序【解答】A，B 設(shè)森林中有4棵樹，樹中結(jié)點的個數(shù)依次為n1、n2、n3、n4，則把森林轉(zhuǎn)換成二叉樹后，其根結(jié)點的右子樹上有（ ）個結(jié)點，根結(jié)點的左子樹上有（ ）個結(jié)點。A n1-1 B n1 C n1+n2+n3 D n2+n3+n4【解答】D，A【分析】由森林轉(zhuǎn)換的二叉樹中，根結(jié)點即為第一棵樹的根結(jié)點，根結(jié)點的左子樹是由第一棵樹中除了根結(jié)點以外其余結(jié)點組成的，根結(jié)點的右子樹是由森林中除第一棵樹外其他樹轉(zhuǎn)換來的。 討論樹、森林和二叉樹的關(guān)系，目的是為了（ ）。A 借助二叉樹上的運算方法去實現(xiàn)對樹

54、的一些運算B 將樹、森林按二叉樹的存儲方式進行存儲并利用二叉樹的算法解決樹的有關(guān)問題C 將樹、森林轉(zhuǎn)換成二叉樹D 體現(xiàn)一種技巧，沒有什么實際意義【解答】B3. 判斷題 在線索二叉樹中，任一結(jié)點均有指向其前驅(qū)和后繼的線索。【解答】錯。某結(jié)點是否有前驅(qū)或后繼的線索，取決于該結(jié)點的標志域是否為1。 在二叉樹的前序遍歷序列中，任意一個結(jié)點均處在其子女的前面。【解答】對。由前序遍歷的操作定義可知。 二叉樹是度為2的樹。【解答】錯。二叉樹和樹是兩種不同的樹結(jié)構(gòu)，例如，左斜樹是一棵二叉樹，但它的度為1。 由樹轉(zhuǎn)換成二叉樹，其根結(jié)點的右子樹總是空的。【解答】對。因為根結(jié)點無兄弟結(jié)點。 用一維數(shù)組存儲二叉樹時，

55、總是以前序遍歷存儲結(jié)點?！窘獯稹垮e。二叉樹的順序存儲結(jié)構(gòu)是按層序存儲的，一般適合存儲完全二叉樹。4證明：對任一滿二叉樹，其分枝數(shù)B2(n0-1) 。（其中，n0為終端結(jié)點數(shù)）【解答】因為在滿二叉樹中沒有度為1的結(jié)點，所以有：n=n0+n2 設(shè)B為樹中分枝數(shù)，則n=B+1所以B=n0 +n2-1再由二叉樹性質(zhì)：n0=n2+1代入上式有：B=n0+n0-1-1=2(n0-1)5證明：已知一棵二叉樹的前序序列和中序序列，則可唯一確定該二叉樹?！窘獯稹孔C明采用歸納法。設(shè)二叉樹的前序遍歷序列為a1a2a3 an，中序遍歷序列為b1b2b3 bn。當(dāng)n=1時，前序遍歷序列為a1，中序遍歷序列為b1，二叉樹

56、只有一個根結(jié)點，所以，a1= b1，可以唯一確定該二叉樹；假設(shè)當(dāng)n<=k時，前序遍歷序列a1a2a3 ak和中序遍歷序列b1b2b3 bk可唯一確定該二叉樹，下面證明當(dāng)n=k+1時，前序遍歷序列a1a2a3 akak+1和中序遍歷序列b1b2b3 bk bk+1可唯一確定一棵二叉樹。在前序遍歷序列中第一個訪問的一定是根結(jié)點，即二叉樹的根結(jié)點是a1，在中序遍歷序列中查找值為a1的結(jié)點，假設(shè)為bi，則a1=bi且b1b2 bi-1是對根結(jié)點a1的左子樹進行中序遍歷的結(jié)果，前序遍歷序列a2a3 ai是對根結(jié)點a1的左子樹進行前序遍歷的結(jié)果，由歸納假設(shè)，前序遍歷序列a2a3 ai和中序遍歷序列b

57、1b2 bi-1唯一確定了根結(jié)點的左子樹，同樣可證前序遍歷序列ai+1ai+2 ak+1和中序遍歷序列bi+1bi+2 bk+1唯一確定了根結(jié)點的右子樹。6已知一棵度為m的樹中有：n1個度為1的結(jié)點，n2個度為2的結(jié)點，nm個度為m的結(jié)點，問該樹中共有多少個葉子結(jié)點？ 【解答】設(shè)該樹的總結(jié)點數(shù)為n，則n=n0+n1+n2+nm 又：n=分枝數(shù)+1=0×n0+1×n1+2×n2+m×nm+1由上述兩式可得：n0= n2+2n3+(m-1)nm+17已知二叉樹的中序和后序序列分別為CBEDAFIGH和CEDBIFHGA，試構(gòu)造該二叉樹?！窘獯稹慷鏄涞臉?gòu)造過程如圖5-12 所示。8對給定的一組權(quán)值W（5，2，9，