第 1 章 緒 論
課后習(xí)題講解

1. 填空

⑴（ ）是數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體進行考慮和處理。
【解答】數(shù)據(jù)元素

⑵（ ）是數(shù)據(jù)的最小單位，（ ）是討論數(shù)據(jù)結(jié)構(gòu)時涉及的最小數(shù)據(jù)單位。
【解答】數(shù)據(jù)項，數(shù)據(jù)元素
【分析】數(shù)據(jù)結(jié)構(gòu)指的是數(shù)據(jù)元素以及數(shù)據(jù)元素之間的關(guān)系。

⑶ 從邏輯關(guān)系上講，數(shù)據(jù)結(jié)構(gòu)主要分為（ ）、（ ）、（ ）和（ ）。
【解答】集合，線性結(jié)構(gòu)，樹結(jié)構(gòu)，圖結(jié)構(gòu)

⑷ 數(shù)據(jù)的存儲結(jié)構(gòu)主要有（ ）和（ ）兩種基本方法，不論哪種存儲結(jié)構(gòu)，都要存儲兩方面的內(nèi)容：（ ）和（ ）。
【解答】順序存儲結(jié)構(gòu)，鏈接存儲結(jié)構(gòu)，數(shù)據(jù)元素，數(shù)據(jù)元素之間的關(guān)系

⑸ 算法具有五個特性，分別是（ ）、（ ）、（ ）、（ ）、（ ）。
【解答】有零個或多個輸入，有一個或多個輸出，有窮性，確定性，可行性

⑹ 算法的描述方法通常有（ ）、（ ）、（ ）和（ ）四種，其中，（ ）被稱為算法語言。
【解答】自然語言，程序設(shè)計語言，流程圖，偽代碼，偽代碼

⑺ 在一般情況下，一個算法的時間復(fù)雜度是（ ）的函數(shù)。
【解答】問題規(guī)模

⑻ 設(shè)待處理問題的規(guī)模為n，若一個算法的時間復(fù)雜度為一個常數(shù)，則表示成數(shù)量級的形式為（ ），若為n*log25n，則表示成數(shù)量級的形式為（ ）。
【解答】Ο(1)，Ο(nlog2n)
【分析】用大O記號表示算法的時間復(fù)雜度，需要將低次冪去掉，將最高次冪的系數(shù)去掉。

2. 選擇題

⑴ 順序存儲結(jié)構(gòu)中數(shù)據(jù)元素之間的邏輯關(guān)系是由（ ）表示的，鏈接存儲結(jié)構(gòu)中的數(shù)據(jù)元素之間的邏輯關(guān)系是由（ ）表示的。
A 線性結(jié)構(gòu) B 非線性結(jié)構(gòu) C 存儲位置 D 指針
【解答】C，D
【分析】順序存儲結(jié)構(gòu)就是用一維數(shù)組存儲數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素，其邏輯關(guān)系由存儲位置（即元素在數(shù)組中的下標(biāo)）表示；鏈接存儲結(jié)構(gòu)中一個數(shù)據(jù)元素對應(yīng)鏈表中的一個結(jié)點，元素之間的邏輯關(guān)系由結(jié)點中的指針表示。

⑵ 假設(shè)有如下遺產(chǎn)繼承規(guī)則：丈夫和妻子可以相互繼承遺產(chǎn)；子女可以繼承父親或母親的遺產(chǎn)；子女間不能相互繼承。則表示該遺產(chǎn)繼承關(guān)系的最合適的數(shù)據(jù)結(jié)構(gòu)應(yīng)該是（ ）。
A 樹 B 圖 C 線性表 D 集合
【解答】B
【分析】將丈夫、妻子和子女分別作為數(shù)據(jù)元素，根據(jù)題意畫出邏輯結(jié)構(gòu)圖。

⑶ 算法指的是（ ）。
A 對特定問題求解步驟的一種描述，是指令的有限序列。
B 計算機程序 C 解決問題的計算方法 D 數(shù)據(jù)處理
【解答】A
【分析】計算機程序是對算法的具體實現(xiàn)；簡單地說，算法是解決問題的方法；數(shù)據(jù)處理是通過算法完成的。所以，只有A是算法的準(zhǔn)確定義。

⑷ 下面（ ）不是算法所必須具備的特性。
A 有窮性 B 確切性 C 高效性 D 可行性
【解答】C
【分析】高效性是好算法應(yīng)具備的特性。

⑸ 算法分析的目的是（ ），算法分析的兩個主要方面是（ ）。
A 找出數(shù)據(jù)結(jié)構(gòu)的合理性 B 研究算法中輸入和輸出的關(guān)系
C 分析算法的效率以求改進 D 分析算法的易讀性和文檔性
E 空間性能和時間性能 F 正確性和簡明性
G 可讀性和文檔性 H 數(shù)據(jù)復(fù)雜性和程序復(fù)雜性
【解答】C，E

3. 判斷題

⑴ 算法的時間復(fù)雜度都要通過算法中的基本語句的執(zhí)行次數(shù)來確定。
【解答】錯。時間復(fù)雜度要通過算法中基本語句執(zhí)行次數(shù)的數(shù)量級來確定。

⑵ 每種數(shù)據(jù)結(jié)構(gòu)都具備三個基本操作：插入、刪除和查找。
【解答】錯。如數(shù)組就沒有插入和刪除操作。此題注意是每種數(shù)據(jù)結(jié)構(gòu)。

⑶ 所謂數(shù)據(jù)的邏輯結(jié)構(gòu)指的是數(shù)據(jù)之間的邏輯關(guān)系。
【解答】錯。是數(shù)據(jù)之間的邏輯關(guān)系的整體。

⑷ 邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無關(guān)。
【解答】對。因此邏輯結(jié)構(gòu)是數(shù)據(jù)組織的主要方面。

⑸ 基于某種邏輯結(jié)構(gòu)之上的基本操作，其實現(xiàn)是唯一的。
【解答】錯。基本操作的實現(xiàn)是基于某種存儲結(jié)構(gòu)設(shè)計的，因而不是唯一的。

4. 分析以下各程序段，并用大O記號表示其執(zhí)行時間。

　　　
【解答】⑴ 基本語句是k=k+10*i，共執(zhí)行了n-2次，所以T(n)=O(n)。
⑵ 基本語句是k=k+10*i，共執(zhí)行了n次，所以T(n)=O(n)。
⑶ 分析條件語句，每循環(huán)一次，i+j 整體加1，共循環(huán)n次，所以T(n)=O(n)。
⑷ 設(shè)循環(huán)體共執(zhí)行T(n)次，每循環(huán)一次，循環(huán)變量y加1，最終T(n)=y，即：
(T(n)+1)2≤n，所以T(n)=O(n1/2)。
⑸ x++是基本語句，所以

5．設(shè)有數(shù)據(jù)結(jié)構(gòu)（D，R），其中D={1, 2, 3, 4, 5, 6}，R={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}。試畫出其邏輯結(jié)構(gòu)圖并指出屬于何種結(jié)構(gòu)。
【解答】其邏輯結(jié)構(gòu)圖如圖1-3所示，它是一種圖結(jié)構(gòu)。

6. 為整數(shù)定義一個抽象數(shù)據(jù)類型，包含整數(shù)的常見運算，每個運算對應(yīng)一個基本操作，每個基本操作的接口需定義前置條件、輸入、功能、輸出和后置條件。
【解答】整數(shù)的抽象數(shù)據(jù)類型定義如下：
ADT integer
Data
整數(shù)a：可以是正整數(shù)(1, 2, 3, … )、負整數(shù)(-1, -2, -3, …)和零
Operation
Constructor
前置條件：整數(shù)a不存在
輸入：一個整數(shù)b
功能：構(gòu)造一個與輸入值相同的整數(shù)
輸出：無
后置條件：整數(shù)a具有輸入的值
Set
前置條件：存在一個整數(shù)a
輸入：一個整數(shù)b
功能：修改整數(shù)a的值，使之與輸入的整數(shù)值相同
輸出：無
后置條件：整數(shù)a的值發(fā)生改變
Add
前置條件：存在一個整數(shù)a
輸入：一個整數(shù)b
功能：將整數(shù)a與輸入的整數(shù)b相加
輸出：相加后的結(jié)果
后置條件：整數(shù)a的值發(fā)生改變
Sub
前置條件：存在一個整數(shù)a
輸入：一個整數(shù)b
功能：將整數(shù)a與輸入的整數(shù)b相減
輸出：相減的結(jié)果
后置條件：整數(shù)a的值發(fā)生改變
Multi
前置條件：存在一個整數(shù)a
輸入：一個整數(shù)b
功能：將整數(shù)a與輸入的整數(shù)b相乘
輸出：相乘的結(jié)果
后置條件：整數(shù)a的值發(fā)生改變
Div
前置條件：存在一個整數(shù)a
輸入：一個整數(shù)b
功能：將整數(shù)a與輸入的整數(shù)b相除
輸出：若整數(shù)b為零，則拋出除零異常，否則輸出相除的結(jié)果
后置條件：整數(shù)a的值發(fā)生改變
Mod
前置條件：存在一個整數(shù)a
輸入：一個整數(shù)b
功能：求當(dāng)前整數(shù)與輸入整數(shù)的模，即正的余數(shù)
輸出：若整數(shù)b為零，則拋出除零異常，否則輸出取模的結(jié)果
后置條件：整數(shù)a的值發(fā)生改變
Equal
前置條件：存在一個整數(shù)a
輸入：一個整數(shù)b
功能：判斷整數(shù)a與輸入的整數(shù)b是否相等
輸出：若相等返回1，否則返回0
后置條件：整數(shù)a的值不發(fā)生改變
endADT

7. 求多項式A(x)的算法可根據(jù)下列兩個公式之一來設(shè)計：
⑴ A(x)=anxn+an-1xn-1+…+a1x+a0
⑵ A(x)=(…(anx+an-1)x+…+a1)x)+a0
根據(jù)算法的時間復(fù)雜度分析比較這兩種算法的優(yōu)劣。
【解答】第二種算法的時間性能要好些。第一種算法需執(zhí)行大量的乘法運算，而第二種算法進行了優(yōu)化，減少了不必要的乘法運算。

8. 算法設(shè)計（要求：算法用偽代碼和C++描述，并分析最壞情況下的時間復(fù)雜度）
⑴ 對一個整型數(shù)組A[n]設(shè)計一個排序算法。
【解答】下面是簡單選擇排序算法的偽代碼描述。

下面是簡單選擇排序算法的C++描述。

分析算法，有兩層嵌套的for循環(huán)，所以， 。

⑵ 找出整型數(shù)組A[n]中元素的最大值和次最大值。
【解答】算法的偽代碼描述如下：

算法的C++描述如下：

分析算法，只有一層循環(huán)，共執(zhí)行n-2次，所以，T(n)=O(n)。

學(xué)習(xí)自測及答案

1．順序存儲結(jié)構(gòu)的特點是（ ），鏈接存儲結(jié)構(gòu)的特點是（ ）。
【解答】用元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系，用指示元素存儲地址的指針表示數(shù)據(jù)元素之間的邏輯關(guān)系。

2. 算法在發(fā)生非法操作時可以作出處理的特性稱為（ ）。
【解答】健壯性

3. 常見的算法時間復(fù)雜度用大Ｏ記號表示為：常數(shù)階( )、對數(shù)階( )、線性階 ( )、平方階( )和指數(shù)階( )。
【解答】Ｏ(1)，Ｏ(log2n)，Ｏ(n)，Ｏ(n2)，Ｏ(2n)

4．將下列函數(shù)按它們在n 時的無窮大階數(shù)，從小到大排列。
n, n-n3+7n5, nlogn, 2n/2, n3, log2n, n1/2+log2n, (3/2)n, n!, n2+log2n
【解答】log2n, n1/2+log2n, n, nlog2n, n2+log2n, n3, n-n3+7n5, 2n/2, (3/2)n, n!

5．試描述數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)據(jù)類型的概念與程序設(shè)計語言中數(shù)據(jù)類型概念的區(qū)別。
【解答】數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一定關(guān)系的數(shù)據(jù)元素的集合。而抽象數(shù)據(jù)類型是指一個數(shù)據(jù)結(jié)構(gòu)以及定義在該結(jié)構(gòu)上的一組操作。程序設(shè)計語言中的數(shù)據(jù)類型是一個值的集合和定義在這個值集上一組操作的總稱。抽象數(shù)據(jù)類型可以看成是對數(shù)據(jù)類型的一種抽象。

6. 對下列用二元組表示的數(shù)據(jù)結(jié)構(gòu),試分別畫出對應(yīng)的邏輯結(jié)構(gòu)圖，并指出屬于何種結(jié)構(gòu)。
⑴ A=(D，R)， 其中D={a1, a2, a3, a4}，R={ }
⑵ B=(D，R)， 其中D={a, b, c, d, e, f}，R={,,,,}
⑶ C=( D，R)，其中D={a，b，c，d，e，f}，R={,,,,,}
⑷ D=(D，R)， 其中D={1, 2, 3, 4, 5, 6}，
R={(1, 2)，(1, 4)，(2, 3)，(2, 4)，(3, 4)，(3, 5)，(3, 6)，(4, 6)}
【解答】⑴ 屬于集合，其邏輯結(jié)構(gòu)圖如圖1-4(a)所示；⑵ 屬于線性結(jié)構(gòu)，其邏輯結(jié)構(gòu)圖如圖1-4(b)所示；⑶ 屬于樹結(jié)構(gòu)，其邏輯結(jié)構(gòu)圖如圖1-4(c)所示；⑷ 屬于圖結(jié)構(gòu)，其邏輯結(jié)構(gòu)圖如圖1-4(d)所示。

7. 求下列算法的時間復(fù)雜度。
count=0; x=1;
while (x {
x*=2;
count++;
}
return count;
【解答】Ｏ(log2n)

第 2 章 線性表
課后習(xí)題講解

1. 填空

⑴ 在順序表中，等概率情況下，插入和刪除一個元素平均需移動（ ）個元素，具體移動元素的個數(shù)與（ ）和（ ）有關(guān)。
【解答】表長的一半，表長，該元素在表中的位置

⑵ 順序表中第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的存儲地址是（ ）。
【解答】108
【分析】第5個元素的存儲地址=第1個元素的存儲地址＋(5－1)×2=108

⑶ 設(shè)單鏈表中指針p 指向結(jié)點A，若要刪除A的后繼結(jié)點（假設(shè)A存在后繼結(jié)點），則需修改指針的操作為（ ）。
【解答】p->next=(p->next)->next

⑷ 單鏈表中設(shè)置頭結(jié)點的作用是（ ）。
【解答】為了運算方便
【分析】例如在插入和刪除操作時不必對表頭的情況進行特殊處理。

⑸ 非空的單循環(huán)鏈表由頭指針head指示，則其尾結(jié)點（由指針p所指）滿足（ ）。
【解答】p->next=head
【分析】如圖2-8所示。

⑹ 在由尾指針rear指示的單循環(huán)鏈表中，在表尾插入一個結(jié)點s的操作序列是（ ）；刪除開始結(jié)點的操作序列為（ ）。
【解答】s->next =rear->next; rear->next =s; rear =s;
q=rear->next->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)；而在給定值為x的結(jié)點后插入一個新結(jié)點需要先查找值為x的結(jié)點，所以時間復(fù)雜度為Ο(n)。

⑻ 可由一個尾指針唯一確定的鏈表有（ ）、（ ）、（ ）。
【解答】循環(huán)鏈表，循環(huán)雙鏈表，雙鏈表

2. 選擇題

⑴ 線性表的順序存儲結(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é)點的位置后，能夠容易找到它的直接前趨；
D 在進行插入、刪除操作時，能更好地保證鏈表不斷開。
【解答】B

⑷ 鏈表不具有的特點是（ ）。
A 可隨機訪問任一元素 B 插入、刪除不需要移動元素
C 不必事先估計存儲空間 D 所需空間與線性表長度成正比
【解答】A

⑸ 若某線性表中最常用的操作是取第i 個元素和找第i個元素的前趨，則采用（ ）存儲方法最節(jié)省時間。
A 順序表 B 單鏈表 C 雙鏈表 D 單循環(huán)鏈表
【解答】A
【分析】線性表中最常用的操作是取第i 個元素，所以，應(yīng)選擇隨機存取結(jié)構(gòu)即順序表，同時在順序表中查找第i個元素的前趨也很方便。單鏈表和單循環(huán)鏈表既不能實現(xiàn)隨機存取，查找第i個元素的前趨也不方便，雙鏈表雖然能快速查找第i個元素的前趨，但不能實現(xiàn)隨機存取。

⑹ 若鏈表中最常用的操作是在最后一個結(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
【分析】在鏈表中的最后一個結(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(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;
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->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. 判斷題

⑴ 線性表的邏輯順序和存儲順序總是一致的。
【解答】錯。順序表的邏輯順序和存儲順序一致，鏈表的邏輯順序和存儲順序不一定一致。

⑵ 線性表的順序存儲結(jié)構(gòu)優(yōu)于鏈接存儲結(jié)構(gòu)。
【解答】錯。兩種存儲結(jié)構(gòu)各有優(yōu)缺點。

⑶ 設(shè)p，q是指針，若p=q，則*p=*q。
【解答】錯。p=q只能表示p和q指向同一起始地址，而所指類型則不一定相同。

⑷ 線性結(jié)構(gòu)的基本特征是：每個元素有且僅有一個直接前驅(qū)和一個直接后繼。
【解答】錯。每個元素最多只有一個直接前驅(qū)和一個直接后繼，第一個元素沒有前驅(qū)，最后一個元素沒有后繼。

⑸ 在單鏈表中，要取得某個元素，只要知道該元素所在結(jié)點的地址即可，因此單鏈表是隨機存取結(jié)構(gòu)。
【解答】錯。要找到該結(jié)點的地址，必須從頭指針開始查找，所以單鏈表是順序存取結(jié)構(gòu)。

4．請說明順序表和單鏈表各有何優(yōu)缺點，并分析下列情況下，采用何種存儲結(jié)構(gòu)更好些。
⑴ 若線性表的總長度基本穩(wěn)定，且很少進行插入和刪除操作，但要求以最快的速度存取線性表中的元素。
⑵ 如果n個線性表同時并存，并且在處理過程中各表的長度會動態(tài)發(fā)生變化。
⑶ 描述一個城市的設(shè)計和規(guī)劃。
【解答】順序表的優(yōu)點：① 無需為表示表中元素之間的邏輯關(guān)系而增加額外的存儲空間；② 可以快速地存取表中任一位置的元素（即隨機存取）。順序表的缺點：① 插入和刪除操作需移動大量元素；② 表的容量難以確定；③ 造成存儲空間的“碎片”。
單鏈表的優(yōu)點：① 不必事先知道線性表的長度；② 插入和刪除元素時只需修改指針，不用移動元素。單鏈表的缺點：① 指針的結(jié)構(gòu)性開銷；② 存取表中任意元素不方便，只能進行順序存取。
⑴ 應(yīng)選用順序存儲結(jié)構(gòu)。因為順序表是隨機存取結(jié)構(gòu)，單鏈表是順序存取結(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ù)組A[n]中所有元素循環(huán)右移k個位置。
【解答】算法思想請參見主教材第一章思想火花。下面給出具體算法。

分析算法，第一次調(diào)用Reverse函數(shù)的時間復(fù)雜度為O(k)，第二次調(diào)用Reverse函數(shù)的時間復(fù)雜度為O(n-k)，第三次調(diào)用Reverse函數(shù)的時間復(fù)雜度為O(n)，所以，總的時間復(fù)雜度為O(n)。

⑵ 已知數(shù)組A[n]中的元素為整型，設(shè)計算法將其調(diào)整為左右兩部分，左邊所有元素為奇數(shù)，右邊所有元素為偶數(shù)，并要求算法的時間復(fù)雜度為Ｏ(n)。
【解答】從數(shù)組的兩端向中間比較，設(shè)置兩個變量i和j，初始時i=0，j=n-1，若A[i]為偶數(shù)并且A[j]為奇數(shù)，則將A[i]與A[j]交換。具體算法如下：

分析算法，兩層循環(huán)將數(shù)組掃描一遍，所以，時間復(fù)雜度為Ｏ(n)。

⑶ 試編寫在無頭結(jié)點的單鏈表上實現(xiàn)線性表的插入操作的算法，并和帶頭結(jié)點的單鏈表上的插入操作的實現(xiàn)進行比較。
【解答】參見2.2.3。

⑷ 試分別以順序表和單鏈表作存儲結(jié)構(gòu)，各寫一實現(xiàn)線性表就地逆置的算法。
【解答】順序表的逆置，即是將對稱元素交換，設(shè)順序表的長度為length，則將表中第i個元素與第length-i-1個元素相交換。具體算法如下：

單鏈表的逆置請參見2.2.4算法2-4和算法2-6。

⑸ 假設(shè)在長度大于1的循環(huán)鏈表中，即無頭結(jié)點也無頭指針，s為指向鏈表中某個結(jié)點的指針，試編寫算法刪除結(jié)點s的前趨結(jié)點。
【解答】利用單循環(huán)鏈表的特點，通過指針s可找到其前驅(qū)結(jié)點r以及r的前驅(qū)結(jié)點p，然后將結(jié)點r刪除，如圖2-11所示，具體算法如下：

⑹ 已知一單鏈表中的數(shù)據(jù)元素含有三類字符：字母、數(shù)字和其他字符。試編寫算法，構(gòu)造三個循環(huán)鏈表，使每個循環(huán)鏈表中只含同一類字符。
【解答】在單鏈表A中依次取元素，若取出的元素是字母，把它插入到字母鏈表B 中，若取出的元素是數(shù)字，則把它插入到數(shù)字鏈表D中，直到鏈表的尾部，這樣表B，D，A中分別存放字母、數(shù)字和其他字符。具體算法如下：

⑺ 設(shè)單鏈表以非遞減有序排列，設(shè)計算法實現(xiàn)在單鏈表中刪去值相同的多余結(jié)點。

【解答】從頭到尾掃描單鏈表，若當(dāng)前結(jié)點的元素值與后繼結(jié)點的元素值不相等，則指針后移；否則刪除該后繼結(jié)點。具體算法如下：

⑻ 判斷帶頭結(jié)點的雙循環(huán)鏈表是否對稱。
【解答】設(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é)點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
【解答】D

2．在長度為n的線性表中查找值為x的數(shù)據(jù)元素的時間復(fù)雜度為： （ ）。
A O(0) B O(1) C O(n) D O(n2)
【解答】C

3．在一個長度為n的順序表的第i（1≤i≤n+1）個元素之前插入一個元素，需向后移動（ ）個元素，刪除第i（1≤i≤n）個元素時，需向前移動（ ）個元素。
【解答】n-i+1，n-i

4．在單鏈表中，除了頭結(jié)點以外，任一結(jié)點的存儲位置由（ ）指示。
【解答】其前趨結(jié)點的指針域

5．當(dāng)線性表采用順序存儲結(jié)構(gòu)時，其主要特點是（ ）。
【解答】邏輯結(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之間（1≤i≤n）的概率為 ，則平均每插入一個元素所要移動的元素個數(shù)又是多少？
【解答】

，

。

8．線性表存放在整型數(shù)組A[arrsize]的前elenum 個單元中，且遞增有序。編寫算法，將元素x插入到線性表的適當(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, 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后，輸出序列是（ ），棧頂指針為（ ）。
【解答】23，1003H

⑵ 棧通常采用的兩種存儲結(jié)構(gòu)是（ ）；其判定棧空的條件分別是（ ），判定棧滿的條件分別是（ ）。
【解答】順序存儲結(jié)構(gòu)和鏈接存儲結(jié)構(gòu)（或順序棧和鏈棧），棧頂指針top= -1和top=NULL，棧頂指針top等于數(shù)組的長度和內(nèi)存無可用空間

⑶（ ）可作為實現(xiàn)遞歸函數(shù)調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)。
【解答】棧
【分析】遞歸函數(shù)的調(diào)用和返回正好符合后進先出性。

⑷ 表達式a*(b+c)-d的后綴表達式是（ ）。
【解答】abc+*d-
【分析】將中綴表達式變?yōu)楹缶Y表達式有一個技巧：將操作數(shù)依次寫下來，再將算符插在它的兩個操作數(shù)的后面。

⑸ 棧和隊列是兩種特殊的線性表，棧的操作特性是（ ），隊列的操作特性是（ ），棧和隊列的主要區(qū)別在于（ ）。
【解答】后進先出，先進先出，對插入和刪除操作限定的位置不同

⑹ 循環(huán)隊列的引入是為了克服（ ）。
【解答】假溢出

⑺ 數(shù)組Q[n]用來表示一個循環(huán)隊列，front為隊頭元素的前一個位置，rear為隊尾元素的位置，計算隊列中元素個數(shù)的公式為（ ）。
【解答】（rear-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é)點的地址。

⑼ 串是一種特殊的線性表，其特殊性體現(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，一個元素出棧后即進入隊列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 鏈表
【解答】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 插入、刪除運算的限定不一樣
【解答】D
【分析】棧和隊列的邏輯結(jié)構(gòu)都是線性的，都有順序存儲和鏈接存儲，有可能包含的運算不一樣，但不是主要區(qū)別，任何數(shù)據(jù)結(jié)構(gòu)在針對具體問題時包含的運算都可能不同。

⑻ 設(shè)數(shù)組S[n]作為兩個棧S1和S2的存儲空間，對任何一個棧只有當(dāng)S[n]全滿時才不能進行進棧操作。為這兩個棧分配空間的最佳方案是（ ）。
A S1的棧底位置為0，S2的棧底位置為n-1
B S1的棧底位置為0，S2的棧底位置為n/2
C S1的棧底位置為0，S2的棧底位置為n
D S1的棧底位置為0，S2的棧底位置為1
【解答】A
【分析】兩棧共享空間首先兩個棧是相向增長的，棧底應(yīng)該分別指向兩個棧中的第一個元素的位置，并注意C++中的數(shù)組下標(biāo)是從0開始的。

⑼ 設(shè)有兩個串p和q，求q在p中首次出現(xiàn)的位置的運算稱作（ ）。
A 連接 B 模式匹配 C 求子串 D 求串長
【解答】B

3. 判斷題

⑴ 有n個元素依次進棧，則出棧序列有(n-1)/2種。
【解答】錯。應(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。
【解答】錯。這是隊空的判定條件，在循環(huán)隊列中要將隊空和隊滿的判定條件區(qū)別開。

⑸ 空串與空格串是相同的。
【解答】錯。空串的長度為零，而空格串的長度不為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)象。
【解答】假設(shè)有一個順序隊列，如圖3-6所示，隊尾指針rear=4，隊頭指針front=1，如果再有元素入隊，就會產(chǎn)生“上溢”，此時的“上溢”又稱為“假溢出”，因為隊列并不是真的溢出了，存儲隊列的數(shù)組中還有2個存儲單元空閑，其下標(biāo)分別為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表示隊頭元素出隊）。
【解答】隊頭元素為5，隊尾元素為9。其執(zhí)行過程如圖3-8所示。

8．空串和空格串有何區(qū)別？串中的空格符有何意義？空串在串處理中有何作用？
【解答】不含任何字符的串稱為空串，其長度為零。僅含空格的串稱為空格串，它的長度為串中空格符的個數(shù)。串中的空格符可用來分隔一般的字符，便于人們識別和閱讀，但計算串長時應(yīng)包括這些空格符?？沾诖幚碇锌勺鳛槿我獯淖哟?。

9. 算法設(shè)計
⑴ 假設(shè)以不帶頭結(jié)點的循環(huán)鏈表表示隊列，并且只設(shè)一個指針指向隊尾結(jié)點，但不設(shè)頭指針。試設(shè)計相應(yīng)的入隊和出隊的算法。
【解答】出隊操作是在循環(huán)鏈表的頭部進行，相當(dāng)于刪除開始結(jié)點，而入隊操作是在循環(huán)鏈表的尾部進行，相當(dāng)于在終端結(jié)點之后插入一個結(jié)點。由于循環(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，編寫算法刪除S中第 i個字符開始的連續(xù)j個字符。
【解答】先判斷串S中要刪除的內(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個單元的順序棧中，假定以地址低端（即下標(biāo)為0的單元）作為棧底，以top作為棧頂指針，當(dāng)出棧時，top的變化為（ ）。
A 不變 B top=0; C top=top-1; D top=top+1;
【解答】C

2．一個棧的入棧序列是a, b, c, d, e，則棧的不可能的出棧序列是（ ）。
A edcba B cdeba C debca D abcde
【解答】C

3．從棧頂指針為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;
【解答】D

4．設(shè)元素1, 2, 3, P, A依次經(jīng)過一個棧，進棧次序為123PA，在棧的輸出序列中，有哪些序列可作為C++程序設(shè)計語言的變量名。
【解答】PA321, P3A21, P32A1, P321A, AP321

5.設(shè)S="I_ am_ a_ teacther"，其長度為（ ）。
【解答】15

6．對于棧和隊列，無論它們采用順序存儲結(jié)構(gòu)還是鏈接存儲結(jié)構(gòu)，進行插入和刪除操作的時間復(fù)雜度都是（ ）。
【解答】Ｏ(1)

7．如果進棧序列為A、B、C、D，則可能的出棧序列是什么？
答：共14種，分別是：ABCD，ABDC，ACBD，ACDB，ADCB，BACD，BADC，BCAD，BCDA，BDCA，CBAD，CBDA，CDBA，DCBA

8．簡述隊列和棧這兩種數(shù)據(jù)結(jié)構(gòu)的相同點和不同點。
【解答】相同點：它們都是插入和刪除操作的位置受限制的線性表。
不同點：棧是限定僅在表尾進行插入和刪除的線性表，是后進先出的線性表，而隊列是限定在表的一端進行插入，在另一端進行刪除的線性表，是先進先出的線性表。

9. 利用兩個棧S1和S2模擬一個隊列，如何利用棧的運算實現(xiàn)隊列的插入和刪除操作，請簡述算法思想。
【解答】利用兩個棧S1和S2模擬一個隊列，當(dāng)需要向隊列中插入一個元素時，用S1來存放已輸入的元素，即通過向棧S1執(zhí)行入棧操作來實現(xiàn)；當(dāng)需要從隊列中刪除元素時，則將S1中元素全部送入到S2中，再從S2中刪除棧頂元素，最后再將S2中元素全部送入到S1中；判斷隊空的條件是：棧S1和S2同時為空。

10. 設(shè)計算法把一個十進制整數(shù)轉(zhuǎn)換為二至九進制之間的任一進制數(shù)輸出。
【解答】算法基于原理：N=(N div d)×d + N mod d （div為整除運算，mod為求余運算）。

11．假設(shè)一個算術(shù)表達式中可以包含三種括號：圓括號“（”和“）”，方括號“[”和“]”以及花括號“{”和“}”，且這三種括號可按任意的次序嵌套使用。編寫算法判斷給定表達式中所含括號是否配對出現(xiàn)。
【解答】假設(shè)表達式已存入字符數(shù)組A[n]中，具體算法如下：

第 4 章 廣義線性表——多維數(shù)組和廣義表
課后習(xí)題講解

1. 填空

⑴ 數(shù)組通常只有兩種運算：（ ）和（ ），這決定了數(shù)組通常采用（ ）結(jié)構(gòu)來實現(xiàn)存儲。
【解答】存取，修改，順序存儲
【分析】數(shù)組是一個具有固定格式和數(shù)量的數(shù)據(jù)集合，在數(shù)組上一般不能做插入、刪除元素的操作。除了初始化和銷毀之外，在數(shù)組中通常只有存取和修改兩種操作。

⑵ 二維數(shù)組A中行下標(biāo)從10到20，列下標(biāo)從5到10，按行優(yōu)先存儲，每個元素占4個存儲單元，A[10][5]的存儲地址是1000，則元素A[15][10]的存儲地址是（ ）。
【解答】1140
【分析】數(shù)組A中每行共有6個元素，元素A[15][10]的前面共存儲了(15-10)×6+5個元素，每個元素占4個存儲單元，所以，其存儲地址是1000+140=1140。

⑶ 設(shè)有一個10階的對稱矩陣A采用壓縮存儲，A[0][0]為第一個元素，其存儲地址為d，每個元素占1個存儲單元，則元素A[8][5]的存儲地址為（ ）。
【解答】d+41
【分析】元素A[8][5]的前面共存儲了(1+2+…+8)+5=41個元素。

⑷ 稀疏矩陣一般壓縮存儲方法有兩種，分別是（ ）和（ ）。
【解答】三元組順序表，十字鏈表

⑸ 廣義表((a), (((b),c)),(d))的長度是（　　　），深度是（　　?。?，表頭是（　　?。?，表尾是（　　?。?BR>【解答】3，4，(a)，((((b),c)),(d))

⑹ 已知廣義表LS=(a，(b，c，d)，e)，用Head和Tail函數(shù)取出LS中原子b的運算是（ ）。
【解答】Head(Head(Tail(LS)))

2. 選擇題

⑴ 二維數(shù)組A的每個元素是由6個字符組成的串，行下標(biāo)的范圍從0~8，列下標(biāo)的范圍是從0~9，則存放A至少需要（　　?。﹤€字節(jié)，A的第8列和第5行共占（　　?。﹤€字節(jié)，若A按行優(yōu)先方式存儲，元素A[8][5]的起始地址與當(dāng)A按列優(yōu)先方式存儲時的（ ）元素的起始地址一致。
A 90 B 180 C 240 D 540 E 108 F 114 G 54
H A[8][5] I A[3][10] J A[5][8] K A[4][9]
【解答】D，E，K
【分析】數(shù)組A為9行10列，共有90個元素，所以，存放A至少需要90×6=540個存儲單元，第8列和第5行共有18個元素（注意行列有一個交叉元素），所以，共占108個字節(jié)，元素A[8][5]按行優(yōu)先存儲的起始地址為d+8×10+5=d+85，設(shè)元素A[i][j]按列優(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

⑸ 廣義表((a), (((b),c)),(d))的長度是（　　?。?，深度是（　　　），表頭是（　　?。?，表尾是（　　　）。
【解答】3，4，(a)，((((b),c)),(d))

⑹ 已知廣義表LS=(a，(b，c，d)，e)，用Head和Tail函數(shù)取出LS中原子b的運算是（ ）。
【解答】Head(Head(Tail(LS)))

2. 選擇題

⑴ 二維數(shù)組A的每個元素是由6個字符組成的串，行下標(biāo)的范圍從0~8，列下標(biāo)的范圍是從0~9，則存放A至少需要（　　?。﹤€字節(jié)，A的第8列和第5行共占（　　?。﹤€字節(jié)，若A按行優(yōu)先方式存儲，元素A[8][5]的起始地址與當(dāng)A按列優(yōu)先方式存儲時的（ ）元素的起始地址一致。
A 90 B 180 C 240 D 540 E 108 F 114 G 54
H A[8][5] I A[3][10] J A[5][8] K A[4][9]
【解答】D，E，K
【分析】數(shù)組A為9行10列，共有90個元素，所以，存放A至少需要90×6=540個存儲單元，第8列和第5行共有18個元素（注意行列有一個交叉元素），所以，共占108個字節(jié)，元素A[8][5]按行優(yōu)先存儲的起始地址為d+8×10+5=d+85，設(shè)元素A[i][j]按列優(yōu)先存儲的起始地址與之相同，則d+j×9+i=d+85，解此方程，得i=4，j=9。

⑵ 將數(shù)組稱為隨機存取結(jié)構(gòu)是因為（　　?。?BR>A 數(shù)組元素是隨機的 B 對數(shù)組任一元素的存取時間是相等的
C 隨時可以對數(shù)組進行訪問 D 數(shù)組的存儲結(jié)構(gòu)是不定
【解答】B

⑶ 下面的說法中，不正確的是（　　　）
A 數(shù)組是一種線性結(jié)構(gòu) B 數(shù)組是一種定長的線性結(jié)構(gòu)
C 除了插入與刪除操作外，數(shù)組的基本操作還有存取、修改、檢索和排序等
D 數(shù)組的基本操作有存取、修改、檢索和排序等，沒有插入與刪除操
【解答】C
【分析】數(shù)組屬于廣義線性表，數(shù)組被創(chuàng)建以后，其維數(shù)和每維中的元素個數(shù)是確定的，所以，數(shù)組通常沒有插入和刪除操作。

⑷ 對特殊矩陣采用壓縮存儲的目的主要是為了（　　?。?BR>A 表達變得簡單 B 對矩陣元素的存取變得簡單
C 去掉矩陣中的多余元素 D 減少不必要的存儲空間
【解答】D
【分析】在特殊矩陣中，有很多值相同的元素并且他們的分布有規(guī)律，沒有必要為值相同的元素重復(fù)存儲。

⑸ 下面（　　?。┎粚儆谔厥饩仃嚒?BR>A 對角矩陣 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)。

⑻ 下面的說法中，不正確的是（　　?。?BR>A 對稱矩陣只須存放包括主對角線元素在內(nèi)的下（或上）三角的元素即可。
B 對角矩陣只須存放非零元素即可。
C 稀疏矩陣中值為零的元素較多，因此可以采用三元組表方法存儲。
D 稀疏矩陣中大量值為零的元素分布有規(guī)律，因此可以采用三元組表方法存儲
【解答】D
【分析】稀疏矩陣中大量值為零的元素分布沒有規(guī)律，因此采用三元組表存儲。如果零元素的分布有規(guī)律，就沒有必要存儲非零元素的行號和列號，而需要按其壓縮規(guī)律找出相應(yīng)的映象函數(shù)。

3. 判斷題

⑴ 數(shù)組是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，數(shù)組元素之間的關(guān)系既不是線性的，也不是樹形的。
【解答】錯。例如二維數(shù)組可以看成是數(shù)據(jù)元素為線性表的線性表。

⑵ 使用三元組表存儲稀疏矩陣的元素，有時并不能節(jié)省存儲空間。
【解答】對。因為三元組表除了存儲非零元素值外，還需要存儲其行號和列號。

⑶ 稀疏矩陣壓縮存儲后，必會失去隨機存取功能。
【解答】對。因為壓縮存儲后，非零元素的存儲位置和行號、列號之間失去了確定的關(guān)系。

⑷ 線性表可以看成是廣義表的特例，如果廣義表中的每個元素都是單元素，則廣義表便成為線性表。
【解答】對。

⑸ 若一個廣義表的表頭為空表，則此廣義表亦為空表。
【解答】錯。如廣義表L=(( )，(a，b))的表頭為空表，但L不是空表。

4．一個稀疏矩陣如圖4-4所示，寫出對應(yīng)的三元組順序表和十字鏈表存儲表示。

【解答】對應(yīng)的三元組順序表如圖4-5所示，十字鏈表如圖4-6所示。

面 6 共 10

5．已知A為稀疏矩陣，試從空間和時間角度比較采用二維數(shù)組和三元組順序表兩種不同的存儲結(jié)構(gòu)完成求 運算的優(yōu)缺點。
【解答】設(shè)稀疏矩陣為m行n列，如果采用二維數(shù)組存儲，其空間復(fù)雜度為Ｏ(m×n)；因為要將所有的矩陣元素累加起來，所以，需要用一個兩層的嵌套循環(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)。
【解答】⑴ ST=((基本工資，津貼，獎金)，(水，電，煤氣)，實發(fā)金額)
Head(Tail(Tail(Head(ST))))=獎金
⑵ 工資表ST的頭尾表示法如圖4-7所示。

7．若在矩陣A中存在一個元素ai,j（0≤i≤n-1，0≤j≤m-1），該元素是第i行元素中最小值且又是第j列元素中最大值，則稱此元素為該矩陣的一個馬鞍點。假設(shè)以二維數(shù)組存儲矩陣A，試設(shè)計一個求該矩陣所有馬鞍點的算法，并分析最壞情況下的時間復(fù)雜度。
【解答】在矩陣中逐行尋找該行中的最小值，然后對其所在的列尋找最大值，如果該列上的最大值與該行上的最小值相等，則說明該元素是鞍點，將它所在行號和列號輸出。

具體算法如下：

分析算法，外層for循環(huán)共執(zhí)行n次，內(nèi)層第一個for循環(huán)執(zhí)行m次，第二個for循環(huán)最壞情況下執(zhí)行n次，所以，最壞情況下的時間復(fù)雜度為Ｏ(mn+n2)。

學(xué)習(xí)自測及答案

1．二維數(shù)組M中每個元素的長度是3個字節(jié)，行下標(biāo)從0到7，列下標(biāo)從0到9，從首地址d開始存儲。若按行優(yōu)先方式存儲，元素M[7][5]的起始地址為（　　 ），若按列優(yōu)先方式存儲，元素M[7][5]的起始地址為（　　 ）。
【解答】d+22，d+141

2．一個n×n的對稱矩陣，按行優(yōu)先或列優(yōu)先進行壓縮存儲，則其存儲容量為（　　 ）。
【解答】n(n+1)/2

3．設(shè)n行n列的下三角矩陣A（行列下標(biāo)均從1開始）已壓縮到一維數(shù)組S[1]~S[n(n+1)/2]中，若按行優(yōu)先存儲，則A[i][j]在數(shù)組S中的存儲位置是（ ）。
【解答】i×(i-1)/2+j

4．已知廣義表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)))
【解答】D

6．設(shè)有三對角矩陣An×n（行、列下標(biāo)均從0開始），將其三條對角線上的元素逐行存于數(shù)組B[3n-2]中，使得B[k]=aij求：
⑴ 用i, j表示k的下標(biāo)變換公式；
⑵ 用k表示i, j的下標(biāo)變換公式。
【解答】⑴ 要求i, j表示k的下標(biāo)變換公式，就是要求在k之前已經(jīng)存儲了多少個非零元素，這些非零元素的個數(shù)就是k的值。元素aij求所在的行為i，列為j，則在其前面的非零元素的個數(shù)是；k=2 + 3(i－1)+( j－i + 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中，編寫算法計算對稱矩陣的乘積。
【解答】對稱矩陣采用壓縮存儲，乘積矩陣也采用壓縮存儲。注意矩陣元素的表示方法。

第 5 章 樹和二叉樹
課后習(xí)題講解

1. 填空題
⑴ 樹是n（n≥0）結(jié)點的有限集合，在一棵非空樹中，有（ ）個根結(jié)點，其余的結(jié)點分成m（m＞0）個（ ）的集合，每個集合都是根結(jié)點的子樹。
【解答】有且僅有一個，互不相交

⑵ 樹中某結(jié)點的子樹的個數(shù)稱為該結(jié)點的（ ），子樹的根結(jié)點稱為該結(jié)點的（ ），該結(jié)點稱為其子樹根結(jié)點的（ ）。
【解答】度，孩子，雙親

⑶ 一棵二叉樹的第i（i≥1）層最多有（ ）個結(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=n2+1，得n0=(n+1)/2，n2=(n-1)/2。

⑷ 設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點，該二叉樹的結(jié)點數(shù)可能達到的最大值是（ ），最小值是（ ）。
【解答】2h -1，2h-1
【分析】最小結(jié)點個數(shù)的情況是第1層有1個結(jié)點，其他層上都只有2個結(jié)點。

⑸ 深度為k的二叉樹中，所含葉子的個數(shù)最多為（ ）。
【解答】2k-1
【分析】在滿二叉樹中葉子結(jié)點的個數(shù)達到最多。

⑹ 具有100個結(jié)點的完全二叉樹的葉子結(jié)點數(shù)為（ ）。
【解答】50
【分析】100個結(jié)點的完全二叉樹中最后一個結(jié)點的編號為100，其雙親即最后一個分支結(jié)點的編號為50，也就是說，從編號51開始均為葉子。

⑺ 已知一棵度為3的樹有2個度為1的結(jié)點，3個度為2的結(jié)點，4個度為3的結(jié)點。則該樹中有（ ）個葉子結(jié)點。
【解答】12
【分析】根據(jù)二叉樹性質(zhì)3的證明過程，有n0=n2+2n3+1（n0、n2、n3分別為葉子結(jié)點、度為2的結(jié)點和度為3的結(jié)點的個數(shù)）。

⑻ 某二叉樹的前序遍歷序列是ABCDEFG，中序遍歷序列是CBDAFGE，則其后序遍歷序列是（ ）。
【解答】CDBGFEA
【分析】根據(jù)前序遍歷序列和后序遍歷序列將該二叉樹構(gòu)造出來。

⑼ 在具有n個結(jié)點的二叉鏈表中，共有（ ）個指針域，其中（ ）個指針域用于指向其左右孩子，剩下的（ ）個指針域則是空的。
【解答】2n，n-1，n+1

⑽ 在有n個葉子的哈夫曼樹中，葉子結(jié)點總數(shù)為（ ），分支結(jié)點總數(shù)為（ ）。
【解答】n，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沒有左孩子的充要條件是（ 　?。?。
A R.lchild=NULL B R.ltag=0 C R.ltag=1 D R.rchild=NULL
【解答】C
【分析】線索二叉樹中某結(jié)點是否有左孩子，不能通過左指針域是否為空來判斷，而要判斷左標(biāo)志是否為1。

⑸ 深度為k的完全二叉樹至少有（ ）個結(jié)點，至多有（ ）個結(jié)點，具有n個結(jié)點的完全二叉樹按層序從1開始編號，則編號最小的葉子的序號是（ ）。
A 2k-2+1 B 2k-1 C 2k -1 D 2k–1 -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é)點，最多的情況是滿二叉樹，編號最小的葉子應(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é)點的（ ）序列，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)對樹的一些運算
B 將樹、森林按二叉樹的存儲方式進行存儲并利用二叉樹的算法解決樹的有關(guān)問題
C 將樹、森林轉(zhuǎn)換成二叉樹
D 體現(xiàn)一種技巧，沒有什么實際意義
【解答】B

3. 判斷題

⑴ 在線索二叉樹中，任一結(jié)點均有指向其前趨和后繼的線索。
【解答】錯。某結(jié)點是否有前驅(qū)或后繼的線索，取決于該結(jié)點的標(biāo)志域是否為1。

⑵ 在二叉樹的前序遍歷序列中，任意一個結(jié)點均處在其子女的前面。
【解答】對。由前序遍歷的操作定義可知。

⑶ 二叉樹是度為2的樹。
【解答】錯。二叉樹和樹是兩種不同的樹結(jié)構(gòu)，例如，左斜樹是一棵二叉樹，但它的度為1。

⑷ 由樹轉(zhuǎn)換成二叉樹，其根結(jié)點的右子樹總是空的。
【解答】對。因為根結(jié)點無兄弟結(jié)點。

⑸ 用一維數(shù)組存儲二叉樹時，總是以前序遍歷存儲結(jié)點。
【解答】錯。二叉樹的順序存儲結(jié)構(gòu)是按層序存儲的，一般適合存儲完全二叉樹。

4．證明：對任一滿二叉樹，其分枝數(shù)B＝2(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．證明：已知一棵二叉樹的前序序列和中序序列，則可唯一確定該二叉樹。
【解答】證明采用歸納法。
設(shè)二叉樹的前序遍歷序列為a1a2a3… an，中序遍歷序列為b1b2b3… bn。
當(dāng)n=1時，前序遍歷序列為a1，中序遍歷序列為b1，二叉樹只有一個根結(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和中序遍歷序列b1b2… 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+1
7．已知二叉樹的中序和后序序列分別為CBEDAFIGH和CEDBIFHGA，試構(gòu)造該二叉樹。
【解答】二叉樹的構(gòu)造過程如圖5-12 所示。

8．對給定的一組權(quán)值W＝（5，2，9，11，8，3，7），試構(gòu)造相應(yīng)的哈夫曼樹，并計算它的帶權(quán)路徑長度。
【解答】構(gòu)造的哈夫曼樹如圖5-13所示。

樹的帶權(quán)路徑長度為：
WPL=2×4+3×4+5×3+7×3+8×3+9×2+11×2
=120

9．已知某字符串S中共有8種字符，各種字符分別出現(xiàn)2次、1次、4次、5次、7次、3次、4次和9次，對該字符串用[0，1]進行前綴編碼，問該字符串的編碼至少有多少位。
【解答】以各字符出現(xiàn)的次數(shù)作為葉子結(jié)點的權(quán)值構(gòu)造的哈夫曼編碼樹如圖5-14所示。其帶權(quán)路徑長度=2×5+1×5+3×4+5×3+9×2+4×3+4×3+7×2=98，所以，該字符串的編碼長度至少為98位。

10．算法設(shè)計

⑴ 設(shè)計算法求二叉樹的結(jié)點個數(shù)。
【解答】本算法不是要打印每個結(jié)點的值，而是求出結(jié)點的個數(shù)。所以可將遍歷算法中的“訪問”操作改為“計數(shù)操作”，將結(jié)點的數(shù)目累加到一個全局變量中，每個結(jié)點累加一次即完成了結(jié)點個數(shù)的求解。
具體算法如下：

⑵ 設(shè)計算法按前序次序打印二叉樹中的葉子結(jié)點。
【解答】本算法的要求與前序遍歷算法既有相同之處，又有不同之處。相同之處是打印次序均為前序，不同之處是此處不是打印每個結(jié)點的值，而是打印出其中的葉子結(jié)點，即為有條件打印。為此，將前序遍歷算法中的訪問操作改為條件打印即可。算法如下：

⑶ 設(shè)計算法求二叉樹的深度。
【解答】當(dāng)二叉樹為空時，深度為0；若二叉樹不為空，深度應(yīng)是其左右子樹深度的最大值加1，而其左右子樹深度的求解又可通過遞歸調(diào)用本算法來完成。具體算法如下：

⑷ 編寫算法，要求輸出二叉樹后序遍歷序列的逆序。
【解答】要想得到后序的逆序，只要按照后序遍歷相反的順序即可，即先訪問根結(jié)點，再遍歷根結(jié)點的右子樹，最后遍歷根結(jié)點的左子樹。注意和前序遍歷的區(qū)別，具體算法如下：

⑸ 以二叉鏈表為存儲結(jié)構(gòu)，編寫算法求二叉樹中結(jié)點x的雙親。
【解答】對二叉鏈表進行遍歷，在遍歷的過程中查找結(jié)點x并記載其雙親。具體算法如下：

⑹ 以二叉鏈表為存儲結(jié)構(gòu)，在二叉樹中刪除以值x為根結(jié)點的子樹。
【解答】對二叉鏈表進行遍歷，在遍歷的過程中查找結(jié)點x并記載其雙親，然后將結(jié)點x的雙親結(jié)點中指向結(jié)點x的指針置空。具體算法如下：

⑺ 一棵具有n個結(jié)點的二叉樹采用順序存儲結(jié)構(gòu)，編寫算法對該二叉樹進行前序遍歷。
【解答】按照題目要求，設(shè)置一個工作棧以完成對該樹的非遞歸算法，思路如下：
① 每訪問一個結(jié)點，將此結(jié)點壓棧，查看此結(jié)點是否有左子樹，若有，訪問左子樹，重復(fù)執(zhí)行該過程直到左子樹為空。
② 從棧彈出一個結(jié)點，如果此結(jié)點有右子樹，訪問右子樹執(zhí)行步驟①，否則重復(fù)執(zhí)行步驟②。
具體算法如下：

⑻ 編寫算法交換二叉樹中所有結(jié)點的左右子樹。
【解答】對二叉樹進行后序遍歷，在遍歷過程中訪問某結(jié)點時交換該結(jié)點的左右子樹。
具體算法如下：

⑼ 以孩子兄弟表示法做存儲結(jié)構(gòu)，求樹中結(jié)點x的第i個孩子。
【解答】先在鏈表中進行遍歷，在遍歷過程中查找值等于x的結(jié)點，然后由此結(jié)點的最左孩子域firstchild找到值為x結(jié)點的第一個孩子，再沿右兄弟域rightsib找到值為x結(jié)點的第i個孩子并返回指向這個孩子的指針。
樹的孩子兄弟表示法中的結(jié)點結(jié)構(gòu)定義如下：
template
struct TNode
{
T data;
TNode *firstchild, *rightsib;
};
具體算法如下：

學(xué)習(xí)自測及答案

1．前序遍歷和中序遍歷結(jié)果相同的二叉樹是（ ）。
A 根結(jié)點無左孩子的二叉樹 B 根結(jié)點無右孩子的二叉樹
C 所有結(jié)點只有左子樹的二叉樹 D 所有結(jié)點只有右子樹的二叉樹
【解答】D

1．前序遍歷和中序遍歷結(jié)果相同的二叉樹是（ ）。 A 根結(jié)點無左孩子的二叉樹 B 根結(jié)點無右孩子的二叉樹 C 所有結(jié)點只有左子樹的二叉樹 D 所有結(jié)點只有右子樹的二叉樹【解答】D

2．由權(quán)值為{3, 8, 6, 2, 5}的葉子結(jié)點生成一棵哈夫曼樹，其帶權(quán)路徑長度為（ ）。
A 24 B 48 C 53 D 72
【解答】C

3．用順序存儲的方法將完全二叉樹中的所有結(jié)點逐層存放在數(shù)組A[1] ~ A[n]中，結(jié)點A[i]若有左子樹，則左子樹的根結(jié)點是（ ）。
　 A A[2i-1] B A[2i+1] C A[i/2] D A[2i]
【解答】D

4．對任何一棵二叉樹T，如果其終端結(jié)點的個數(shù)為n0，度為2的結(jié)點個數(shù)為n2，則（ ）。
A n0=n2-1 B n0=n2 C n0=n2+1 D 沒有規(guī)律
【解答】C

5．一棵滿二叉樹中共有n個結(jié)點，其中有m個葉子結(jié)點，深度為h，則（ ）。
A n=h+m B h+m=2n C m=h-1 D n=2h-1
【解答】D

6．對于完全二叉樹中的任一結(jié)點，若其右分支下的子孫的最大層次為h，則其左分支下的子孫的最大層次為（ ）。
A h B h+1 C h或h+1 D 任意
【解答】C

7．假定一棵度為3的樹中結(jié)點數(shù)為50，則其最小高度應(yīng)為 。
A 3 B 4 C 5 D 6
【解答】C

8．在線索二叉樹中，一個結(jié)點是葉子結(jié)點的充要條件為（ ）。
A 左線索標(biāo)志為0，右線索標(biāo)志為1 B 左線索標(biāo)志為1，右線索標(biāo)志為0
C 左、右線索標(biāo)志均為0 D 左、右線索標(biāo)志均為1
【解答】C

9．對于一棵具有n個結(jié)點的樹，其所有結(jié)點的度之和為（ ）。
【解答】n-1

10．在順序存儲的二叉樹中，編號為i和j的兩個結(jié)點處在同一層的條件是（ ）。
【解答】

11．現(xiàn)有按前序遍歷二叉樹的結(jié)果ABC，問有哪幾種不同的二叉樹可以得到這一結(jié)果？
【解答】共有5種二叉樹可以得到這一結(jié)果，如圖5-15所示。

12．試找出分別滿足下列條件的所有二叉樹：
⑴ 前序序列和中序序列相同。
⑵ 中序序列和后序序列相同。
⑶ 前序序列和后序序列相同。
【解答】 ⑴ 空二叉樹、只有一個根結(jié)點的二叉樹和右斜樹。
⑵ 空二叉樹、只有一個根結(jié)點的二叉樹和左斜樹。
⑶ 空二叉樹、只有一個根結(jié)點的二叉樹
13．將下面圖5-16所示的樹轉(zhuǎn)換為二叉樹，圖5-17所示的二叉樹轉(zhuǎn)換為樹或森林。

【解答】圖5-16所示樹轉(zhuǎn)換的二叉樹如圖5-18所示，圖5-17所示二叉樹轉(zhuǎn)換的森林如圖5-19所示。

14．以孩子兄弟表示法作為存儲結(jié)構(gòu)，編寫算法求樹的深度。
【解答】采用遞歸算法實現(xiàn)。若樹為空樹，則其深度為0，否則其深度等于第一棵子樹的深度+1和兄弟子樹的深度中的較大者。具體算法如下：

15．設(shè)計算法，判斷一棵二叉樹是否為完全二叉樹。
【解答】根據(jù)完全二叉樹的定義可知，對完全二叉樹按照從上到下、從左到右的次序（即層序）遍歷應(yīng)該滿足：
⑴ 若某結(jié)點沒有左孩子，則其一定沒有右孩子；
⑵ 若某結(jié)點無右孩子，則其所有后繼結(jié)點一定無孩子。
若有一結(jié)點不滿足其中任意一條，則該二叉樹就一定不是完全二叉樹。因此可采用按層次遍歷二叉樹的方法依次對每個結(jié)點進行判斷是否滿足上述兩個條件。為此，需設(shè)兩個標(biāo)志變量BJ和CM，其中BJ表示已掃描過的結(jié)點是否均有左右孩子，CM存放局部判斷結(jié)果及最后的結(jié)果。
具體算法如下：