數(shù)據(jù)結(jié)構(gòu),算法與應(yīng)用(C語言學(xué)習(xí)知識描述)習(xí)題集標(biāo)準(zhǔn)參考答案

第1章概論

1.數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)類型的含義分別是什么？

數(shù)據(jù)：對客觀事物的符號表示，在計算機(jī)科學(xué)中是指所有能輸入到計算機(jī)中并由計算機(jī)

程序處理的符號的總稱。

數(shù)據(jù)元素：數(shù)據(jù)的基本單位，在計算機(jī)程序中通常作為一個整體考慮。

數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)元素之間的關(guān)系+運(yùn)算，是以數(shù)據(jù)為成員的結(jié)構(gòu)，是帶結(jié)構(gòu)的數(shù)據(jù)元素

的集合，數(shù)據(jù)元素之間存在著一種或多種特定的關(guān)系。

數(shù)據(jù)類型:數(shù)據(jù)類型是用來區(qū)分不同的數(shù)據(jù)；由于數(shù)據(jù)在存儲時所需要的容量各不相同，

不同的數(shù)據(jù)就必須要分配不同大小的內(nèi)存空間來存儲，所有就要將數(shù)據(jù)劃分成不同的數(shù)據(jù)類

型。數(shù)據(jù)類型包含取值范圍和基本運(yùn)算等概念。

2.什么是數(shù)據(jù)的邏輯結(jié)構(gòu)？什么是數(shù)據(jù)的物理結(jié)構(gòu)？數(shù)據(jù)的邏輯結(jié)構(gòu)與物理結(jié)構(gòu)的區(qū)別和

聯(lián)系是什么？

邏輯結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)定義了數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)元素之間的相互邏輯關(guān)系。數(shù)據(jù)的邏

輯結(jié)構(gòu)包含下面兩個方面的信息：

①數(shù)據(jù)元素的信息；

②各數(shù)據(jù)元素之間的關(guān)系。

物理結(jié)構(gòu)：也叫儲存結(jié)構(gòu)，是指邏輯結(jié)構(gòu)的存儲表示，即數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)存

儲空間中的存放形式，包括結(jié)點(diǎn)的數(shù)據(jù)和結(jié)點(diǎn)間關(guān)系的存儲表示。

數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)是密不可分的，一個操作算法的設(shè)計取決于所選定的邏輯結(jié)

構(gòu)，而算法的實(shí)現(xiàn)依賴于所采與的存儲結(jié)構(gòu)。采用不同的存儲結(jié)構(gòu)，其數(shù)據(jù)處理的效率是不

同的。因此，在進(jìn)行數(shù)據(jù)處理時，針對不同問題，選擇合理的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)非常重要。

3.數(shù)據(jù)結(jié)構(gòu)的主要操作包括哪些？

對于各種數(shù)據(jù)結(jié)構(gòu)而言，他們在基本操作上是相似的，最常用的操作有：

?創(chuàng)建：建立一個數(shù)據(jù)結(jié)構(gòu)；

?清除：清除一個數(shù)據(jù)結(jié)構(gòu)；

?插入：在數(shù)據(jù)結(jié)構(gòu)中增加新的結(jié)點(diǎn)；

?刪除：把指定的結(jié)點(diǎn)從數(shù)據(jù)結(jié)構(gòu)中刪除；

?訪問：對數(shù)據(jù)結(jié)構(gòu)中的結(jié)點(diǎn)進(jìn)行訪問：

?更新：改變指定結(jié)點(diǎn)的值或改變指定的某些結(jié)點(diǎn)之間的關(guān)系；

?查找：在數(shù)據(jù)結(jié)構(gòu)中查找滿足一定條件的結(jié)點(diǎn)；

?排序：對數(shù)據(jù)結(jié)構(gòu)中各個結(jié)點(diǎn)按指定數(shù)據(jù)項的值，以升序或降序重新排列。

4.什么是抽象數(shù)據(jù)類型？如何定義抽象數(shù)據(jù)類型？

抽象數(shù)據(jù)類型（AbstractDataType簡稱ADT）是指一個數(shù)學(xué)模型以及定義在此數(shù)學(xué)

模型上的一組操作。ADT是與具體的物理存儲無關(guān)的數(shù)據(jù)類型，因此，不論ADT的內(nèi)部結(jié)

構(gòu)如何變化，只要其數(shù)據(jù)結(jié)構(gòu)的特性不變，都不影響其外部使用。

對抽象數(shù)據(jù)類型的描述一般用（D,R,P）三元組表示，抽象數(shù)據(jù)類型的定義格式為：

ADT＜抽象數(shù)據(jù)類型名〉

（

數(shù)據(jù)對象D：〈數(shù)據(jù)對象的定義〉

數(shù)據(jù)關(guān)系R：〈數(shù)據(jù)關(guān)系的定義〉

基本操作P：〈基本操作的定義,

}ADT＜抽象數(shù)據(jù)類型名〉

其中，D是數(shù)據(jù)對象，R是D上的關(guān)系集，P是對D的基本操作集。

數(shù)據(jù)對象和數(shù)據(jù)關(guān)系的定義用偽代碼來描述?；静僮鞯亩x格式為：

基本操作名（參數(shù)表）

初始條件：〈初始條件描述》

操作結(jié)果：V操作結(jié)果描述〉

初始條件說明操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件；操作結(jié)果說明操作完成后，

數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。

5.什么是算法？算法的基本特征是什么？

算法：是在有限的步驟內(nèi)解決數(shù)學(xué)問題的過程，是以一步接一步的方式來詳細(xì)描述計算

機(jī)如何將輸入轉(zhuǎn)化為所要求的輸出的過程，即算法是對計算機(jī)上執(zhí)行的計算過程的具體描

述。一個有效的算法必須滿足的五個重要特性：

①有窮性：算法必須能在有限的時間內(nèi)做完，即在任何情況下，算法必須能在執(zhí)行有

限個步驟之后終止，都不能陷入無窮循環(huán)中。

②確定性：算法中的每一個步驟，必須經(jīng)過明確的定義，并且能夠被計算機(jī)所理解和

執(zhí)行，而不能是抽象和模糊的概念，更不允許有二義性。

③輸入：算法有0個或多個輸入值，來描述算法開始前運(yùn)算對象的初始情況，這是算

法執(zhí)行的起點(diǎn)或是依據(jù)。0個輸入是指算法本身給出了運(yùn)算對象的初始條件。

④輸出：算法至少有1個或多個輸出值，反映對運(yùn)算對象的處理結(jié)果，沒有輸出的算

法沒有任何意義。

⑤可行性：算法中要做的運(yùn)算都是基本運(yùn)算，能夠被精確地進(jìn)行。即算法中執(zhí)行的任

何計算都可以被分解為基本的運(yùn)算步，每個基本的運(yùn)算步都可以在有限的時間內(nèi)完成。

6.什么是算法分析？算法分析主要考慮哪幾方面的內(nèi)容？

算法的研究與實(shí)際問題直接相關(guān)，用來解一個問題可以有很多不同的算法，他們之間的

效果可能會有很大差異。算法設(shè)計者最關(guān)心的就是什么是有效的算法，如何評價一個算法的

優(yōu)劣，如何從多種算法中選擇好的算法。除了要首先考慮算法的正確性外，還要分析和評價

算法的性能。分析和評價算法的性能主要要考慮以下兩個方面：

①時間代價：執(zhí)行算法所耗費(fèi)的時間。一個好的算法首先應(yīng)該比其他算法的運(yùn)行時間代

價要小。算法的時間代價的大小用算法的時間復(fù)雜度來度量。

②空間代價：執(zhí)行算法所耗費(fèi)的存儲空間，主要是輔助空間。算法運(yùn)行所需的空間消耗

是衡量算法優(yōu)劣的另一個重要因素。算法的空間代價的大小用算法的空間復(fù)雜度來度量。

7.分析下面算法的時間復(fù)雜度。

（1）答：時間復(fù)雜度為「

（2）時間復(fù)雜度：n

（3）時間復(fù)雜度：百

（4）時間復(fù)雜度：n2

（5）時間復(fù)雜度:0（log2n）

8.算法設(shè)計中的遞歸、窮舉、遞推和迭代等算法的基本思想是什么？

遞推法：是利用問題本身所具有的一種遞推關(guān)系求解問題的一種方法。它把問題求解分

成若干步，找出相鄰幾步的關(guān)系，從而達(dá)到求解問題的目的。具有如下性質(zhì)的問題可以采用

遞推法：當(dāng)?shù)玫絾栴}規(guī)模為i-1的解后，由問題的遞推性質(zhì)，能構(gòu)造出問題規(guī)模為i的解。

因此，程序可以從i=0或i=l出發(fā)，由已知i-1規(guī)模的解，通過遞推，獲得問題規(guī)模為i的

解，直至得到問題規(guī)模為n的解。

遞歸法：遞歸策略是利用函數(shù)直接或間接地調(diào)用自身來完成某個計算過程。能采用遞歸

描述的算法通常有這樣的特征：為求解規(guī)模為n的問題，設(shè)法將它分解成規(guī)模較小的問題，

然后從這些小問題的解方便地構(gòu)造出更大問題的解，并且這些規(guī)模較小的問題也能采用同樣

的分解和綜合方法，分解成規(guī)模更小的問題，并從這些更小問題的解構(gòu)造出較大規(guī)模問題的

解。

窮舉法：窮舉搜索法也稱窮舉法或搜索法是對可能是解的眾多候選解按某種順序進(jìn)行

逐一枚舉和檢驗，并從中找出那些符合要求的候選解作為問題的解。

迭代法：數(shù)值分析中通過從一個初始估計出發(fā)尋找一系列近似解來解決問題（一般是解

方程或者方程組）的過程，為實(shí)現(xiàn)這一過程所使用的方法統(tǒng)稱為迭代法。

9.算法設(shè)計中的分治策略、貪心策略、動態(tài)規(guī)劃策略、回溯策略以及分支定界策略的基本思

想是什么?

分治策略的基本思想是把一個規(guī)模為n的問題劃分為若干個規(guī)模較小、且與原問題相似

的子問題，然后分別求解這些子問題，最后把各子結(jié)果合并得到整個問題的解。分解的子問

題通常與原問題相似，所以可以遞歸地使用分治策略來求解。

貪心策略的基本思想是把一個整體最優(yōu)問題分解為一系列的最優(yōu)選擇問題，決策一旦做

出，就不能再更改。它是通過若干次的貪心選擇而得出最優(yōu)解（或較優(yōu)解）的一種解題策略。

動態(tài)規(guī)劃策略與貪心策略類似，將一個問題劃分為重復(fù)的子問題，通過對相同子問題的

求解來解決較大問題，即將一個問題的解決方案視為一系列決策的結(jié)果。不同的是，在貪心

策略中，每采用一次貪心準(zhǔn)則便做出一個不可撤回的決策，可能得不到問題的最優(yōu)解。而在

動態(tài)規(guī)劃中，處理要按照某種規(guī)則進(jìn)行選擇，還要考察每個最優(yōu)決策序列中是否包含一個最

優(yōu)子序列，目的是得到問題的最優(yōu)解。

回溯策略也叫試探法，它的基本思想是：在一些問題求解進(jìn)程中，先選擇某一種可能情

況向前探索，當(dāng)發(fā)現(xiàn)所選用的試探性操作不是最佳選擇，需退回一步，重新選擇繼續(xù)進(jìn)行試

探，直到找到問題的解或者證明問題無解。

分支定界策略也經(jīng)常被稱為分支限界策略，它的基本思想是:首先確定目標(biāo)值的上下界,

然后一邊搜索一邊剪掉空間樹的某些不可能產(chǎn)生最優(yōu)解的分支，提高搜索效率。

第二章線性表

1.具有什么特征的數(shù)據(jù)結(jié)構(gòu)被稱為線性表？

線性表是一種最常用、最簡單的典型線性數(shù)據(jù)結(jié)構(gòu)，應(yīng)用非常廣泛。線性表是由n(n?O)

個數(shù)據(jù)元素組成的一個有限序列，線性表中數(shù)據(jù)元素的個數(shù)n稱為線性表的長度。當(dāng)n=0

時，稱為空表。

對于非空線性表，數(shù)據(jù)元素之間存在一對一的關(guān)系，具體特性如下：

第一個數(shù)據(jù)元素沒有前驅(qū)；

最后一個數(shù)據(jù)元素沒有后繼外；

其他數(shù)據(jù)元素都是首尾相接、有且只有一個前驅(qū)和后繼。

2.如何實(shí)現(xiàn)線性表的順序存儲結(jié)構(gòu)？

把線性表的結(jié)點(diǎn)按邏輯順序依次存放在一組地址連續(xù)的存儲單元里就構(gòu)成了線性表的

順序存儲，采用順序存儲結(jié)構(gòu)的線性表簡稱順序表。線性表的順序存儲結(jié)構(gòu)有如下特點(diǎn)：

?線性表中所有元素所占的存儲空間是連續(xù)的；

?線性表的邏輯順序與物理順序一致；

?數(shù)組中的每一個元素的位置可以用公式來確定。假設(shè)線性表中的第一個數(shù)據(jù)元素的

存儲地址(指第一個字節(jié)的地址，即首地址)為LOC(ei),每一個數(shù)據(jù)元素占k個

字節(jié)，則線性表中第i個元素ei在計算機(jī)存儲空間中的存儲地址為：

LOC(ei)=LOC(ei)+(i-l)k

3.如何實(shí)現(xiàn)線性表的4種鏈?zhǔn)酱鎯Y(jié)構(gòu)？

數(shù)據(jù)結(jié)構(gòu)中的每一個數(shù)據(jù)元素對應(yīng)于一個存儲單元，這種存儲單元稱為存儲結(jié)點(diǎn)，簡稱

結(jié)點(diǎn)。每個結(jié)點(diǎn)分為兩部分：一部分用于存放數(shù)據(jù)元素的值，稱為數(shù)據(jù)域；另一部分是指針,

用于指向與該結(jié)點(diǎn)在邏輯上相連的其他結(jié)點(diǎn)，稱為指針域。對于線性表，指針域用于指向該

結(jié)點(diǎn)的前一個或后一個結(jié)點(diǎn)(即前驅(qū)結(jié)點(diǎn)或后繼結(jié)點(diǎn))。通過結(jié)點(diǎn)的指針域?qū)個結(jié)點(diǎn)按其

邏輯結(jié)構(gòu)連接在一起的數(shù)據(jù)存儲結(jié)構(gòu)，稱為鏈?zhǔn)酱鎯Y(jié)構(gòu)。

單向鏈表：在線性鏈表中，用一個專門的指針指向線性表中第一個結(jié)點(diǎn)，每一個結(jié)點(diǎn)的

指針都指向它的下一個邏輯結(jié)點(diǎn)，線性鏈表的最后一個結(jié)點(diǎn)的指針為空(用NULL或0表

示)，表示鏈表終止，這樣的線性鏈表稱為單向鏈表。下圖是單向鏈表示意圖。

線性表的單向鏈?zhǔn)酱鎯?/p>

循環(huán)鏈表:將單向鏈表最后一個結(jié)點(diǎn)的指針指向頭結(jié)點(diǎn)，這樣整個鏈表就構(gòu)成一個循環(huán),

這種鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為單向循環(huán)鏈表，簡稱循環(huán)鏈表。頭結(jié)點(diǎn)的指針域指向線性表的第一個

元素的結(jié)點(diǎn)；循環(huán)鏈表中最后一個結(jié)點(diǎn)的指針域不再是NULL,而是指向頭結(jié)點(diǎn)。只有頭結(jié)

點(diǎn)的循環(huán)鏈表稱為空循環(huán)鏈表。下圖是帶頭結(jié)點(diǎn)的非空循環(huán)鏈表和空循環(huán)鏈表示意圖。

（a）帶頭結(jié)點(diǎn)的非空循環(huán)鏈表（b）帶頭結(jié)點(diǎn)的空循環(huán)鏈

帶頭結(jié)點(diǎn)的循環(huán)鏈表

雙向鏈表：雙向鏈表的每個結(jié)點(diǎn)含有兩個指針域，一個指針指向其前驅(qū)結(jié)點(diǎn)；另一個指

針指向其后繼結(jié)點(diǎn)。雙向鏈表結(jié)點(diǎn)的結(jié)構(gòu)下圖（a）所示。

雙向循環(huán)鏈表：如果將雙向鏈表第一個結(jié)點(diǎn)的prev指針指向最后一個結(jié)點(diǎn)，將最后一

個結(jié)點(diǎn)的next指針與指向第一個結(jié)點(diǎn)，就構(gòu)成了雙向循環(huán)鏈表。下圖（b）和（c）是雙向

鏈表和雙向循環(huán)表的邏輯結(jié)構(gòu)示意圖。

（c）雙向循環(huán)鏈表

圖雙向鏈表結(jié)點(diǎn)結(jié)構(gòu)及雙向鏈表

4.順序表和線性鏈表分別有哪些優(yōu)點(diǎn)和缺點(diǎn)？

線性表的順序存儲與鏈?zhǔn)酱鎯Ρ容^

比較內(nèi)容順序存儲鏈?zhǔn)酱鎯?/p>

結(jié)點(diǎn)存儲空間少（不需要為表示結(jié)點(diǎn)的邏輯關(guān)系增多（需要增加指針域來表示結(jié)點(diǎn)之間

加開銷）的邏輯關(guān)系）

空間利用率低（采用數(shù)組，按表的最大長度靜態(tài)高（根據(jù)表的實(shí)際長度動態(tài)分配存儲

分配存儲空間）空間）

插入、刪除操作慢（需要大量移動元素）快（僅更改指針指向，不需要移動元

素）

訪問元素快（直接訪問）慢（通過指針移動才能訪問）

實(shí)現(xiàn)難易程度相對容易（基于數(shù)組操作，一般高級相對困難（基于指針操作）

語言都提供數(shù)組類型）

5.請列舉出一些線性表問題的實(shí)例。

①按員工號排序的員工基本情況表；

②奧運(yùn)會各項比賽日程；

③按學(xué)號記錄的學(xué)生的成績單；

等等。

6.對于順序表和單向鏈表，如何實(shí)現(xiàn)統(tǒng)計重復(fù)元素個數(shù)的操作？

在順序表中實(shí)現(xiàn)統(tǒng)計重復(fù)元素個數(shù)的操作：

在教材的【描述2-1】中，增加一個統(tǒng)計重復(fù)元素個數(shù)的成員函數(shù)：

intCount(constT&x);〃返回x出現(xiàn)的次數(shù)

在教材的【描述2-2】中，增加查找重復(fù)元素個數(shù)的成員函數(shù)的實(shí)現(xiàn):

〃實(shí)現(xiàn)統(tǒng)計重復(fù)元素個數(shù)

template<classT>

intLinearList<T>::Count(constT&x)

(

intcount=0;

for(inti=0;i<length;i++)

if(element[i]==x)

count++;

returncount;

)

在順序表中實(shí)現(xiàn)統(tǒng)計重復(fù)元素個數(shù)的操作：

在教材的【描述2-3】中，增加一個統(tǒng)計重復(fù)元素個數(shù)的成員函數(shù)：

intCount(constT&x);〃返回x出現(xiàn)的次數(shù)

在教材的【描述2-4】中，增加查找重復(fù)元素個數(shù)的成員函數(shù)的實(shí)現(xiàn):

〃實(shí)現(xiàn)統(tǒng)計重復(fù)元素個數(shù)

tempiate<classT>

intLinkList<T>::Count(constT&x)

{

LinkNode<T>*p=head->next;

intcount=0;

while(p!=NULL&&)

(

if(p->data==x)

count++;

p=p->next;

)

returncount;

第3章棧和隊列

i.具有什么特征的數(shù)據(jù)結(jié)構(gòu)被稱為棧和隊列？先進(jìn)后出、棧頂、棧底、先進(jìn)先出、隊頭、

隊尾的概念是什么？

棧：一種插入和刪除都只能在表的同一端進(jìn)行的線性表。

隊列：一種只允許在表的一端進(jìn)行插入操作，而在表的另一端進(jìn)行刪除操作的線性表。

先進(jìn)后出：元素是以由，e2,……en順序進(jìn)入數(shù)據(jù)結(jié)構(gòu)，以相反的順序即e。，e?i，……

由離開數(shù)據(jù)結(jié)構(gòu)。

棧頂：允許進(jìn)行插入和刪除操作的一端。

棧底：棧中與棧頂相對的另一端。

先進(jìn)先出：元素是以e”e2,……e”順序進(jìn)入數(shù)據(jù)結(jié)構(gòu)，以相同的順序即由，e2,……

e“離開數(shù)據(jù)結(jié)構(gòu)。

隊頭：允許刪除操作的一端。

隊尾：允許插入操作的一端。

2.簡述在順序棧的棧頂插入一個元素的操作過程。

在插入元素之前，首先要判斷棧是否為滿，如果棧滿，返回“沾滿無法插入”等錯誤提

示信息；否則讓top指針(指向當(dāng)前順序棧的棧頂)向后移動一個元素空間(元素大小)，

將要插入的元素放入top指針指向的內(nèi)存單元中。

3.一個棧的輸入序列為1、2、3,試給出全部可能的出棧序列。

可分為三種情況：

①、當(dāng)只有一個存儲空間時，只有一種出棧序列：1、2、3.

②、當(dāng)有兩個存儲空間時，有：1、2、3,2、1、3,2、3、1等3種出棧序列

③、當(dāng)存儲空間大于等于三個時，有：1、2、3,2、1、3,2、3、1,3、2、1

等4種出棧序列。

4.循環(huán)隊列的優(yōu)點(diǎn)是什么？在循環(huán)隊列中，僅依據(jù)頭尾指針相等，無法判斷隊列是“空''還

是“滿”。要解決這個問題，常用的兩種方法是什么？

循環(huán)隊列的優(yōu)點(diǎn)有兩點(diǎn)：一是可以避免發(fā)生順序隊列的“假上溢”現(xiàn)象；二是充分利用

隊列的存儲空間。

兩種判斷隊列是“空”還是“滿”的方法：一是約定少用一個元素空間；二是使用計數(shù)

器size記錄當(dāng)前隊列的實(shí)際長度。

5.簡述在鏈接棧中插入一個元素的操作過程。

鏈接棧的插入操作，先將待進(jìn)棧結(jié)點(diǎn)的指針域指向原來的棧頂結(jié)點(diǎn)，然后將棧頂指針top

修改指向該結(jié)點(diǎn)，使進(jìn)棧元素結(jié)點(diǎn)成為新的棧頂結(jié)點(diǎn)。

6.請列舉出一些可以用棧和隊列表示的實(shí)際問題。

所有''后進(jìn)先出”(LIFO,LastInFirstOut)的實(shí)際問題都可以用棧表示。棧的應(yīng)用主要

有：數(shù)制的轉(zhuǎn)換、括號的匹配檢查、行編輯處理、表達(dá)式求解、走迷宮以及高級語言中函數(shù)

的嵌套調(diào)用和遞歸的實(shí)現(xiàn)等。

所有“先進(jìn)先出''(FIFO,FirstInFirstOut)的實(shí)際問題都可以用隊列表示。如日常中的

排隊問題，隊列的應(yīng)用主要有:操作系統(tǒng)中各種資源請求排隊和各種緩沖區(qū)的先進(jìn)先出管理,

各種應(yīng)用系統(tǒng)中的事件規(guī)劃和事件模擬，樹的層次遍歷和圖的廣度優(yōu)先遍歷等。

第4章數(shù)組、字符串與廣義表

1.具有什么特征的數(shù)據(jù)結(jié)構(gòu)被稱為數(shù)組？

數(shù)組可以看成是形如(index,value)的數(shù)據(jù)集合，其中，index是元素的索引，表示數(shù)

據(jù)的邏輯位置，任意兩個數(shù)據(jù)的index都不相同；value表示數(shù)據(jù)元素的值。

2.設(shè)有二維數(shù)組a[5][6],每個元素占相鄰的8個字節(jié)，存儲器按字節(jié)編址，已知a的起始地

址是1000,試計算：

(1)數(shù)組a的最后一個元素起始地址；

1000+(30-1)*8=1232。

(2)按行序優(yōu)先時，元素a[3]⑸的起始地址：

1000+(3*6+5)*8=1184

(3)按行列序優(yōu)先時，元素a[4][3]的起始地址。

1000+(3*5+4)*8=1152

3.請簡述數(shù)組和矩陣的關(guān)系。

矩陣是指縱橫排列的二維數(shù)據(jù)表格。在高級語言編程中，通常用二維數(shù)組來描述一個矩

陣，從而可以對矩陣中的元素進(jìn)行隨機(jī)存取。但矩陣的索引通常從1而不是像數(shù)組那樣從0

開始，并且使用A(i,j)而不是A[i,j]的形式來引用矩陣中的元素。

4.矩陣有哪些基本運(yùn)算？

矩陣的操作包括轉(zhuǎn)置、加法、減法和乘法等。

5.稀疏矩陣的特點(diǎn)是什么？為什么要對稀疏矩陣采用壓縮存儲技術(shù)？

稀疏矩陣的特點(diǎn)是矩陣中非零元素個數(shù)遠(yuǎn)遠(yuǎn)少于矩陣零元素個數(shù)。

采用壓縮存儲技術(shù)主要是為了節(jié)省空間。

6.設(shè)A和B是稀疏矩陣，都以三元組作為存儲結(jié)構(gòu)，請寫出矩陣相加的算法?=人+1?。

//稀疏矩陣的三元組表示

Sinclude<iostream>

usingnamespacestd;

ftdefineM50

ttdefineN50

#defineMaxSize20

typedefintElemType;

typedefstruct

(

intr;

intc;

ElemTyped;

}TupNode;

typedefstruct

introws;

intcols;

intnums;

TupNodedata[MaxSize];

}TSMatrix;

intA[M][N],B[M][N];

〃建立三元組

voidCreateMat(intA[M][N],TSMatrix&t,introw,intcol)

(

inti,j;

t.rows=row;t.cols=col;t.nums=0;

for(i=0;i<M;i++)

(

for(j-0;j<N;j++)

(

if(A[i][j]!=O)

(

t.data[t.nums].r=i;t.data[t.nums].c=j;

t.data[t.nums].d=A[i][j];t.nums++;

)

)

}

}

〃矩陣相加

intMatAdd(TSMatrix&a,TSMatrix&b,TSMatrix&c)

(

inti=0,j=0,k=0;

ElemTypev;

if(a.rows!=b.rows||a.cols!=b.cols)return0;

c.rows=a.rows;c.cols=a.cols;

while(i<a.nums&&j<b.nums)

(

if(a.data[i].r==b.data[j].r)

(

if(a.data[i].c<b.data[j].c)

(

c.data[k],r=a.data[i].r;

c.data[k].c=a.data[i].c;

c.data[k].d=a.data[i].d;

i++;k++;

)

elseif(a.data[i].c>b.data[j].c)

(

c.data[k].r=b.data[j].r;

c.data[k].c=b.data[j].c;

c.data[k].d=b.data[j].d;

j++；k++;

)

else

v=a.data[i].d+b.data[j].d;

if(v!=0)

(

c.data[k]?r=a.data[i].r;

c.data[k].c=a.data[i].c;

c.data[k].d=v;

k++;

)

i++；j++；

)

)

elseif(a.data[i].r<b.data[j].r)

(

c.data[k].r=a.data[i].r;

c.data[k].c=a.data[i].c;

c.data[k].d=a.data[i].d;

i++;k++;

)

else

(

c.data[k].r=b.data[j].r;

c.data[k].c=b.data[j].c;

c.data[k].d=b.data[j].d;

j++；k++;

)

}

if(i=a.nums)

while(j<b.nums)

(

c.data[k].r=b.data[j].r;

c.data[k].c=b.data[j].c;

c.data[k].d=b.data[j].d;

j++；k++;

)

if(j==b.nums)

while(i<a.nums)

(

c.data[k].r=a.data[i].r;

c.data[k].c=a.data[i].c;

c.data[k].d=a.data[i].d;

i++;k++;

)

c.nums=k;

return1;

)

〃輸出三元組

voidDispMat(TSMatrixt)

(

inti;

if(t.nums<=0)

(

cout<〈〃此矩陣所有元素都為〃<<endl;

return;

)

cout<<t.rows?，\tf<<t.cols<<，\V?t.nums?endl;

cout<<，z-----------------"<<endl;

for(i=0;i<t.nums;i++)

cout<<t.data[i].r?*\t*?t.data[i].c?)\tf?t.data[i].d?endl?endl;

}

〃主函數(shù)

intmain()

(

introw,col,i,j;

TSMatrixa,b,c;

cout<<〃請輸入矩陣的行、列數(shù)：\n〃；

cin?row>>col;

cout*〃請輸入矩陣A的元素：\n〃；

for(i=0;i<row;i++)

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

cin?A[i][j];

cout<<〃請輸入矩陣B的元素：\n〃；

for(i=0;i<row;i++)

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

cin?B[i][j];

CreateMat(A,a,row,col);

CreateMat(B,b,row,col);

cout*〃矩陣A的三元組表示為：\n〃；

DispMat(a);

cout<<〃矩陣B的三元組表示為：\n〃；

DispMat(b);

if(MatAdd(a,b,c))

(

cout<<〃矩陣A、B相加后得到的三元組表示為：\n〃；

DispMat(c);

)

return0;

7.簡述字符串與一維字符型數(shù)組的區(qū)別與聯(lián)系。

字符串簡稱串，它是一種以字符為元素的特殊線性表。字符串可以看成是以字符為元素

的一維數(shù)組。具體實(shí)現(xiàn)時，在C/C++中的字符串使用為字符型數(shù)組來表示。為了便于確定字

符串的結(jié)尾，在字符型數(shù)組中使用\0(就是0)作為字符串的截止符。

8.列舉一些需要進(jìn)行字符串模式匹配的應(yīng)用場景。

例如，在文本編輯中經(jīng)常要查找某一特定單詞或者一段話在整篇文章中出現(xiàn)的位置，按

照姓名查找某個學(xué)生、員工、居民。有效的模式匹配能極大地提高文本編輯程序的能力。

9.列舉幾個字符串的其他操作。

求字符串中某個子串出現(xiàn)的次數(shù)，刪除滿足條件的子串，字符串字符移位等。

10.什么是廣義表？廣義表與線性表的區(qū)別是什么？

廣義表又稱列表，是由n(n20)個元素組成的有窮序列：GL=(e”e2,……en),但與

線性表不同的是，廣義表中的元素允許以不同的形式出現(xiàn)：它可以是一個原子(邏輯上不能

再分解的元素)，也可以是另一個廣義表。

11.一個廣義表是(a,(a,b,c),d,e,(m,n),(w,(i,j),x)),請問該廣義表的長度、

深度分別是多少？請畫出該廣義表的單鏈表存儲結(jié)構(gòu)示意圖。

該廣義表的深度是3,長度是6。

該廣義表的單鏈表存儲結(jié)構(gòu)示意圖如下：

12.請列舉出一些可以歸納成數(shù)組、矩陣、字符串和廣義表數(shù)據(jù)結(jié)構(gòu)的實(shí)際問題。

線性表的順序存儲、學(xué)生編號和姓名的問題、各班級的學(xué)生編號和姓名的問題等，都可

以歸結(jié)為數(shù)組。

不同物品所需原材料的數(shù)量、不同產(chǎn)地原材料的價格、不同類型的住宅需要的物品數(shù)量

等，不同學(xué)生的計算機(jī)成績，不同職工的工資等都可以歸結(jié)為矩陣。

學(xué)生的姓名和學(xué)號、學(xué)?；蚋鲉挝坏拿Q、國家名稱、一篇文章、一個高級語言源程序

等，都可歸結(jié)為字符串。

應(yīng)用高斯消元法求解方程組可以歸結(jié)為廣義表。

第5章樹和二叉樹

i.請簡述樹、二叉樹、滿二叉樹和完全二叉樹的結(jié)構(gòu)特性。

樹：只有最頂層的結(jié)點(diǎn)沒有前驅(qū)，其余結(jié)點(diǎn)都有且只有一個前驅(qū)；一個結(jié)點(diǎn)可以沒有后

繼，也可以有一個或多個后繼。

二叉樹：一種特殊形態(tài)的樹，每個結(jié)點(diǎn)至多有兩個后繼。

滿二叉樹:一種特殊形態(tài)的二叉樹，除了最后一層的結(jié)點(diǎn)為葉子結(jié)點(diǎn)外其它結(jié)點(diǎn)都有左、

右兩棵子樹的二叉樹。

完全二叉樹：一種特殊形態(tài)的二叉樹，其結(jié)點(diǎn)與相同深度的滿二叉樹中的結(jié)點(diǎn)編號完全

一致，即對于深度為k的完全二叉樹，其前k-i層與深度為k的滿二叉樹的前k-1層完全一

樣，只是在第k層上有可能缺少右邊若干個結(jié)點(diǎn)。

2.請解釋結(jié)點(diǎn)的度、樹的度、結(jié)點(diǎn)的層、樹的深度、分支、路徑、路徑長度、樹的路徑長

度、葉子結(jié)點(diǎn)、分支結(jié)點(diǎn)、內(nèi)部結(jié)點(diǎn)、孩子、雙親、兄弟、堂兄弟、祖先、子孫、有序樹、

無序樹和森林等基本術(shù)語的含義。

結(jié)點(diǎn)的度和樹的度：一個結(jié)點(diǎn)的后繼的數(shù)目稱為該結(jié)點(diǎn)的度，樹中各結(jié)點(diǎn)度的最大值

稱為樹的度。

結(jié)點(diǎn)的層和樹的深度：樹的根結(jié)點(diǎn)所在的層為第1層，其余結(jié)點(diǎn)的層等于其前驅(qū)結(jié)點(diǎn)

的層加1,樹中各結(jié)點(diǎn)的層的最大值稱為樹的深度。

分支、路徑、路徑長度和樹的路徑長度：從一個結(jié)點(diǎn)到其后繼結(jié)點(diǎn)之間的連線稱為一

個分支，從一個結(jié)點(diǎn)X到另一個結(jié)點(diǎn)Y所經(jīng)歷的所有分支構(gòu)成結(jié)點(diǎn)X到結(jié)點(diǎn)Y的路徑，一

條路徑上的分支數(shù)目稱為路徑長度，從樹的根結(jié)點(diǎn)到其他各個結(jié)點(diǎn)的路徑長度之和稱為樹的

路徑長度。

葉子結(jié)點(diǎn)、分支結(jié)點(diǎn)和內(nèi)部結(jié)點(diǎn)：樹中度為0的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)（或終端結(jié)點(diǎn)），

度不為0的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)（或非終端結(jié)點(diǎn)），除根結(jié)點(diǎn)以外的分支結(jié)點(diǎn)也稱為內(nèi)部結(jié)點(diǎn)。

孩子和雙親：在樹中，一個結(jié)點(diǎn)的后繼結(jié)點(diǎn)稱為該結(jié)點(diǎn)的孩子，相應(yīng)地，一個結(jié)點(diǎn)的前

驅(qū)結(jié)點(diǎn)稱為該結(jié)點(diǎn)的雙親，即一個結(jié)點(diǎn)是其孩子結(jié)點(diǎn)的雙親、其雙親結(jié)點(diǎn)的孩子。

兄弟和堂兄弟：同一雙親的孩子結(jié)點(diǎn)之間互稱為兄弟，不同雙親但在同一層的結(jié)點(diǎn)之

間互稱為堂兄弟。

祖先和子孫：從樹的根結(jié)點(diǎn)到某一個結(jié)點(diǎn)X的路徑上經(jīng)歷的所有結(jié)點(diǎn)（包括根結(jié)點(diǎn)但

不包括結(jié)點(diǎn)X）稱為結(jié)點(diǎn)X的祖先，以某一結(jié)點(diǎn)X為根的子樹上的所有非根結(jié)點(diǎn)（即除結(jié)

點(diǎn)X外）稱為結(jié)點(diǎn)X的子孫。

有序樹和無序樹：對于樹中的任一結(jié)點(diǎn)，如果其各棵子樹的相對次序被用來表示數(shù)據(jù)

之間的關(guān)系，即交換子樹位置會改變樹所表示的內(nèi)容，則稱該樹為有序樹；否則稱為無序樹。

森林：m（m20）棵互不相交的樹的集合就構(gòu)成了森林。

3.請簡述二叉樹的五條基本性質(zhì)。

性質(zhì)1：在二叉樹的第i層上至多有22個結(jié)點(diǎn)（乏1）。

性質(zhì)2：深度為k的二叉樹至多有2〈1個結(jié)點(diǎn)。

性質(zhì)3：在二叉樹中，若度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）數(shù)為n°,度為2的結(jié)點(diǎn)數(shù)為血，

則no=ri2+l。

性質(zhì)4：具有n個結(jié)點(diǎn)的完全二叉樹其深度為Llog2nJ+l（其中Llog2nJ表示不大于log2n

的最大整數(shù)）。

性質(zhì)5：采用順序編號的完全二叉樹具有如下性質(zhì)：若一個分支結(jié)點(diǎn)的編號為i,則其

左子樹的根結(jié)點(diǎn)（即左孩子結(jié)點(diǎn)）編號為2*i，右子樹的根結(jié)點(diǎn)（即右孩子結(jié)點(diǎn)）編號為2*i+l；

反之，若一個非根結(jié)點(diǎn)的編號為i,則其雙親結(jié)點(diǎn)的編號為山2」（其中Li/2」表示不大于i/2

的最大整數(shù)）。

4.請簡述二叉樹的常用操作及各操作的含義。

創(chuàng)建一棵空二叉樹：創(chuàng)建一棵沒有任何結(jié)點(diǎn)的二叉樹。在順序表示中，根據(jù)樹的深度

為結(jié)點(diǎn)分配內(nèi)存；在二叉鏈表表示中，將指向根結(jié)點(diǎn)的指針賦值為NULL。

刪除一棵二叉樹：將二叉樹各結(jié)點(diǎn)所占據(jù)的內(nèi)存釋放。

清空二叉樹：將二叉樹的所有結(jié)點(diǎn)刪除，使之成為一棵空二叉樹。

以指定元素值創(chuàng)建根結(jié)點(diǎn)：創(chuàng)建根結(jié)點(diǎn)，并以指定值作為根結(jié)點(diǎn)的元素值。

將一個結(jié)點(diǎn)作為指定結(jié)點(diǎn)的左孩子插入：根據(jù)指定元素值生成一個新結(jié)點(diǎn)，并將其作

為指定結(jié)點(diǎn)的左孩子。

將一個結(jié)點(diǎn)作為指定結(jié)點(diǎn)的右孩子插入：根據(jù)指定元素值生成一個新結(jié)點(diǎn)，并將其作

為指定結(jié)點(diǎn)的右孩子。

先序遍歷二叉樹：也稱為先根遍歷，其訪問方式遞歸定義如下：對于一棵二叉樹，先

訪問其根結(jié)點(diǎn)，再訪問根結(jié)點(diǎn)的左、右子樹；對于左、右子樹中的結(jié)點(diǎn)仍然是按照先序遍歷

方式訪問，即先訪問根結(jié)點(diǎn)，再訪問根結(jié)點(diǎn)的左、右子樹。

中序遍歷二叉樹：也稱為中根遍歷，其訪問方式遞歸定義如下：對于一棵二叉樹，先

訪問根結(jié)點(diǎn)左子樹，再訪問根結(jié)點(diǎn)，最后訪問右子樹；對于左、右子樹中的結(jié)點(diǎn)仍然是按照

中序遍歷方式訪問。

后序遍歷二叉樹：也稱為后根遍歷，其訪問方式遞歸定義如下：對于一棵二叉樹，先

訪問根結(jié)點(diǎn)的左子樹，后訪問右子樹，最后訪問根結(jié)點(diǎn)；對于左、右子樹中的結(jié)點(diǎn)仍然是按

照后序遍歷方式訪問。

逐層遍歷二叉樹：從第1層開始依次對每層中的結(jié)點(diǎn)按照從左至右的順序進(jìn)行訪問。

獲取指定結(jié)點(diǎn)的雙親結(jié)點(diǎn)：根據(jù)指定結(jié)點(diǎn)獲取其雙親結(jié)點(diǎn)。在順序表示中，可以直接

根據(jù)指定結(jié)點(diǎn)的位置計算雙親結(jié)點(diǎn)的位置；在二叉鏈表表示中，則需要從根結(jié)點(diǎn)開始遍歷二

叉樹直至找到指定結(jié)點(diǎn)的雙親結(jié)點(diǎn)。

刪除以指定結(jié)點(diǎn)為根的子樹：將以指定結(jié)點(diǎn)為根結(jié)點(diǎn)的子樹上的所有結(jié)點(diǎn)（包括指定

結(jié)點(diǎn)）刪除。

按關(guān)鍵字查找結(jié)點(diǎn)：按照某種規(guī)則（先序、中序、后序或逐層）依次訪問二叉樹中的

每一結(jié)點(diǎn)，直至找到與關(guān)鍵字匹配的結(jié)點(diǎn)。

判斷二叉樹是否為空：判斷一棵二叉樹是否為空二叉樹。

修改指定結(jié)點(diǎn)的元素值：將指定結(jié)點(diǎn)的元素值修改為指定值。

計算二叉樹的深度：按照某種規(guī)則依次訪問二叉樹中的每一結(jié)點(diǎn)，計算各結(jié)點(diǎn)所在層

的最大值。

計算二叉樹的葉子結(jié)點(diǎn)數(shù)：按照某種規(guī)則依次訪問二叉樹中的每一結(jié)點(diǎn)，計算度為0

的結(jié)點(diǎn)數(shù)。

5.請簡述順序表示的二叉樹中各結(jié)點(diǎn)的編號規(guī)則。

順序表示的二叉樹中各結(jié)點(diǎn)的編號與相同深度的完全二叉樹中對應(yīng)結(jié)點(diǎn)的編號相同。

6.請簡述二叉鏈表表示和三叉鏈表表示的二叉樹中結(jié)點(diǎn)的結(jié)構(gòu)。

在二叉鏈表表示中，雙親結(jié)點(diǎn)有指向其孩子結(jié)點(diǎn)的指針，而孩子結(jié)點(diǎn)不包含指向其雙親

結(jié)點(diǎn)的指針；在三叉鏈表表示中，雙親結(jié)點(diǎn)有指向其孩子結(jié)點(diǎn)的指針，而孩子結(jié)點(diǎn)也包含指

向其雙親結(jié)點(diǎn)的指針。

7.請簡述二叉樹的四種遍歷方式及每一種遍歷方式中結(jié)點(diǎn)的訪問順序。

先序遍歷二叉樹：也稱為先根遍歷，其訪問方式遞歸定義如下：對于一棵二叉樹，先

訪問其根結(jié)點(diǎn)，再訪問根結(jié)點(diǎn)的左、右子樹；對于左、右子樹中的結(jié)點(diǎn)仍然是按照先序遍歷

方式訪問，即先訪問根結(jié)點(diǎn)，再訪問根結(jié)點(diǎn)的左、右子樹。

中序遍歷二叉樹：也稱為中根遍歷，其訪問方式遞歸定義如下：對于一棵二叉樹，先

訪問根結(jié)點(diǎn)左子樹，再訪問根結(jié)點(diǎn)，最后訪問右子樹；對于左、右子樹中的結(jié)點(diǎn)仍然是按照

中序遍歷方式訪問。

后序遍歷二叉樹：也稱為后根遍歷，其訪問方式遞歸定義如下：對于一棵二叉樹，先

訪問根結(jié)點(diǎn)的左子樹，后訪問右子樹，最后訪問根結(jié)點(diǎn)；對于左、右子樹中的結(jié)點(diǎn)仍然是按

照后序遍歷方式訪問。

逐層遍歷二叉樹：從第1層開始依次對每層中的結(jié)點(diǎn)按照從左至右的順序進(jìn)行訪問。

8.已知一棵二叉樹的先序遍歷結(jié)果為A、B、D、G、C、E、F、H、I,中序遍歷結(jié)果為D、

G、B、A、E、C、H、F、I,請給出該二叉樹的后序遍歷結(jié)果。

G、D、B、E、H、I、F、C、A

9.已知一棵二叉樹的中序遍歷結(jié)果為D、G、B、A、E、C、H、F、I,后序遍歷結(jié)果為G、

D、B、E、H、I、F、C、A,請給出該二叉樹的先序遍歷結(jié)果。

A、B、D、G、C、E、F、H、I

10.已知一棵二叉樹的先序遍歷結(jié)果為A、B、D、G、C、E、F、H、I,后序遍歷結(jié)果為G、

D、B、E、H、I、F、C、A,請給出該二叉樹的中序遍歷結(jié)果。

D、G、B、A、E、C、H、F、I

11.請簡述哈夫曼樹的結(jié)構(gòu)特性。

哈夫曼樹，又稱最優(yōu)二叉樹，是指在由〃個葉子結(jié)點(diǎn)構(gòu)成的一類二叉樹中具有最短帶權(quán)

路徑長度的二叉樹。

12.請簡述結(jié)點(diǎn)的權(quán)、結(jié)點(diǎn)的帶權(quán)路徑長度、樹的帶權(quán)路徑長度等基本術(shù)語的含義。

結(jié)點(diǎn)的權(quán)和結(jié)點(diǎn)的帶權(quán)路徑長度：在實(shí)際應(yīng)用中，往往給樹中的結(jié)點(diǎn)賦予一個具有某

種意義的實(shí)數(shù)，該實(shí)數(shù)就稱為是結(jié)點(diǎn)的權(quán)。結(jié)點(diǎn)的帶權(quán)路徑長度是指從樹根到該結(jié)點(diǎn)的路徑

長度與結(jié)點(diǎn)的權(quán)的乘積。

樹的帶權(quán)路徑長度：是指樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和，記為=叱Z,

(其中，〃為葉子結(jié)點(diǎn)的數(shù)目，W,?為第i個葉子結(jié)點(diǎn)的權(quán)，L為根結(jié)點(diǎn)到第i個葉子結(jié)點(diǎn)的

路徑長度，可知卬心為第i個葉子結(jié)點(diǎn)的帶權(quán)路徑長度).

13.請簡述哈夫曼樹的構(gòu)造方法。

哈夫曼樹的構(gòu)造方法如下：

(a)已知〃個權(quán)值為W,…的結(jié)點(diǎn)，將每個結(jié)點(diǎn)作為根結(jié)點(diǎn)生成〃棵只有

根結(jié)點(diǎn)的二叉樹Ti，形成森林F={T,,4,…,T“}。

(b)從森林F中選出根結(jié)點(diǎn)權(quán)值最小的兩棵二叉樹。和Tq,并通過添加新的根結(jié)點(diǎn)

將它們合并為一棵新二叉樹，新二叉樹中。和為分別作為根結(jié)點(diǎn)的左子樹和右子樹，且根

結(jié)點(diǎn)的權(quán)值等于。和〃兩棵二叉樹的根結(jié)點(diǎn)權(quán)值之和。以合并后生成的新二叉樹替代森林

F中的原有二叉樹G和G。重復(fù)該步驟直至森林F中只存在一棵二叉樹。

14.請簡述哈夫曼碼的作用及其編碼方法。

哈夫曼編碼是指將用其他編碼法表示的字符序列轉(zhuǎn)成用哈夫曼碼表示以減少存儲空間，

其具體方法為：

(a)以要編碼的字符集C={c},c2,c“}作為葉子結(jié)點(diǎn)、字符出現(xiàn)的頻度或次數(shù)W={Wi,

W2,…,w”}作為結(jié)點(diǎn)的權(quán)，構(gòu)造哈夫曼樹。

(b)規(guī)定哈夫曼樹中，從根結(jié)點(diǎn)開始，雙親結(jié)點(diǎn)到左孩子結(jié)點(diǎn)的分支標(biāo)為0,雙親結(jié)

點(diǎn)到右孩子結(jié)點(diǎn)的分支標(biāo)為1。從根結(jié)點(diǎn)到某一葉子結(jié)點(diǎn)經(jīng)過的分支形成的編碼即是該葉子

結(jié)點(diǎn)所對應(yīng)字符的哈夫曼碼。

15.請簡述樹的四種常用表示方式。

雙親表示法：在孩子結(jié)點(diǎn)中設(shè)置一個指針域記錄其雙親結(jié)點(diǎn)的存儲位置。

孩子表示法：在雙親結(jié)點(diǎn)中設(shè)置指向孩子結(jié)點(diǎn)的指針域來表示一棵樹。

孩子雙親表示法：綜合了孩子表示法和雙親表示法的特點(diǎn)，既在孩子結(jié)點(diǎn)中設(shè)置記錄

雙親結(jié)點(diǎn)位置的指針域，又在雙親結(jié)點(diǎn)中設(shè)置記錄孩子結(jié)點(diǎn)位置的指針域。

孩子兄弟表示法：又稱為二叉鏈表表示法，與二叉樹的二叉鏈表表示法存儲結(jié)構(gòu)完全

相同，只是結(jié)點(diǎn)中指針域的含義有所不同（一個指針域指向該結(jié)點(diǎn)的第一個孩子結(jié)點(diǎn)，另一

個指針域指向該結(jié)點(diǎn)的下一個兄弟結(jié)點(diǎn)）。

16.請簡述森林轉(zhuǎn)換為二叉樹的具體步驟。

將森林中的每棵樹都用二叉鏈表表示法表示，并將各棵二叉樹的根結(jié)點(diǎn)看做是兄弟結(jié)

點(diǎn)，在它們之間加上連線；將結(jié)點(diǎn)到第一個孩子結(jié)點(diǎn)的連線作為左子樹的邊，結(jié)點(diǎn)到兄弟結(jié)

點(diǎn)的連線作為右子樹的邊。

17.請簡述二叉樹轉(zhuǎn)化為樹或森林的具體步驟。

將一個結(jié)點(diǎn)左子樹的邊作為該結(jié)點(diǎn)指向第一個孩子結(jié)點(diǎn)的連線，右子樹的邊作為該結(jié)點(diǎn)

到兄弟結(jié)點(diǎn)的連線；在雙親結(jié)點(diǎn)和它的各孩子結(jié)點(diǎn)之間加上連線，并刪除兄弟結(jié)點(diǎn)之間的連

線，得到一棵樹或一個包含若干棵樹的森林。

第6章圖

i.請簡述圖的結(jié)構(gòu)特性。

圖G由頂點(diǎn)(圖中通常將結(jié)點(diǎn)稱為頂點(diǎn))的非空有限集合V和邊的集合E組成，記為

G=(V,E)。每一個頂點(diǎn)偶對就是圖中的一條邊，所以，E用于表示V上的連接關(guān)系。在一個

圖中，至少要包含一個頂點(diǎn)，但可以沒有任何邊。

2.請解釋有向圖、無向圖、弧、弧尾、弧頭、頂點(diǎn)的度、頂點(diǎn)的入度、頂點(diǎn)的出度、路徑、

路徑長度、回路、簡單回路、連通圖、單向連通圖、強(qiáng)連通圖、子圖、連通分量、強(qiáng)連通分

量、權(quán)、帶權(quán)圖、生成樹、最小生成樹等基本術(shù)語的含義。

有向圖、弧、弧尾和弧頭：若E(G)中的頂點(diǎn)偶對是有序的，則這些有序偶對就形成了

有向邊，此時圖G稱為有向圖。其中，有向邊也簡稱為弧。在有向圖G中，對于一條從頂

點(diǎn)Vi到頂點(diǎn)Vj的弧，記為＜Vi,Vj＞并有＜Vi,Vj＞CE(G),稱Vi為弧尾，Vj為弧頭。

無向圖：若E(G)中的頂點(diǎn)偶對是無序的，則這些無序偶對就形成了無向邊，此時圖G

稱為無向圖。

頂點(diǎn)的度、頂點(diǎn)的入度和頂點(diǎn)的出度：在無向圖中，與頂點(diǎn)叫相關(guān)聯(lián)的邊的數(shù)目稱為

頂點(diǎn)Vi的度。在有向圖中，以頂點(diǎn)環(huán)為弧頭的弧的數(shù)目稱為頂點(diǎn)明的入度；以頂點(diǎn)環(huán)為弧

尾的弧的數(shù)目稱為%的出度：頂點(diǎn)環(huán)的入度和出度之和稱為Vi的度。

路徑和路徑長度：在圖G中，若存在一個頂點(diǎn)序列v]),使得對于任意

0051有＜v],v產(chǎn)〉wE(G)(若G為有向圖)或(v?,v/)eE(G)(若G為無向圖)，則該序

列是從頂點(diǎn)V?到頂點(diǎn)V：」的一條路徑。一條路徑中邊的數(shù)目稱為路徑長度。

回路和簡單回路：在一條路徑中，若組成路徑的頂點(diǎn)序列中第一個頂點(diǎn)與最后一個頂

點(diǎn)相同，則該路徑稱為回路(或環(huán))；在一個回路中，若除第一個頂點(diǎn)與最后一個頂點(diǎn)外,

其他頂點(diǎn)只出現(xiàn)一次，則該回路稱為簡單回路(或簡單環(huán))。

連通圖：無向圖G中，若任意兩個頂點(diǎn)都是連通的，則稱G為連通圖。

單向連通圖和強(qiáng)連通圖：有向圖G中，若任意兩個頂點(diǎn)都是單向連通的，則稱G是單

向連通圖；若任意兩個頂點(diǎn)都是強(qiáng)連通的，則稱G為強(qiáng)連通圖。

子圖：對于圖G、G',若滿足V(G，)￡V(G)且E(G)uE(G),則G是G的子圖。

連通分量和強(qiáng)連通分量：一個無向圖的極大連通子圖稱為該無向圖的連通分量；一個

有向圖的極大強(qiáng)連通子圖稱為該有向圖的強(qiáng)連通分量。

權(quán)和帶權(quán)圖：可以為一個圖中的每條邊標(biāo)上一個具有某種意義的實(shí)數(shù)，該實(shí)數(shù)就稱為是

邊的權(quán)。邊上帶權(quán)的圖就稱為帶權(quán)圖。

生成樹和最小生成樹：若無向圖G的一個子圖G，是一棵包含圖G所有頂點(diǎn)的樹，則

G稱為圖G的生成樹。在所有形式的生成樹中，邊上的權(quán)之和最小的生成樹，稱為最小生

成樹。

3.請列舉可以用圖來描述的實(shí)際問題。

請參考例6-1和例6-2o

4.請簡述圖的基本操作及各操作的含義。

創(chuàng)建圖：創(chuàng)建不包含任何頂點(diǎn)和邊的空圖。

對圖作深度優(yōu)先遍歷：類似于樹的先序遍歷，即從某一個頂點(diǎn)開始訪問，訪問后將該頂

點(diǎn)去除得到若干子圖，對每個子圖再依次進(jìn)行深度優(yōu)先遍歷。

對圖作廣度優(yōu)先遍歷：類似于樹的逐層遍歷，即先從某一個頂點(diǎn)開始訪問，然后訪問與

該頂點(diǎn)相鄰接且未被訪問過的頂點(diǎn)集5(G),再訪問與V|(G)中頂點(diǎn)相鄰接且未被訪問

過的頂點(diǎn)集V2(G),重復(fù)該過程直至與初始頂點(diǎn)連通的所有頂點(diǎn)都被訪問完。對于非連

通圖或非強(qiáng)連通圖，還要從某一個未被訪問的頂點(diǎn)開始重復(fù)上一過程，直至所有頂點(diǎn)訪

問完畢。

獲取頂點(diǎn)數(shù)目：獲取圖中所包含的頂點(diǎn)的數(shù)目。

獲取邊的數(shù)目：獲取圖中所包含的邊的數(shù)目.

獲取與指定頂點(diǎn)相關(guān)聯(lián)的第一條邊：對無向圖，獲取到與指定頂點(diǎn)相關(guān)聯(lián)的第一條邊;

對有向圖，獲取到以指定頂點(diǎn)作為弧尾的第一條弧。不同表示方法獲取到的結(jié)果會有所

不同(鄰接矩陣法按頂點(diǎn)編號順序，鄰接壓縮表和鄰接鏈表按邊的添加順序)。

獲取與指定邊有相同關(guān)聯(lián)頂點(diǎn)的下一條邊：對無向圖，獲取到與指定邊(nVl,nV2)有相

同關(guān)聯(lián)頂點(diǎn)nVl的下一條邊；對有向圖，獲取到與指定?。糿Vl,nV2＞有相同弧尾nVl

的下一條弧。不同表示方法獲取到的結(jié)果會有所不同(鄰接矩陣法按頂點(diǎn)編號順序，鄰

接壓縮表和鄰接鏈表按邊的添加順序)。

添加一個頂點(diǎn)：向圖中添加一個新頂點(diǎn)。

添加一條邊：對無向圖，向圖中添加一條新邊；對有向圖，向圖中添加一條新弧。

獲取一個頂點(diǎn)中存儲的數(shù)據(jù)：根據(jù)頂點(diǎn)編號獲取該頂點(diǎn)中存儲的數(shù)據(jù)。

判斷一條邊是否存在：對無向圖，判斷兩個頂點(diǎn)nVl和nV2之間是否存在邊；對有向

圖，判斷是否存在從頂點(diǎn)nVl到頂點(diǎn)nV2的弧。

設(shè)置一條邊的權(quán)：對無向圖，設(shè)置指定邊(nVl,nV2)上的權(quán)；對有向圖，設(shè)置指定弧

＜nVl,nV2＞上的權(quán)。

獲取一條邊的權(quán)：對無向圖，獲取指定邊(nVl,nV2)上的權(quán)；對有向圖，獲取指定弧

＜nVl,nV2＞上的權(quán)。

5.請簡述圖的三種常用表示方法。

鄰接矩陣法：用矩陣來表示各頂點(diǎn)之間的連接關(guān)系。對于有n個頂點(diǎn)的圖G=(V,E),

其鄰接矩陣A為n*n的方陣，元素(0＜ij＜n)定義為：

唱.對無向圖存在(明,)

jeE(G)對有向圖存在＜￥，,＞e￡(G)

期[7]=(00反之

其中，Wjj為邊(Vi,Vj)或＜V“Vj＞上的權(quán)。

鄰接壓縮表：鄰接矩陣的一種壓縮表示形式，使用3個順序表來表示圖中頂點(diǎn)之間的連

接關(guān)系和權(quán)。設(shè)圖中共有n個頂點(diǎn){vo,vi,…,Vn-i},3個順序表分別為s、w和h。在s中依

次記錄與頂點(diǎn)Vi(i=0,1,...,n-l)相關(guān)聯(lián)的頂點(diǎn)；在w中依次記錄s中存儲的各條邊的權(quán);

在h中依次記錄與頂點(diǎn)叫相關(guān)聯(lián)的頂點(diǎn)在s中的起始存儲位置。

鄰接鏈表：圖的一種鏈?zhǔn)酱鎯Y(jié)構(gòu)。每個頂點(diǎn)中設(shè)置一個指向鏈表頭的指針，在鏈表中

保存與該頂點(diǎn)相鄰接的頂點(diǎn)信息(包括頂點(diǎn)位置及兩個頂點(diǎn)形成的邊的權(quán))。

6.請簡述圖的兩種常用遍歷方法及每一種遍歷方法中結(jié)點(diǎn)的訪問順序。

廣度優(yōu)先遍歷：類似于樹的逐層遍歷，即先從某一個頂點(diǎn)開始訪問，然后訪問與該頂

點(diǎn)相鄰接且未被訪問過的頂點(diǎn)集Vi(G),再訪問與V/G)中頂點(diǎn)相鄰接且未被訪問過的頂點(diǎn)

集VMG),重復(fù)該過程直至與初始頂點(diǎn)連通的所有頂點(diǎn)都被訪問完。對于非連通圖或非強(qiáng)連

通圖，還要從某一個未被訪問的頂點(diǎn)開始重復(fù)上一過程，直至所有頂點(diǎn)訪問完畢。

深度優(yōu)先遍歷：類似于樹的先序遍歷，即從某一個頂點(diǎn)開始訪問，訪問后將該頂點(diǎn)去

除得到若干子圖，對每個子圖再依次進(jìn)行深度優(yōu)先遍歷0

7.請列舉最小生成樹和最短路徑可以用于解決什么應(yīng)用問題。

請參考例6-1和例6-2。

8.請簡述Prim算法的作用和具體步驟。

Prim算法用于最小生成樹問題求解。對于有n個頂點(diǎn)的圖G=(V,E),Prim算法從空樹

T開始，按照以下規(guī)則將n個頂點(diǎn)和n-1條邊依次添加到樹中，形成最小生成樹：

(a)從某一頂點(diǎn)vo,開始，將該頂點(diǎn)作為樹的根結(jié)點(diǎn)加入到T中，使得T中的數(shù)據(jù)元素

集合D={vo'},數(shù)據(jù)元素關(guān)系集合R={}。

(b)對于一個頂點(diǎn)在集合D中、另一個頂點(diǎn)在集合V-D中的那些邊，找出權(quán)最小的一

條邊，將該邊在集合V-D中的頂點(diǎn)V；(i=l,2,...,n-l)加入到集合D中，并將頂點(diǎn)間關(guān)系<vj,

Vi'>(j<i)加入到關(guān)系集合R中。

(c)重復(fù)上一步驟直至集合D中包括圖G中所有n個頂點(diǎn)(此時關(guān)系集合R中包括

n-1條邊)。若在某一步驟中找不到邊，則說明圖G是一個非連通圖或非強(qiáng)連通圖，在這種

情況下不存在最小生成樹。

9.請簡述Kruskal算法的作用和具體步驟。

Kruskal算法用于最小生成樹問題求解。對于有n個頂點(diǎn)的圖G=(V,E),Kruskal算法根

據(jù)圖G中所有n個頂點(diǎn)生成一個包括n棵只有根結(jié)點(diǎn)的樹Ti(i=0,1,…,n-1)的森林F,并

按照以下規(guī)則森林F中的樹合并，形成最小生成樹：

(a)從邊集合E中選取未被訪問過且具有最小權(quán)的邊，置該邊狀態(tài)為已訪問。判斷該

邊的兩個頂點(diǎn)是否屬于不同的樹，若屬于不同的樹則使用該邊將兩棵樹合并為一棵；若屬于

同一棵樹則不做任何處理。

(b)重復(fù)上一步驟直至森林F中只剩下一棵樹，該樹即是圖G的最小生成樹。若最后

森林F中剩下不止一棵樹，則說明圖G是非連通圖或非強(qiáng)連通圖，在這種情況下不存在最

小生成樹。

10.請簡述Dijkstra算法的作用和具體步驟。

Dijkstra算法用于計算從某個頂點(diǎn)到其余各頂點(diǎn)的最短路徑。對于有n個頂點(diǎn)的圖G=(V,

E),若要計算從頂點(diǎn)vo'到其余各頂點(diǎn)vf(i=l,2,…,n-1)的最短路徑，則其計算步驟為：

(a)令集合S為已計算出最短路徑的頂點(diǎn)集合(初始時5=卜0'}),w(vj,旬)表示從頂

點(diǎn)“到頂點(diǎn)V：的邊的權(quán)(這里為方便計算，令w(vf,Vi)=O),D(vo；vi)表示當(dāng)前計算得到的

從頂點(diǎn)Vo'到頂點(diǎn)Vi'的最短路徑長度(初始D(vo',Vi')=w(vo',Vi'))o

(b)將頂點(diǎn)Vm'=argmin(D(v(/,v「))加入到集合S中，并將從頂點(diǎn)Vo'到頂點(diǎn)Vm'的最短

v/eV-S

路徑記錄下來。若仍有頂點(diǎn)沒有加到集合S中，則對集合V-S中的頂點(diǎn)V「計算

D(v()',v「)=心嗯(D(vo,,v；)+w(vf,v「))。

(c)重復(fù)上一步驟直至圖中所有頂點(diǎn)都加到集合S中。

11.請簡述Floyd算法的作用和具體步驟。

Floyd算法用于計算每一對頂點(diǎn)之間的最短路徑。對于有n個頂點(diǎn)的圖G=(V,E),若要

計算任意兩個頂點(diǎn)可和V。(j,k為區(qū)間上的整數(shù)且j#k)之間的最短路徑，則其計算步

驟為：

(a)令w(v；,V。)表示連接頂點(diǎn)V；和頂點(diǎn)Vk'的邊的權(quán)(這里為方便計算，令w(Vj',Vj')=O),

D(v；,V。)表示當(dāng)前計算得到的從頂點(diǎn)V：到頂點(diǎn)V。的最短路徑長度(初始D(v；,v?=w(Vj',

Vk'))O

(b)對于圖中每一個頂點(diǎn)Vi'(i依次取值為0,1,n-1),若D(v/,Vk')>D(v；,vf)+D(Vi，,Vk'),

則表明路徑（Vj；…,Vi'，…，Vk'）的長度更短,此時令D（Vj；Vk'）=D（v；,Vi）+D（Vi，,Vk'）并更新從頂點(diǎn)

可到頂點(diǎn)VI?的路徑。

第7章排序算法

i.請簡述排序的作用。

排序的作用是將一個待排序元素集合按關(guān)鍵字遞增(或遞減)順序整理為一個有序序列。

2.請簡述穩(wěn)定排序和不穩(wěn)定排序的含義。

若采用某種排序算法對任一組元素進(jìn)行排序，在排序前后，那些具有相同關(guān)鍵字值的元

素之間的相對次序都保持不變，則將這種排序算法稱為是穩(wěn)定的，否則稱為是不穩(wěn)定的。

3.請簡述各種排序算法的適用范圍。

排序算法的適用范圍如下：

(a)直接插入排序、簡單選擇排序和冒泡排序都是簡單排序算法，它們的時間復(fù)雜度

和空間復(fù)