數(shù)據(jù)結(jié)構(gòu)習(xí)題和答案及解析

千里之行，始于足下讓知識(shí)帶有溫度。第第2頁(yè)/共2頁(yè)精品文檔推薦數(shù)據(jù)結(jié)構(gòu)習(xí)題和答案及解析第1章緒論

課后習(xí)題講解

1.填空

⑴（）是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體舉行考慮和處理。

【解答】數(shù)據(jù)元素

⑵（）是數(shù)據(jù)的最小單位，（）是研究數(shù)據(jù)結(jié)構(gòu)時(shí)涉及的最小數(shù)據(jù)單位。

【解答】數(shù)據(jù)項(xiàng)，數(shù)據(jù)元素

【分析】數(shù)據(jù)結(jié)構(gòu)指的是數(shù)據(jù)元素以及數(shù)據(jù)元素之間的關(guān)系。

⑶從規(guī)律關(guān)系上講，數(shù)據(jù)結(jié)構(gòu)主要分為（）、（）、（）和（）。

【解答】集合，線性結(jié)構(gòu)，樹(shù)結(jié)構(gòu)，圖結(jié)構(gòu)

⑷數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)主要有（）和（）兩種基本辦法，不論哪種存儲(chǔ)結(jié)構(gòu)，都要存儲(chǔ)兩方面的內(nèi)容：（）和（）。

【解答】挨次存儲(chǔ)結(jié)構(gòu)，鏈接存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素，數(shù)據(jù)元素之間的關(guān)系

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

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

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

【解答】自然語(yǔ)言，程序設(shè)計(jì)語(yǔ)言，流程圖，偽代碼，偽代碼

⑺在普通狀況下，一個(gè)算法的時(shí)光復(fù)雜度是（）的函數(shù)。

【解答】問(wèn)題規(guī)模

⑻設(shè)待處理問(wèn)題的規(guī)模為n，若一個(gè)算法的時(shí)光復(fù)雜度為一個(gè)常數(shù)，則表示成數(shù)量級(jí)的形式為（），若為n*log25n，則表示成數(shù)量級(jí)的形式為（）。

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

【分析】用大O記號(hào)表示算法的時(shí)光復(fù)雜度，需要將低次冪去掉，將最高次冪的系數(shù)去掉。

2.挑選題

⑴挨次存儲(chǔ)結(jié)構(gòu)中數(shù)據(jù)元素之間的規(guī)律關(guān)系是由（）表示的，鏈接存儲(chǔ)結(jié)構(gòu)中的數(shù)據(jù)元素之間的規(guī)律關(guān)系是由（）表示的。

A線性結(jié)構(gòu)

B非線性結(jié)構(gòu)

C存儲(chǔ)位置

D指針

【解答】C，D

【分析】挨次存儲(chǔ)結(jié)構(gòu)就是用一維數(shù)組存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素，其規(guī)律關(guān)系由存儲(chǔ)位置（即元素在數(shù)組中的下標(biāo)）表示；鏈接存儲(chǔ)結(jié)構(gòu)中一個(gè)數(shù)據(jù)元素對(duì)應(yīng)鏈表中的一個(gè)結(jié)點(diǎn)，元素之間的規(guī)律關(guān)系由結(jié)點(diǎn)中的指針表示。

⑵假設(shè)有如下遺產(chǎn)繼承規(guī)章：丈夫和妻子可以互相繼承遺產(chǎn)；子女可以繼承父親或母親的遺產(chǎn)；子女間不能互相繼承。則表示該遺產(chǎn)繼承關(guān)系的最合適的數(shù)據(jù)結(jié)構(gòu)應(yīng)當(dāng)是（）。

A樹(shù)

B圖

C線性表

D集合

【解答】B

【分析】將丈夫、妻子和子女分離作為數(shù)據(jù)元素，按照題意畫(huà)出規(guī)律結(jié)構(gòu)圖。

⑶算法指的是（）。

A對(duì)特定問(wèn)題求解步驟的一種描述，是指令的有限序列。

B計(jì)算機(jī)程序

C解決問(wèn)題的計(jì)算辦法

D數(shù)據(jù)處理

【解答】A

【分析】計(jì)算機(jī)程序是對(duì)算法的詳細(xì)實(shí)現(xiàn)；容易地說(shuō)，算法是解決問(wèn)題的辦法；數(shù)據(jù)處理是通過(guò)算法完成的。所以，惟獨(dú)A是算法的精確?????定義。

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

A有窮性

B確切性

C高效性

D可行性

【解答】C

【分析】高效性是好算法應(yīng)具備的特性。

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

A找出數(shù)據(jù)結(jié)構(gòu)的合理性

B討論算法中輸入和輸出的關(guān)系

C分析算法的效率以求改進(jìn)

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

E空間性能和時(shí)光性能

F正確性和簡(jiǎn)明性

G可讀性和文檔性H數(shù)據(jù)復(fù)雜性和程序復(fù)雜性

【解答】C，E

⑴算法的時(shí)光復(fù)雜度都要通過(guò)算法中的基本語(yǔ)句的執(zhí)行次數(shù)來(lái)確定。

【解答】錯(cuò)。時(shí)光復(fù)雜度要通過(guò)算法中基本語(yǔ)句執(zhí)行次數(shù)的數(shù)量級(jí)來(lái)確定。

⑵每種數(shù)據(jù)結(jié)構(gòu)都具備三個(gè)基本操作：插入、刪除和查找。

【解答】錯(cuò)。如數(shù)組就沒(méi)有插入和刪除操作。此題注重是每種數(shù)據(jù)結(jié)構(gòu)。

⑶所謂數(shù)據(jù)的規(guī)律結(jié)構(gòu)指的是數(shù)據(jù)之間的規(guī)律關(guān)系。

【解答】錯(cuò)。是數(shù)據(jù)之間的規(guī)律關(guān)系的整體。

⑷規(guī)律結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無(wú)關(guān)。

【解答】對(duì)。因此規(guī)律結(jié)構(gòu)是數(shù)據(jù)組織的主要方面。

⑸基于某種規(guī)律結(jié)構(gòu)之上的基本操作，其實(shí)現(xiàn)是唯一的。

【解答】錯(cuò)?；静僮鞯膶?shí)現(xiàn)是基于某種存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)的，因而不是唯一的。

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

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

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

⑶分析條件語(yǔ)句，每循環(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++是基本語(yǔ)句，所以

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)}。試畫(huà)出其規(guī)律結(jié)構(gòu)圖并指出屬于何種結(jié)構(gòu)。【解答】其規(guī)律結(jié)構(gòu)圖如圖1-3所示，它是一種圖結(jié)構(gòu)。

6.為整數(shù)定義一個(gè)抽象數(shù)據(jù)類型，包含整數(shù)的常見(jiàn)運(yùn)算，每個(gè)運(yùn)算對(duì)應(yīng)一個(gè)基本操作，每個(gè)基本操作的接口需定義前置條件、輸入、功能、輸出和后置條件。

【解答】整數(shù)的抽象數(shù)據(jù)類型定義如下：

ADTinteger

Data

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

Constructor

前置條件：整數(shù)a不存在

輸入：一個(gè)整數(shù)b

功能：構(gòu)造一個(gè)與輸入值相同的整數(shù)

輸出：無(wú)

后置條件：整數(shù)a具有輸入的值

Set

前置條件：存在一個(gè)整數(shù)a

輸入：一個(gè)整數(shù)b

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

輸出：無(wú)

后置條件：整數(shù)a的值發(fā)生轉(zhuǎn)變

Add

前置條件：存在一個(gè)整數(shù)a

輸入：一個(gè)整數(shù)b

功能：將整數(shù)a與輸入的整數(shù)b相加輸出：相加后的結(jié)果

后置條件：整數(shù)a的值發(fā)生轉(zhuǎn)變Sub

前置條件：存在一個(gè)整數(shù)a

輸入：一個(gè)整數(shù)b

功能：將整數(shù)a與輸入的整數(shù)b相減輸出：相減的結(jié)果

后置條件：整數(shù)a的值發(fā)生轉(zhuǎn)變Multi

前置條件：存在一個(gè)整數(shù)a

輸入：一個(gè)整數(shù)b

功能：將整數(shù)a與輸入的整數(shù)b相乘輸出：相乘的結(jié)果

后置條件：整數(shù)a的值發(fā)生轉(zhuǎn)變

Div

前置條件：存在一個(gè)整數(shù)a

輸入：一個(gè)整數(shù)b

功能：將整數(shù)a與輸入的整數(shù)b相除

輸出：若整數(shù)b為零，則拋出除零異樣，否則輸出相除的結(jié)果后置條件：整數(shù)a的值發(fā)生轉(zhuǎn)變

Mod

前置條件：存在一個(gè)整數(shù)a

輸入：一個(gè)整數(shù)b

功能：求當(dāng)前整數(shù)與輸入整數(shù)的模，即正的余數(shù)

輸出：若整數(shù)b為零，則拋出除零異樣，否則輸出取模的結(jié)果后置條件：整數(shù)a的值發(fā)生轉(zhuǎn)變

Equal

前置條件：存在一個(gè)整數(shù)a

輸入：一個(gè)整數(shù)b

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

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

后置條件：整數(shù)a的值不發(fā)生轉(zhuǎn)變

endADT

7.求多項(xiàng)式A(x)的算法可按照下列兩個(gè)公式之一來(lái)設(shè)計(jì)：

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

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

按照算法的時(shí)光復(fù)雜度分析比較這兩種算法的優(yōu)劣。

【解答】其次種算法的時(shí)光性能要好些。第一種算法需執(zhí)行大量的乘法運(yùn)算，而其次種算法舉行了優(yōu)化，削減了不須要的乘法運(yùn)算。

8.算法設(shè)計(jì)（要求：算法用偽代碼和C++描述，并分析最壞狀況下的時(shí)光復(fù)雜度）

⑴對(duì)一個(gè)整型數(shù)組A[n]設(shè)計(jì)一個(gè)排序算法。

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

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

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

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

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

算法的C++描述如下：

分析算法，惟獨(dú)一層循環(huán)，共執(zhí)行n-2次，所以，T(n)=O(n)。學(xué)習(xí)自測(cè)及答案

1．挨次存儲(chǔ)結(jié)構(gòu)的特點(diǎn)是（），鏈接存儲(chǔ)結(jié)構(gòu)的特點(diǎn)是（）。

【解答】用元素在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)元素之間的規(guī)律關(guān)系，用指示元素存儲(chǔ)地址的指針表示數(shù)據(jù)元素之間的規(guī)律關(guān)系。

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

【解答】茁壯性

3.常見(jiàn)的算法時(shí)光復(fù)雜度用大Ｏ記號(hào)表示為：常數(shù)階()、對(duì)數(shù)階()、線性階()、平方階()和指數(shù)階()?！窘獯稹浚?1)，Ｏ(log2n)，Ｏ(n)，Ｏ(n2)，Ｏ(2n)

4．將下列函數(shù)按它們?cè)趎時(shí)的無(wú)窮大階數(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è)計(jì)語(yǔ)言中數(shù)據(jù)類型概念的區(qū)分。

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

6.對(duì)下列用二元組表示的數(shù)據(jù)結(jié)構(gòu),試分離畫(huà)出對(duì)應(yīng)的規(guī)律結(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)}

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

⑶屬于樹(shù)結(jié)構(gòu)，其規(guī)律結(jié)構(gòu)圖如圖1-4(c)所示；⑷屬于圖結(jié)構(gòu)，其規(guī)律結(jié)構(gòu)圖如圖1-4(d)所示。

7.求下列算法的時(shí)光復(fù)雜度。

count=0;x=1;

while(x{

x*=2;

count++;

}

returncount;

【解答】Ｏ(log2n)

第2章線性表

課后習(xí)題講解

1.填空

⑴在挨次表中，等概率狀況下，插入和刪除一個(gè)元素平均需移動(dòng)（）個(gè)元素，詳細(xì)移動(dòng)元素的個(gè)數(shù)與（）和（）有關(guān)。

【解答】表長(zhǎng)的一半，表長(zhǎng)，該元素在表中的位置

⑵挨次表中第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長(zhǎng)度為2，則第5個(gè)元素的存儲(chǔ)地址是（）。

【解答】108

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

⑶設(shè)單鏈表中指針p指向結(jié)點(diǎn)A，若要?jiǎng)h除A的后繼結(jié)點(diǎn)（假設(shè)A存在后繼結(jié)點(diǎn)），則需修改指針的操作為（）。

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

⑷單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是（）。

【解答】為了運(yùn)算便利

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

⑸非空的單循環(huán)鏈表由頭指針head指示，則其尾結(jié)點(diǎn)（由指針p所指）滿足（）。

【解答】p->next=head

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

⑹在由尾指針rear指示的單循環(huán)鏈表中，在表尾插入一個(gè)結(jié)點(diǎn)s的操作序列是（）；刪除開(kāi)頭結(jié)點(diǎn)的操作序列為（）。

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

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

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

⑺一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表，在指針p所指結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)光復(fù)雜度為（）；在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)光復(fù)雜度為（）。

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

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

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

【解答】循環(huán)鏈表，循環(huán)雙鏈表，雙鏈表

2.挑選題

⑴線性表的挨次存儲(chǔ)結(jié)構(gòu)是一種（）的存儲(chǔ)結(jié)構(gòu)，線性表的鏈接存儲(chǔ)結(jié)構(gòu)是一種（）的存儲(chǔ)結(jié)構(gòu)。

A隨機(jī)存取

B挨次存取

C索引存取

D散列存取

【解答】A，B

【分析】參見(jiàn)2.2.1。

⑵線性表采納鏈接存儲(chǔ)時(shí)，其地址（）。

A必需是延續(xù)的

B部分地址必需是延續(xù)的

C一定是不延續(xù)的

D延續(xù)與否均可以

【解答】D

【分析】線性表的鏈接存儲(chǔ)是用一組隨意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素，這組存儲(chǔ)單元可以延續(xù)，也可以不延續(xù)，甚至可以零散分布在內(nèi)存中隨意位置。

⑶單循環(huán)鏈表的主要優(yōu)點(diǎn)是（）。

A不再需要頭指針了

B從表中任一結(jié)點(diǎn)動(dòng)身都能掃描到囫圇鏈表；

C已知某個(gè)結(jié)點(diǎn)的位置后，能夠簡(jiǎn)單找到它的直接前趨；

D在舉行插入、刪除操作時(shí)，能更好地保證鏈表不斷開(kāi)。

【解答】B

⑷鏈表不具有的特點(diǎn)是（）。

A可隨機(jī)拜訪任一元素

B插入、刪除不需要移動(dòng)元素

C不必事先估量存儲(chǔ)空間

D所需空間與線性表長(zhǎng)度成正比

【解答】A

⑸若某線性表中最常用的操作是取第i個(gè)元素和找第i個(gè)元素的前趨，則采納（）存儲(chǔ)辦法最節(jié)約時(shí)光。

A挨次表

B單鏈表

C雙鏈表

D單循環(huán)鏈表

【分析】線性表中最常用的操作是取第i個(gè)元素，所以，應(yīng)挑選隨機(jī)存取結(jié)構(gòu)即挨次表，同時(shí)在挨次表中查找第i個(gè)元素的前趨也很便利。單鏈表和單循環(huán)鏈表既不能實(shí)現(xiàn)隨機(jī)存取，查找第i個(gè)元素的前趨也不便利，雙鏈表雖然能迅速查找第i個(gè)元素的前趨，但不能實(shí)現(xiàn)隨機(jī)存取。

⑹若鏈表中最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)和刪除第一個(gè)結(jié)點(diǎn)，則采納（）存儲(chǔ)辦法最節(jié)約時(shí)光。

A單鏈表

B帶頭指針的單循環(huán)鏈表

C雙鏈表

D帶尾指針的單循環(huán)鏈表

【解答】D

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

⑺若鏈表中最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)和刪除最后一個(gè)結(jié)點(diǎn)，則采納（）存儲(chǔ)辦法最節(jié)約運(yùn)算時(shí)光。

A單鏈表

B循環(huán)雙鏈表C單循環(huán)鏈表D帶尾指針的單循環(huán)鏈表

【解答】B

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

⑻在具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然有序的時(shí)光復(fù)雜度是（）。

AO(1)

BO(n)

CO(n2)

DO(nlog2n)

【分析】首先應(yīng)挨次查找新結(jié)點(diǎn)在單鏈表中的位置。

⑼對(duì)于n個(gè)元素組成的線性表，建立一個(gè)有序單鏈表的時(shí)光復(fù)雜度是（）。

AO(1)

BO(n)

CO(n2)

DO(nlog2n)

【解答】C

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

⑽使用雙鏈表存儲(chǔ)線性表，其優(yōu)點(diǎn)是可以（）。

A提高查找速度

B更便利數(shù)據(jù)的插入和刪除

C節(jié)省存儲(chǔ)空間

D很快回收存儲(chǔ)空間

【解答】B

【分析】在鏈表中普通只能舉行挨次查找，所以，雙鏈表并不能提高查找速度，由于雙鏈表中有兩個(gè)指針域，明顯不能節(jié)省存儲(chǔ)空間，對(duì)于動(dòng)態(tài)存儲(chǔ)分配，回收存儲(chǔ)空間的速度是一樣的。因?yàn)殡p鏈表具有對(duì)稱性，所以，其插入和刪除操作越發(fā)便利。

⑾在一個(gè)單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的直接前驅(qū)，若在q和p之間插入s所指結(jié)點(diǎn)，則執(zhí)行（）操作。

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之間插入新結(jié)點(diǎn)，所以，不用考慮修改指針的挨次。

⑿在循環(huán)雙鏈表的p所指結(jié)點(diǎn)后插入s所指結(jié)點(diǎn)的操作是（）。

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

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

3.推斷題

⑴線性表的規(guī)律挨次和存儲(chǔ)挨次總是全都的。

【解答】錯(cuò)。挨次表的規(guī)律挨次和存儲(chǔ)挨次全都，鏈表的規(guī)律挨次和存儲(chǔ)挨次不一定全都。

⑵線性表的挨次存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈接存儲(chǔ)結(jié)構(gòu)。

【解答】錯(cuò)。兩種存儲(chǔ)結(jié)構(gòu)各有優(yōu)缺點(diǎn)。

⑶設(shè)p，q是指針，若p=q，則*p=*q。

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

⑷線性結(jié)構(gòu)的基本特征是：每個(gè)元素有且僅有一個(gè)直接前驅(qū)和一個(gè)直接后繼。

【解答】錯(cuò)。每個(gè)元素最多惟獨(dú)一個(gè)直接前驅(qū)和一個(gè)直接后繼，第一個(gè)元素沒(méi)有前驅(qū)，最后一個(gè)元素沒(méi)有后繼。

⑸在單鏈表中，要取得某個(gè)元素，只要知道該元素所在結(jié)點(diǎn)的地址即可，因此單鏈表是隨機(jī)存取結(jié)構(gòu)?！窘獯稹垮e(cuò)。要找到該結(jié)點(diǎn)的地址，必需從頭指針開(kāi)頭查找，所以單鏈表是挨次存取結(jié)構(gòu)。

4．請(qǐng)說(shuō)明挨次表和單鏈表各有何優(yōu)缺點(diǎn)，并分析下列狀況下，采納何種存儲(chǔ)結(jié)構(gòu)更好些。

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

⑵假如n個(gè)線性表同時(shí)并存，并且在處理過(guò)程中各表的長(zhǎng)度會(huì)動(dòng)態(tài)發(fā)生變化。

⑶描述一個(gè)城市的設(shè)計(jì)和規(guī)劃。

【解答】挨次表的優(yōu)點(diǎn)：①無(wú)需為表示表中元素之間的規(guī)律關(guān)系而增強(qiáng)額外的存儲(chǔ)空間；②可以迅速地存取表中任一位置的元素（即隨機(jī)存?。?。挨次表的缺點(diǎn)：①插入和刪除操作需移動(dòng)大量元素；②表的容量難以確定；③造成存儲(chǔ)空間的“碎片”。

單鏈表的優(yōu)點(diǎn)：①不必事先知道線性表的長(zhǎng)度；②插入和刪除元素時(shí)只需修改指針，不用移動(dòng)元素。單鏈表的缺點(diǎn)：①指針的結(jié)構(gòu)性開(kāi)銷；②存取表中隨意元素不便利，只能舉行挨次存取。

⑴應(yīng)選用挨次存儲(chǔ)結(jié)構(gòu)。由于挨次表是隨機(jī)存取結(jié)構(gòu)，單鏈表是挨次存取結(jié)構(gòu)。本題很少舉行插入和刪除操作，所以空間變化不大，且需要迅速存取，所以應(yīng)選用挨次存儲(chǔ)結(jié)構(gòu)。

⑵應(yīng)選用鏈接存儲(chǔ)結(jié)構(gòu)。鏈表簡(jiǎn)單實(shí)現(xiàn)表容量的擴(kuò)充，適合表的長(zhǎng)度動(dòng)態(tài)發(fā)生變化。

⑶應(yīng)選用鏈接存儲(chǔ)結(jié)構(gòu)。由于一個(gè)城市的設(shè)計(jì)和規(guī)劃涉及活動(dòng)無(wú)數(shù)，需要常常修改、擴(kuò)充和刪除各種信息，才干適應(yīng)不斷進(jìn)展的需要。而挨次表的插入、刪除的效率低，故不合適。

5．算法設(shè)計(jì)

⑴設(shè)計(jì)一個(gè)時(shí)光復(fù)雜度為Ｏ(n)的算法，實(shí)現(xiàn)將數(shù)組A[n]中全部元素循環(huán)右移k個(gè)位置。

【解答】算法思想請(qǐng)參見(jiàn)主教材第一章思想火花。下面給出詳細(xì)算法。

分析算法，第一次調(diào)用Reverse函數(shù)的時(shí)光復(fù)雜度為O(k)，其次次調(diào)用Reverse函數(shù)的時(shí)光復(fù)雜度為

O(n-k)，第三次調(diào)用Reverse函數(shù)的時(shí)光復(fù)雜度為O(n)，所以，總的時(shí)光復(fù)雜度為O(n)。

⑵已知數(shù)組A[n]中的元素為整型，設(shè)計(jì)算法將其調(diào)節(jié)為左右兩部分，左邊全部元素為奇數(shù)，右邊全部元素為偶數(shù)，并要求算法的時(shí)光復(fù)雜度為Ｏ(n)。

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

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

⑶試編寫(xiě)在無(wú)頭結(jié)點(diǎn)的單鏈表上實(shí)現(xiàn)線性表的插入操作的算法，并和帶頭結(jié)點(diǎn)的單鏈表上的插入操作的實(shí)現(xiàn)舉行比較。

【解答】參見(jiàn)2.2.3。

⑷試分離以挨次表和單鏈表作存儲(chǔ)結(jié)構(gòu)，各寫(xiě)一實(shí)現(xiàn)線性表就地逆置的算法。

【解答】挨次表的逆置，即是將對(duì)稱元素交換，設(shè)挨次表的長(zhǎng)度為length，則將表中第i個(gè)元素與第length-i-1個(gè)元素相交換。詳細(xì)算法如下：

單鏈表的逆置請(qǐng)參見(jiàn)2.2.4算法2-4和算法2-6。

⑸假設(shè)在長(zhǎng)度大于1的循環(huán)鏈表中，即無(wú)頭結(jié)點(diǎn)也無(wú)頭指針，s為指向鏈表中某個(gè)結(jié)點(diǎn)的指針，試編寫(xiě)算法刪除結(jié)點(diǎn)s的前趨結(jié)點(diǎn)。

【解答】利用單循環(huán)鏈表的特點(diǎn)，通過(guò)指針s可找到其前驅(qū)結(jié)點(diǎn)r以及r的前驅(qū)結(jié)點(diǎn)p，然后將結(jié)點(diǎn)r刪除，如圖2-11所示，詳細(xì)算法如下：

⑹已知一單鏈表中的數(shù)據(jù)元素含有三類字符：字母、數(shù)字和其他字符。試編寫(xiě)算法，構(gòu)造三個(gè)循環(huán)鏈表，使每個(gè)循環(huán)鏈表中只含同一類字符。

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

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

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

⑻推斷帶頭結(jié)點(diǎn)的雙循環(huán)鏈表是否對(duì)稱。

【解答】設(shè)工作指針p和q分離指向循環(huán)雙鏈表的開(kāi)頭結(jié)點(diǎn)和終端結(jié)點(diǎn)，若結(jié)點(diǎn)p和結(jié)點(diǎn)q的數(shù)據(jù)域相等，則工作指針p后移，工作指針q前移，直到指針p和指針q指向同一結(jié)點(diǎn)（循環(huán)雙鏈表中結(jié)點(diǎn)個(gè)數(shù)為奇數(shù)），或結(jié)點(diǎn)q成為結(jié)點(diǎn)p的前驅(qū)（循環(huán)雙鏈表中結(jié)點(diǎn)個(gè)數(shù)為偶數(shù)）。如圖2-12所示。

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

1.已知一維數(shù)組A采納挨次存儲(chǔ)結(jié)構(gòu)，每個(gè)元素占用4個(gè)存儲(chǔ)單元，第9個(gè)元素的地址為144，則第一個(gè)元素的地址是（）。

A108

B180

C176

D112

【解答】D

2．在長(zhǎng)度為n的線性表中查找值為x的數(shù)據(jù)元素的時(shí)光復(fù)雜度為：（）。

AO(0)

BO(1)

CO(n)

DO(n2)

【解答】C

3．在一個(gè)長(zhǎng)度為n的挨次表的第i（1≤i≤n+1）個(gè)元素之前插入一個(gè)元素，需向后移動(dòng)（）個(gè)元素，刪除第i（1≤i≤n）個(gè)元素時(shí)，需向前移動(dòng)（）個(gè)元素。

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

4．在單鏈表中，除了頭結(jié)點(diǎn)以外，任一結(jié)點(diǎn)的存儲(chǔ)位置由（）指示。

【解答】其前趨結(jié)點(diǎn)的指針域

5．當(dāng)線性表采納挨次存儲(chǔ)結(jié)構(gòu)時(shí)，其主要特點(diǎn)是（）。

【解答】規(guī)律結(jié)構(gòu)中相鄰的結(jié)點(diǎn)在存儲(chǔ)結(jié)構(gòu)中仍相鄰

6．在雙鏈表中，每個(gè)結(jié)點(diǎn)設(shè)置了兩個(gè)指針域，其中一個(gè)指向（）結(jié)點(diǎn)，另一個(gè)指向（）結(jié)點(diǎn)。

【解答】前驅(qū)，后繼

7．設(shè)A是一個(gè)線性表（a1,a2,…,an），采納挨次存儲(chǔ)結(jié)構(gòu)，則在等概率的前提下，平均每插入一個(gè)元

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

【解答】

，

。

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

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

9.已知單鏈表中各結(jié)點(diǎn)的元素值為整型且遞增有序，設(shè)計(jì)算法刪除鏈表中全部大于mink且小于maxk的全部元素，并釋放被刪結(jié)點(diǎn)的存儲(chǔ)空間。

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

10．設(shè)單循環(huán)鏈表L1，對(duì)其遍歷的結(jié)果是：x1,x2,x3,…,xn-1,xn。請(qǐng)將該循環(huán)鏈表拆成兩個(gè)單循環(huán)鏈表L1和L2，使得L1中含有原L1表中序號(hào)為奇數(shù)的結(jié)點(diǎn)且遍歷結(jié)果為：x1,x3,…；L2中含有原L1表中序號(hào)為偶數(shù)的結(jié)點(diǎn)且遍歷結(jié)果為：…,x4,x2。

【解答】算法如下：

第3章特別線性表——棧、隊(duì)列和串

課后習(xí)題講解

1.填空

⑴設(shè)有一個(gè)空棧，棧頂指針為1000H，現(xiàn)有輸入序列為1、2、3、4、5，經(jīng)過(guò)push，push，pop，push，pop，push，push后，輸出序列是（），棧頂指針為（）。

【解答】23，1003H

⑵棧通常采納的兩種存儲(chǔ)結(jié)構(gòu)是（）；其判定?？盏臈l件分離是（），判定棧滿的條件分離是（）。【解答】挨次存儲(chǔ)結(jié)構(gòu)和鏈接存儲(chǔ)結(jié)構(gòu)（或挨次棧和鏈棧），棧頂指針top=-1和top=NULL，棧頂指針top等于數(shù)組的長(zhǎng)度和內(nèi)存無(wú)可用空間

⑶（）可作為實(shí)現(xiàn)遞歸函數(shù)調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)。

【解答】棧

【分析】遞歸函數(shù)的調(diào)用和返回正巧符合后進(jìn)先出性。

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

【解答】abc+*d-

【分析】將中綴表達(dá)式變?yōu)楹缶Y表達(dá)式有一個(gè)技巧：將操作數(shù)依次寫(xiě)下來(lái)，再將算符插在它的兩個(gè)操作數(shù)的后面。

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

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

⑹循環(huán)隊(duì)列的引入是為了克服（）。

【解答】假溢出

⑺數(shù)組Q[n]用來(lái)表示一個(gè)循環(huán)隊(duì)列，front為隊(duì)頭元素的前一個(gè)位置，rear為隊(duì)尾元素的位置，計(jì)算隊(duì)列中元素個(gè)數(shù)的公式為（）。

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

【分析】也可以是（rear-front）%n，但rear-front的結(jié)果可能是負(fù)整數(shù)，而對(duì)一個(gè)負(fù)整數(shù)求模，其結(jié)果在不同的編譯器環(huán)境下可能會(huì)有所不同。

⑻用循環(huán)鏈表表示的隊(duì)列長(zhǎng)度為n，若只設(shè)頭指針，則出隊(duì)和入隊(duì)的時(shí)光復(fù)雜度分離是（）和（）?！窘獯稹浚?1)，Ｏ(n)

【分析】在帶頭指針的循環(huán)鏈表中，出隊(duì)即是刪除開(kāi)頭結(jié)點(diǎn)，這只需修改相應(yīng)指針；入隊(duì)即是在終端結(jié)點(diǎn)的后面插入一個(gè)結(jié)點(diǎn)，這需要從頭指針開(kāi)頭查找終端結(jié)點(diǎn)的地址。

⑼串是一種特別的線性表，其特別性體現(xiàn)在（）。

【解答】數(shù)據(jù)元素的類型是一個(gè)字符

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

【解答】長(zhǎng)度相同且對(duì)應(yīng)位置的字符相等

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

2.挑選題

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

A不確定

Bn-i

Cn-i-1

Dn-i+1

【解答】D

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

⑵設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素e1、e2、e3、e4、e5、e6依次通過(guò)棧S，一個(gè)元素出棧后即進(jìn)入隊(duì)列Q，若6個(gè)元素出隊(duì)的挨次是e2、e4、e3、e6、e5、e1，則棧S的容量至少應(yīng)當(dāng)是（）。

A6

B4

C3

D2

【解答】C

【分析】因?yàn)殛?duì)列具有先進(jìn)先出性，所以，此題中隊(duì)列形同虛設(shè)，即出棧的挨次也是e2、e4、e3、e6、e5、e1。

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

A54321

B45321

C43512

D12345

【解答】C

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

⑷設(shè)計(jì)一個(gè)判別表達(dá)式中左右括號(hào)是否配對(duì)的算法，采納（）數(shù)據(jù)結(jié)構(gòu)最佳

A挨次表

B棧

C隊(duì)列

D鏈表

【解答】B

【分析】每個(gè)右括號(hào)與它前面的最后一個(gè)沒(méi)有匹配的左括號(hào)配對(duì)，因此具有后進(jìn)先出性。

⑸在解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配問(wèn)題時(shí)通常設(shè)置一個(gè)打印緩沖區(qū)，該緩沖區(qū)應(yīng)當(dāng)是一個(gè)（）結(jié)構(gòu)。

A棧B隊(duì)列C數(shù)組D線性表

【解答】B

【分析】先進(jìn)入打印緩沖區(qū)的文件先被打印，因此具有先進(jìn)先出性。

⑹一個(gè)隊(duì)列的入隊(duì)挨次是1，2，3，4，則隊(duì)列的輸出挨次是（）。

A4321

B1234

C1432

D3241

【解答】B

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

⑺棧和隊(duì)列的主要區(qū)分在于（）。

A它們的規(guī)律結(jié)構(gòu)不一樣

B它們的存儲(chǔ)結(jié)構(gòu)不一樣

C所包含的運(yùn)算不一樣

D插入、刪除運(yùn)算的限定不一樣

【解答】D

【分析】棧和隊(duì)列的規(guī)律結(jié)構(gòu)都是線性的，都有挨次存儲(chǔ)和鏈接存儲(chǔ)，有可能包含的運(yùn)算不一樣，但不是主要區(qū)分，任何數(shù)據(jù)結(jié)構(gòu)在針對(duì)詳細(xì)問(wèn)題時(shí)包含的運(yùn)算都可能不同。

⑻設(shè)數(shù)組S[n]作為兩個(gè)棧S1和S2的存儲(chǔ)空間，對(duì)任何一個(gè)棧惟獨(dú)當(dāng)S[n]全滿時(shí)才不能舉行進(jìn)棧操作。為這兩個(gè)棧分配空間的最佳計(jì)劃是（）。

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

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

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

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

【解答】A

【分析】?jī)蓷７窒砜臻g首先兩個(gè)棧是相向增長(zhǎng)的，棧底應(yīng)當(dāng)分離指向兩個(gè)棧中的第一個(gè)元素的位置，并注重C++中的數(shù)組下標(biāo)是從0開(kāi)頭的。

⑼設(shè)有兩個(gè)串p和q，求q在p中首次浮現(xiàn)的位置的運(yùn)算稱作（）。

A銜接

B模式匹配

C求子串

D求串長(zhǎng)

【解答】B

3.推斷題

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

【解答】錯(cuò)。應(yīng)當(dāng)有種。

⑵棧可以作為實(shí)現(xiàn)過(guò)程調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)。

【解答】對(duì)。只要操作滿足后進(jìn)先出性，都可以采納棧作為輔助數(shù)據(jù)結(jié)構(gòu)。

⑶在棧滿的狀況下不能做進(jìn)棧操作，否則將產(chǎn)生“上溢”。

【解答】對(duì)。

⑷在循環(huán)隊(duì)列中，front指向隊(duì)頭元素的前一個(gè)位置，rear指向隊(duì)尾元素的位置，則隊(duì)滿的條件是

front=rear。

【解答】錯(cuò)。這是隊(duì)空的判定條件，在循環(huán)隊(duì)列中要將隊(duì)空和隊(duì)滿的判定條件區(qū)分開(kāi)。

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

【解答】錯(cuò)?？沾拈L(zhǎng)度為零，而空格串的長(zhǎng)度不為0，其長(zhǎng)度是串中空格的個(gè)數(shù)。

4.設(shè)有一個(gè)棧，元素進(jìn)棧的次序?yàn)锳，B，C，D，E，能否得到如下出棧序列，若能，請(qǐng)寫(xiě)出操作序列，若不能，請(qǐng)說(shuō)明緣由。

⑴C，E，A，B，D

⑵C，B，A，D，E

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

5.舉例說(shuō)明挨次隊(duì)列的“假溢出”現(xiàn)象。

【解答】假設(shè)有一個(gè)挨次隊(duì)列，如圖3-6所示，隊(duì)尾指針rear=4，隊(duì)頭指針front=1，假如再有元素入隊(duì)，就會(huì)產(chǎn)生“上溢”，此時(shí)的“上溢”又稱為“假溢出”，由于隊(duì)列并不是真的溢出了，存儲(chǔ)隊(duì)列的數(shù)組中還有2個(gè)存儲(chǔ)單元空閑，其下標(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í)行過(guò)程如圖3-7所示。

7．在操作序列EnQueue(1)、EnQueue(3)、DeQueue、EnQueue(5)、EnQueue(7)、DeQueue、EnQueue(9)之后，隊(duì)頭元素和隊(duì)尾元素分離是什么（EnQueue(k)表示整數(shù)k入隊(duì)，DeQueue表示隊(duì)頭元素出隊(duì)）?！窘獯稹筷?duì)頭元素為5，隊(duì)尾元素為9。其執(zhí)行過(guò)程如圖3-8所示。

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

【解答】不含任何字符的串稱為空串，其長(zhǎng)度為零。僅含空格的串稱為空格串，它的長(zhǎng)度為串中空格符的個(gè)數(shù)。串中的空格符可用來(lái)分隔普通的字符，便于人們識(shí)別和閱讀，但計(jì)算串長(zhǎng)時(shí)應(yīng)包括這些空格符?？沾诖幚碇锌勺鳛殡S意串的子串。

9.算法設(shè)計(jì)

⑴假設(shè)以不帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個(gè)指針指向隊(duì)尾結(jié)點(diǎn)，但不設(shè)頭指針。試設(shè)計(jì)相應(yīng)的入隊(duì)和出隊(duì)的算法。

【解答】出隊(duì)操作是在循環(huán)鏈表的頭部舉行，相當(dāng)于刪除開(kāi)頭結(jié)點(diǎn)，而入隊(duì)操作是在循環(huán)鏈表的尾部舉行，相當(dāng)于在終端結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)。因?yàn)檠h(huán)鏈表不帶頭結(jié)點(diǎn)，需要處理空表的特別狀況。

入隊(duì)算法如下：

出隊(duì)算法如下：

⑵設(shè)挨次棧S中有2n個(gè)元素，從棧頂?shù)綏５椎脑匾来螢閍2n，a2n-1，…，a1，要求通過(guò)一個(gè)循環(huán)隊(duì)列重新羅列棧中元素，使得從棧頂?shù)綏５椎脑匾来螢閍2n，a2n-2，…，a2，a2n-1，a2n-3，…，a1，請(qǐng)?jiān)O(shè)計(jì)算法實(shí)現(xiàn)該操作，要求空間復(fù)雜度和時(shí)光復(fù)雜度均為O(n)。

【解答】操作步驟為：

①將全部元素出棧并入隊(duì)；

②依次將隊(duì)列元素出隊(duì)，假如是偶數(shù)結(jié)點(diǎn)，則再入隊(duì)，假如是奇數(shù)結(jié)點(diǎn)，則入棧；

③將奇數(shù)結(jié)點(diǎn)出棧并入隊(duì)；

④將偶數(shù)結(jié)點(diǎn)出隊(duì)并入棧；

⑤將全部元素出棧并入隊(duì)；

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

⑶用挨次存儲(chǔ)結(jié)構(gòu)存儲(chǔ)串S，編寫(xiě)算法刪除S中第i個(gè)字符開(kāi)頭的延續(xù)j個(gè)字符。

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

⑷對(duì)于采納挨次存儲(chǔ)結(jié)構(gòu)的串S，編寫(xiě)一個(gè)函數(shù)刪除其值等于ch的全部字符。

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

⑸對(duì)串的模式匹配KMP算法設(shè)計(jì)求模式滑動(dòng)位置的next函數(shù)。

【解答】參見(jiàn)3.2.5

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

1．在一個(gè)具有n個(gè)單元的挨次棧中，假定以地址低端（即下標(biāo)為0的單元）作為棧底，以top作為棧頂指針，當(dāng)出棧時(shí)，top的變化為（）。

A不變

Btop=0;

Ctop=top-1;

Dtop=top+1;

【解答】C

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

Aedcba

Bcdeba

Cdebca

Dabcde

【解答】C

3．從棧頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn)，用x保存被刪除結(jié)點(diǎn)的值，則執(zhí)行（）。

Ax=top;top=top->next;

Bx=top->data;

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

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

【解答】D

4．設(shè)元素1,2,3,P,A依次經(jīng)過(guò)一個(gè)棧，進(jìn)棧次序?yàn)?23PA，在棧的輸出序列中，有哪些序列可作為C++程序設(shè)計(jì)語(yǔ)言的變量名。

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

5.設(shè)S="I_am_a_teacther"，其長(zhǎng)度為（）。

【解答】15

第4章廣義線性表——多維數(shù)組和廣義表

課后習(xí)題講解

1.填空

⑴數(shù)組通常惟獨(dú)兩種運(yùn)算：（）和（），這打算了數(shù)組通常采納（）結(jié)構(gòu)來(lái)實(shí)現(xiàn)存儲(chǔ)。

【解答】存取，修改，挨次存儲(chǔ)

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

⑵二維數(shù)組A中行下標(biāo)從10到20，列下標(biāo)從5到10，按行優(yōu)先存儲(chǔ)，每個(gè)元素占4個(gè)存儲(chǔ)單元，A[10][5]的存儲(chǔ)地址是1000，則元素A[15][10]的存儲(chǔ)地址是（）。

【解答】1140

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

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

【解答】d+41

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

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

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

⑸廣義表((a),(((b),c)),(d))的長(zhǎng)度是（），深度是（），表頭是（），表尾是（）?！窘獯稹?，4，(a)，((((b),c)),(d))

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

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

2.挑選題

⑴二維數(shù)組A的每個(gè)元素是由6個(gè)字符組成的串，行下標(biāo)的范圍從0~8，列下標(biāo)的范圍是從0~9，則存放A至少需要（）個(gè)字節(jié)，A的第8列和第5行共占（）個(gè)字節(jié)，若A按行優(yōu)先方式存儲(chǔ)，元素A[8][5]的起始地址與當(dāng)A按列優(yōu)先方式存儲(chǔ)時(shí)的（）元素的起始地址全都。

A90

B180

C240

D540

E108

F114

G54

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

【解答】D，E，K

【分析】數(shù)組A為9行10列，共有90個(gè)元素，所以，存放A至少需要90×6=540個(gè)存儲(chǔ)單元，第8列和第5行共有18個(gè)元素（注重行列有一個(gè)交錯(cuò)元素），所以，共占108個(gè)字節(jié)，元素A[8][5]按行優(yōu)先存儲(chǔ)

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

⑵將數(shù)組稱為隨機(jī)存取結(jié)構(gòu)是由于（）

A數(shù)組元素是隨機(jī)的

B對(duì)數(shù)組任一元素的存取時(shí)光是相等的

C隨時(shí)可以對(duì)數(shù)組舉行拜訪

D數(shù)組的存儲(chǔ)結(jié)構(gòu)是不定

【解答】B

⑶下面的說(shuō)法中，不正確的是（）

A數(shù)組是一種線性結(jié)構(gòu)

B數(shù)組是一種定長(zhǎng)的線性結(jié)構(gòu)

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

D數(shù)組的基本操作有存取、修改、檢索和排序等，沒(méi)有插入與刪除操

【解答】C

【分析】數(shù)組屬于廣義線性表，數(shù)組被創(chuàng)建以后，其維數(shù)和每維中的元素個(gè)數(shù)是確定的，所以，數(shù)組通常沒(méi)有插入和刪除操作。

⑷對(duì)特別矩陣采納壓縮存儲(chǔ)的目的主要是為了（）

A表達(dá)變得容易

B對(duì)矩陣元素的存取變得容易

C去掉矩陣中的多余元素

D削減不須要的存儲(chǔ)空間

【解答】D

【分析】在特別矩陣中，有無(wú)數(shù)值相同的元素并且他們的分布有邏輯，沒(méi)有須要為值相同的元素重復(fù)存儲(chǔ)。

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

A對(duì)角矩陣

B三角矩陣

C稀疏矩陣

D對(duì)稱矩陣

【解答】C

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

A()

B(())

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

【解答】B

⑺下面的說(shuō)法中，不正確的是（）

A廣義表是一種多層次的結(jié)構(gòu)

B廣義表是一種非線性結(jié)構(gòu)

C廣義表是一種分享結(jié)構(gòu)

D廣義表是一種遞歸

【解答】B

【分析】從各層元素各自具有的線性關(guān)系講，廣義表屬于線性結(jié)構(gòu)。

⑻下面的說(shuō)法中，不正確的是（）

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

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

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

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

【分析】稀疏矩陣中大量值為零的元素分布沒(méi)有邏輯，因此采納三元組表存儲(chǔ)。假如零元素的分布有邏輯，就沒(méi)有須要存儲(chǔ)非零元素的行號(hào)和列號(hào)，而需要按其壓縮邏輯找出相應(yīng)的映象函數(shù)。

3.推斷題

⑴數(shù)組是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，數(shù)組元素之間的關(guān)系既不是線性的，也不是樹(shù)形的。

【解答】錯(cuò)。例如二維數(shù)組可以看成是數(shù)據(jù)元素為線性表的線性表。

⑵使用三元組表存儲(chǔ)稀疏矩陣的元素，有時(shí)并不能節(jié)約存儲(chǔ)空間。

【解答】對(duì)。由于三元組表除了存儲(chǔ)非零元素值外，還需要存儲(chǔ)其行號(hào)和列號(hào)。

⑶稀疏矩陣壓縮存儲(chǔ)后，必會(huì)失去隨機(jī)存取功能。

【解答】對(duì)。由于壓縮存儲(chǔ)后，非零元素的存儲(chǔ)位置和行號(hào)、列號(hào)之間失去了確定的關(guān)系。

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

【解答】對(duì)。

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

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

4．一個(gè)稀疏矩陣如圖4-4所示，寫(xiě)出對(duì)應(yīng)的三元組挨次表和十字鏈表存儲(chǔ)表示。

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

5．已知A為稀疏矩陣，試從空間和時(shí)光角度比較采納二維數(shù)組和三元組挨次表兩種不同的存儲(chǔ)結(jié)構(gòu)完成求運(yùn)算的優(yōu)缺點(diǎn)。

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

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

【分析】設(shè)滿二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)個(gè)數(shù)為n2，因?yàn)闈M二叉樹(shù)中不存在度為1的結(jié)點(diǎn)，所以n=n0+n2；由二叉樹(shù)的性質(zhì)n0=n2+1，得n0=(n+1)/2，n2=(n-1)/2。

⑷設(shè)高度為h的二叉樹(shù)上惟獨(dú)度為0和度為2的結(jié)點(diǎn)，該二叉樹(shù)的結(jié)點(diǎn)數(shù)可能達(dá)到的最大值是（），最小值是（）。

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

【分析】最小結(jié)點(diǎn)個(gè)數(shù)的狀況是第1層有1個(gè)結(jié)點(diǎn)，其他層上都惟獨(dú)2個(gè)結(jié)點(diǎn)。

⑸深度為k的二叉樹(shù)中，所含葉子的個(gè)數(shù)最多為（）。

【解答】2k-1

【分析】在滿二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù)達(dá)到最多。

⑹具有100個(gè)結(jié)點(diǎn)的徹低二叉樹(shù)的葉子結(jié)點(diǎn)數(shù)為（）。

【解答】50

【分析】100個(gè)結(jié)點(diǎn)的徹低二叉樹(shù)中最后一個(gè)結(jié)點(diǎn)的編號(hào)為100，其雙親即最后一個(gè)分支結(jié)點(diǎn)的編號(hào)為50，也就是說(shuō)，從編號(hào)51開(kāi)頭均為葉子。

⑺已知一棵度為3的樹(shù)有2個(gè)度為1的結(jié)點(diǎn)，3個(gè)度為2的結(jié)點(diǎn)，4個(gè)度為3的結(jié)點(diǎn)。則該樹(shù)中有（）個(gè)葉子結(jié)點(diǎn)。

【解答】12

【分析】按照二叉樹(shù)性質(zhì)3的證實(shí)過(guò)程，有n0=n2+2n3+1（n0、n2、n3分離為葉子結(jié)點(diǎn)、度為2的結(jié)點(diǎn)和度為3的結(jié)點(diǎn)的個(gè)數(shù)）。

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

【解答】CDBGFEA

【分析】按照前序遍歷序列和后序遍歷序列將該二叉樹(shù)構(gòu)造出來(lái)。

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

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

⑽在有n個(gè)葉子的哈夫曼樹(shù)中，葉子結(jié)點(diǎn)總數(shù)為（），分支結(jié)點(diǎn)總數(shù)為（）。

【解答】n，n-1

【分析】n-1個(gè)分支結(jié)點(diǎn)是經(jīng)過(guò)n-1次合并后得到的。

2.挑選題

⑴假如結(jié)點(diǎn)A有3個(gè)兄弟，B是A的雙親，則結(jié)點(diǎn)B的度是（）。

A1

B2

C3

D4

【解答】D

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

An-1

Bn

C+1

D不能確定

【解答】D

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

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

A空或惟獨(dú)一個(gè)結(jié)點(diǎn)

B高度等于其結(jié)點(diǎn)數(shù)

C任一結(jié)點(diǎn)無(wú)左孩子

D任一結(jié)點(diǎn)無(wú)右孩子

【解答】B

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

⑷線索二叉樹(shù)中某結(jié)點(diǎn)R沒(méi)有左孩子的充要條件是（）。

A=NULL

B=0

C=1

D=NULL

【解答】C

【分析】線索二叉樹(shù)中某結(jié)點(diǎn)是否有左孩子，不能通過(guò)左指針域是否為空來(lái)推斷，而要推斷左標(biāo)志是否為1。

⑸深度為k的徹低二叉樹(shù)至少有（）個(gè)結(jié)點(diǎn)，至多有（）個(gè)結(jié)點(diǎn)，具有n個(gè)結(jié)點(diǎn)的徹低二叉樹(shù)按層序從1開(kāi)頭編號(hào)，則編號(hào)最小的葉子的序號(hào)是（）。

A2k-2+1

B2k-1

C2k-1

D2k–1-1

E2k+1

F2k+1-1

G2k-1+1

H2k

【解答】B，C，A

【分析】深度為k的徹低二叉樹(shù)最少結(jié)點(diǎn)數(shù)的狀況應(yīng)是第k層上惟獨(dú)1個(gè)結(jié)點(diǎn)，最多的狀況是滿二叉樹(shù)，編號(hào)最小的葉子應(yīng)當(dāng)是在結(jié)點(diǎn)數(shù)最少的狀況下，葉子結(jié)點(diǎn)的編號(hào)。

⑹一個(gè)高度為h的滿二叉樹(shù)共有n個(gè)結(jié)點(diǎn)，其中有m個(gè)葉子結(jié)點(diǎn)，則有（）成立。

An=h+m

Bh+m=2n

Cm=h-1

Dn=2m-1

【解答】D

【分析】滿二叉樹(shù)中沒(méi)有度為1的結(jié)點(diǎn)，所以有m個(gè)葉子結(jié)點(diǎn)，則度為2的結(jié)點(diǎn)個(gè)數(shù)為m-1。

⑺任何一棵二叉樹(shù)的葉子結(jié)點(diǎn)在前序、中序、后序遍歷序列中的相對(duì)次序（）。

A絕對(duì)不發(fā)生轉(zhuǎn)變

B絕對(duì)發(fā)生轉(zhuǎn)變

C不能確定

D有時(shí)發(fā)生變化

【解答】A

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

⑻假如T'是由有序樹(shù)T轉(zhuǎn)換而來(lái)的二叉樹(shù)，那么T中結(jié)點(diǎn)的前序序列就是T'中結(jié)點(diǎn)的（）序列，T中結(jié)點(diǎn)的后序序列就是T'中結(jié)點(diǎn)的（）序列。

A前序

B中序

C后序

D層序

【解答】A，B

⑼設(shè)森林中有4棵樹(shù)，樹(shù)中結(jié)點(diǎn)的個(gè)數(shù)依次為n1、n2、n3、n4，則把森林轉(zhuǎn)換成二叉樹(shù)后，其根結(jié)點(diǎn)的右子樹(shù)上有（）個(gè)結(jié)點(diǎn)，根結(jié)點(diǎn)的左子樹(shù)上有（）個(gè)結(jié)點(diǎn)。

An1-1

Bn1

Cn1+n2+n3

Dn2+n3+n4

【解答】D，A

【分析】由森林轉(zhuǎn)換的二叉樹(shù)中，根結(jié)點(diǎn)即為第一棵樹(shù)的根結(jié)點(diǎn)，根結(jié)點(diǎn)的左子樹(shù)是由第一棵樹(shù)中除了根結(jié)點(diǎn)以外其余結(jié)點(diǎn)組成的，根結(jié)點(diǎn)的右子樹(shù)是由森林中除第一棵樹(shù)外其他樹(shù)轉(zhuǎn)換來(lái)的。

⑽研究樹(shù)、森林和二叉樹(shù)的關(guān)系，目的是為了（）。

A借助二叉樹(shù)上的運(yùn)算辦法去實(shí)現(xiàn)對(duì)樹(shù)的一些運(yùn)算

B將樹(shù)、森林按二叉樹(shù)的存儲(chǔ)方式舉行存儲(chǔ)并利用二叉樹(shù)的算法解決樹(shù)的有關(guān)問(wèn)題

C將樹(shù)、森林轉(zhuǎn)換成二叉樹(shù)

D體現(xiàn)一種技巧，沒(méi)有什么實(shí)際意義

【解答】B

3.推斷題

⑴在線索二叉樹(shù)中，任一結(jié)點(diǎn)均有指向其前趨和后繼的線索。

【解答】錯(cuò)。某結(jié)點(diǎn)是否有前驅(qū)或后繼的線索，取決于該結(jié)點(diǎn)的標(biāo)志域是否為1。

⑵在二叉樹(shù)的前序遍歷序列中，隨意一個(gè)結(jié)點(diǎn)均處在其子女的前面。

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

⑶二叉樹(shù)是度為2的樹(shù)。

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

⑷由樹(shù)轉(zhuǎn)換成二叉樹(shù)，其根結(jié)點(diǎn)的右子樹(shù)總是空的。

【解答】對(duì)。由于根結(jié)點(diǎn)無(wú)兄弟結(jié)點(diǎn)。

⑸用一維數(shù)組存儲(chǔ)二叉樹(shù)時(shí)，總是以前序遍歷存儲(chǔ)結(jié)點(diǎn)。

【解答】錯(cuò)。二叉樹(shù)的挨次存儲(chǔ)結(jié)構(gòu)是按層序存儲(chǔ)的，普通適合存儲(chǔ)徹低二叉樹(shù)。

4．證實(shí)：對(duì)任一滿二叉樹(shù)，其分枝數(shù)B＝2(n0-1)。（其中，n0為終端結(jié)點(diǎn)數(shù)）【解答】由于在滿二叉樹(shù)中沒(méi)有度為1的結(jié)點(diǎn)，所以有：

n=n0+n2

設(shè)B為樹(shù)中分枝數(shù)，則

n=B+1

所以

B=n0+n2-1

再由二叉樹(shù)性質(zhì)：

n0=n2+1

代入上式有：

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

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

【解答】證實(shí)采納歸納法。

設(shè)二叉樹(shù)的前序遍歷序列為a1a2a3…an，中序遍歷序列為b1b2b3…bn。

當(dāng)n=1時(shí)，前序遍歷序列為a1，中序遍歷序列為b1，二叉樹(shù)惟獨(dú)一個(gè)根結(jié)點(diǎn)，所以，a1=b1，可以唯一確定該二叉樹(shù)；

假設(shè)當(dāng)nA關(guān)鍵活動(dòng)不按期完成就會(huì)影響囫圇工程的完成時(shí)光

B任何一個(gè)關(guān)鍵活動(dòng)提前完成，那么囫圇工程將會(huì)提前完成

C全部的關(guān)鍵活動(dòng)都提前完成，那么囫圇工程將會(huì)提前完成

D某些關(guān)鍵活動(dòng)若提前完成，那么囫圇工程將會(huì)提前完

【解答】B

【分析】AOE網(wǎng)中的關(guān)鍵路徑可能不止一條，假如某一個(gè)關(guān)鍵活動(dòng)提前完成，還不能提前囫圇工程，而必需同時(shí)提高在幾條關(guān)鍵路徑上的關(guān)鍵活動(dòng)。

3.推斷題

⑴一個(gè)有向圖的鄰接表和逆鄰接表中的結(jié)點(diǎn)個(gè)數(shù)一定相等。

【解答】對(duì)。鄰接表和逆鄰接表的區(qū)分僅在于出邊和入邊，邊表中的結(jié)點(diǎn)個(gè)數(shù)都等于有向圖中邊的個(gè)數(shù)。

⑵用鄰接矩陣存儲(chǔ)圖，所占用的存儲(chǔ)空間大小只與圖中頂點(diǎn)個(gè)數(shù)有關(guān)，而與圖的邊數(shù)無(wú)關(guān)。

【解答】對(duì)。鄰接矩陣的空間復(fù)雜度為Ｏ(n2)，與邊的個(gè)數(shù)無(wú)關(guān)。

⑶圖G的生成樹(shù)是該圖的一個(gè)微小連通子圖

【解答】錯(cuò)。必需包含所有頂點(diǎn)。

⑷無(wú)向圖的鄰接矩陣一定是對(duì)稱的，有向圖的鄰接矩陣一定是不對(duì)稱的

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

⑸對(duì)隨意一個(gè)圖，從某頂點(diǎn)動(dòng)身舉行一次深度優(yōu)先或廣度優(yōu)先遍歷，可拜訪圖的全部頂點(diǎn)。

【解答】錯(cuò)。惟獨(dú)連通圖從某頂點(diǎn)動(dòng)身舉行一次遍歷，可拜訪圖的全部頂點(diǎn)。

⑹在一個(gè)有向圖的拓?fù)湫蛄兄校繇旤c(diǎn)a在頂點(diǎn)b之前，則圖中必有一條弧。

【解答】錯(cuò)。只能說(shuō)明從頂點(diǎn)a到頂點(diǎn)b有一條路徑。

⑺若一個(gè)有向圖的鄰接矩陣中對(duì)角線以下元素均為零，則該圖的拓?fù)湫蛄斜厝淮嬖凇?/p>

【解答】對(duì)。參見(jiàn)第11題的證實(shí)。

⑻在AOE網(wǎng)中一定惟獨(dú)一條關(guān)鍵路徑br/>【解答】錯(cuò)。AOE網(wǎng)中可能有不止一條關(guān)鍵路徑，他們的路徑長(zhǎng)度相同。

4．n個(gè)頂點(diǎn)的無(wú)向圖，采納鄰接表存儲(chǔ)，回答下列問(wèn)題br/>⑴圖中有多少條邊？

⑵隨意兩個(gè)頂點(diǎn)i和j是否有邊相連？

⑶隨意一個(gè)頂點(diǎn)的度是多少br/>【解答】

⑴邊表中的結(jié)點(diǎn)個(gè)數(shù)之和除以2。

⑵第i個(gè)邊表中是否含有結(jié)點(diǎn)j。

⑶該頂點(diǎn)所對(duì)應(yīng)的邊表中所含結(jié)點(diǎn)個(gè)數(shù)。

5．n個(gè)頂點(diǎn)的無(wú)向圖，采納鄰接矩陣存儲(chǔ)，回答下列問(wèn)題：

⑴圖中有多少條邊？

⑵隨意兩個(gè)頂點(diǎn)i和j是否有邊相連？

⑶隨意一個(gè)頂點(diǎn)的度是多少？

【解答】

⑴鄰接矩陣中非零元素個(gè)數(shù)的總和除以2。

⑵當(dāng)鄰接矩陣A中A[i][j]=1（或A[j][i]=1）時(shí)，表示兩頂點(diǎn)之間有邊相連。

⑶計(jì)算鄰接矩陣上該頂點(diǎn)對(duì)應(yīng)的行上非零元素的個(gè)數(shù)。

6．證實(shí)：生成樹(shù)中最長(zhǎng)路徑的起點(diǎn)和盡頭的度均為１。

【解答】用反證法證實(shí)。

設(shè)v1,v2,…,vk是生成樹(shù)的一條最長(zhǎng)路徑，其中，v1為起點(diǎn)，vk為盡頭。若vk的度為2，取vk的另一個(gè)鄰接點(diǎn)v，因?yàn)樯蓸?shù)中無(wú)回路，所以，v在最長(zhǎng)路徑上，明顯v1,v2,…,vk,v的路徑最長(zhǎng)，與假設(shè)沖突。所以生成樹(shù)中最長(zhǎng)路徑的盡頭的度為1。

同理可證起點(diǎn)v1的度不能大于1，只能為1。

7．已知一個(gè)連通圖如圖6-6所示，試給出圖的鄰接矩陣和鄰接表存儲(chǔ)暗示圖，若從頂點(diǎn)v1動(dòng)身對(duì)該圖舉行遍歷，分離給出一個(gè)按深度優(yōu)先遍歷和廣度優(yōu)先遍歷的頂點(diǎn)序列。

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

深度優(yōu)先遍歷序列為：v1v2v3v5v4v6

廣度優(yōu)先遍歷序列為：v1v2v4v6v3v5

鄰接表表示如下：

8．圖6-7所示是一個(gè)無(wú)向帶權(quán)圖，請(qǐng)分離按Prim算法和Kruskal算法求最小生成樹(shù)。

【解答】按Prim算法求最小生成樹(shù)的過(guò)程如下：

按Kruskal算法求最小生成樹(shù)的過(guò)程如下：

9．對(duì)于圖6-8所示的帶權(quán)有向圖，求從源點(diǎn)v1到其他各頂點(diǎn)的最短路徑。

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

源點(diǎn)盡頭最短路徑最短路徑長(zhǎng)度

v1v7v1v77

v1v5v1v511

v1v4v1v7v413

v1v6v1v7v4v616

v1v2v1v7v222

v1v3v1v7v4v6v325

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

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

源點(diǎn)盡頭最短路徑最短路徑長(zhǎng)度

v1v3v1v315

v1v5v1v515

v1v2v1v3v225

v1v6v1v3v2v640

v1v4v1v3v2v445

11．證實(shí)：只要適當(dāng)?shù)亓_列頂點(diǎn)的次序，就能使有向無(wú)環(huán)圖的鄰接矩陣中主對(duì)角線以下的元素所有為0。【解答】隨意n個(gè)結(jié)點(diǎn)的有向無(wú)環(huán)圖都可以得到一個(gè)拓?fù)湫蛄?。設(shè)拓?fù)湫蛄袨関0v1v2…vn-1，我們來(lái)證實(shí)此時(shí)的鄰接矩陣A為上三角矩陣。證實(shí)采納反證法。

假設(shè)此時(shí)的鄰接矩陣不是上三角矩陣，那么，存在下標(biāo)i和j（i>j），使得A[i][j]不等于零，即圖中存在從vi到vj的一條有向邊。由拓?fù)湫蛄械亩x可知，在隨意拓?fù)湫蛄兄校瑅i的位置一定在vj之前，而在上述拓?fù)湫蛄衯0v1v2…vn-1中，因?yàn)閕>j，即vi的位置在vj之后，導(dǎo)致沖突。因此命題正確。

12.算法設(shè)計(jì)

⑴設(shè)計(jì)算法，將一個(gè)無(wú)向圖的鄰接矩陣轉(zhuǎn)換為鄰接表。

【解答】先設(shè)置一個(gè)空的鄰接表，然后在鄰接矩陣上查找值不為零的元素，找到后在鄰接表的對(duì)應(yīng)單鏈表中插入相應(yīng)的邊表結(jié)點(diǎn)。

鄰接矩陣存儲(chǔ)結(jié)構(gòu)定義如下：

constintMaxSize=10;

template

structAdjMatrix{

Tvertex[MaxSize];

6.2.1

6C在一個(gè)具有n個(gè)頂點(diǎn)的有向徹低圖中包含有（）條邊：

An(n-1)/2

Bn(n-1)

Cn(n+1)/2

Dn2

【解答】B

6．n個(gè)頂點(diǎn)的連通圖用鄰接矩陣表示時(shí)，該矩陣至少有（）個(gè)非零元素。

【解答】2(n-1)

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

【解答】1000

8．一個(gè)具有n個(gè)頂點(diǎn)k條邊的無(wú)向圖是一個(gè)森林（n>k），則該森林中必有（）棵樹(shù)。

Ak

Bn

Cn-k

D1

【解答】C

9．用深度優(yōu)先遍歷辦法遍歷一個(gè)有向無(wú)環(huán)圖，并在深度優(yōu)先遍歷算法中按退棧次序打印出相應(yīng)的頂點(diǎn)，則輸出的頂點(diǎn)序列是（）。

A逆拓?fù)溆行?/p>

B拓?fù)溆行?/p>

C無(wú)序

D深度優(yōu)先遍歷序列

【解答】A

10.關(guān)鍵路徑是AOE網(wǎng)中（）。

A從源點(diǎn)到盡頭的最長(zhǎng)路徑B從源點(diǎn)到盡頭的最長(zhǎng)路徑

C最長(zhǎng)的回路

D最短的回路

【解答】A

11.已知無(wú)向圖G的鄰接表如圖6-10所示，分離寫(xiě)出從頂點(diǎn)1動(dòng)身的深度遍歷和廣度遍歷序列，并畫(huà)出相應(yīng)的生成樹(shù)。

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

對(duì)應(yīng)的生成樹(shù)為：

廣度優(yōu)先遍歷序列為：1，2，4，3，5，6

對(duì)應(yīng)的生成樹(shù)為：

12.已知已個(gè)AOV網(wǎng)如圖6-11所示，寫(xiě)出全部拓?fù)湫蛄小?/p>

【解答】拓?fù)湫蛄袨椋簐0v1v5v2v3v6v4、v0v1v5v2v6v3v4、v0v1v5v6v2v3v4。

第