數(shù)據(jù)結(jié)構(gòu)馬世霞習(xí)題答案2020版

1.6習(xí)題

一、名詞解釋

1.數(shù)據(jù)結(jié)構(gòu)：相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。

結(jié)構(gòu)，就是數(shù)據(jù)之間的關(guān)系，即數(shù)據(jù)與數(shù)據(jù)之間的排列方式。

2.數(shù)據(jù)元素：是有一定意義數(shù)據(jù)的基本單位，可由若干個(gè)數(shù)據(jù)項(xiàng)組成，在計(jì)算機(jī)中通

常作為整體處理，也可稱為結(jié)點(diǎn)、記錄。

如：在人類社會(huì)中，一個(gè)“人”是一個(gè)數(shù)據(jù)元素，是有一定意義的作為整體處理的基本

單位，在社會(huì)關(guān)系里，一般都是拿某個(gè)人說事兒，不會(huì)拿某個(gè)人的胳膊或腿兒說事兒；

但在醫(yī)學(xué)結(jié)構(gòu)上，人又由若干部分組成，比如四肢、心、肝、脾、肺、腎等。

3.數(shù)據(jù)項(xiàng)：是具有獨(dú)立含義的最小標(biāo)識(shí)單位。如一個(gè)“人”有眼睛、耳朵、手等數(shù)據(jù)

項(xiàng)，也可有姓名、年齡、性別等這些數(shù)據(jù)項(xiàng)。一個(gè)記錄可稱為一個(gè)數(shù)據(jù)元素，而這個(gè)元素中

的某一字段就是一個(gè)數(shù)據(jù)項(xiàng)。

4.邏輯結(jié)構(gòu)有時(shí)也稱數(shù)據(jù)結(jié)構(gòu)，它是數(shù)據(jù)元素之間關(guān)系的描述，可以看作是從具體問

題抽象出來的數(shù)學(xué)模型，與數(shù)據(jù)的存儲(chǔ)無關(guān)，是獨(dú)立于計(jì)算機(jī)的。

5.物理結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示和實(shí)現(xiàn)，也稱存儲(chǔ)結(jié)構(gòu)。

6.時(shí)間復(fù)雜度：當(dāng)問題規(guī)模很大時(shí)，程序執(zhí)行時(shí)間隨問題規(guī)模增長程度的一個(gè)度

量。

7.空間復(fù)雜度：是指程序運(yùn)行從開始到結(jié)束所需的存儲(chǔ)量。

二、判斷題

（1）數(shù)據(jù)元素是最小的項(xiàng)。（X）

（2）算法就是程序。（X）

（算法是解決問題的有限指令序列，它可以用某個(gè)具體的程序來表示，也可以用自然

語言、流程圖、偽代碼表示。

即可以用程序來表達(dá)算法，但算法不見得就是程序。

目前，用來表達(dá)算法用得最多的是偽代碼，因?yàn)閭未a比具體的程序要求寬松、易理

解，同時(shí)又比自然語言更容易轉(zhuǎn)換成可實(shí)現(xiàn)的程序。）

（3）數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)對(duì)象與對(duì)象中數(shù)據(jù)元素之間關(guān)系的集合。（V）

（4）從邏輯關(guān)系上講，數(shù)據(jù)結(jié)構(gòu)主要分為兩大類：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。（J）

(5)數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無關(guān)。(。)

三、填空題

(1)算法的一個(gè)特性是確定性,即針對(duì)一組確定的輸入，算法應(yīng)始終得出一組確定的

結(jié)果。

(2)算法的一個(gè)特性是有窮性,即算法必須執(zhí)行有限步就結(jié)束。

(3)數(shù)據(jù)是信息的載體,它能夠被計(jì)算機(jī)程序識(shí)別、存儲(chǔ)和加工處理。

(4)此題不嚴(yán)謹(jǐn)。

數(shù)據(jù)結(jié)構(gòu)是帶結(jié)構(gòu)的數(shù)據(jù)元素的集合，因此，可以說數(shù)據(jù)結(jié)構(gòu)由“數(shù)據(jù)”和“結(jié)

構(gòu)”兩個(gè)元素組成;

另外，一般討論一個(gè)具體的數(shù)據(jù)結(jié)構(gòu)時(shí)，我們會(huì)討論它的邏輯數(shù)據(jù)、物理結(jié)構(gòu)和

數(shù)據(jù)的運(yùn)算三個(gè)方面。

(就像“土豆炒牛肉”由土豆和牛肉兩樣主菜組成，當(dāng)我們討論這個(gè)菜品時(shí)，會(huì)討論它

的色、香、味三個(gè)方面。)

(5)數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)包括線性結(jié)構(gòu)和非線性結(jié)構(gòu)結(jié)構(gòu)兩大類。

四、簡答題

1.數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)元素之間的邏輯關(guān)系可以由四種基本數(shù)據(jù)關(guān)系組成，簡述它們的名

稱與含義。

答：

(1)集合結(jié)構(gòu)：在集合結(jié)構(gòu)中，數(shù)據(jù)元素間的關(guān)系是“屬于同一個(gè)集合”。集合是元素

關(guān)系極為松散的一種結(jié)構(gòu)。

(2)線性結(jié)構(gòu)：該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著“一對(duì)一”的關(guān)系。

(3)樹型結(jié)構(gòu)：該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著“一對(duì)多”的關(guān)系。

(4)圖形結(jié)構(gòu)：該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著“多對(duì)多”的關(guān)系。

2.簡述算法的特性。

答：

(1)有窮性。一個(gè)算法必須在有窮步之后結(jié)束，即必須在人類現(xiàn)有的壽命長度下、有

現(xiàn)實(shí)意義的有限時(shí)間內(nèi)完成。如你編寫算法，計(jì)算機(jī)需要30年的時(shí)間才能結(jié)束，算法的意

義就不大。

(2)確定性。算法的每一步必須有確切的定義，無二義性。相同的輸入僅有唯一的輸

出結(jié)果。(比如:"小明對(duì)小強(qiáng)說他的爸爸去出差了”就是一個(gè)歧義句。)

(3)可行性。算法中的每一步都可實(shí)現(xiàn)，即每一步都在當(dāng)前環(huán)境條件下可以通過有限

次運(yùn)算實(shí)現(xiàn)。

(4)輸入。一個(gè)算法具有零個(gè)或多個(gè)輸入，可以沒有輸入。

(5)輸出。一個(gè)算法具有一個(gè)或多個(gè)輸出，至少有一個(gè)輸出。(沒有輸出對(duì)我們?nèi)祟?/p>

就沒有反饋,那么這個(gè)算法就沒有意義。)

3.設(shè)計(jì)一個(gè)好的算法通常要考慮哪些要求？

要設(shè)計(jì)一個(gè)好的算法通常要考慮以下的要求。

(1)正確性。算法的執(zhí)行結(jié)果應(yīng)當(dāng)滿足預(yù)先規(guī)定的功能和性能要求。

“正確性”的含義是所設(shè)計(jì)的程序沒有語法錯(cuò)誤，對(duì)于刁難性的數(shù)據(jù)也能夠得到滿足

要求的輸出結(jié)果。

(2)可讀性。一個(gè)算法應(yīng)當(dāng)思路清晰、層次分明、簡單明了、易讀易懂。

一個(gè)好的算法首先應(yīng)該是便于交流，其次才是機(jī)器可執(zhí)行，可讀性好的算法有助于編

程人員對(duì)算法的理解，而難懂的算法對(duì)于隱藏的錯(cuò)誤不易調(diào)試和修改。

(3)健壯性(魯棒性)。當(dāng)輸入不合法數(shù)據(jù)時(shí)，應(yīng)能作適當(dāng)處理，不至引起嚴(yán)重后

果，陷入死機(jī)。

(4)高效率和低存儲(chǔ)量。有效使用存儲(chǔ)空間和有較高的時(shí)間效率。

4.常用算法大致可以分為幾大類？

答：常用的算法大致可以被分為蠻力算法、分治算法、減治算法、變治算法以及動(dòng)態(tài)規(guī)

劃算法等幾大類。

五、觀察下列算法回答以下問題。

(1)每一個(gè)算法的意圖是什么？

(2)每一個(gè)算法的關(guān)鍵步驟是什么？

(3)每一個(gè)算法的關(guān)鍵步驟執(zhí)行了多少步？

(4)算法的時(shí)間復(fù)雜度是什么？

①for(i=0;i<n;i++)

for(j=0;j<n;j++)

a++;

答：

算法意圖：變量a自增n?次；

算法的關(guān)鍵步驟：a++;

關(guān)鍵步驟執(zhí)行次數(shù)：胡次；

算法的時(shí)間復(fù)雜度：T(n)=0(n2)

②for(i=0;i<n;i++)

for(j=i;j<i;j++)

x++;

答：

算法意圖：什么也不做；

算法的關(guān)鍵步驟：X++;

關(guān)鍵步驟執(zhí)行次數(shù)：0次；

算法的時(shí)間復(fù)雜度：T(n)=0(1)

分析：

雖然看起來是雙層循環(huán)，但第二次循環(huán)for(j=i;j〈i;j++)的循環(huán)體因?yàn)椴粷M足j〈i

的條件而不執(zhí)行；所以事實(shí)上第一層循環(huán)的任何一次執(zhí)行，都是什么也不做。

無論問題規(guī)模n為多少，關(guān)鍵步驟“x++;”的執(zhí)行次數(shù)都為0次。常量階的時(shí)間復(fù)雜

度記為T(n)=0(1)?

③i=l;

答：

算法意圖：將i的值賦值為1;

算法的關(guān)鍵步驟：i=l；

關(guān)鍵步驟執(zhí)行次數(shù)：1次；

算法的時(shí)間復(fù)雜度：T(n)=O(1)

第2章

1.名詞解釋

(1)線性表

具有相同數(shù)據(jù)類型的n(n>=0)個(gè)數(shù)據(jù)元素的有限序列，排列方式為“一個(gè)接一個(gè)的排

列”。通常記為：

(ai,32,ai-i,a,,8i+i,"an)

其中，n為表長，n=0時(shí)稱為空表。

(2)順序表

用順序存儲(chǔ)方式存放的線性表叫順序表，順序存儲(chǔ)是指在內(nèi)存中用地址連續(xù)的一塊

存儲(chǔ)空間順序存放線性表的各元素。

特點(diǎn)：①用物理上的相鄰實(shí)現(xiàn)數(shù)據(jù)元素邏輯關(guān)系上的相鄰;②可實(shí)現(xiàn)隨機(jī)存取。

(3)線性單鏈表

用鏈?zhǔn)酱鎯?chǔ)方式存放的線性表叫鏈表。

鏈表是通過一組任意的存儲(chǔ)單元來存儲(chǔ)線性表中的數(shù)據(jù)元素，對(duì)每個(gè)數(shù)據(jù)元素a”除了

存放數(shù)據(jù)元素的自身的信息a之外，還需要存放其后繼ai+i所在的存貯單元的地址，這兩

部分信息組成一個(gè)“結(jié)點(diǎn)”，存放數(shù)據(jù)元素信息的稱為數(shù)據(jù)域data,存放其后繼地址的稱為

指針域nexto因此n個(gè)元素的線性表通過每個(gè)結(jié)點(diǎn)的指針域聯(lián)成了一個(gè)“鏈子”，稱之為

鏈表。其中：

線性、單向鏈結(jié)構(gòu)的叫線性單鏈表；

線性、雙向鏈結(jié)構(gòu)的叫線性雙向鏈表；

環(huán)形、單向鏈結(jié)構(gòu)的叫單循環(huán)鏈表；

環(huán)形、雙向鏈結(jié)構(gòu)的叫雙循環(huán)鏈表。

(4)單循環(huán)鏈表

在單鏈表的基礎(chǔ)上，鏈表最后一個(gè)結(jié)點(diǎn)的指針域不為空，而是指向第一個(gè)結(jié)點(diǎn)，使得鏈

表頭尾結(jié)點(diǎn)相連，整個(gè)鏈表形成一個(gè)環(huán)。

單循環(huán)鏈表特點(diǎn)：從表中任何一個(gè)結(jié)點(diǎn)出發(fā)均可找到其它結(jié)點(diǎn)。

(單鏈表特點(diǎn)：要找鏈表中任何一個(gè)結(jié)點(diǎn)，必須從頭結(jié)點(diǎn)開始遍歷該結(jié)點(diǎn)以前的整個(gè)鏈

表。)

2.判斷題(在各題后填寫“4”或“X”)

(1)線性表若采用鏈?zhǔn)酱鎯?chǔ)表示時(shí)所有存儲(chǔ)結(jié)點(diǎn)之間的地址可連續(xù)可不連續(xù)(4)

(2)鏈?zhǔn)酱鎯?chǔ)在插入和刪除時(shí)需要保持?jǐn)?shù)據(jù)元素原來的物理順序，不需要保持原來的邏

輯順序。(X)

(3)鏈表中每個(gè)結(jié)點(diǎn)都是兩個(gè)域。(X)

解析：單鏈表中每個(gè)結(jié)點(diǎn)都是兩個(gè)域，雙鏈表不是兩個(gè)域。

(4)在順序表中，邏輯上相鄰的元素在物理位置上不一定相鄰。(X)

(5)順序表可以按下標(biāo)隨機(jī)(或直接)訪問，順序表還可以從某一指定元素開始，向前

或向后逐個(gè)元素順序訪問。(4)

3.填空題

(1)線性表的順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)：線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)

構(gòu)是一種循序訪問的存儲(chǔ)結(jié)構(gòu)，即要訪問線性表中的任一元素，必須“順藤摸瓜”先逐個(gè)

遍歷該元素之前的所有元素。

(“隨機(jī)存取”，有時(shí)亦稱直接訪問，指的是當(dāng)存儲(chǔ)器中的消息被讀取或?qū)懭霑r(shí)，所需要

的時(shí)間與這段信息所在的位置無關(guān)。)

(2)線性表采用順序存儲(chǔ)結(jié)構(gòu)時(shí),其存儲(chǔ)地址通常必須是連續(xù)的，采用鏈?zhǔn)酱鎯?chǔ)

結(jié)構(gòu)時(shí)，其存儲(chǔ)地址連續(xù)與否均可以。

(3)已知順序表長度為n(元素序號(hào)為0?n-l),在i位置(lWi/n+l)插入一個(gè)元素

需要移動(dòng)正1個(gè)元素，把i位置(iWiWn)的元素刪除需要移動(dòng)上j個(gè)元素。

4.含有n個(gè)結(jié)點(diǎn)的線性單鏈表中，在指針p所指結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為

0(1)，在指針p所指結(jié)點(diǎn)前插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為0(n)。

(因?yàn)樵趩捂湵碇?，任何一個(gè)結(jié)點(diǎn)含后繼指針，但不含前驅(qū)指針，所以在p所指結(jié)點(diǎn)后

插入一個(gè)新結(jié)點(diǎn)，需要從第一個(gè)結(jié)點(diǎn)開始逐一訪問。)

5.含有n個(gè)結(jié)點(diǎn)的線性單鏈表中，在給定值為d的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度

為QS上，在給定值為d的結(jié)點(diǎn)前插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為Qin)o

6.含有n個(gè)結(jié)點(diǎn)的雙向鏈表中，在指針p所指結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為

0(1),在指針p所指結(jié)點(diǎn)前插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為QLL。

7.在具有n個(gè)結(jié)點(diǎn)的按結(jié)點(diǎn)數(shù)據(jù)有序的線性單鏈表中插入一個(gè)新結(jié)點(diǎn)并使鏈表依然有

序的操作的時(shí)間復(fù)雜度是皿I。

四、選擇題

(1)設(shè)單鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為(data,next)。若想摘除結(jié)點(diǎn)*p(*p既不是第一個(gè)也不是

最后一個(gè)結(jié)點(diǎn))的直接后繼，則應(yīng)執(zhí)行下列哪一個(gè)操作？

A.p->next=p->next->next;

B.p=p->next;p->next=p->next->next;

C.p->next=p->next;

D.p=p->next->next;

(2)在一個(gè)長度為n的順序表中向第i個(gè)元素位置插入一個(gè)新元素時(shí)，

需要從后向前依次后移個(gè)元素。

A.n-i

B.n-i+1

C.n-i-1

D.i

(3)設(shè)單鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為(data,next)?已知指針q所指結(jié)點(diǎn)是指針p所指結(jié)點(diǎn)的直

接前驅(qū)，若在*q與*p之間插入結(jié)點(diǎn)*s,則應(yīng)執(zhí)行下列哪一個(gè)操作？

A.s->next=p->next;p->next=s

B.q->next=s;s->next=p;

C.p->next=s->next;s->next=p

D.p->next=s;s->next=q;

(4)在一個(gè)長度為n的順序表的表尾插入一個(gè)新元素的漸進(jìn)時(shí)間復(fù)雜度為。

A.O(n)

B.O(l)

C.O(n2)

DO(log2n)

(5)設(shè)雙向循環(huán)鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為(data,prior,next),且不帶表頭結(jié)點(diǎn)。若想在指針p

所指結(jié)點(diǎn)之后插入指針s所指結(jié)點(diǎn)，則應(yīng)執(zhí)行下列哪一個(gè)操作？

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->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;

五、簡答題

簡述順序表與鏈表的優(yōu)缺點(diǎn)。

是否是否

存儲(chǔ)密度存取效率增刪效率

需預(yù)先分配需連續(xù)存儲(chǔ)空間

順序表高需要需要高低

鏈表低不需要不需要低高

順序表的存儲(chǔ)效率高，存取速度快。但它的空間大小一經(jīng)定義，在程序整個(gè)運(yùn)行期

間不會(huì)發(fā)生改變，因此，不易擴(kuò)充。同時(shí)，由于在插入或刪除時(shí)，為保持原有次序，平均

需要移動(dòng)一半（或近一半）元素，修改效率不高。

鏈?zhǔn)酱鎯?chǔ)表示的存儲(chǔ)空間一般在程序的運(yùn)行過程中動(dòng)態(tài)分配和釋放，且只要存儲(chǔ)器

中還有空間，就不會(huì)產(chǎn)生存儲(chǔ)溢出的問題。同時(shí)在插入和刪除時(shí)不需要保持?jǐn)?shù)據(jù)元素原來

的物理順序，只需要保持原來的邏輯順序，因此不必移動(dòng)數(shù)據(jù)，只需修改它們的鏈接指

針，修改效率較高。但存取表中的數(shù)據(jù)元素時(shí)，只能循序訪問，因此存取效率不高。

循序訪問，“順藤摸瓜”逐個(gè)按序訪問?

六、編程

有順序表A和B,其元素均按從小到大的升序排列，編寫一個(gè)算法將它們合并成一個(gè)

順序表C,要求C的元素也是從小到大的升序排列。如：

已知：A={5,8,9,12,16},B={1,3,5,7}求：己{1,3,5,5,7,8,9,12,16}

提示：(1)依次掃描通過A和B的元素，比較當(dāng)前的元素的值，將較小值的元素賦

給C,如此直到一個(gè)線性表掃描完畢；

(2)將未完的那個(gè)順序表中余下部分賦給C即可。C的容量要能夠容納A、B兩個(gè)線

性表相加的長度。

程序“24.c”如下：

#include<stdio.h>

#defineMaxSize50

typedefintDataType;

typedefstruct

(

DataTypedata[MaxSize];

intlast;/*線性表的最后一個(gè)元素last*/

}Lnode,*List;

voidMerge_List(LnodeA,LnodeB,Lnode*C)/*合并C=A+B*/

{

inti,j,k；

i=l;j=l;k=l;

while(i<=A.last&&j<=B.last)

if(A.data[i]<=B.data[j])

(

C->data[k]=A.data[i];

k-H-;

i++；

}

else

C->data[k]=B.datafj];

k++；j++；

while(i<=A.last)

{

C->data[k]=A.data[i];

k++;

i++;

}

while(j<=B.last)

{C->data[k]=B.data[j];

k++；jf}

C->last=k-1;

)

main()

{LnodeA,B,C;

inti,k,m;

printff請(qǐng)輸入A順序表元素，元素為整型量，用空格分開，-1為結(jié)束標(biāo)志：”)；

A.last=0;i=0;scanf(n%dn,&i);

while(i!=-1){/*輸入A順序表元素，建立有序表*/

k=A.last;

while((k>=l)&&(i<A.data[k]))

k??；

fbr(m=A.last;m>=k+1;m-)

A.data[m+1]=A.data[m];

A.datafk+1]=i;A.last-H-；

scanff%d”,&i);}

printf(〃\n\n請(qǐng)輸入B順序表元素，元素為整型，-1為結(jié)束標(biāo)志：”)；

B.last=0;i=0;scanf(M%dn,&i);

while(i!=-l){/*輸入B順序表元素，建立有序表*/

k=B.last;

while((k>=l)&&(i<B.data[k]))

for(m=B.last;m>=k+1;m-)B.data[m+1]=B.data[m];

B.data[k+1]=i;B.last-H-;

scanf(M%dn,&i);}

printf(〃\nA有序表元素列表：”);

for(i=l;i<=A.last;i++)

prmtf(M%d",A.data[i]);

printf(M\nn);

printf(”\nB有序表元素列表：”)；

for(i=1;i<=B.last;i++)

printff%dn,B.data[i]);

printff\n”)；

MergeList(A,B,&C);

printf(”\n合并后C有序表元素列表:\n“);

for(i=l;i<=C.last;i++)

printff'%dn,C.data[i]);

printff'n”)；

}

算法的時(shí)間性能是O(m+n),其中1n是A表長，n是B表長。運(yùn)行結(jié)果如圖2-23所

6"D八數(shù)據(jù)結(jié)構(gòu)源代碼\2_4\Debug\2_4-exe”

請(qǐng)輸入A順序表

請(qǐng)輸入B順序表元素，元素為整型，T■為結(jié)束標(biāo)志：1357T

。有序表元素列表：5891216

B有序表元素列表：135?

合并后C有序表元素列表：

圖2-23兩個(gè)有序表合并運(yùn)行結(jié)果

3.5習(xí)題

一、名詞解釋

(1)棧

棧是限制在表的一端進(jìn)行插入和刪除操作的線性表。

允許插入、刪除的這一端稱為棧頂，另一個(gè)固定端稱為棧底。

棧的順序結(jié)構(gòu)：利用順序存儲(chǔ)方式實(shí)現(xiàn)的棧稱為順序棧。

棧的鏈?zhǔn)浇Y(jié)構(gòu)：用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)的棧稱為鏈棧。

(2)隊(duì)

隊(duì)是一種“先進(jìn)先出”(FIFO--FirstInFirstOut)的數(shù)據(jù)結(jié)構(gòu)，即插入操作在表一端進(jìn)行,

而刪除操作在表的另一端進(jìn)行，這種數(shù)據(jù)結(jié)構(gòu)稱為隊(duì)列。

把允許插入的一端稱為隊(duì)尾(rear),把允許刪除的一端稱為隊(duì)頭(front)。

隊(duì)的順序結(jié)構(gòu)：順序存儲(chǔ)的隊(duì)稱為順序隊(duì)。

隊(duì)的鏈?zhǔn)浇Y(jié)構(gòu)：采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的隊(duì)稱為鏈隊(duì)。

二、判斷題

(1)棧和隊(duì)列都是特殊的線性表。(V)

(2)棧和隊(duì)列都將插入和刪除操作限制在表的端點(diǎn)處進(jìn)行。(V)

(3)只允許在表的一端進(jìn)行插入和刪除操作的線性表稱為棧。(V)

(4)沒有元素的棧稱為空棧，空棧用不著棧頂指針。(x)

(5)只要棧不空，就能任意刪除棧的元素。(x)

(6)棧允許刪除的一端稱為棧頂，而棧底元素是不能刪除的。(x)

(7)對(duì)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的棧進(jìn)行操作不必判斷溢出。(V)

(8)元素進(jìn)出隊(duì)列一定滿足“先進(jìn)先出”的規(guī)律。(V)

(9)鏈隊(duì)列不存在溢出問題。(V)

(10)在鏈隊(duì)列中刪除一個(gè)元素是在鏈表的最前端進(jìn)行的。(V)

三、單項(xiàng)選擇題

(1)棧和隊(duì)列的共同之處在于它們具有相同的(A)。

A.邏輯特性B.物理特性C.運(yùn)算方法D.元素類型

(2)棧和隊(duì)列都是特殊的線性表，其特殊性在于(C)。

A.它們具有一般線性表所沒有的邏輯特性

B.它們的存儲(chǔ)結(jié)構(gòu)比較特殊

C.對(duì)它們的使用方法做了限制

D.它們比一般線性表更簡單

(3)若5個(gè)元素的出棧序列為1,2,3,4,5,則進(jìn)棧序列可能是()0

A.2,4,3,1,5B.2,3,1,5,4

C.3,1,4,2,5D.3,1,2,5,4

(4)某隊(duì)列初始為空，若它的輸入序列為a,b,c,d,它的輸出序列應(yīng)為()。

A.a,b,c,dB.d,c,b,a

C.a,c,b,dD.d,a,c,b

(5)當(dāng)3個(gè)元素的進(jìn)棧序列給定以后，由這3個(gè)元素組成的可能的出棧序列應(yīng)該有

()。

A.5種B.6種C.4種D.3種

(6)若棧采用順序存儲(chǔ)結(jié)構(gòu)，正常情況下，往堆棧中插入一個(gè)元素，棧頂指針top的

變化是()o

A.不變B.top=0C.--topD.top++

(7)若棧采用順序存儲(chǔ)結(jié)構(gòu)，正常情況下，刪除棧中一個(gè)元素，棧頂指針top的變

化是()。

A.不變B.top=0C.top--D.top++

(8)若隊(duì)列采用順序存儲(chǔ)結(jié)構(gòu)，元素的排列順序(B)。

A.與元素的值的大小有關(guān)

B.由元素進(jìn)入隊(duì)列的先后順序決定

C.與隊(duì)頭指針和隊(duì)尾指針的取值有關(guān)

n與作為順序存儲(chǔ)結(jié)構(gòu)的數(shù)組的大小有關(guān)

(9)若非空棧采用含頭結(jié)點(diǎn)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，棧頂指針為top,刪除堆棧的一個(gè)元素

的過程是依次執(zhí)行：p=top,(B),free(p)0

A.top=p->nextB.top->next=p->next

C.p=topD.p=p->next

(10)若隊(duì)列采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),隊(duì)頭元素指針與隊(duì)尾元素指針分別為front和rear,

向隊(duì)列中插入一個(gè)由P所指的新結(jié)點(diǎn)的過程是依次執(zhí)行：()，rear二p。

A.rear=pB.front二p

C.rear->next=pD.front->next=p

(11)若非空隊(duì)列采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，隊(duì)頭元素指針與隊(duì)尾元素指針分別為front和rear,

刪除隊(duì)列的一?1■元素的過程是依次執(zhí)行：p=front,(),free(p)0

A.rear=pB.rear=p->next

C.rear=p->nextD.front=p->next

(12)在循環(huán)隊(duì)列中，若front與rear分別表示隊(duì)頭元素和隊(duì)尾元素的位置，則判斷循

環(huán)隊(duì)列隊(duì)空的條件是(C)。

A.front=rear+lB.rear=front+l

C.front==rearD.rear=front-l

四、填空題

(1)棧和隊(duì)列的邏輯結(jié)構(gòu)都是線性一結(jié)構(gòu)。

(2)棧的插入和刪除操作都是在棧頂一進(jìn)行,而隊(duì)列的插入操作在.隊(duì)尾.進(jìn)行,刪除

操作在一隊(duì)頭_進(jìn)行。

(3)對(duì)某棧執(zhí)行刪除操作時(shí)，只有在一棧中只有一個(gè)元素的一情況下,才會(huì)將棧底元素

刪除。

(4)在具體的程序設(shè)計(jì)過程中，棧的順序存儲(chǔ)結(jié)構(gòu)一般是利用一個(gè)數(shù)組一描述的,同

時(shí)還要定義一個(gè)整型變量來一給出棧頂元素的位置―。

(5)若棧采用順序存儲(chǔ)結(jié)構(gòu)，在不產(chǎn)生溢出的情況下往棧中插入一個(gè)新元素，

首先一將棧頂指針后移一個(gè)位置一，然后將被插入元素放在修改后的棧頂指針?biāo)赋龅奈?/p>

(6)若隊(duì)列采用順序存儲(chǔ)結(jié)構(gòu)，未溢出時(shí)插入一個(gè)元素首先將隊(duì)尾指針后移一個(gè)位

置一然后再一將被插入元素放在修改后的隊(duì)尾指針?biāo)赋龅奈恢猫D。

(7)當(dāng)棧的最大長度難以估計(jì)時(shí)，最好采用一鏈?zhǔn)揭淮鎯?chǔ)結(jié)構(gòu)。

五、綜合應(yīng)用題

(1)已知棧采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，初始時(shí)為空，請(qǐng)畫出a,b,c,d四個(gè)元素依次進(jìn)棧以

后該棧的狀態(tài)，然后再畫出此時(shí)的那個(gè)棧頂元素出棧后棧的狀態(tài)。

(2)若按從左到右的順序依次讀人已知序列{a,b,c,d,e,f,g}中的元素，然后結(jié)

合棧操作，能得到下列序列中的哪些序列(每個(gè)元素進(jìn)棧一次，下列序列表示出棧的次序)？

A.{d,e,c,f,b,g,a}B.{f,e,g,d,a,c,b}

C.{e,f,d,g,b,c,a}D.{c,d,b,e,f,a,g)

答：A、D滿足出棧序列。滿足A出棧次序的具體操作序列為：

a,bed進(jìn)棧，然后d出棧；

然后e進(jìn)棧，接著e出棧；

然后c出棧；

然后f進(jìn)棧，接著f出棧；

然后b出棧；

然后g進(jìn)棧，接著g出棧

最后a出棧。

出棧序列：d,e,c,f,b,g,a,所以A滿足出棧序列。

滿足D出棧次序的具體操作序列請(qǐng)同學(xué)們自行寫出。

4.7習(xí)題

一、選擇

(1)串是()?

A不少于一個(gè)字母和序列B任意個(gè)字母的序列

C不少于一個(gè)字符的序列D有限個(gè)字符的序列

(2)串的長度是()o

A串中不同字母的個(gè)數(shù)B串中不同字符的個(gè)數(shù)

C串中所含字符的個(gè)數(shù)，且大于0D串中所含字符的個(gè)數(shù)

(3)設(shè)串sl='abedefg',s2=*pqrst,函數(shù)CON(X,Y)返回X和串的連接串，SUB

(S,I,J)返回串S的從序號(hào)I的字符開始的J個(gè)字符組成的子串，LEN(S)返回串S的長

度，則CON(SUB(si,2,LEN(s2)),SUB(sl,LEN(s2),2))的結(jié)果串是()。

AbcdefBbcdefgCbcpqrstDbcdefef

注釋：CON(SUB(si,2,LEN(s2)),SUB(sl,LEN(s2),2))

=CON(SUB(si,2,5),SUB(sl,5,2))

=CON(bcdef,ef)

二bcdefef

(4)數(shù)組A[l：5H1：6]的每個(gè)元素占5個(gè)單元，將其按行優(yōu)先次序存儲(chǔ)在起始起址

為1000的連續(xù)的內(nèi)存單元中，則元素A[5,5]的地址為(A)。

A1140B1145C1120D1125

注釋：該數(shù)組為5行6列，

按照公式：Loc[i,j]=Loc[l,1]+(nX(i-l)+j-l)Xsize,

其中m=5,n=6,size=5,

那么Loc[5,5>Loc[l,1]+(6X(5-1)+5-1)X5=1140

(5)對(duì)矩陣壓縮存儲(chǔ)是為了()。

A方便運(yùn)算B節(jié)省空間C方便存儲(chǔ)D提高運(yùn)算速度

(6)數(shù)組通常具有的兩種基本操作是()。

A插入與刪除B索引和修改

C查找和修改D查找與刪除

注釋：數(shù)組，連續(xù)存儲(chǔ)，不適合經(jīng)常插入和刪除；適合經(jīng)常查找和修改(定位后修

改某單元內(nèi)的值，單元個(gè)數(shù)和單元之間的邏輯順序不做修改。)

(7)二維數(shù)組M[i,j]的行下標(biāo)i的范圍從0到4,列下標(biāo)j的范圍從0到5,M按行

存儲(chǔ)時(shí)元素\1[3,5]的起始地址與M按列存儲(chǔ)時(shí)元素()的起始地址相同。

Am[2,4]BM[3,4]CM[3,5]DM[4,4]

注釋：按行存儲(chǔ)時(shí)，M[3,5]是第24個(gè)元素(前3行是3X6個(gè)，第4行是6個(gè))

按列存儲(chǔ)時(shí)，M[3,4]是第24個(gè)元素(前4列是4X5個(gè)，第5列是4個(gè))

(8)稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種，即()?

A二維數(shù)組和三組數(shù)組B三元組表和散列

C三元組表和十字鏈表D散列和十字鏈表

(9)設(shè)有上三角矩陣a(1:5,1:5),現(xiàn)將其上三角中的元素按列優(yōu)先順序存放在一維數(shù)

組b(l:15)中。已知b［l］的地址為100,每個(gè)元素占用2個(gè)存儲(chǔ)單元，則a［3,4］的地址為

(A)o

A116B118C120D122

第79頁公式，其中i=3,j=4.

上三角矩陣Loc[i,j]=Loc[1,1]+j(j-l)/2+i-l

=Loc[1,1]+8個(gè)元素所占的存儲(chǔ)單元個(gè)數(shù)

=100+16

=116

二、判斷題

(1)串長度是指串中不同字符的個(gè)數(shù)。(X)

［注］串長度：串中所包含的字符個(gè)數(shù)，無論是相同字符還是不同字符。

(2)串是n個(gè)字母的有限序列(n>0)。(X)

［注］是字符，不是字母

(3)如果兩個(gè)串含有相同的字符，則說它們相等。(X)

［注］長度相等且對(duì)應(yīng)位置的字符都相等。

(4)空串與空格串是相同的。(X)

(5)對(duì)矩陣壓縮存儲(chǔ)的方法只能用三元組表存儲(chǔ)矩陣元素。(X)

［注］還有行邏輯鏈接的順序表和十字鏈表。

三、填空題

(1)串值的兩種最基本的存儲(chǔ)方式是順序存儲(chǔ)方式和鏈接存儲(chǔ)方式。

(2)兩個(gè)串相等的充分必要是字符串長度相同且對(duì)應(yīng)位置字符相同。

(3)空串的長度等于?。

(4)空格串是空格組成的非空串，其長度等于串中空格字符的個(gè)數(shù)。

(5)設(shè)s='Iamateacher',其長度是14。

(6)設(shè)sl=，good,,s2=，',s3-bye!,,則si,s2和s3連接后的結(jié)果

是goodbye!

(7)對(duì)矩陣采用壓縮存儲(chǔ)是為了節(jié)省存儲(chǔ)空間。

(8)設(shè)N行N列的下三角矩陣A己壓縮到一維數(shù)組S(1：N(N+1)/2)中，若按行

序?yàn)橹鞔鎯?chǔ)，則A[LJ1對(duì)應(yīng)的S中的存儲(chǔ)位置是一i(i-D/2+jT。

四、程序填空：

(1)采用順序存儲(chǔ)結(jié)構(gòu)編寫算法：將串r中所有值為chi的字符換成ch2。

#defineMaxSize100

typedefstruct

{charstr[MaxSize];

intlen;

}strtype;

Strtype*trans(r,chl,ch2)

Strtype*r;

charch1,ch2;

inti;

for(i=0;i<r->len;i++)

if(r->str[i]==chl)

r->str[i]=ch2；

return(r);

(2)執(zhí)行下列函數(shù)會(huì)產(chǎn)生什么的結(jié)果？

Voiddemonstrate()

{StrAssign(s,"thisisabook");//s=uthisisabook”

StrReplace(s,SubString(s,3,7),44eseare");//s=4tthesearebook''

StrAssign(t,StrCat(s,us"));//t=s=44thesearebooks^^

StrAssign(u,"xyxyxyxyxyxy");//u=xyxyxyxyxyxy

StrAssign(v,SubString(u,6,3))；//v=yxy

StrAssign(w,"W”)；〃w=W

printf("t=”,t,“v=",v,‘'u='',StrReplace(u,v,w));

輸出:

t=thesearebooks

v=yxy

u=xWxWxW

五、算法設(shè)計(jì)：

1采用順序存儲(chǔ)結(jié)構(gòu)編寫算法：

(1)將串r中刪除其值等于ch的所有字符。

(2)將串r中所有字符按照相反的次序仍存放在r中。

(3)將串rl中第index個(gè)字符起求出首次與串r2相同的子串的起始位置。

(4)從串r中刪除所有與r3相同的子串。

2編寫鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下刪除串S從位置i開始長度為k的子串的算法。

L串的算法設(shè)計(jì)1

分別在順序存儲(chǔ)和一般鏈接存儲(chǔ)兩種方式下用C語言寫出實(shí)現(xiàn)把串si復(fù)制到串S2的串復(fù)

制函數(shù)strcpy(sl,s2)。

2.串的算法設(shè)計(jì)2

在一般鏈接存儲(chǔ)(一個(gè)結(jié)點(diǎn)存放一個(gè)字符)方式下，寫出采用簡單算法實(shí)現(xiàn)串的模式匹配的C

語言函數(shù)intL_index(t,p)?

串的算法設(shè)計(jì)1

分別在順序存儲(chǔ)和一般鏈接存儲(chǔ)兩種方式下，用C語言寫出實(shí)現(xiàn)把串si復(fù)制到串s2的串復(fù)

制函數(shù)strcpy(sl,s2)o

順序存儲(chǔ)：

#include"string.h"

#defineMAXN100

chars[MAXN];

intS_strlen(chars[])

(

inti;

for(i=0;s[i]!=W;i++);

return(i);

voidS_strcpy(charsl[],chars2[])//

(

inti;

for(i=0;sl[i]!=W;i4-+)

s2[i]=sl[i];

s2[i]=,\0';

)

一般鏈接存儲(chǔ)：

#include"stdio.h"

typedefstructnode

(

chardata;

structnode*link;

}NODE;

NODE*L_strcpy(NODE*sl)

(

NODE*s2,*tl,*t2,*s;

if(sl==NULL)return(NULL);

else

(

tl=sl;

t2=(NODE*)malloc(sizeof(NODE));

s2=t2;

while(tl!=NULL)

(

s=(NODE*)malloc(sizeof(NODE));

s->data=tI->data;

t2->link=s;

t2=s;

tl=tl->link;

)

t2->link=NULL;

s=s2;

s2=s2->link;

free(s);

return(s2);

串的算法設(shè)計(jì)2

在一般鏈接存儲(chǔ)(一個(gè)結(jié)點(diǎn)存放一個(gè)字符)方式下，寫出采用簡單算法實(shí)現(xiàn)串的模式匹配的C

語言函數(shù)intL_index(t,p)o

#include"stdio.h"

typedefstructnode

(

chardata;

structnode*link;

}NODE;

intL_index(NODE*t,NODE*p)

(

NODE*tl,*pl,*t2;

inti;

tl=t;i=l;

while(tl!=NULL)

(

pl=p;

t2=tl->link;

while(p1->data==t1->data&&p1!=NULL)

pl=pl->link;

tl=tl->link;

}

if(pl==NULL)return(i);

i++；

tl=t2;

)

return(O);

第5章習(xí)題答案

一、選擇

1.以下說法錯(cuò)誤的是（）

A.樹形結(jié)構(gòu)的特點(diǎn)是一個(gè)結(jié)點(diǎn)可以有多個(gè)直接前趨

B.線性結(jié)構(gòu)中的一個(gè)結(jié)點(diǎn)至多只有一個(gè)直接后繼

C.樹形結(jié)構(gòu)可以表達(dá)（組織）更復(fù)雜的數(shù)據(jù)

D.樹（及一切樹形結(jié)構(gòu)）是一種“分支層次”結(jié)構(gòu)

2.以下說法錯(cuò)誤的是（BC）

A.二叉樹可以是空集

B.二叉樹的任一結(jié)點(diǎn)都直兩棵子樹（是“最多有”兩棵子樹）

C.二叉樹與樹具有相同的樹形結(jié)構(gòu)（二叉樹的孩子必有左右之分，只有一個(gè)孩子時(shí)也要分

出左右，而樹即使是有序樹，只有一個(gè)孩子時(shí)部分左右）

D.二叉樹中任一結(jié)點(diǎn)的兩棵子樹有次序之分

3、以下說法錯(cuò)誤的是（）

A.完全二叉樹上結(jié)點(diǎn)之間的父子關(guān)系可由它們編號(hào)之間的關(guān)系來表達(dá)

B.在三叉鏈表上，二叉樹的求雙親運(yùn)算很容易實(shí)現(xiàn)

C.在二叉鏈表上，求根，求左、右孩子等很容易實(shí)現(xiàn)

D.在二叉鏈表上，求雙親運(yùn)算的時(shí)間性能很好

4、以下說法錯(cuò)誤的是（）

A.一般在哈夫曼樹中，權(quán)值越大的葉子離根結(jié)點(diǎn)越近

B.哈夫曼樹中沒有度數(shù)為1的分支結(jié)點(diǎn)

C.若初始森林中共有n裸二叉樹，最終求得的哈夫曼樹共有2n-l個(gè)結(jié)點(diǎn)

D.若初始森林中共有n裸二叉樹，進(jìn)行2n-l次合并后才能剩下一棵最終的哈夫樹

5.深度為6的二叉樹最多有（）個(gè)結(jié)點(diǎn)（）

A.64B.63C.32D.31

6.將含有83個(gè)結(jié)點(diǎn)的完全二叉樹從根結(jié)點(diǎn)開始編號(hào)，根為1號(hào)，后面按從上到下、從

左到右的順序?qū)Y(jié)點(diǎn)編號(hào)，那么編號(hào)為41的雙結(jié)點(diǎn)編號(hào)為（）

A.42B.40C.21D.20

7.設(shè)二叉樹有n個(gè)結(jié)點(diǎn)，則其深度為（）

A.n-1B.nC.5floor（log2n）D.無法確定

注：完全二叉樹才能確定其深度。

8.設(shè)深度為k的二叉樹上只有度為0和度為2的節(jié)點(diǎn)，則這類二叉樹上所含結(jié)點(diǎn)總

數(shù)最少（）個(gè)

A.k+1B.2kC.2k-1D.2k+1

注：單支數(shù)含結(jié)點(diǎn)個(gè)數(shù)最少，但題目規(guī)定該二叉樹中不存在度為1的結(jié)點(diǎn)。所以，在

單支樹的基礎(chǔ)上把結(jié)點(diǎn)補(bǔ)齊，使之度數(shù)為2或0,結(jié)果就是有2k-l個(gè)結(jié)點(diǎn)。

9.下列說法中正確的是（）

A.任何一棵二叉樹中至少有一個(gè)結(jié)點(diǎn)的度為2

B.任何一棵二叉樹中每個(gè)結(jié)點(diǎn)的度都為2

C.任何一棵二叉樹中的度肯定等于2

D.任何一棵二叉樹中的度可以小于2

10.對(duì)含有（）個(gè)結(jié)點(diǎn)的非空二叉樹，采用任何一種遍歷方式，其結(jié)點(diǎn)訪問序列

均相同。

A.0B.lC.2D.不存在這樣的二叉樹

11.已知某二叉樹的后續(xù)遍歷序列是dabec,中序遍歷序列是deabc,它的先序遍歷序列是

（）

A.acbedB.deabcC.decabD.cedba

12.某二叉樹的先序遍歷結(jié)點(diǎn)訪問順序是abdgcefh,中序遍歷的結(jié)點(diǎn)訪問順序是

dgbaechf,則其后序遍歷的結(jié)點(diǎn)訪問順序是（）

A.bdgcefhaB.gdbecfhaC.D.bdgechfaD.gdbehfca

分析：先序遍歷序列的第一個(gè)字符為根結(jié)點(diǎn)。時(shí)于中序遍歷，根結(jié)點(diǎn)在中序遍歷序列的中間，左邊部分

是根結(jié)點(diǎn)的左子樹的中序遍歷序列，右邊部分是根結(jié)點(diǎn)的右子樹的中序遍歷序列。

先序：abdgcefh->abdgcefh

中序?dgbaechf->dgbaechf

得出結(jié)論：a是樹根，a有左子樹和右子樹，左子樹有bdg結(jié)點(diǎn)，右子樹有cefh結(jié)點(diǎn).

先序：bdg->bdg

中序：dgb->dgb

得出結(jié)論：b是左子樹的根結(jié)點(diǎn)，b無右子樹，有左子樹.

先序：dg->dg

中序：dg->dg

得出結(jié)論：d是b的左子樹的根結(jié)點(diǎn)，d無左子樹，有右子樹.

先序：cefh->cefh

中序：echf->echf

得出結(jié)論：c是右子樹的根結(jié)點(diǎn)，c有左子樹（只有巳結(jié)點(diǎn)），有右子樹（有fh結(jié)點(diǎn)）.

先序：fh—>fh

中序：hf->hf

得出結(jié)論：f是c的左子樹的根結(jié)點(diǎn)，用左子樹（只有h結(jié)點(diǎn)），無右子樹。

還原二叉樹為：

a

bc

def

gh

后序遍歷序列：gdbehfca

13、二叉樹的先序遍歷序列中，任意一個(gè)結(jié)點(diǎn)均處在其子女結(jié)點(diǎn)的前面，這種說法

（）

A.正確B.錯(cuò)誤

14.由于二叉樹中每個(gè)結(jié)點(diǎn)的度最大為2,所以二叉樹是一種特殊的樹，這種說法

（）

A.正確B.錯(cuò)誤

15.二叉樹是每個(gè)結(jié)點(diǎn)的度不超過2的有序樹的特殊情況，這種說法)

A.正確B.錯(cuò)誤

16.深度為5的二叉樹至多有()個(gè)結(jié)點(diǎn)。

A.16B.32C.31D.10

二、填空

1.樹(及一切樹形結(jié)構(gòu))是一種一1次_結(jié)構(gòu)。在樹上，結(jié)點(diǎn)沒有直接前趨。對(duì)

樹上任一結(jié)點(diǎn)X來說，X是它的任一干樹的根結(jié)點(diǎn)惟一的一雙親.。

2.一棵樹上的任何結(jié)點(diǎn)(不包括根本身)稱為根的子孫。若B是A的子孫，則

稱A是B的祖先

3.一般的，二叉樹有一空—二叉樹、一只有超—的二叉樹、只有_左子樹的二叉樹、

只有一右子樹____的二叉樹、同時(shí)有左子樹、右玉樹—的二叉樹五種基本形態(tài)。

4.二叉樹第i(i>=l)層上至多有"一個(gè)結(jié)點(diǎn)。

5.深度為k(k>=l)的二叉樹至多有上蟲個(gè)結(jié)點(diǎn)。

6.對(duì)任何二叉樹，若度為2的節(jié)點(diǎn)數(shù)為止，則葉子數(shù)n產(chǎn).1+L。

7.滿二叉樹上各層的結(jié)點(diǎn)數(shù)已達(dá)到了二叉樹可以容納的_極限一。滿二叉樹也是一完全二

叉樹，但反之不然。

8.具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為口哂」+

如果將一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹按層編號(hào)，則對(duì)任一編號(hào)為i(l<=i<=n)的結(jié)點(diǎn)X

有：

9,若i=l,則結(jié)點(diǎn)X是一根結(jié)點(diǎn)；；若i>L則X的雙親結(jié)點(diǎn)的編號(hào)為一返

10.二叉樹通常有酶_存儲(chǔ)結(jié)構(gòu)和暹式一存儲(chǔ)結(jié)構(gòu)兩類存儲(chǔ)結(jié)構(gòu)。

11.每個(gè)二叉鏈表的訪問只能從_握_結(jié)點(diǎn)的指針，該指針具有標(biāo)識(shí)二叉鏈表的作用。

12.對(duì)二叉鏈表的訪問只能從_根_指針開始,若二叉樹為空，則一根指針__=NULL.

13.二叉鏈表中每個(gè)存儲(chǔ)結(jié)點(diǎn)的每個(gè)指針域必須有一個(gè)值，這個(gè)值或者是_至—的

指針，或者是.左孩子或右孩子指針一

14.具有n個(gè)結(jié)點(diǎn)的二叉樹中,一共有個(gè)指針域，其中只有_m』一個(gè)用來指向結(jié)點(diǎn)

的左右孩子，其余的.n+1個(gè)指針域?yàn)镹ULLo

15.二叉樹有不同的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，其中最常用的是_二叉鏈表—與一三叉鏈表一。

16.在先序一遍歷二叉樹的序列中,任何結(jié)點(diǎn)的子樹上的所有結(jié)點(diǎn)，都是直接跟在該

結(jié)點(diǎn)之后。

17.哈夫曼樹是帶權(quán)路徑度一最小一的樹,通常權(quán)值較大的結(jié)點(diǎn)離根一越近一。

18.有m個(gè)葉子結(jié)點(diǎn)的哈夫曼樹，其結(jié)點(diǎn)總數(shù)為2m-L。

19.任意一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，若它有m個(gè)葉子，則該二叉樹上度數(shù)為1的結(jié)

點(diǎn)為n-2m+l個(gè)。根據(jù)P84性質(zhì)3:n2=n0-l

20.由任何一棵樹轉(zhuǎn)換成二叉樹時(shí),其根結(jié)點(diǎn)的右子樹總是空的。

三、簡答題

1.簡述二叉鏈表的類型定義。

2.簡述三叉鏈表的類型定義。

3.分別畫出含3個(gè)結(jié)點(diǎn)的樹與二叉樹的所有不同形態(tài)。

提示：含3個(gè)結(jié)點(diǎn)的樹，共有兩種形態(tài)；

含3個(gè)結(jié)點(diǎn)的二叉樹，共有五種形態(tài)

4.已知一棵二叉樹的中序遍歷根序列和后序遍歷序列分別為BDCEAFHG和EDCBHGEA,

試畫出這棵二叉樹。

5.將下圖所示的森林轉(zhuǎn)換成二叉樹。

6.給定權(quán)值7,18,3,32,5,26,12,8,構(gòu)造相應(yīng)的哈夫曼樹。

6、