千里之行，始于足下讓知識帶有溫度。第第2頁/共2頁精品文檔推薦數據結構習題和答案及解析第1章緒論

課后習題講解

1.填空

⑴（）是數據的基本單位，在計算機程序中通常作為一個整體舉行考慮和處理。

【解答】數據元素

⑵（）是數據的最小單位，（）是研究數據結構時涉及的最小數據單位。

【解答】數據項，數據元素

【分析】數據結構指的是數據元素以及數據元素之間的關系。

⑶從規律關系上講，數據結構主要分為（）、（）、（）和（）。

【解答】集合，線性結構，樹結構，圖結構

⑷數據的存儲結構主要有（）和（）兩種基本辦法，不論哪種存儲結構，都要存儲兩方面的內容：（）和（）。

【解答】挨次存儲結構，鏈接存儲結構，數據元素，數據元素之間的關系

⑸算法具有五個特性，分離是（）、（）、（）、（）、（）。

【解答】有零個或多個輸入，有一個或多個輸出，有窮性，確定性，可行性

⑹算法的描述辦法通常有（）、（）、（）和（）四種，其中，（）被稱為算法語言。

【解答】自然語言，程序設計語言，流程圖，偽代碼，偽代碼

⑺在普通狀況下，一個算法的時光復雜度是（）的函數。

【解答】問題規模

⑻設待處理問題的規模為n，若一個算法的時光復雜度為一個常數，則表示成數量級的形式為（），若為n*log25n，則表示成數量級的形式為（）。

【解答】Ο(1)，Ο(nlog2n)

【分析】用大O記號表示算法的時光復雜度，需要將低次冪去掉，將最高次冪的系數去掉。

2.挑選題

⑴挨次存儲結構中數據元素之間的規律關系是由（）表示的，鏈接存儲結構中的數據元素之間的規律關系是由（）表示的。

A線性結構

B非線性結構

C存儲位置

D指針

【解答】C，D

【分析】挨次存儲結構就是用一維數組存儲數據結構中的數據元素，其規律關系由存儲位置（即元素在數組中的下標）表示；鏈接存儲結構中一個數據元素對應鏈表中的一個結點，元素之間的規律關系由結點中的指針表示。

⑵假設有如下遺產繼承規章：丈夫和妻子可以互相繼承遺產；子女可以繼承父親或母親的遺產；子女間不能互相繼承。則表示該遺產繼承關系的最合適的數據結構應當是（）。

A樹

B圖

C線性表

D集合

【解答】B

【分析】將丈夫、妻子和子女分離作為數據元素，按照題意畫出規律結構圖。

⑶算法指的是（）。

A對特定問題求解步驟的一種描述，是指令的有限序列。

B計算機程序

C解決問題的計算辦法

D數據處理

【解答】A

【分析】計算機程序是對算法的詳細實現；容易地說，算法是解決問題的辦法；數據處理是通過算法完成的。所以，惟獨A是算法的精確?????定義。

⑷下面（）不是算法所必需具備的特性。

A有窮性

B確切性

C高效性

D可行性

【解答】C

【分析】高效性是好算法應具備的特性。

⑸算法分析的目的是（），算法分析的兩個主要方面是（）。

A找出數據結構的合理性

B討論算法中輸入和輸出的關系

C分析算法的效率以求改進

D分析算法的易讀性和文檔性

E空間性能和時光性能

F正確性和簡明性

G可讀性和文檔性H數據復雜性和程序復雜性

【解答】C，E

⑴算法的時光復雜度都要通過算法中的基本語句的執行次數來確定。

【解答】錯。時光復雜度要通過算法中基本語句執行次數的數量級來確定。

⑵每種數據結構都具備三個基本操作：插入、刪除和查找。

【解答】錯。如數組就沒有插入和刪除操作。此題注重是每種數據結構。

⑶所謂數據的規律結構指的是數據之間的規律關系。

【解答】錯。是數據之間的規律關系的整體。

⑷規律結構與數據元素本身的內容和形式無關。

【解答】對。因此規律結構是數據組織的主要方面。

⑸基于某種規律結構之上的基本操作，其實現是唯一的。

【解答】錯。基本操作的實現是基于某種存儲結構設計的，因而不是唯一的。

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

【解答】⑴基本語句是k=k+10*i，共執行了n-2次，所以T(n)=O(n)。

⑵基本語句是k=k+10*i，共執行了n次，所以T(n)=O(n)。

⑶分析條件語句，每循環一次，i+j整體加1，共循環n次，所以T(n)=O(n)。

⑷設循環體共執行T(n)次，每循環一次，循環變量y加1，終于T(n)=y，即：

(T(n)+1)2≤n，所以T(n)=O(n1/2)。

⑸x++是基本語句，所以

5．設有數據結構（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)}。試畫出其規律結構圖并指出屬于何種結構。【解答】其規律結構圖如圖1-3所示，它是一種圖結構。

6.為整數定義一個抽象數據類型，包含整數的常見運算，每個運算對應一個基本操作，每個基本操作的接口需定義前置條件、輸入、功能、輸出和后置條件。

【解答】整數的抽象數據類型定義如下：

ADTinteger

Data

整數a：可以是正整數(1,2,3,…)、負整數(-1,-2,-3,…)和零Operation

Constructor

前置條件：整數a不存在

輸入：一個整數b

功能：構造一個與輸入值相同的整數

輸出：無

后置條件：整數a具有輸入的值

Set

前置條件：存在一個整數a

輸入：一個整數b

功能：修改整數a的值，使之與輸入的整數值相同

輸出：無

后置條件：整數a的值發生轉變

Add

前置條件：存在一個整數a

輸入：一個整數b

功能：將整數a與輸入的整數b相加輸出：相加后的結果

后置條件：整數a的值發生轉變Sub

前置條件：存在一個整數a

輸入：一個整數b

功能：將整數a與輸入的整數b相減輸出：相減的結果

后置條件：整數a的值發生轉變Multi

前置條件：存在一個整數a

輸入：一個整數b

功能：將整數a與輸入的整數b相乘輸出：相乘的結果

后置條件：整數a的值發生轉變

Div

前置條件：存在一個整數a

輸入：一個整數b

功能：將整數a與輸入的整數b相除

輸出：若整數b為零，則拋出除零異樣，否則輸出相除的結果后置條件：整數a的值發生轉變

Mod

前置條件：存在一個整數a

輸入：一個整數b

功能：求當前整數與輸入整數的模，即正的余數

輸出：若整數b為零，則拋出除零異樣，否則輸出取模的結果后置條件：整數a的值發生轉變

Equal

前置條件：存在一個整數a

輸入：一個整數b

功能：推斷整數a與輸入的整數b是否相等

輸出：若相等返回1，否則返回0

后置條件：整數a的值不發生轉變

endADT

7.求多項式A(x)的算法可按照下列兩個公式之一來設計：

⑴A(x)=anxn+an-1xn-1+…+a1x+a0

⑵A(x)=(…(anx+an-1)x+…+a1)x)+a0

按照算法的時光復雜度分析比較這兩種算法的優劣。

【解答】其次種算法的時光性能要好些。第一種算法需執行大量的乘法運算，而其次種算法舉行了優化，削減了不須要的乘法運算。

8.算法設計（要求：算法用偽代碼和C++描述，并分析最壞狀況下的時光復雜度）

⑴對一個整型數組A[n]設計一個排序算法。

【解答】下面是容易挑選排序算法的偽代碼描述。

下面是容易挑選排序算法的C++描述。

分析算法，有兩層嵌套的for循環，所以，。

⑵找出整型數組A[n]中元素的最大值和次最大值。

【解答】算法的偽代碼描述如下：

算法的C++描述如下：

分析算法，惟獨一層循環，共執行n-2次，所以，T(n)=O(n)。學習自測及答案

1．挨次存儲結構的特點是（），鏈接存儲結構的特點是（）。

【解答】用元素在存儲器中的相對位置來表示數據元素之間的規律關系，用指示元素存儲地址的指針表示數據元素之間的規律關系。

2.算法在發生非法操作時可以作出處理的特性稱為（）。

【解答】茁壯性

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

4．將下列函數按它們在n時的無窮大階數，從小到大羅列。

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．試描述數據結構和抽象數據類型的概念與程序設計語言中數據類型概念的區分。

【解答】數據結構是指互相之間存在一定關系的數據元素的集合。而抽象數據類型是指一個數據結構以及定義在該結構上的一組操作。程序設計語言中的數據類型是一個值的集合和定義在這個值集上一組操作的總稱。抽象數據類型可以看成是對數據類型的一種抽象。

6.對下列用二元組表示的數據結構,試分離畫出對應的規律結構圖，并指出屬于何種結構。

⑴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)}

【解答】⑴屬于集合，其規律結構圖如圖1-4(a)所示；⑵屬于線性結構，其規律結構圖如圖1-4(b)所示；

⑶屬于樹結構，其規律結構圖如圖1-4(c)所示；⑷屬于圖結構，其規律結構圖如圖1-4(d)所示。

7.求下列算法的時光復雜度。

count=0;x=1;

while(x{

x*=2;

count++;

}

returncount;

【解答】Ｏ(log2n)

第2章線性表

課后習題講解

1.填空

⑴在挨次表中，等概率狀況下，插入和刪除一個元素平均需移動（）個元素，詳細移動元素的個數與（）和（）有關。

【解答】表長的一半，表長，該元素在表中的位置

⑵挨次表中第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的存儲地址是（）。

【解答】108

【分析】第5個元素的存儲地址=第1個元素的存儲地址＋(5－1)×2=108

⑶設單鏈表中指針p指向結點A，若要刪除A的后繼結點（假設A存在后繼結點），則需修改指針的操作為（）。

【解答】p->next=(p->next)->next

⑷單鏈表中設置頭結點的作用是（）。

【解答】為了運算便利

【分析】例如在插入和刪除操作時不必對表頭的狀況舉行特別處理。

⑸非空的單循環鏈表由頭指針head指示，則其尾結點（由指針p所指）滿足（）。

【解答】p->next=head

【分析】如圖2-8所示。

⑹在由尾指針rear指示的單循環鏈表中，在表尾插入一個結點s的操作序列是（）；刪除開頭結點的操作序列為（）。

【解答】s->next=rear->next;rear->next=s;rear=s;

q=rear->next->next;rear->next->next=q->next;deleteq;

【分析】操作暗示圖如圖2-9所示：

⑺一個具有n個結點的單鏈表，在指針p所指結點后插入一個新結點的時光復雜度為（）；在給定值為x的結點后插入一個新結點的時光復雜度為（）。

【解答】Ο(1)，Ο(n)

【分析】在p所指結點后插入一個新結點只需修改指針，所以時光復雜度為Ο(1)；而在給定值為x的結點后插入一個新結點需要先查找值為x的結點，所以時光復雜度為Ο(n)。

⑻可由一個尾指針唯一確定的鏈表有（）、（）、（）。

【解答】循環鏈表，循環雙鏈表，雙鏈表

2.挑選題

⑴線性表的挨次存儲結構是一種（）的存儲結構，線性表的鏈接存儲結構是一種（）的存儲結構。

A隨機存取

B挨次存取

C索引存取

D散列存取

【解答】A，B

【分析】參見2.2.1。

⑵線性表采納鏈接存儲時，其地址（）。

A必需是延續的

B部分地址必需是延續的

C一定是不延續的

D延續與否均可以

【解答】D

【分析】線性表的鏈接存儲是用一組隨意的存儲單元存儲線性表的數據元素，這組存儲單元可以延續，也可以不延續，甚至可以零散分布在內存中隨意位置。

⑶單循環鏈表的主要優點是（）。

A不再需要頭指針了

B從表中任一結點動身都能掃描到囫圇鏈表；

C已知某個結點的位置后，能夠簡單找到它的直接前趨；

D在舉行插入、刪除操作時，能更好地保證鏈表不斷開。

【解答】B

⑷鏈表不具有的特點是（）。

A可隨機拜訪任一元素

B插入、刪除不需要移動元素

C不必事先估量存儲空間

D所需空間與線性表長度成正比

【解答】A

⑸若某線性表中最常用的操作是取第i個元素和找第i個元素的前趨，則采納（）存儲辦法最節約時光。

A挨次表

B單鏈表

C雙鏈表

D單循環鏈表

【分析】線性表中最常用的操作是取第i個元素，所以，應挑選隨機存取結構即挨次表，同時在挨次表中查找第i個元素的前趨也很便利。單鏈表和單循環鏈表既不能實現隨機存取，查找第i個元素的前趨也不便利，雙鏈表雖然能迅速查找第i個元素的前趨，但不能實現隨機存取。

⑹若鏈表中最常用的操作是在最后一個結點之后插入一個結點和刪除第一個結點，則采納（）存儲辦法最節約時光。

A單鏈表

B帶頭指針的單循環鏈表

C雙鏈表

D帶尾指針的單循環鏈表

【解答】D

【分析】在鏈表中的最后一個結點之后插入一個結點需要知道終端結點的地址，所以，單鏈表、帶頭指針的單循環鏈表、雙鏈表都不合適，考慮在帶尾指針的單循環鏈表中刪除第一個結點，其時光性能是O(1)，所以，答案是D。

⑺若鏈表中最常用的操作是在最后一個結點之后插入一個結點和刪除最后一個結點，則采納（）存儲辦法最節約運算時光。

A單鏈表

B循環雙鏈表C單循環鏈表D帶尾指針的單循環鏈表

【解答】B

【分析】在鏈表中的最后一個結點之后插入一個結點需要知道終端結點的地址，所以，單鏈表、單循環鏈表都不合適，刪除最后一個結點需要知道終端結點的前驅結點的地址，所以，帶尾指針的單循環鏈表不合適，而循環雙鏈表滿足條件。

⑻在具有n個結點的有序單鏈表中插入一個新結點并仍然有序的時光復雜度是（）。

AO(1)

BO(n)

CO(n2)

DO(nlog2n)

【分析】首先應挨次查找新結點在單鏈表中的位置。

⑼對于n個元素組成的線性表，建立一個有序單鏈表的時光復雜度是（）。

AO(1)

BO(n)

CO(n2)

DO(nlog2n)

【解答】C

【分析】該算法需要將n個元素依次插入到有序單鏈表中，而插入每個元素需O(n)。

⑽使用雙鏈表存儲線性表，其優點是可以（）。

A提高查找速度

B更便利數據的插入和刪除

C節省存儲空間

D很快回收存儲空間

【解答】B

【分析】在鏈表中普通只能舉行挨次查找，所以，雙鏈表并不能提高查找速度，由于雙鏈表中有兩個指針域，明顯不能節省存儲空間，對于動態存儲分配，回收存儲空間的速度是一樣的。因為雙鏈表具有對稱性，所以，其插入和刪除操作越發便利。

⑾在一個單鏈表中，已知q所指結點是p所指結點的直接前驅，若在q和p之間插入s所指結點，則執行（）操作。

As->next=p->next;p->next=s;

Bq->next=s;s->next=p;

Cp->next=s->next;s->next=p;

Dp->next=s;s->next=q;

【解答】B

【分析】注重此題是在q和p之間插入新結點，所以，不用考慮修改指針的挨次。

⑿在循環雙鏈表的p所指結點后插入s所指結點的操作是（）。

Ap->next=s;s->prior=p;p->next->prior=s;s->next=p->next;

Bp->next=s;p->next->prior=s;s->prior=p;s->next=p->next;

Cs->prior=p;s->next=p->next;p->next=s;p->next->prior=s;

Ds->prior=p;s->next=p->next;p->next->prior=s;p->next=s

【解答】D

【分析】在鏈表中，對指針的修改必需保持線性表的規律關系，否則，將違反線性表的規律特征，圖2-10給出備選答案C和D的圖解。

3.推斷題

⑴線性表的規律挨次和存儲挨次總是全都的。

【解答】錯。挨次表的規律挨次和存儲挨次全都，鏈表的規律挨次和存儲挨次不一定全都。

⑵線性表的挨次存儲結構優于鏈接存儲結構。

【解答】錯。兩種存儲結構各有優缺點。

⑶設p，q是指針，若p=q，則*p=*q。

【解答】錯。p=q只能表示p和q指向同一起始地址，而所指類型則不一定相同。

⑷線性結構的基本特征是：每個元素有且僅有一個直接前驅和一個直接后繼。

【解答】錯。每個元素最多惟獨一個直接前驅和一個直接后繼，第一個元素沒有前驅，最后一個元素沒有后繼。

⑸在單鏈表中，要取得某個元素，只要知道該元素所在結點的地址即可，因此單鏈表是隨機存取結構。【解答】錯。要找到該結點的地址，必需從頭指針開頭查找，所以單鏈表是挨次存取結構。

4．請說明挨次表和單鏈表各有何優缺點，并分析下列狀況下，采納何種存儲結構更好些。

⑴若線性表的總長度基本穩定，且很少舉行插入和刪除操作，但要求以最快的速度存取線性表中的元素。

⑵假如n個線性表同時并存，并且在處理過程中各表的長度會動態發生變化。

⑶描述一個城市的設計和規劃。

【解答】挨次表的優點：①無需為表示表中元素之間的規律關系而增強額外的存儲空間；②可以迅速地存取表中任一位置的元素（即隨機存取）。挨次表的缺點：①插入和刪除操作需移動大量元素；②表的容量難以確定；③造成存儲空間的“碎片”。

單鏈表的優點：①不必事先知道線性表的長度；②插入和刪除元素時只需修改指針，不用移動元素。單鏈表的缺點：①指針的結構性開銷；②存取表中隨意元素不便利，只能舉行挨次存取。

⑴應選用挨次存儲結構。由于挨次表是隨機存取結構，單鏈表是挨次存取結構。本題很少舉行插入和刪除操作，所以空間變化不大，且需要迅速存取，所以應選用挨次存儲結構。

⑵應選用鏈接存儲結構。鏈表簡單實現表容量的擴充，適合表的長度動態發生變化。

⑶應選用鏈接存儲結構。由于一個城市的設計和規劃涉及活動無數，需要常常修改、擴充和刪除各種信息，才干適應不斷進展的需要。而挨次表的插入、刪除的效率低，故不合適。

5．算法設計

⑴設計一個時光復雜度為Ｏ(n)的算法，實現將數組A[n]中全部元素循環右移k個位置。

【解答】算法思想請參見主教材第一章思想火花。下面給出詳細算法。

分析算法，第一次調用Reverse函數的時光復雜度為O(k)，其次次調用Reverse函數的時光復雜度為

O(n-k)，第三次調用Reverse函數的時光復雜度為O(n)，所以，總的時光復雜度為O(n)。

⑵已知數組A[n]中的元素為整型，設計算法將其調節為左右兩部分，左邊全部元素為奇數，右邊全部元素為偶數，并要求算法的時光復雜度為Ｏ(n)。

【解答】從數組的兩端向中間比較，設置兩個變量i和j，初始時i=0，j=n-1，若A[i]為偶數并且A[j]為奇數，則將A[i]與A[j]交換。詳細算法如下：

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

⑶試編寫在無頭結點的單鏈表上實現線性表的插入操作的算法，并和帶頭結點的單鏈表上的插入操作的實現舉行比較。

【解答】參見2.2.3。

⑷試分離以挨次表和單鏈表作存儲結構，各寫一實現線性表就地逆置的算法。

【解答】挨次表的逆置，即是將對稱元素交換，設挨次表的長度為length，則將表中第i個元素與第length-i-1個元素相交換。詳細算法如下：

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

⑸假設在長度大于1的循環鏈表中，即無頭結點也無頭指針，s為指向鏈表中某個結點的指針，試編寫算法刪除結點s的前趨結點。

【解答】利用單循環鏈表的特點，通過指針s可找到其前驅結點r以及r的前驅結點p，然后將結點r刪除，如圖2-11所示，詳細算法如下：

⑹已知一單鏈表中的數據元素含有三類字符：字母、數字和其他字符。試編寫算法，構造三個循環鏈表，使每個循環鏈表中只含同一類字符。

【解答】在單鏈表A中依次取元素，若取出的元素是字母，把它插入到字母鏈表B中，若取出的元素是數字，則把它插入到數字鏈表D中，直到鏈表的尾部，這樣表B，D，A中分離存放字母、數字和其他字符。詳細算法如下：

⑺設單鏈表以非遞減有序羅列，設計算法實現在單鏈表中刪去值相同的多余結點。

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

⑻推斷帶頭結點的雙循環鏈表是否對稱。

【解答】設工作指針p和q分離指向循環雙鏈表的開頭結點和終端結點，若結點p和結點q的數據域相等，則工作指針p后移，工作指針q前移，直到指針p和指針q指向同一結點（循環雙鏈表中結點個數為奇數），或結點q成為結點p的前驅（循環雙鏈表中結點個數為偶數）。如圖2-12所示。

學習自測及答案

1.已知一維數組A采納挨次存儲結構，每個元素占用4個存儲單元，第9個元素的地址為144，則第一個元素的地址是（）。

A108

B180

C176

D112

【解答】D

2．在長度為n的線性表中查找值為x的數據元素的時光復雜度為：（）。

AO(0)

BO(1)

CO(n)

DO(n2)

【解答】C

3．在一個長度為n的挨次表的第i（1≤i≤n+1）個元素之前插入一個元素，需向后移動（）個元素，刪除第i（1≤i≤n）個元素時，需向前移動（）個元素。

【解答】n-i+1，n-i

4．在單鏈表中，除了頭結點以外，任一結點的存儲位置由（）指示。

【解答】其前趨結點的指針域

5．當線性表采納挨次存儲結構時，其主要特點是（）。

【解答】規律結構中相鄰的結點在存儲結構中仍相鄰

6．在雙鏈表中，每個結點設置了兩個指針域，其中一個指向（）結點，另一個指向（）結點。

【解答】前驅，后繼

7．設A是一個線性表（a1,a2,…,an），采納挨次存儲結構，則在等概率的前提下，平均每插入一個元

素需要移動的元素個數為多少若元素插在ai與ai+1之間（1≤i≤n）的概率為，則平均每插入一個元素所要移動的元素個數又是多少？

【解答】

，

。

8．線性表存放在整型數組A[arrsize]的前elenum個單元中，且遞增有序。編寫算法，將元素x插入到線性表的適當位置上，以保持線性表的有序性，并且分析算法的時光復雜度。

【解答】本題是在一個遞增有序表中插入元素x，基本思路是從有序表的尾部開頭依次取元素與x比較，若大于x，此元素后移一位，再取它前面一個元素重復上述步驟；否則，找到插入位置，將x插入。詳細算法如下：

9.已知單鏈表中各結點的元素值為整型且遞增有序，設計算法刪除鏈表中全部大于mink且小于maxk的全部元素，并釋放被刪結點的存儲空間。

【解答】由于是在有序單鏈表上的操作，所以，要充分利用其有序性。在單鏈表中查找第一個大于mink的結點和第一個小于maxk的結點，再將二者間的全部結點刪除。

10．設單循環鏈表L1，對其遍歷的結果是：x1,x2,x3,…,xn-1,xn。請將該循環鏈表拆成兩個單循環鏈表L1和L2，使得L1中含有原L1表中序號為奇數的結點且遍歷結果為：x1,x3,…；L2中含有原L1表中序號為偶數的結點且遍歷結果為：…,x4,x2。

【解答】算法如下：

第3章特別線性表——棧、隊列和串

課后習題講解

1.填空

⑴設有一個空棧，棧頂指針為1000H，現有輸入序列為1、2、3、4、5，經過push，push，pop，push，pop，push，push后，輸出序列是（），棧頂指針為（）。

【解答】23，1003H

⑵棧通常采納的兩種存儲結構是（）；其判定棧空的條件分離是（），判定棧滿的條件分離是（）。【解答】挨次存儲結構和鏈接存儲結構（或挨次棧和鏈棧），棧頂指針top=-1和top=NULL，棧頂指針top等于數組的長度和內存無可用空間

⑶（）可作為實現遞歸函數調用的一種數據結構。

【解答】棧

【分析】遞歸函數的調用和返回正巧符合后進先出性。

⑷表達式a*(b+c)-d的后綴表達式是（）。

【解答】abc+*d-

【分析】將中綴表達式變為后綴表達式有一個技巧：將操作數依次寫下來，再將算符插在它的兩個操作數的后面。

⑸棧和隊列是兩種特別的線性表，棧的操作特性是（），隊列的操作特性是（），棧和隊列的主要區分在于（）。

【解答】后進先出，先進先出，對插入和刪除操作限定的位置不同

⑹循環隊列的引入是為了克服（）。

【解答】假溢出

⑺數組Q[n]用來表示一個循環隊列，front為隊頭元素的前一個位置，rear為隊尾元素的位置，計算隊列中元素個數的公式為（）。

【解答】（rear-front+n）%n

【分析】也可以是（rear-front）%n，但rear-front的結果可能是負整數，而對一個負整數求模，其結果在不同的編譯器環境下可能會有所不同。

⑻用循環鏈表表示的隊列長度為n，若只設頭指針，則出隊和入隊的時光復雜度分離是（）和（）。【解答】Ｏ(1)，Ｏ(n)

【分析】在帶頭指針的循環鏈表中，出隊即是刪除開頭結點，這只需修改相應指針；入隊即是在終端結點的后面插入一個結點，這需要從頭指針開頭查找終端結點的地址。

⑼串是一種特別的線性表，其特別性體現在（）。

【解答】數據元素的類型是一個字符

⑽兩個串相等的充分須要條件是（）。

【解答】長度相同且對應位置的字符相等

【分析】例如"abc"≠"abc"，"abc"≠"bca"。

2.挑選題

⑴若一個棧的輸入序列是1，2，3，…，n，輸出序列的第一個元素是n，則第i個輸出元素是（）。

A不確定

Bn-i

Cn-i-1

Dn-i+1

【解答】D

【分析】此時，輸出序列一定是輸入序列的逆序。

⑵設棧S和隊列Q的初始狀態為空，元素e1、e2、e3、e4、e5、e6依次通過棧S，一個元素出棧后即進入隊列Q，若6個元素出隊的挨次是e2、e4、e3、e6、e5、e1，則棧S的容量至少應當是（）。

A6

B4

C3

D2

【解答】C

【分析】因為隊列具有先進先出性，所以，此題中隊列形同虛設，即出棧的挨次也是e2、e4、e3、e6、e5、e1。

⑶一個棧的入棧序列是1，2，3，4，5，則棧的不行能的輸出序列是（）。

A54321

B45321

C43512

D12345

【解答】C

【分析】此題有一個技巧：在輸出序列中隨意元素后面不能浮現比該元素小并且是升序（指的是元素的序號）的兩個元素。

⑷設計一個判別表達式中左右括號是否配對的算法，采納（）數據結構最佳

A挨次表

B棧

C隊列

D鏈表

【解答】B

【分析】每個右括號與它前面的最后一個沒有匹配的左括號配對，因此具有后進先出性。

⑸在解決計算機主機與打印機之間速度不匹配問題時通常設置一個打印緩沖區，該緩沖區應當是一個（）結構。

A棧B隊列C數組D線性表

【解答】B

【分析】先進入打印緩沖區的文件先被打印，因此具有先進先出性。

⑹一個隊列的入隊挨次是1，2，3，4，則隊列的輸出挨次是（）。

A4321

B1234

C1432

D3241

【解答】B

【分析】隊列的入隊挨次和出隊挨次總是全都的。

⑺棧和隊列的主要區分在于（）。

A它們的規律結構不一樣

B它們的存儲結構不一樣

C所包含的運算不一樣

D插入、刪除運算的限定不一樣

【解答】D

【分析】棧和隊列的規律結構都是線性的，都有挨次存儲和鏈接存儲，有可能包含的運算不一樣，但不是主要區分，任何數據結構在針對詳細問題時包含的運算都可能不同。

⑻設數組S[n]作為兩個棧S1和S2的存儲空間，對任何一個棧惟獨當S[n]全滿時才不能舉行進棧操作。為這兩個棧分配空間的最佳計劃是（）。

AS1的棧底位置為0，S2的棧底位置為n-1

BS1的棧底位置為0，S2的棧底位置為n/2

CS1的棧底位置為0，S2的棧底位置為n

DS1的棧底位置為0，S2的棧底位置為1

【解答】A

【分析】兩棧分享空間首先兩個棧是相向增長的，棧底應當分離指向兩個棧中的第一個元素的位置，并注重C++中的數組下標是從0開頭的。

⑼設有兩個串p和q，求q在p中首次浮現的位置的運算稱作（）。

A銜接

B模式匹配

C求子串

D求串長

【解答】B

3.推斷題

⑴有n個元素依次進棧，則出棧序列有(n-1)/2種。

【解答】錯。應當有種。

⑵棧可以作為實現過程調用的一種數據結構。

【解答】對。只要操作滿足后進先出性，都可以采納棧作為輔助數據結構。

⑶在棧滿的狀況下不能做進棧操作，否則將產生“上溢”。

【解答】對。

⑷在循環隊列中，front指向隊頭元素的前一個位置，rear指向隊尾元素的位置，則隊滿的條件是

front=rear。

【解答】錯。這是隊空的判定條件，在循環隊列中要將隊空和隊滿的判定條件區分開。

⑸空串與空格串是相同的。

【解答】錯。空串的長度為零，而空格串的長度不為0，其長度是串中空格的個數。

4.設有一個棧，元素進棧的次序為A，B，C，D，E，能否得到如下出棧序列，若能，請寫出操作序列，若不能，請說明緣由。

⑴C，E，A，B，D

⑵C，B，A，D，E

【解答】⑴不能，由于在C、E出棧的狀況下，A一定在棧中，而且在B的下面，不行能先于B出棧。⑵可以，設Ｉ為進棧操作，Ｏ為入棧操作，則其操作序列為IIIOOOIOIO。

5.舉例說明挨次隊列的“假溢出”現象。

【解答】假設有一個挨次隊列，如圖3-6所示，隊尾指針rear=4，隊頭指針front=1，假如再有元素入隊，就會產生“上溢”，此時的“上溢”又稱為“假溢出”，由于隊列并不是真的溢出了，存儲隊列的數組中還有2個存儲單元空閑，其下標分離為0和1。

6.在操作序列push(1)、push(2)、pop、push(5)、push(7)、pop、push(6)之后，棧頂元素和棧底元素分離是什么（push(k)表示整數k入棧，pop表示棧頂元素出棧。）

【解答】棧頂元素為6，棧底元素為1。其執行過程如圖3-7所示。

7．在操作序列EnQueue(1)、EnQueue(3)、DeQueue、EnQueue(5)、EnQueue(7)、DeQueue、EnQueue(9)之后，隊頭元素和隊尾元素分離是什么（EnQueue(k)表示整數k入隊，DeQueue表示隊頭元素出隊）。【解答】隊頭元素為5，隊尾元素為9。其執行過程如圖3-8所示。

8．空串和空格串有何區分串中的空格符有何意義空串在串處理中有何作用？

【解答】不含任何字符的串稱為空串，其長度為零。僅含空格的串稱為空格串，它的長度為串中空格符的個數。串中的空格符可用來分隔普通的字符，便于人們識別和閱讀，但計算串長時應包括這些空格符。空串在串處理中可作為隨意串的子串。

9.算法設計

⑴假設以不帶頭結點的循環鏈表表示隊列，并且只設一個指針指向隊尾結點，但不設頭指針。試設計相應的入隊和出隊的算法。

【解答】出隊操作是在循環鏈表的頭部舉行，相當于刪除開頭結點，而入隊操作是在循環鏈表的尾部舉行，相當于在終端結點之后插入一個結點。因為循環鏈表不帶頭結點，需要處理空表的特別狀況。

入隊算法如下：

出隊算法如下：

⑵設挨次棧S中有2n個元素，從棧頂到棧底的元素依次為a2n，a2n-1，…，a1，要求通過一個循環隊列重新羅列棧中元素，使得從棧頂到棧底的元素依次為a2n，a2n-2，…，a2，a2n-1，a2n-3，…，a1，請設計算法實現該操作，要求空間復雜度和時光復雜度均為O(n)。

【解答】操作步驟為：

①將全部元素出棧并入隊；

②依次將隊列元素出隊，假如是偶數結點，則再入隊，假如是奇數結點，則入棧；

③將奇數結點出棧并入隊；

④將偶數結點出隊并入棧；

⑤將全部元素出棧并入隊；

⑥將全部元素出隊并入棧即為所求。

⑶用挨次存儲結構存儲串S，編寫算法刪除S中第i個字符開頭的延續j個字符。

【解答】先推斷串S中要刪除的內容是否存在，若存在，則將第i+j-1之后的字符前移j個位置。算法如下：

⑷對于采納挨次存儲結構的串S，編寫一個函數刪除其值等于ch的全部字符。

【解答】從后向前刪除值為ch的全部元素，這樣全部移動的元素中沒有值為ch的元素，能削減移動元素的次數，提高算法的效率。算法如下：

⑸對串的模式匹配KMP算法設計求模式滑動位置的next函數。

【解答】參見3.2.5

學習自測及答案

1．在一個具有n個單元的挨次棧中，假定以地址低端（即下標為0的單元）作為棧底，以top作為棧頂指針，當出棧時，top的變化為（）。

A不變

Btop=0;

Ctop=top-1;

Dtop=top+1;

【解答】C

2．一個棧的入棧序列是a,b,c,d,e，則棧的不行能的出棧序列是（）。

Aedcba

Bcdeba

Cdebca

Dabcde

【解答】C

3．從棧頂指針為top的鏈棧中刪除一個結點，用x保存被刪除結點的值，則執行（）。

Ax=top;top=top->next;

Bx=top->data;

Ctop=top->next;x=top->data;

Dx=top->data;top=top->next;

【解答】D

4．設元素1,2,3,P,A依次經過一個棧，進棧次序為123PA，在棧的輸出序列中，有哪些序列可作為C++程序設計語言的變量名。

【解答】PA321,P3A21,P32A1,P321A,AP321

5.設S="I_am_a_teacther"，其長度為（）。

【解答】15

第4章廣義線性表——多維數組和廣義表

課后習題講解

1.填空

⑴數組通常惟獨兩種運算：（）和（），這打算了數組通常采納（）結構來實現存儲。

【解答】存取，修改，挨次存儲

【分析】數組是一個具有固定格式和數量的數據集合，在數組上普通不能做插入、刪除元素的操作。除了初始化和銷毀之外，在數組中通常惟獨存取和修改兩種操作。

⑵二維數組A中行下標從10到20，列下標從5到10，按行優先存儲，每個元素占4個存儲單元，A[10][5]的存儲地址是1000，則元素A[15][10]的存儲地址是（）。

【解答】1140

【分析】數組A中每行共有6個元素，元素A[15][10]的前面共存儲了(15-10)×6+5個元素，每個元素占4個存儲單元，所以，其存儲地址是1000+140=1140。

⑶設有一個10階的對稱矩陣A采納壓縮存儲，A[0][0]為第一個元素，其存儲地址為d，每個元素占1個存儲單元，則元素A[8][5]的存儲地址為（）。

【解答】d+41

【分析】元素A[8][5]的前面共存儲了(1+2+…+8)+5=41個元素。

⑷稀疏矩陣普通壓縮存儲辦法有兩種，分離是（）和（）。

【解答】三元組挨次表，十字鏈表

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

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

【解答】Head(Head(Tail(LS)))

2.挑選題

⑴二維數組A的每個元素是由6個字符組成的串，行下標的范圍從0~8，列下標的范圍是從0~9，則存放A至少需要（）個字節，A的第8列和第5行共占（）個字節，若A按行優先方式存儲，元素A[8][5]的起始地址與當A按列優先方式存儲時的（）元素的起始地址全都。

A90

B180

C240

D540

E108

F114

G54

HA[8][5]IA[3][10]JA[5][8]KA[4][9]

【解答】D，E，K

【分析】數組A為9行10列，共有90個元素，所以，存放A至少需要90×6=540個存儲單元，第8列和第5行共有18個元素（注重行列有一個交錯元素），所以，共占108個字節，元素A[8][5]按行優先存儲

的起始地址為d+8×10+5=d+85，設元素A[i][j]按列優先存儲的起始地址與之相同，則d+j×9+i=d+85，解此方程，得i=4，j=9。

⑵將數組稱為隨機存取結構是由于（）

A數組元素是隨機的

B對數組任一元素的存取時光是相等的

C隨時可以對數組舉行拜訪

D數組的存儲結構是不定

【解答】B

⑶下面的說法中，不正確的是（）

A數組是一種線性結構

B數組是一種定長的線性結構

C除了插入與刪除操作外，數組的基本操作還有存取、修改、檢索和排序等

D數組的基本操作有存取、修改、檢索和排序等，沒有插入與刪除操

【解答】C

【分析】數組屬于廣義線性表，數組被創建以后，其維數和每維中的元素個數是確定的，所以，數組通常沒有插入和刪除操作。

⑷對特別矩陣采納壓縮存儲的目的主要是為了（）

A表達變得容易

B對矩陣元素的存取變得容易

C去掉矩陣中的多余元素

D削減不須要的存儲空間

【解答】D

【分析】在特別矩陣中，有無數值相同的元素并且他們的分布有邏輯，沒有須要為值相同的元素重復存儲。

⑸下面（）不屬于特別矩陣。

A對角矩陣

B三角矩陣

C稀疏矩陣

D對稱矩陣

【解答】C

⑹若廣義表A滿足Head(A)=Tail(A)，則A為（）

A()

B(())

C((),())D((),(),())

【解答】B

⑺下面的說法中，不正確的是（）

A廣義表是一種多層次的結構

B廣義表是一種非線性結構

C廣義表是一種分享結構

D廣義表是一種遞歸

【解答】B

【分析】從各層元素各自具有的線性關系講，廣義表屬于線性結構。

⑻下面的說法中，不正確的是（）

A對稱矩陣只須存放包括主對角線元素在內的下（或上）三角的元素即可。

B對角矩陣只須存放非零元素即可。

C稀疏矩陣中值為零的元素較多，因此可以采納三元組表辦法存儲。

D稀疏矩陣中大量值為零的元素分布有邏輯，因此可以采納三元組表辦法存儲【解答】D

【分析】稀疏矩陣中大量值為零的元素分布沒有邏輯，因此采納三元組表存儲。假如零元素的分布有邏輯，就沒有須要存儲非零元素的行號和列號，而需要按其壓縮邏輯找出相應的映象函數。

3.推斷題

⑴數組是一種復雜的數據結構，數組元素之間的關系既不是線性的，也不是樹形的。

【解答】錯。例如二維數組可以看成是數據元素為線性表的線性表。

⑵使用三元組表存儲稀疏矩陣的元素，有時并不能節約存儲空間。

【解答】對。由于三元組表除了存儲非零元素值外，還需要存儲其行號和列號。

⑶稀疏矩陣壓縮存儲后，必會失去隨機存取功能。

【解答】對。由于壓縮存儲后，非零元素的存儲位置和行號、列號之間失去了確定的關系。

⑷線性表可以看成是廣義表的特例，假如廣義表中的每個元素都是單元素，則廣義表便成為線性表。

【解答】對。

⑸若一個廣義表的表頭為空表，則此廣義表亦為空表。

【解答】錯。如廣義表L=(()，(a，b))的表頭為空表，但L不是空表。

4．一個稀疏矩陣如圖4-4所示，寫出對應的三元組挨次表和十字鏈表存儲表示。

【解答】對應的三元組挨次表如圖4-5所示，十字鏈表如圖4-6所示。

5．已知A為稀疏矩陣，試從空間和時光角度比較采納二維數組和三元組挨次表兩種不同的存儲結構完成求運算的優缺點。

【解答】設稀疏矩陣為m行n列，假如采納二維數組存儲，其空間復雜度為Ｏ(m×n)；由于要將全部的矩陣元素累加起來，所以，需要用一個兩層的嵌套循環，其時光復雜度亦為Ｏ(m×n)。假如采納三元組挨次表舉行壓縮存儲，假設矩陣中有t個非零元素，其空間復雜度為Ｏ(t)，將全部的矩陣元素累加起來只需將三元組挨次表掃描一遍，其時光復雜度亦為Ｏ(t)。當t0）個結點的滿二叉樹共有（）個葉子結點和（）個非終端結點。

【解答】2i-1，(n+1)/2，(n-1)/2

【分析】設滿二叉樹中葉子結點的個數為n0，度為2的結點個數為n2，因為滿二叉樹中不存在度為1的結點，所以n=n0+n2；由二叉樹的性質n0=n2+1，得n0=(n+1)/2，n2=(n-1)/2。

⑷設高度為h的二叉樹上惟獨度為0和度為2的結點，該二叉樹的結點數可能達到的最大值是（），最小值是（）。

【解答】2h-1，2h-1

【分析】最小結點個數的狀況是第1層有1個結點，其他層上都惟獨2個結點。

⑸深度為k的二叉樹中，所含葉子的個數最多為（）。

【解答】2k-1

【分析】在滿二叉樹中葉子結點的個數達到最多。

⑹具有100個結點的徹低二叉樹的葉子結點數為（）。

【解答】50

【分析】100個結點的徹低二叉樹中最后一個結點的編號為100，其雙親即最后一個分支結點的編號為50，也就是說，從編號51開頭均為葉子。

⑺已知一棵度為3的樹有2個度為1的結點，3個度為2的結點，4個度為3的結點。則該樹中有（）個葉子結點。

【解答】12

【分析】按照二叉樹性質3的證實過程，有n0=n2+2n3+1（n0、n2、n3分離為葉子結點、度為2的結點和度為3的結點的個數）。

⑻某二叉樹的前序遍歷序列是ABCDEFG，中序遍歷序列是CBDAFGE，則其后序遍歷序列是（）。

【解答】CDBGFEA

【分析】按照前序遍歷序列和后序遍歷序列將該二叉樹構造出來。

⑼在具有n個結點的二叉鏈表中，共有（）個指針域，其中（）個指針域用于指向其左右孩子，剩下的（）個指針域則是空的。

【解答】2n，n-1，n+1

⑽在有n個葉子的哈夫曼樹中，葉子結點總數為（），分支結點總數為（）。

【解答】n，n-1

【分析】n-1個分支結點是經過n-1次合并后得到的。

2.挑選題

⑴假如結點A有3個兄弟，B是A的雙親，則結點B的度是（）。

A1

B2

C3

D4

【解答】D

⑵設二叉樹有n個結點，則其深度為（）。

An-1

Bn

C+1

D不能確定

【解答】D

【分析】此題并沒有指明是徹低二叉樹，則其深度最多是n，最少是+1。

⑶二叉樹的前序序列和后序序列正巧相反，則該二叉樹一定是（）的二叉樹。

A空或惟獨一個結點

B高度等于其結點數

C任一結點無左孩子

D任一結點無右孩子

【解答】B

【分析】此題注重是序列正巧相反，則左斜樹和右斜樹均滿足條件。

⑷線索二叉樹中某結點R沒有左孩子的充要條件是（）。

A=NULL

B=0

C=1

D=NULL

【解答】C

【分析】線索二叉樹中某結點是否有左孩子，不能通過左指針域是否為空來推斷，而要推斷左標志是否為1。

⑸深度為k的徹低二叉樹至少有（）個結點，至多有（）個結點，具有n個結點的徹低二叉樹按層序從1開頭編號，則編號最小的葉子的序號是（）。

A2k-2+1

B2k-1

C2k-1

D2k–1-1

E2k+1

F2k+1-1

G2k-1+1

H2k

【解答】B，C，A

【分析】深度為k的徹低二叉樹最少結點數的狀況應是第k層上惟獨1個結點，最多的狀況是滿二叉樹，編號最小的葉子應當是在結點數最少的狀況下，葉子結點的編號。

⑹一個高度為h的滿二叉樹共有n個結點，其中有m個葉子結點，則有（）成立。

An=h+m

Bh+m=2n

Cm=h-1

Dn=2m-1

【解答】D

【分析】滿二叉樹中沒有度為1的結點，所以有m個葉子結點，則度為2的結點個數為m-1。

⑺任何一棵二叉樹的葉子結點在前序、中序、后序遍歷序列中的相對次序（）。

A絕對不發生轉變

B絕對發生轉變

C不能確定

D有時發生變化

【解答】A

【分析】三種遍歷次序均是先左子樹后右子樹。

⑻假如T'是由有序樹T轉換而來的二叉樹，那么T中結點的前序序列就是T'中結點的（）序列，T中結點的后序序列就是T'中結點的（）序列。

A前序

B中序

C后序

D層序

【解答】A，B

⑼設森林中有4棵樹，樹中結點的個數依次為n1、n2、n3、n4，則把森林轉換成二叉樹后，其根結點的右子樹上有（）個結點，根結點的左子樹上有（）個結點。

An1-1

Bn1

Cn1+n2+n3

Dn2+n3+n4

【解答】D，A

【分析】由森林轉換的二叉樹中，根結點即為第一棵樹的根結點，根結點的左子樹是由第一棵樹中除了根結點以外其余結點組成的，根結點的右子樹是由森林中除第一棵樹外其他樹轉換來的。

⑽研究樹、森林和二叉樹的關系，目的是為了（）。

A借助二叉樹上的運算辦法去實現對樹的一些運算

B將樹、森林按二叉樹的存儲方式舉行存儲并利用二叉樹的算法解決樹的有關問題

C將樹、森林轉換成二叉樹

D體現一種技巧，沒有什么實際意義

【解答】B

3.推斷題

⑴在線索二叉樹中，任一結點均有指向其前趨和后繼的線索。

【解答】錯。某結點是否有前驅或后繼的線索，取決于該結點的標志域是否為1。

⑵在二叉樹的前序遍歷序列中，隨意一個結點均處在其子女的前面。

【解答】對。由前序遍歷的操作定義可知。

⑶二叉樹是度為2的樹。

【解答】錯。二叉樹和樹是兩種不同的樹結構，例如，左斜樹是一棵二叉樹，但它的度為1。

⑷由樹轉換成二叉樹，其根結點的右子樹總是空的。

【解答】對。由于根結點無兄弟結點。

⑸用一維數組存儲二叉樹時，總是以前序遍歷存儲結點。

【解答】錯。二叉樹的挨次存儲結構是按層序存儲的，普通適合存儲徹低二叉樹。

4．證實：對任一滿二叉樹，其分枝數B＝2(n0-1)。（其中，n0為終端結點數）【解答】由于在滿二叉樹中沒有度為1的結點，所以有：

n=n0+n2

設B為樹中分枝數，則

n=B+1

所以

B=n0+n2-1

再由二叉樹性質：

n0=n2+1

代入上式有：

B=n0+n0-1-1=2(n0-1)

5．證實：已知一棵二叉樹的前序序列和中序序列，則可唯一確定該二叉樹。

【解答】證實采納歸納法。

設二叉樹的前序遍歷序列為a1a2a3…an，中序遍歷序列為b1b2b3…bn。

當n=1時，前序遍歷序列為a1，中序遍歷序列為b1，二叉樹惟獨一個根結點，所以，a1=b1，可以唯一確定該二叉樹；

假設當nA關鍵活動不按期完成就會影響囫圇工程的完成時光

B任何一個關鍵活動提前完成，那么囫圇工程將會提前完成

C全部的關鍵活動都提前完成，那么囫圇工程將會提前完成

D某些關鍵活動若提前完成，那么囫圇工程將會提前完

【解答】B

【分析】AOE網中的關鍵路徑可能不止一條，假如某一個關鍵活動提前完成，還不能提前囫圇工程，而必需同時提高在幾條關鍵路徑上的關鍵活動。

3.推斷題

⑴一個有向圖的鄰接表和逆鄰接表中的結點個數一定相等。

【解答】對。鄰接表和逆鄰接表的區分僅在于出邊和入邊，邊表中的結點個數都等于有向圖中邊的個數。

⑵用鄰接矩陣存儲圖，所占用的存儲空間大小只與圖中頂點個數有關，而與圖的邊數無關。

【解答】對。鄰接矩陣的空間復雜度為Ｏ(n2)，與邊的個數無關。

⑶圖G的生成樹是該圖的一個微小連通子圖

【解答】錯。必需包含所有頂點。

⑷無向圖的鄰接矩陣一定是對稱的，有向圖的鄰接矩陣一定是不對稱的

【解答】錯。有向圖的鄰接矩陣不一定對稱，例如有向徹低圖的鄰接矩陣就是對稱的。

⑸對隨意一個圖，從某頂點動身舉行一次深度優先或廣度優先遍歷，可拜訪圖的全部頂點。

【解答】錯。惟獨連通圖從某頂點動身舉行一次遍歷，可拜訪圖的全部頂點。

⑹在一個有向圖的拓撲序列中，若頂點a在頂點b之前，則圖中必有一條弧。

【解答】錯。只能說明從頂點a到頂點b有一條路徑。

⑺若一個有向圖的鄰接矩陣中對角線以下元素均為零，則該圖的拓撲序列必然存在。

【解答】對。參見第11題的證實。

⑻在AOE網中一定惟獨一條關鍵路徑br/>【解答】錯。AOE網中可能有不止一條關鍵路徑，他們的路徑長度相同。

4．n個頂點的無向圖，采納鄰接表存儲，回答下列問題br/>⑴圖中有多少條邊？

⑵隨意兩個頂點i和j是否有邊相連？

⑶隨意一個頂點的度是多少br/>【解答】

⑴邊表中的結點個數之和除以2。

⑵第i個邊表中是否含有結點j。

⑶該頂點所對應的邊表中所含結點個數。

5．n個頂點的無向圖，采納鄰接矩陣存儲，回答下列問題：

⑴圖中有多少條邊？

⑵隨意兩個頂點i和j是否有邊相連？

⑶隨意一個頂點的度是多少？

【解答】

⑴鄰接矩陣中非零元素個數的總和除以2。

⑵當鄰接矩陣A中A[i][j]=1（或A[j][i]=1）時，表示兩頂點之間有邊相連。

⑶計算鄰接矩陣上該頂點對應的行上非零元素的個數。

6．證實：生成樹中最長路徑的起點和盡頭的度均為１。

【解答】用反證法證實。

設v1,v2,…,vk是生成樹的一條最長路徑，其中，v1為起點，vk為盡頭。若vk的度為2，取vk的另一個鄰接點v，因為生成樹中無回路，所以，v在最長路徑上，明顯v1,v2,…,vk,v的路徑最長，與假設沖突。所以生成樹中最長路徑的盡頭的度為1。

同理可證起點v1的度不能大于1，只能為1。

7．已知一個連通圖如圖6-6所示，試給出圖的鄰接矩陣和鄰接表存儲暗示圖，若從頂點v1動身對該圖舉行遍歷，分離給出一個按深度優先遍歷和廣度優先遍歷的頂點序列。

【解答】鄰接矩陣表示如下：

深度優先遍歷序列為：v1v2v3v5v4v6

廣度優先遍歷序列為：v1v2v4v6v3v5

鄰接表表示如下：

8．圖6-7所示是一個無向帶權圖，請分離按Prim算法和Kruskal算法求最小生成樹。

【解答】按Prim算法求最小生成樹的過程如下：

按Kruskal算法求最小生成樹的過程如下：

9．對于圖6-8所示的帶權有向圖，求從源點v1到其他各頂點的最短路徑。

【解答】從源點v1到其他各頂點的最短路徑如下表所示。

源點盡頭最短路徑最短路徑長度

v1v7v1v77

v1v5v1v511

v1v4v1v7v413

v1v6v1v7v4v616

v1v2v1v7v222

v1v3v1v7v4v6v325

10．如圖6-9所示的有向網圖，利用Dijkstra算法求從頂點v1到其他各頂點的最短路徑。

【解答】從源點v1到其他各頂點的最短路徑如下表所示。

源點盡頭最短路徑最短路徑長度

v1v3v1v315

v1v5v1v515

v1v2v1v3v225

v1v6v1v3v2v640

v1v4v1v3v2v445

11．證實：只要適當地羅列頂點的次序，就能使有向無環圖的鄰接矩陣中主對角線以下的元素所有為0。【解答】隨意n個結點的有向無環圖都可以得到一個拓撲序列。設拓撲序列為v0v1v2…vn-1，我們來證實此時的鄰接矩陣A為上三角矩陣。證實采納反證法。

假設此時的鄰接矩陣不是上三角矩陣，那么，存在下標i和j（i>j），使得A[i][j]不等于零，即圖中存在從vi到vj的一條有向邊。由拓撲序列的定義可知，在隨意拓撲序列中，vi的位置一定在vj之前，而在上述拓撲序列v0v1v2…vn-1中，因為i>j，即vi的位置在vj之后，導致沖突。因此命題正確。

12.算法設計

⑴設計算法，將一個無向圖的鄰接矩陣轉換為鄰接表。

【解答】先設置一個空的鄰接表，然后在鄰接矩陣上查找值不為零的元素，找到后在鄰接表的對應單鏈表中插入相應的邊表結點。

鄰接矩陣存儲結構定義如下：

constintMaxSize=10;

template

structAdjMatrix{

Tvertex[MaxSize];

6.2.1

6C在一個具有n個頂點的有向徹低圖中包含有（）條邊：

An(n-1)/2

Bn(n-1)

Cn(n+1)/2

Dn2

【解答】B

6．n個頂點的連通圖用鄰接矩陣表示時，該矩陣至少有（）個非零元素。

【解答】2(n-1)

7．表示一個有100個頂點，1000條邊的有向圖的鄰接矩陣有（）個非零矩陣元素。

【解答】1000

8．一個具有n個頂點k條邊的無向圖是一個森林（n>k），則該森林中必有（）棵樹。

Ak

Bn

Cn-k

D1

【解答】C

9．用深度優先遍歷辦法遍歷一個有向無環圖，并在深度優先遍歷算法中按退棧次序打印出相應的頂點，則輸出的頂點序列是（）。

A逆拓撲有序

B拓撲有序

C無序

D深度優先遍歷序列

【解答】A

10.關鍵路徑是AOE網中（）。

A從源點到盡頭的最長路徑B從源點到盡頭的最長路徑

C最長的回路

D最短的回路

【解答】A

11.已知無向圖G的鄰接表如圖6-10所示，分離寫出從頂點1動身的深度遍歷和廣度遍歷序列，并畫出相應的生成樹。

【解答】深度優先遍歷序列為：1，2，3，4，5，6

對應的生成樹為：

廣度優先遍歷序列為：1，2，4，3，5，6

對應的生成樹為：

12.已知已個AOV網如圖6-11所示，寫出全部拓撲序列。

【解答】拓撲序列為：v0v1v5v2v3v6v4、v0v1v5v2v6v3v4、v0v1v5v6v2v3v4。

第