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

第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ù)組中得下標)表示;鏈接存儲結(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就是算法得準確定義。⑷下面()不就是算法所必須具備得特性。

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,E3、判斷題⑴算法得時間復(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)就是唯一得。

【解答】錯?；静僮鞯脤崿F(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ù)類型定義如下:

ADTinteger

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

功能:求當前整數(shù)與輸入整數(shù)得模,即正得余數(shù)

輸出:若整數(shù)b為零,則拋出除零異常,否則輸出取模得結(jié)果

后置條件:整數(shù)a得值發(fā)生改變

Equal

前置條件:存在一個整數(shù)a

輸入:一個整數(shù)b

功能:判斷整數(shù)a與輸入得整數(shù)b就是否相等

輸出:若相等返回1,否則返回0

后置條件:整數(shù)a得值不發(fā)生改變

endADT7、求多項式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++;

}

returncount;

【解答】Ｏ(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;deleteq;

【分析】操作示意圖如圖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ù)雜度就是()。

AO(1)BO(n)CO(n2)DO(nlog2n)

【解答】B

【分析】首先應(yīng)順序查找新結(jié)點在單鏈表中得位置。⑼對于n個元素組成得線性表,建立一個有序單鏈表得時間復(fù)雜度就是()。

AO(1)BO(n)CO(n2)DO(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í)行()操作。

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é)點,所以,不用考慮修改指針得順序。⑿在循環(huán)雙鏈表得p所指結(jié)點后插入s所指結(jié)點得操作就是()。

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

【分析】在鏈表中,對指針得修改必須保持線性表得邏輯關(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é)點?！窘獯稹繌念^到尾掃描單鏈表,若當前結(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,則第一個元素得地址就是()。

A108B180C176D112

【解答】D2.在長度為n得線性表中查找值為x得數(shù)據(jù)元素得時間復(fù)雜度為:()。

AO(0)BO(1)CO(n)DO(n2)

【解答】C3.在一個長度為n得順序表得第i(1≤i≤n+1)個元素之前插入一個元素,需向后移動()個元素,刪除第i(1≤i≤n)個元素時,需向前移動()個元素。

【解答】n-i+1,n-i4.在單鏈表中,除了頭結(jié)點以外,任一結(jié)點得存儲位置由()指示。

【解答】其前趨結(jié)點得指針域5.當線性表采用順序存儲結(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插入到線性表得適當位置上,以保持線性表得有序性,并且分析算法得時間復(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)就是();其判定?？盏脳l件分別就是(),判定棧滿得條件分別就是()。

【解答】順序存儲結(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不確定Bn-iCn-i-1Dn-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)該就是()。

A6B4C3D2

【解答】C

【分析】由于隊列具有先進先出性,所以,此題中隊列形同虛設(shè),即出棧得順序也就是e2、e4、e3、e6、e5、e1。⑶一個棧得入棧序列就是1,2,3,4,5,則棧得不可能得輸出序列就是()。

A54321B45321C43512D12345

【解答】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,則隊列得輸出順序就是()。

A4321B1234C1432D3241

【解答】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得存儲空間,對任何一個棧只有當S[n]全滿時才不能進行進棧操作。為這兩個棧分配空間得最佳方案就是()。

AS1得棧底位置為0,S2得棧底位置為n-1

BS1得棧底位置為0,S2得棧底位置為n/2

CS1得棧底位置為0,S2得棧底位置為n

DS1得棧底位置為0,S2得棧底位置為1

【解答】A

【分析】兩棧共享空間首先兩個棧就是相向增長得,棧底應(yīng)該分別指向兩個棧中得第一個元素得位置,并注意C++中得數(shù)組下標就是從0開始得。⑼設(shè)有兩個串p與q,求q在p中首次出現(xiàn)得位置得運算稱作()。

A連接B模式匹配C求子串D求串長

【解答】B3、判斷題⑴有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個存儲單元空閑,其下標分別為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)鏈表得頭部進行,相當于刪除開始結(jié)點,而入隊操作就是在循環(huán)鏈表得尾部進行,相當于在終端結(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個單元得順序棧中,假定以地址低端(即下標為0得單元)作為棧底,以top作為棧頂指針,當出棧時,top得變化為()。

A不變Btop=0;Ctop=top-1;Dtop=top+1;

【解答】C2.一個棧得入棧序列就是a,b,c,d,e,則棧得不可能得出棧序列就是()。

AedcbaBcdebaCdebcaDabcde

【解答】C3.從棧頂指針為top得鏈棧中刪除一個結(jié)點,用x保存被刪除結(jié)點得值,則執(zhí)行()。

Ax=top;top=top->next;Bx=top->data;

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

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

【解答】PA321,P3A21,P32A1,P321A,AP3215、設(shè)S="I_am_a_teacther",其長度為()。

【解答】15第4章廣義線性表——多維數(shù)組與廣義表課后習(xí)題講解1、填空⑴數(shù)組通常只有兩種運算:()與(),這決定了數(shù)組通常采用()結(jié)構(gòu)來實現(xiàn)存儲。

【解答】存取,修改,順序存儲

【分析】數(shù)組就是一個具有固定格式與數(shù)量得數(shù)據(jù)集合,在數(shù)組上一般不能做插入、刪除元素得操作。除了初始化與銷毀之外,在數(shù)組中通常只有存取與修改兩種操作。⑵二維數(shù)組A中行下標從10到20,列下標從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))得長度就是(),深度就是(),表頭就是(),表尾就是()。

【解答】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個字符組成得串,行下標得范圍從0~8,列下標得范圍就是從0~9,則存放A至少需要()個字節(jié),A得第8列與第5行共占()個字節(jié),若A按行優(yōu)先方式存儲,元素A[8][5]得起始地址與當A按列優(yōu)先方式存儲時得()元素得起始地址一致。

A90B180C240D540E108F114G54

HA[8][5]IA[3][10]JA[5][8]KA[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數(shù)組就是一種線性結(jié)構(gòu)B數(shù)組就是一種定長得線性結(jié)構(gòu)

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

D數(shù)組得基本操作有存取、修改、檢索與排序等,沒有插入與刪除操

【解答】C

【分析】數(shù)組屬于廣義線性表,數(shù)組被創(chuàng)建以后,其維數(shù)與每維中得元素個數(shù)就是確定得,所以,數(shù)組通常沒有插入與刪除操作。⑷對特殊矩陣采用壓縮存儲得目得主要就是為了()

A表達變得簡單B對矩陣元素得存取變得簡單

C去掉矩陣中得多余元素D減少不必要得存儲空間

【解答】D

【分析】在特殊矩陣中,有很多值相同得元素并且她們得分布有規(guī)律,沒有必要為值相同得元素重復(fù)存儲。⑸下面()不屬于特殊矩陣。

A對角矩陣B三角矩陣C稀疏矩陣D對稱矩陣

【解答】C⑹若廣義表A滿足Head(A)=Tail(A),則A為()

A()B(())C((),())D((),(),())

【解答】B⑺下面得說法中,不正確得就是()

A廣義表就是一種多層次得結(jié)構(gòu)B廣義表就是一種非線性結(jié)構(gòu)

C廣義表就是一種共享結(jié)構(gòu)D廣義表就是一種遞歸

【解答】B

【分析】從各層元素各自具有得線性關(guān)系講,廣義表屬于線性結(jié)構(gòu)。⑻下面得說法中,不正確得就是()

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

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

C稀疏矩陣中值為零得元素較多,因此可以采用三元組表方法存儲。

D稀疏矩陣中大量值為零得元素分布有規(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所示。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)。當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é),行下標從0到7,列下標從0到9,從首地址d開始存儲。若按行優(yōu)先方式存儲,元素M[7][5]得起始地址為(),若按列優(yōu)先方式存儲,元素M[7][5]得起始地址為()。

【解答】d+22,d+1412.一個n×n得對稱矩陣,按行優(yōu)先或列優(yōu)先進行壓縮存儲,則其存儲容量為()。

【解答】n(n+1)/23.設(shè)n行n列得下三角矩陣A(行列下標均從1開始)已壓縮到一維數(shù)組S[1]~S[n(n+1)/2]中,若按行優(yōu)先存儲,則A[i][j]在數(shù)組S中得存儲位置就是()。

【解答】i×(i-1)/2+j4.已知廣義表LS=(a,(b,c),(d,e,a)),運用Head函數(shù)與Tail函數(shù)取出LS中原子d得運算就是()。

【解答】Head(Head(Tail(Tail(LS))))5.廣義表(a,b,(c,(d)))得表尾就是()。

A(d)B(c,(d))Cb,(c,(d))D(b,(c,(d)))

【解答】D6.設(shè)有三對角矩陣An×n(行、列下標均從0開始),將其三條對角線上得元素逐行存于數(shù)組B[3n-2]中,使得B[k]=aij求:

⑴用i,j表示k得下標變換公式;

⑵用k表示i,j得下標變換公式。

【解答】⑴要求i,j表示k得下標變換公式,就就是要求在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就是當前非零元素得個數(shù),整除即為其所在行號,取余表示當前行中第幾個非零元素,加上前面零元素所在列數(shù)就就是當前列號,即: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得度就是()。

A1B2C3D4

【解答】D

⑵設(shè)二叉樹有n個結(jié)點,則其深度為()。

An-1BnC+1D不能確定

【解答】D

【分析】此題并沒有指明就是完全二叉樹,則其深度最多就是n,最少就是+1。

⑶二叉樹得前序序列與后序序列正好相反,則該二叉樹一定就是()得二叉樹。

A空或只有一個結(jié)點B高度等于其結(jié)點數(shù)

C任一結(jié)點無左孩子D任一結(jié)點無右孩子

【解答】B

【分析】此題注意就是序列正好相反,則左斜樹與右斜樹均滿足條件。

⑷線索二叉樹中某結(jié)點R沒有左孩子得充要條件就是()。

AR、lchild=NULLBR、ltag=0CR、ltag=1DR、rchild=NULL

【解答】C

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

⑸深度為k得完全二叉樹至少有()個結(jié)點,至多有()個結(jié)點,具有n個結(jié)點得完全二叉樹按層序從1開始編號,則編號最小得葉子得序號就是()。

A2k-2+1B2k-1C2k-1D2k–1-1

E2k+1F2k+1-1G

⑹一個高度為h得滿二叉樹共有n個結(jié)點,其中有m個葉子結(jié)點,則有()成立。

An=h+mBh+m=2nCm=h-1Dn=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é)點。

An1-1Bn1Cn1+n2+n3Dn2+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)一種技巧,沒有什么實際意義

【解答】B3、判斷題

⑴在線索二叉樹中,任一結(jié)點均有指向其前趨與后繼得線索。

【解答】錯。某結(jié)點就是否有前驅(qū)或后繼得線索,取決于該結(jié)點得標志域就是否為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。

當n=1時,前序遍歷序列為a1,中序遍歷序列為b1,二叉樹只有一個根結(jié)點,所以,a1=b1,可以唯一確定該二叉樹;

假設(shè)當n<=k時,前序遍歷序列a1a2a3…ak與中序遍歷序列b1b2b3…bk可唯一確定該二叉樹,下面證明當n=k+1時,前序遍歷序列a1a2a3…akak+1與中序遍歷序列b1b2b3…bkbk+1可唯一確定一棵二叉樹。

在前序遍歷序列中第一個訪問得一定就是根結(jié)點,即二叉樹得根結(jié)點就是a1,在中序遍歷序列中查找值為a1得結(jié)點,假設(shè)為bi,則a1=bi且b1b2…bi-1就是對根結(jié)點a1得左子樹進行中序遍歷得結(jié)果,前序遍歷序列a2a6.已知一棵度為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

=1209.已知某字符串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è)計算法求二叉樹得深度。

【解答】當二叉樹為空時,深度為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

structTNode

{

Tdata;

TNode*firstchild,*rightsib;

};

具體算法如下:學(xué)習(xí)自測及答案

1.前序遍歷與中序遍歷結(jié)果相同得二叉樹就是()。

A根結(jié)點無左孩子得二叉樹B根結(jié)點無右孩子得二叉樹

C所有結(jié)點只有左子樹得二叉樹D所有結(jié)點只有右子樹得二叉樹

【解答】D1.前序遍歷與中序遍歷結(jié)果相同得二叉樹就是()。A根結(jié)點無左孩子得二叉樹B根結(jié)點無右孩子得二叉樹C所有結(jié)點只有左子樹得二叉樹D所有結(jié)點只有右子樹得二叉樹【解答】D

2.由權(quán)值為{3,8,6,2,5}得葉子結(jié)點生成一棵哈夫曼樹,其帶權(quán)路徑長度為()。

A24B48C53D72

【解答】C

3.用順序存儲得方法將完全二叉樹中得所有結(jié)點逐層存放在數(shù)組A[1]~A[n]中,結(jié)點A[i]若有左子樹,則左子樹得根結(jié)點就是()。

AA[2i-1]BA[2i+1]CA[i/2]DA[2i]

【解答】D

4.對任何一棵二叉樹T,如果其終端結(jié)點得個數(shù)為n0,度為2得結(jié)點個數(shù)為n2,則()。

An0=n2-1Bn0=n2Cn0=n2+1D沒有規(guī)律

【解答】C

5.一棵滿二叉樹中共有n個結(jié)點,其中有m個葉子結(jié)點,深度為h,則()。

An=h+mBh+m=2nCm=h-1Dn=2h-1

【解答】D

6.對于完全二叉樹中得任一結(jié)點,若其右分支下得子孫得最大層次為h,則其左分支下得子孫得最大層次為()。

AhBh+1Ch或h+1D任意

【解答】C

7.假定一棵度為3得樹中結(jié)點數(shù)為50,則其最小高度應(yīng)為。

A3B4C5D6

【解答】C

8.在線索二叉樹中,一個結(jié)點就是葉子結(jié)點得充要條件為()。

A左線索標志為0,右線索標志為1B左線索標志為1,右線索標志為0

C左、右線索標志均為0D左、右線索標志均為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)換為樹或森林?！窘獯稹繄D5-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è)兩個標志變量BJ與CM,其中BJ表示已掃描過得結(jié)點就是否均有左右孩子,CM存放局部判斷結(jié)果及最后得結(jié)果。

具體算法如下:第6章圖課后習(xí)題講解1、填空題⑴設(shè)無向圖G中頂點數(shù)為n,則圖G至少有()條邊,至多有()條邊;若G為有向圖,則至少有()條邊,至多有()條邊。

【解答】0,n(n-1)/2,0,n(n-1)

【分析】圖得頂點集合就是有窮非空得,而邊集可以就是空集;邊數(shù)達到最多得圖稱為完全圖,在完全圖中,任意兩個頂點之間都存在邊。⑵任何連通圖得連通分量只有一個,即就是()。

【解答】其自身⑶圖得存儲結(jié)構(gòu)主要有兩種,分別就是()與()。

【解答】鄰接矩陣,鄰接表

【分析】這就是最常用得兩種存儲結(jié)構(gòu),此外,還有十字鏈表、鄰接多重表、邊集數(shù)組等。⑷已知無向圖G得頂點數(shù)為n,邊數(shù)為e,其鄰接表表示得空間復(fù)雜度為()。

【解答】Ｏ(n+e)

【分析】在無向圖得鄰接表中,頂點表有n個結(jié)點,邊表有2e個結(jié)點,共有n+2e個結(jié)點,其空間復(fù)雜度為Ｏ(n+2e)=Ｏ(n+e)。⑸已知一個有向圖得鄰接矩陣表示,計算第j個頂點得入度得方法就是()。

【解答】求第j列得所有元素之與⑹有向圖G用鄰接矩陣A[n][n]存儲,其第i行得所有元素之與等于頂點i得()。

【解答】出度⑺圖得深度優(yōu)先遍歷類似于樹得()遍歷,它所用到得數(shù)據(jù)結(jié)構(gòu)就是();圖得廣度優(yōu)先遍歷類似于樹得()遍歷,它所用到得數(shù)據(jù)結(jié)構(gòu)就是()。

【解答】前序,棧,層序,隊列⑻對于含有n個頂點e條邊得連通圖,利用Prim算法求最小生成樹得時間復(fù)雜度為(),利用Kruskal算法求最小生成樹得時間復(fù)雜度為()。

【解答】Ｏ(n2),Ｏ(elog2e)

【分析】Prim算法采用鄰接矩陣做存儲結(jié)構(gòu),適合于求稠密圖得最小生成樹;Kruskal算法采用邊集數(shù)組做存儲結(jié)構(gòu),適合于求稀疏圖得最小生成樹。⑼如果一個有向圖不存在(),則該圖得全部頂點可以排列成一個拓撲序列。

【解答】回路⑽在一個有向圖中,若存在弧、、,則在其拓撲序列中,頂點vi,vj,vk得相對次序為()。

【解答】vi,vj,vk

【分析】對由頂點vi,vj,vk組成得圖進行拓撲排序。2、選擇題⑴在一個無向圖中,所有頂點得度數(shù)之與等于所有邊數(shù)得()倍。

A1/2B1C2D4

【解答】C

【分析】設(shè)無向圖中含有n個頂點e條邊,則。⑵n個頂點得強連通圖至少有()條邊,其形狀就是()。

AnBn+1Cn-1Dn×(n-1)

E無回路F有回路G環(huán)狀H樹狀

【解答】A,G⑶含n個頂點得連通圖中得任意一條簡單路徑,其長度不可能超過()。

A1Bn/2Cn-1Dn

【解答】C

【分析】若超過n-1,則路徑中必存在重復(fù)得頂點。⑷對于一個具有n個頂點得無向圖,若采用鄰接矩陣存儲,則該矩陣得大小就是()。

AnB(n-1)2Cn-1Dn2

【解答】D⑸圖得生成樹(),n個頂點得生成樹有()條邊。

A唯一B不唯一C唯一性不能確定

DnEn+1Fn-1

【解答】C,F⑹設(shè)無向圖G=(V,E)與G'=(V',E'),如果G'就是G得生成樹,則下面得說法中錯誤得就是()。

AG'為G得子圖BG'為G得連通分量

CG'為G得極小連通子圖且V=V'DG'就是G得一個無環(huán)子圖

【解答】B

【分析】連通分量就是無向圖得極大連通子圖,其中極大得含義就是將依附于連通分量中頂點得所有邊都加上,所以,連通分量中可能存在回路。⑺G就是一個非連通無向圖,共有28條邊,則該圖至少有()個頂點。

A6B7C8D9

【解答】D

【分析】n個頂點得無向圖中,邊數(shù)e≤n(n-1)/2,將e=28代入,有n≥8,現(xiàn)已知無向圖非連通,則n=9。⑻最小生成樹指得就是()。

A由連通網(wǎng)所得到得邊數(shù)最少得生成樹

B由連通網(wǎng)所得到得頂點數(shù)相對較少得生成樹

C連通網(wǎng)中所有生成樹中權(quán)值之與為最小得生成樹

D連通網(wǎng)得極小連通子圖⑼判定一個有向圖就是否存在回路除了可以利用拓撲排序方法外,還可以用()。

A求關(guān)鍵路徑得方法B求最短路徑得方法

C廣度優(yōu)先遍歷算法D深度優(yōu)先遍歷算法

【解答】D

【分析】當有向圖中無回路時,從某頂點出發(fā)進行深度優(yōu)先遍歷時,出棧得順序(退出DFSTraverse算法)即為逆向得拓撲序列。⑽下面關(guān)于工程計劃得AOE網(wǎng)得敘述中,不正確得就是()?br/>A關(guān)鍵活動不按期完成就會影響整個工程得完成時間

B任何一個關(guān)鍵活動提前完成,那么整個工程將會提前完成

C所有得關(guān)鍵活動都提前完成,那么整個工程將會提前完成

D某些關(guān)鍵活動若提前完成,那么整個工程將會提前完

【解答】B

【分析】AOE網(wǎng)中得關(guān)鍵路徑可能不止一條,如果某一個關(guān)鍵活動提前完成,還不能提前整個工程,而必須同時提高在幾條關(guān)鍵路徑上得關(guān)鍵活動。3、判斷題⑴一個有向圖得鄰接表與逆鄰接表中得結(jié)點個數(shù)一定相等。

【解答】對。鄰接表與逆鄰接表得區(qū)別僅在于出邊與入邊,邊表中得結(jié)點個數(shù)都等于有向圖中邊得個數(shù)。⑵用鄰接矩陣存儲圖,所占用得存儲空間大小只與圖中頂點個數(shù)有關(guān),而與圖得邊數(shù)無關(guān)。

【解答】對。鄰接矩陣得空間復(fù)雜度為Ｏ(n2),與邊得個數(shù)無關(guān)。⑶圖G得生成樹就是該圖得一個極小連通子圖

【解答】錯。必須包含全部頂點。⑷無向圖得鄰接矩陣一定就是對稱得,有向圖得鄰接矩陣一定就是不對稱得

【解答】錯。有向圖得鄰接矩陣不一定對稱,例如有向完全圖得鄰接矩陣就就是對稱得。⑸對任意一個圖,從某頂點出發(fā)進行一次深度優(yōu)先或廣度優(yōu)先遍歷,可訪問圖得所有頂點。

【解答】錯。只