《數(shù)據(jù)結(jié)構(gòu)、算法與應用(C++語言描述)》習題參考答案doc

1、第1章 概 論1.數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)類型的含義分別是什么？數(shù)據(jù)：對客觀事物的符號表示，在計算機科學中是指所有能輸入到計算機中并由計算機程序處理的符號的總稱。數(shù)據(jù)元素：數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體考慮。數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)元素之間的關(guā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ù)類型包含取值范圍和基本運算等概念。2.什么是數(shù)據(jù)的邏輯結(jié)構(gòu)？什么是數(shù)據(jù)的物理結(jié)構(gòu)

2、？數(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)在計算機存儲空間中的存放形式，包括結(jié)點的數(shù)據(jù)和結(jié)點間關(guān)系的存儲表示。數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)是密不可分的，一個操作算法的設(shè)計取決于所選定的邏輯結(jié)構(gòu)，而算法的實現(xiàn)依賴于所采與的存儲結(jié)構(gòu)。采用不同的存儲結(jié)構(gòu)，其數(shù)據(jù)處理的效率是不同的。因此，在進行數(shù)據(jù)處理時，針對不同問題，選擇合理的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)非常重要。3.數(shù)據(jù)結(jié)構(gòu)的主要操作包括哪些？對于

3、各種數(shù)據(jù)結(jié)構(gòu)而言，他們在基本操作上是相似的，最常用的操作有：l 創(chuàng)建：建立一個數(shù)據(jù)結(jié)構(gòu)；l 清除：清除一個數(shù)據(jù)結(jié)構(gòu)；l 插入：在數(shù)據(jù)結(jié)構(gòu)中增加新的結(jié)點；l 刪除：把指定的結(jié)點從數(shù)據(jù)結(jié)構(gòu)中刪除；l 訪問：對數(shù)據(jù)結(jié)構(gòu)中的結(jié)點進行訪問；l 更新：改變指定結(jié)點的值或改變指定的某些結(jié)點之間的關(guān)系；l 查找：在數(shù)據(jù)結(jié)構(gòu)中查找滿足一定條件的結(jié)點；l 排序：對數(shù)據(jù)結(jié)構(gòu)中各個結(jié)點按指定數(shù)據(jù)項的值，以升序或降序重新排列。4.什么是抽象數(shù)據(jù)類型？如何定義抽象數(shù)據(jù)類型？抽象數(shù)據(jù)類型（Abstract Data Type 簡稱ADT）是指一個數(shù)學模型以及定義在此數(shù)學模型上的一組操作。ADT是與具體的物理存儲無關(guān)的數(shù)據(jù)類

4、型，因此，不論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é)果：<操作結(jié)果描述>初始條件說明操作執(zhí)行

5、之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應滿足的條件；操作結(jié)果說明操作完成后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應返回的結(jié)果。5.什么是算法？算法的基本特征是什么？算法：是在有限的步驟內(nèi)解決數(shù)學問題的過程，是以一步接一步的方式來詳細描述計算機如何將輸入轉(zhuǎn)化為所要求的輸出的過程，即算法是對計算機上執(zhí)行的計算過程的具體描述。一個有效的算法必須滿足的五個重要特性： 有窮性：算法必須能在有限的時間內(nèi)做完，即在任何情況下，算法必須能在執(zhí)行有限個步驟之后終止，都不能陷入無窮循環(huán)中。 確定性：算法中的每一個步驟，必須經(jīng)過明確的定義，并且能夠被計算機所理解和執(zhí)行，而不能是抽象和模糊的概念，更不允許有二義性。 輸入：算法有0個或多個輸入值，來描述

6、算法開始前運算對象的初始情況，這是算法執(zhí)行的起點或是依據(jù)。0個輸入是指算法本身給出了運算對象的初始條件。 輸出：算法至少有1個或多個輸出值，反映對運算對象的處理結(jié)果，沒有輸出的算法沒有任何意義。 可行性：算法中要做的運算都是基本運算，能夠被精確地進行。即算法中執(zhí)行的任何計算都可以被分解為基本的運算步，每個基本的運算步都可以在有限的時間內(nèi)完成。6.什么是算法分析？算法分析主要考慮哪幾方面的內(nèi)容？算法的研究與實際問題直接相關(guān)，用來解一個問題可以有很多不同的算法，他們之間的效果可能會有很大差異。算法設(shè)計者最關(guān)心的就是什么是有效的算法，如何評價一個算法的優(yōu)劣，如何從多種算法中選擇好的算法。除了要首先考

7、慮算法的正確性外，還要分析和評價算法的性能。分析和評價算法的性能主要要考慮以下兩個方面：時間代價：執(zhí)行算法所耗費的時間。一個好的算法首先應該比其他算法的運行時間代價要小。算法的時間代價的大小用算法的時間復雜度來度量?？臻g代價：執(zhí)行算法所耗費的存儲空間，主要是輔助空間。算法運行所需的空間消耗是衡量算法優(yōu)劣的另一個重要因素。算法的空間代價的大小用算法的空間復雜度來度量。7.分析下面算法的時間復雜度。（1）答：時間復雜度為n2（2）時間復雜度：n（3）時間復雜度：（4）時間復雜度：n2（5）時間復雜度：O(log2n)8.算法設(shè)計中的遞歸、窮舉、遞推和迭代等算法的基本思想是什么？遞推法：是利用問題本

8、身所具有的一種遞推關(guān)系求解問題的一種方法。它把問題求解分成若干步，找出相鄰幾步的關(guān)系，從而達到求解問題的目的。具有如下性質(zhì)的問題可以采用遞推法：當?shù)玫絾栴}規(guī)模為i-1的解后，由問題的遞推性質(zhì)，能構(gòu)造出問題規(guī)模為i的解。因此，程序可以從i=0或i=1出發(fā)，由已知i-1規(guī)模的解，通過遞推，獲得問題規(guī)模為i的解，直至得到問題規(guī)模為n的解。遞歸法：遞歸策略是利用函數(shù)直接或間接地調(diào)用自身來完成某個計算過程。能采用遞歸描述的算法通常有這樣的特征：為求解規(guī)模為n的問題，設(shè)法將它分解成規(guī)模較小的問題，然后從這些小問題的解方便地構(gòu)造出更大問題的解，并且這些規(guī)模較小的問題也能采用同樣的分解和綜合方法，分解成規(guī)模更

9、小的問題，并從這些更小問題的解構(gòu)造出較大規(guī)模問題的解。窮舉法：窮舉搜索法也稱窮舉法或搜索法是對可能是解的眾多候選解按某種順序進行 逐一枚舉和檢驗，并從中找出那些符合要求的候選解作為問題的解。迭代法：數(shù)值分析中通過從一個初始估計出發(fā)尋找一系列近似解來解決問題（一般是解方程或者方程組）的過程，為實現(xiàn)這一過程所使用的方法統(tǒng)稱為迭代法。9.算法設(shè)計中的分治策略、貪心策略、動態(tài)規(guī)劃策略、回溯策略以及分支定界策略的基本思想是什么？分治策略的基本思想是把一個規(guī)模為n的問題劃分為若干個規(guī)模較小、且與原問題相似的子問題，然后分別求解這些子問題，最后把各子結(jié)果合并得到整個問題的解。分解的子問題通常與原問題相似，所

10、以可以遞歸地使用分治策略來求解。貪心策略的基本思想是把一個整體最優(yōu)問題分解為一系列的最優(yōu)選擇問題，決策一旦做出，就不能再更改。它是通過若干次的貪心選擇而得出最優(yōu)解（或較優(yōu)解）的一種解題策略。動態(tài)規(guī)劃策略與貪心策略類似，將一個問題劃分為重復的子問題，通過對相同子問題的求解來解決較大問題，即將一個問題的解決方案視為一系列決策的結(jié)果。不同的是，在貪心策略中，每采用一次貪心準則便做出一個不可撤回的決策，可能得不到問題的最優(yōu)解。而在動態(tài)規(guī)劃中，處理要按照某種規(guī)則進行選擇，還要考察每個最優(yōu)決策序列中是否包含一個最優(yōu)子序列，目的是得到問題的最優(yōu)解。回溯策略也叫試探法，它的基本思想是：在一些問題求解進程中，先

11、選擇某一種可能情況向前探索，當發(fā)現(xiàn)所選用的試探性操作不是最佳選擇，需退回一步，重新選擇繼續(xù)進行試探，直到找到問題的解或者證明問題無解。分支定界策略也經(jīng)常被稱為分支限界策略，它的基本思想是：首先確定目標值的上下界，然后一邊搜索一邊剪掉空間樹的某些不可能產(chǎn)生最優(yōu)解的分支，提高搜索效率。第二章 線性表1具有什么特征的數(shù)據(jù)結(jié)構(gòu)被稱為線性表？線性表是一種最常用、最簡單的典型線性數(shù)據(jù)結(jié)構(gòu)，應用非常廣泛。線性表是由n（n0）個數(shù)據(jù)元素組成的一個有限序列，線性表中數(shù)據(jù)元素的個數(shù)n稱為線性表的長度。當n=0時，稱為空表。對于非空線性表，數(shù)據(jù)元素之間存在一對一的關(guān)系，具體特性如下：第一個數(shù)據(jù)元素沒有前驅(qū)；最后一個

12、數(shù)據(jù)元素沒有后繼外；其他數(shù)據(jù)元素都是首尾相接、有且只有一個前驅(qū)和后繼。2如何實現(xiàn)線性表的順序存儲結(jié)構(gòu)？把線性表的結(jié)點按邏輯順序依次存放在一組地址連續(xù)的存儲單元里就構(gòu)成了線性表的順序存儲，采用順序存儲結(jié)構(gòu)的線性表簡稱順序表。線性表的順序存儲結(jié)構(gòu)有如下特點：l 線性表中所有元素所占的存儲空間是連續(xù)的；l 線性表的邏輯順序與物理順序一致；l 數(shù)組中的每一個元素的位置可以用公式來確定。假設(shè)線性表中的第一個數(shù)據(jù)元素的存儲地址（指第一個字節(jié)的地址，即首地址）為 LOC(e1)，每一個數(shù)據(jù)元素占k個字節(jié)，則線性表中第i個元素ei在計算機存儲空間中的存儲地址為：LOC(ei)=LOC(e1)+(i-1)k3如

13、何實現(xiàn)線性表的4種鏈式存儲結(jié)構(gòu)？數(shù)據(jù)結(jié)構(gòu)中的每一個數(shù)據(jù)元素對應于一個存儲單元，這種存儲單元稱為存儲結(jié)點，簡稱結(jié)點。每個結(jié)點分為兩部分：一部分用于存放數(shù)據(jù)元素的值，稱為數(shù)據(jù)域；另一部分是指針，用于指向與該結(jié)點在邏輯上相連的其他結(jié)點，稱為指針域。對于線性表，指針域用于指向該結(jié)點的前一個或后一個結(jié)點（即前驅(qū)結(jié)點或后繼結(jié)點）。通過結(jié)點的指針域?qū)個結(jié)點按其邏輯結(jié)構(gòu)連接在一起的數(shù)據(jù)存儲結(jié)構(gòu)，稱為鏈式存儲結(jié)構(gòu)。單向鏈表：在線性鏈表中，用一個專門的指針指向線性表中第一個結(jié)點，每一個結(jié)點的指針都指向它的下一個邏輯結(jié)點，線性鏈表的最后一個結(jié)點的指針為空（用NULL或0表示），表示鏈表終止，這樣的線性鏈表稱為單向

14、鏈表。下圖是單向鏈表示意圖。firste1e2 ei en NULLNULL NULL線性表的單向鏈式存儲循環(huán)鏈表：將單向鏈表最后一個結(jié)點的指針指向頭結(jié)點，這樣整個鏈表就構(gòu)成一個循環(huán)，這種鏈式存儲結(jié)構(gòu)稱為單向循環(huán)鏈表，簡稱循環(huán)鏈表。頭結(jié)點的指針域指向線性表的第一個元素的結(jié)點；循環(huán)鏈表中最后一個結(jié)點的指針域不再是NULL，而是指向頭結(jié)點。只有頭結(jié)點的循環(huán)鏈表稱為空循環(huán)鏈表。下圖是帶頭結(jié)點的非空循環(huán)鏈表和空循環(huán)鏈表示意圖。e1headen 頭結(jié)點head頭結(jié)點（a）帶頭結(jié)點的非空循環(huán)鏈表 （b）帶頭結(jié)點的空循環(huán)鏈表帶頭結(jié)點的循環(huán)鏈表雙向鏈表：雙向鏈表的每個結(jié)點含有兩個指針域，一個指針指向其前驅(qū)結(jié)點

15、；另一個指針指向其后繼結(jié)點。雙向鏈表結(jié)點的結(jié)構(gòu)下圖（a）所示。e2en（b）雙向鏈表e1e2en（c）雙向循環(huán)鏈表prev data next（a）雙向鏈表結(jié)點結(jié)構(gòu)firstfirste1end雙向循環(huán)鏈表：如果將雙向鏈表第一個結(jié)點的prev指針指向最后一個結(jié)點，將最后一個結(jié)點的next指針與指向第一個結(jié)點，就構(gòu)成了雙向循環(huán)鏈表。下圖（b）和（c）是雙向鏈表和雙向循環(huán)表的邏輯結(jié)構(gòu)示意圖。圖 雙向鏈表結(jié)點結(jié)構(gòu)及雙向鏈表4順序表和線性鏈表分別有哪些優(yōu)點和缺點？線性表的順序存儲與鏈式存儲比較比較內(nèi)容順序存儲鏈式存儲結(jié)點存儲空間少（不需要為表示結(jié)點的邏輯關(guān)系增加開銷）多（需要增加指針域來表示結(jié)點之間的

16、邏輯關(guān)系）空間利用率低（采用數(shù)組，按表的最大長度靜態(tài)分配存儲空間）高（根據(jù)表的實際長度動態(tài)分配存儲空間）插入、刪除操作慢（需要大量移動元素）快（僅更改指針指向，不需要移動元素）訪問元素快（直接訪問）慢（通過指針移動才能訪問）實現(xiàn)難易程度相對容易（基于數(shù)組操作，一般高級語言都提供數(shù)組類型）相對困難（基于指針操作）5請列舉出一些線性表問題的實例。按員工號排序的員工基本情況表；奧運會各項比賽日程；按學號記錄的學生的成績單；等等。6. 對于順序表和單向鏈表，如何實現(xiàn)統(tǒng)計重復元素個數(shù)的操作？在順序表中實現(xiàn)統(tǒng)計重復元素個數(shù)的操作：在教材的【描述2-1】中，增加一個統(tǒng)計重復元素個數(shù)的成員函數(shù)：int Cou

17、nt(const T&x); /返回x出現(xiàn)的次數(shù)在教材的【描述2-2】中，增加查找重復元素個數(shù)的成員函數(shù)的實現(xiàn)：/實現(xiàn)統(tǒng)計重復元素個數(shù)template<class T>int LinearList<T>:Count(const T& x)int count=0;for (int i=0; i<length; i+)if(elementi=x)count+;return count;在順序表中實現(xiàn)統(tǒng)計重復元素個數(shù)的操作：在教材的【描述2-3】中，增加一個統(tǒng)計重復元素個數(shù)的成員函數(shù)：int Count(const T&x); /返回x出現(xiàn)的次數(shù)

18、在教材的【描述2-4】中，增加查找重復元素個數(shù)的成員函數(shù)的實現(xiàn)：/實現(xiàn)統(tǒng)計重復元素個數(shù)template<class T>int LinkList<T>:Count(const T& x)LinkNode<T> * p=head->next;int count=0;while (p!=NULL && )if (p->data =x) count+;p=p->next;return count;第3章 棧和隊列1具有什么特征的數(shù)據(jù)結(jié)構(gòu)被稱為棧和隊列？先進后出、棧頂、棧底、先進先出、隊頭、隊尾的概念是什么？棧：一種插入和刪

19、除都只能在表的同一端進行的線性表。隊列：一種只允許在表的一端進行插入操作，而在表的另一端進行刪除操作的線性表。先進后出：元素是以e1，e2，en順序進入數(shù)據(jù)結(jié)構(gòu)，以相反的順序即en，en-1，e1離開數(shù)據(jù)結(jié)構(gòu)。棧頂：允許進行插入和刪除操作的一端。棧底：棧中與棧頂相對的另一端。先進先出：元素是以e1，e2，en順序進入數(shù)據(jù)結(jié)構(gòu)，以相同的順序即e1，e2，en。 離開數(shù)據(jù)結(jié)構(gòu)。隊頭：允許刪除操作的一端。隊尾：允許插入操作的一端。 2簡述在順序棧的棧頂插入一個元素的操作過程。在插入元素之前，首先要判斷棧是否為滿，如果棧滿，返回“沾滿無法插入”等錯誤提示信息；否則讓top指針（指向當前順序棧的棧頂）向

20、后移動一個元素空間（元素大?。?，將要插入的元素放入top指針指向的內(nèi)存單元中。3. 一個棧的輸入序列為1、2、3，試給出全部可能的出棧序列。可分為三種情況：、當只有一個存儲空間時，只有一種出棧序列：1、2、3.、當有兩個存儲空間時，有：1、2、3， 2、1、3， 2、3、1等3種出棧序列、當存儲空間大于等于三個時，有：1、2、3， 2、1、3， 2、3、1， 3、2、1等4種出棧序列。4循環(huán)隊列的優(yōu)點是什么？在循環(huán)隊列中，僅依據(jù)頭尾指針相等，無法判斷隊列是“空”還是“滿”。要解決這個問題，常用的兩種方法是什么？循環(huán)隊列的優(yōu)點有兩點：一是可以避免發(fā)生順序隊列的“假上溢”現(xiàn)象；二是充分利用隊列的存

21、儲空間。兩種判斷隊列是“空”還是“滿”的方法：一是約定少用一個元素空間；二是使用計數(shù)器size記錄當前隊列的實際長度。5. 簡述在鏈接棧中插入一個元素的操作過程。鏈接棧的插入操作，先將待進棧結(jié)點的指針域指向原來的棧頂結(jié)點，然后將棧頂指針top修改指向該結(jié)點，使進棧元素結(jié)點成為新的棧頂結(jié)點。6請列舉出一些可以用棧和隊列表示的實際問題。所有“后進先出”(LIFO，Last In First Out）的實際問題都可以用棧表示。棧的應用主要有：數(shù)制的轉(zhuǎn)換、括號的匹配檢查、行編輯處理、表達式求解、走迷宮以及高級語言中函數(shù)的嵌套調(diào)用和遞歸的實現(xiàn)等。所有“先進先出”(FIFO，F(xiàn)irst In First

22、Out）的實際問題都可以用隊列表示。如日常中的排隊問題，隊列的應用主要有：操作系統(tǒng)中各種資源請求排隊和各種緩沖區(qū)的先進先出管理，各種應用系統(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ù)組a56，每個元素占相鄰的8個字節(jié)，存儲器按字節(jié)編址，已知a的起始地址是1000，試計算：（1）數(shù)組a的最后一個元素起始地址；1000+（30-1）*8=

23、1232。（2）按行序優(yōu)先時，元素a35的起始地址；1000+（3*6+5）*8=1184（3）按行列序優(yōu)先時，元素a43的起始地址。1000+（3*5+4）*8=11523.請簡述數(shù)組和矩陣的關(guān)系。矩陣是指縱橫排列的二維數(shù)據(jù)表格。在高級語言編程中，通常用二維數(shù)組來描述一個矩陣，從而可以對矩陣中的元素進行隨機存取。但矩陣的索引通常從1而不是像數(shù)組那樣從0開始，并且使用A（i，j）而不是Ai，j的形式來引用矩陣中的元素。4.矩陣有哪些基本運算？矩陣的操作包括轉(zhuǎn)置、加法、減法和乘法等。5.稀疏矩陣的特點是什么？為什么要對稀疏矩陣采用壓縮存儲技術(shù)？稀疏矩陣的特點是矩陣中非零元素個數(shù)遠遠少于矩陣零元素

24、個數(shù)。采用壓縮存儲技術(shù)主要是為了節(jié)省空間。6.設(shè)A和B是稀疏矩陣，都以三元組作為存儲結(jié)構(gòu)，請寫出矩陣相加的算法C=A+B。/稀疏矩陣的三元組表示#include <iostream>using namespace std;#define M 50#define N 50#define MaxSize 20typedef int ElemType; typedef structint r;int c;ElemType d; TupNode;typedef structint rows;int cols;int nums;TupNode dataMaxSize; TSMatrix;in

25、t AMN,BMN;/建立三元組void CreateMat(int AMN,TSMatrix &t,int row,int col)int i,j;t.rows=row;t.cols=col;t.nums=0;for(i=0;i<M;i+) for(j=0;j<N;j+)if(Aij!=0)t.datat.nums.r=i;t.datat.nums.c=j;t.datat.nums.d=Aij;t.nums+; /矩陣相加int MatAdd(TSMatrix &a,TSMatrix &b,TSMatrix &c) int i=0,j=0,k=0;

26、ElemType v;if(a.rows!=b.rows|a.cols!=b.cols) return 0;c.rows=a.rows;c.cols=a.cols;while(i<a.nums && j<b.nums)if(a.datai.r=b.dataj.r)if(a.datai.c<b.dataj.c)c.datak.r=a.datai.r;c.datak.c=a.datai.c;c.datak.d=a.datai.d;i+;k+; else if(a.datai.c>b.dataj.c) c.datak.r=b.dataj.r;c.datak.c

27、=b.dataj.c;c.datak.d=b.dataj.d;j+;k+; elsev=a.datai.d+b.dataj.d;if(v!=0)c.datak.r=a.datai.r;c.datak.c=a.datai.c;c.datak.d=v;k+;i+;j+; else if(a.datai.r<b.dataj.r)c.datak.r=a.datai.r;c.datak.c=a.datai.c;c.datak.d=a.datai.d;i+;k+; elsec.datak.r=b.dataj.r;c.datak.c=b.dataj.c;c.datak.d=b.dataj.d;j+;k

28、+; if (i=a.nums)while (j<b.nums)c.datak.r=b.dataj.r;c.datak.c=b.dataj.c;c.datak.d=b.dataj.d;j+;k+;if (j=b.nums)while (i<a.nums)c.datak.r=a.datai.r;c.datak.c=a.datai.c;c.datak.d=a.datai.d;i+;k+;c.nums=k; return 1; /輸出三元組void DispMat(TSMatrix t) int i;if(t.nums<=0) cout<<"此矩陣所有元素都為

29、"<<endl;return;cout<<t.rows<<'t'<<t.cols<<'t'<<t.nums<<endl;cout<<"-"<<endl;for(i=0;i<t.nums;i+)cout<<t.datai.r<<'t'<<t.datai.c<<'t'<<t.datai.d<<endl<<end

30、l; /主函數(shù)int main()int row,col,i,j;TSMatrix a,b,c;cout<<"請輸入矩陣的行、列數(shù)：n"cin>>row>>col;cout<<"請輸入矩陣A的元素：n"for(i=0;i<row;i+)for(j=0;j<col;j+)cin>>Aij; cout<<"請輸入矩陣B的元素：n"for(i=0;i<row;i+)for(j=0;j<col;j+)cin>>Bij; CreateMa

31、t(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);return 0;7.簡述字符串與一維字符型數(shù)組的區(qū)別與聯(lián)系。字符串簡稱串，它是一種以字符為元素的特殊線性表。字符串可以看成是以字符為元素的一維數(shù)組。具體實現(xiàn)時，在C/C+中的字符串使用為字符

32、型數(shù)組來表示。為了便于確定字符串的結(jié)尾，在字符型數(shù)組中使用0（就是0）作為字符串的截止符。8.列舉一些需要進行字符串模式匹配的應用場景。例如，在文本編輯中經(jīng)常要查找某一特定單詞或者一段話在整篇文章中出現(xiàn)的位置，按照姓名查找某個學生、員工、居民。有效的模式匹配能極大地提高文本編輯程序的能力。9.列舉幾個字符串的其他操作。求字符串中某個子串出現(xiàn)的次數(shù)，刪除滿足條件的子串，字符串字符移位等。10.什么是廣義表？廣義表與線性表的區(qū)別是什么？廣義表又稱列表，是由n（n0）個元素組成的有窮序列：GL=（e1，e2，en），但與線性表不同的是，廣義表中的元素允許以不同的形式出現(xiàn)：它可以是一個原子（邏輯上不能

33、再分解的元素），也可以是另一個廣義表。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)的實際問題。線性表的順序存儲、學生編號和姓名的問題、各班級的學生編號和姓名的問題等，都可以歸結(jié)為數(shù)組。不同物品所需原材料的數(shù)量、不同產(chǎn)地原材料的價格、不同類型的住宅需要的物品數(shù)量等，不同學生的計算機成績，不同職工的工資等都可以歸結(jié)為矩陣。學生的姓名和學號、學

34、校或各單位的名稱、國家名稱、一篇文章、一個高級語言源程序等，都可歸結(jié)為字符串。應用高斯消元法求解方程組可以歸結(jié)為廣義表。第5章 樹和二叉樹1. 請簡述樹、二叉樹、滿二叉樹和完全二叉樹的結(jié)構(gòu)特性。樹：只有最頂層的結(jié)點沒有前驅(qū)，其余結(jié)點都有且只有一個前驅(qū)；一個結(jié)點可以沒有后繼，也可以有一個或多個后繼。二叉樹：一種特殊形態(tài)的樹，每個結(jié)點至多有兩個后繼。滿二叉樹：一種特殊形態(tài)的二叉樹，除了最后一層的結(jié)點為葉子結(jié)點外其它結(jié)點都有左、右兩棵子樹的二叉樹。完全二叉樹：一種特殊形態(tài)的二叉樹，其結(jié)點與相同深度的滿二叉樹中的結(jié)點編號完全一致，即對于深度為k的完全二叉樹，其前k-1層與深度為k的滿二叉樹的前k-1層

35、完全一樣，只是在第k層上有可能缺少右邊若干個結(jié)點。2. 請解釋結(jié)點的度、樹的度、結(jié)點的層、樹的深度、分支、路徑、路徑長度、樹的路徑長度、葉子結(jié)點、分支結(jié)點、內(nèi)部結(jié)點、孩子、雙親、兄弟、堂兄弟、祖先、子孫、有序樹、無序樹和森林等基本術(shù)語的含義。結(jié)點的度和樹的度：一個結(jié)點的后繼的數(shù)目稱為該結(jié)點的度，樹中各結(jié)點度的最大值稱為樹的度。結(jié)點的層和樹的深度：樹的根結(jié)點所在的層為第1層，其余結(jié)點的層等于其前驅(qū)結(jié)點的層加1，樹中各結(jié)點的層的最大值稱為樹的深度。分支、路徑、路徑長度和樹的路徑長度：從一個結(jié)點到其后繼結(jié)點之間的連線稱為一個分支，從一個結(jié)點X到另一個結(jié)點Y所經(jīng)歷的所有分支構(gòu)成結(jié)點X到結(jié)點Y的路徑，一

36、條路徑上的分支數(shù)目稱為路徑長度，從樹的根結(jié)點到其他各個結(jié)點的路徑長度之和稱為樹的路徑長度。葉子結(jié)點、分支結(jié)點和內(nèi)部結(jié)點：樹中度為0的結(jié)點稱為葉子結(jié)點（或終端結(jié)點），度不為0的結(jié)點稱為分支結(jié)點（或非終端結(jié)點），除根結(jié)點以外的分支結(jié)點也稱為內(nèi)部結(jié)點。孩子和雙親：在樹中，一個結(jié)點的后繼結(jié)點稱為該結(jié)點的孩子，相應地，一個結(jié)點的前驅(qū)結(jié)點稱為該結(jié)點的雙親，即一個結(jié)點是其孩子結(jié)點的雙親、其雙親結(jié)點的孩子。兄弟和堂兄弟：同一雙親的孩子結(jié)點之間互稱為兄弟，不同雙親但在同一層的結(jié)點之間互稱為堂兄弟。祖先和子孫：從樹的根結(jié)點到某一個結(jié)點X的路徑上經(jīng)歷的所有結(jié)點（包括根結(jié)點但不包括結(jié)點X）稱為結(jié)點X的祖先，以某一結(jié)點

37、X為根的子樹上的所有非根結(jié)點（即除結(jié)點X外）稱為結(jié)點X的子孫。有序樹和無序樹：對于樹中的任一結(jié)點，如果其各棵子樹的相對次序被用來表示數(shù)據(jù)之間的關(guān)系，即交換子樹位置會改變樹所表示的內(nèi)容，則稱該樹為有序樹；否則稱為無序樹。森林：m（m0）棵互不相交的樹的集合就構(gòu)成了森林。3. 請簡述二叉樹的五條基本性質(zhì)。性質(zhì)1：在二叉樹的第i層上至多有2i-1個結(jié)點（i1）。性質(zhì)2：深度為k的二叉樹至多有2k-1個結(jié)點。性質(zhì)3：在二叉樹中，若度為0的結(jié)點（即葉子結(jié)點）數(shù)為n0，度為2的結(jié)點數(shù)為n2，則n0=n2+1。性質(zhì)4：具有n個結(jié)點的完全二叉樹其深度為ëlog2nû+1（其中ël

38、og2nû表示不大于log2n的最大整數(shù)）。性質(zhì)5：采用順序編號的完全二叉樹具有如下性質(zhì)：若一個分支結(jié)點的編號為i，則其左子樹的根結(jié)點（即左孩子結(jié)點）編號為2*i，右子樹的根結(jié)點（即右孩子結(jié)點）編號為2*i+1；反之，若一個非根結(jié)點的編號為i，則其雙親結(jié)點的編號為ëi/2û（其中ëi/2û表示不大于i/2的最大整數(shù)）。4. 請簡述二叉樹的常用操作及各操作的含義。創(chuàng)建一棵空二叉樹：創(chuàng)建一棵沒有任何結(jié)點的二叉樹。在順序表示中，根據(jù)樹的深度為結(jié)點分配內(nèi)存；在二叉鏈表表示中，將指向根結(jié)點的指針賦值為NULL。刪除一棵二叉樹：將二叉樹各結(jié)點所占據(jù)的內(nèi)存釋

39、放。清空二叉樹：將二叉樹的所有結(jié)點刪除，使之成為一棵空二叉樹。以指定元素值創(chuàng)建根結(jié)點：創(chuàng)建根結(jié)點，并以指定值作為根結(jié)點的元素值。將一個結(jié)點作為指定結(jié)點的左孩子插入：根據(jù)指定元素值生成一個新結(jié)點，并將其作為指定結(jié)點的左孩子。將一個結(jié)點作為指定結(jié)點的右孩子插入：根據(jù)指定元素值生成一個新結(jié)點，并將其作為指定結(jié)點的右孩子。先序遍歷二叉樹：也稱為先根遍歷，其訪問方式遞歸定義如下：對于一棵二叉樹，先訪問其根結(jié)點，再訪問根結(jié)點的左、右子樹；對于左、右子樹中的結(jié)點仍然是按照先序遍歷方式訪問，即先訪問根結(jié)點，再訪問根結(jié)點的左、右子樹。中序遍歷二叉樹：也稱為中根遍歷，其訪問方式遞歸定義如下：對于一棵二叉樹，先訪問

40、根結(jié)點左子樹，再訪問根結(jié)點，最后訪問右子樹；對于左、右子樹中的結(jié)點仍然是按照中序遍歷方式訪問。后序遍歷二叉樹：也稱為后根遍歷，其訪問方式遞歸定義如下：對于一棵二叉樹，先訪問根結(jié)點的左子樹，后訪問右子樹，最后訪問根結(jié)點；對于左、右子樹中的結(jié)點仍然是按照后序遍歷方式訪問。逐層遍歷二叉樹：從第1層開始依次對每層中的結(jié)點按照從左至右的順序進行訪問。獲取指定結(jié)點的雙親結(jié)點：根據(jù)指定結(jié)點獲取其雙親結(jié)點。在順序表示中，可以直接根據(jù)指定結(jié)點的位置計算雙親結(jié)點的位置；在二叉鏈表表示中，則需要從根結(jié)點開始遍歷二叉樹直至找到指定結(jié)點的雙親結(jié)點。刪除以指定結(jié)點為根的子樹：將以指定結(jié)點為根結(jié)點的子樹上的所有結(jié)點（包括指

41、定結(jié)點）刪除。按關(guān)鍵字查找結(jié)點：按照某種規(guī)則（先序、中序、后序或逐層）依次訪問二叉樹中的每一結(jié)點，直至找到與關(guān)鍵字匹配的結(jié)點。判斷二叉樹是否為空：判斷一棵二叉樹是否為空二叉樹。修改指定結(jié)點的元素值：將指定結(jié)點的元素值修改為指定值。計算二叉樹的深度：按照某種規(guī)則依次訪問二叉樹中的每一結(jié)點，計算各結(jié)點所在層的最大值。計算二叉樹的葉子結(jié)點數(shù)：按照某種規(guī)則依次訪問二叉樹中的每一結(jié)點，計算度為0的結(jié)點數(shù)。5. 請簡述順序表示的二叉樹中各結(jié)點的編號規(guī)則。順序表示的二叉樹中各結(jié)點的編號與相同深度的完全二叉樹中對應結(jié)點的編號相同。6. 請簡述二叉鏈表表示和三叉鏈表表示的二叉樹中結(jié)點的結(jié)構(gòu)。在二叉鏈表表示中，雙

42、親結(jié)點有指向其孩子結(jié)點的指針，而孩子結(jié)點不包含指向其雙親結(jié)點的指針；在三叉鏈表表示中，雙親結(jié)點有指向其孩子結(jié)點的指針，而孩子結(jié)點也包含指向其雙親結(jié)點的指針。7. 請簡述二叉樹的四種遍歷方式及每一種遍歷方式中結(jié)點的訪問順序。先序遍歷二叉樹：也稱為先根遍歷，其訪問方式遞歸定義如下：對于一棵二叉樹，先訪問其根結(jié)點，再訪問根結(jié)點的左、右子樹；對于左、右子樹中的結(jié)點仍然是按照先序遍歷方式訪問，即先訪問根結(jié)點，再訪問根結(jié)點的左、右子樹。中序遍歷二叉樹：也稱為中根遍歷，其訪問方式遞歸定義如下：對于一棵二叉樹，先訪問根結(jié)點左子樹，再訪問根結(jié)點，最后訪問右子樹；對于左、右子樹中的結(jié)點仍然是按照中序遍歷方式訪問。

43、后序遍歷二叉樹：也稱為后根遍歷，其訪問方式遞歸定義如下：對于一棵二叉樹，先訪問根結(jié)點的左子樹，后訪問右子樹，最后訪問根結(jié)點；對于左、右子樹中的結(jié)點仍然是按照后序遍歷方式訪問。逐層遍歷二叉樹：從第1層開始依次對每層中的結(jié)點按照從左至右的順序進行訪問。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、A9. 已知一棵二叉樹的中序遍歷結(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

44、、C、E、F、H、I10. 已知一棵二叉樹的先序遍歷結(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、I11. 請簡述哈夫曼樹的結(jié)構(gòu)特性。哈夫曼樹，又稱最優(yōu)二叉樹，是指在由n個葉子結(jié)點構(gòu)成的一類二叉樹中具有最短帶權(quán)路徑長度的二叉樹。12. 請簡述結(jié)點的權(quán)、結(jié)點的帶權(quán)路徑長度、樹的帶權(quán)路徑長度等基本術(shù)語的含義。結(jié)點的權(quán)和結(jié)點的帶權(quán)路徑長度：在實際應用中，往往給樹中的結(jié)點賦予一個具有某種意義的實數(shù)，該實數(shù)就稱為是結(jié)點的權(quán)。結(jié)點的帶權(quán)路徑長度是指從樹根到該結(jié)點的路徑長度與結(jié)點的權(quán)的乘積。樹的帶權(quán)路

45、徑長度：是指樹中所有葉子結(jié)點的帶權(quán)路徑長度之和，記為（其中，n為葉子結(jié)點的數(shù)目，Wi為第i個葉子結(jié)點的權(quán)，Li為根結(jié)點到第i個葉子結(jié)點的路徑長度，可知WiLi為第i個葉子結(jié)點的帶權(quán)路徑長度）。13. 請簡述哈夫曼樹的構(gòu)造方法。哈夫曼樹的構(gòu)造方法如下：（a）已知n個權(quán)值為Wi（i=1, 2, , n）的結(jié)點，將每個結(jié)點作為根結(jié)點生成n棵只有根結(jié)點的二叉樹Ti，形成森林F=T1, T2, , Tn。（b）從森林F中選出根結(jié)點權(quán)值最小的兩棵二叉樹Tp和Tq，并通過添加新的根結(jié)點將它們合并為一棵新二叉樹，新二叉樹中Tp和Tq分別作為根結(jié)點的左子樹和右子樹，且根結(jié)點的權(quán)值等于Tp和Tq兩棵二叉樹的根結(jié)點

46、權(quán)值之和。以合并后生成的新二叉樹替代森林F中的原有二叉樹Tp和Tq。重復該步驟直至森林F中只存在一棵二叉樹。14. 請簡述哈夫曼碼的作用及其編碼方法。哈夫曼編碼是指將用其他編碼法表示的字符序列轉(zhuǎn)成用哈夫曼碼表示以減少存儲空間，其具體方法為：（a）以要編碼的字符集C=c1, c2, , cn作為葉子結(jié)點、字符出現(xiàn)的頻度或次數(shù)W=w1, w2, , wn作為結(jié)點的權(quán)，構(gòu)造哈夫曼樹。（b）規(guī)定哈夫曼樹中，從根結(jié)點開始，雙親結(jié)點到左孩子結(jié)點的分支標為0，雙親結(jié)點到右孩子結(jié)點的分支標為1。從根結(jié)點到某一葉子結(jié)點經(jīng)過的分支形成的編碼即是該葉子結(jié)點所對應字符的哈夫曼碼。15. 請簡述樹的四種常用表示方式。雙

47、親表示法：在孩子結(jié)點中設(shè)置一個指針域記錄其雙親結(jié)點的存儲位置。孩子表示法：在雙親結(jié)點中設(shè)置指向孩子結(jié)點的指針域來表示一棵樹。孩子雙親表示法：綜合了孩子表示法和雙親表示法的特點，既在孩子結(jié)點中設(shè)置記錄雙親結(jié)點位置的指針域，又在雙親結(jié)點中設(shè)置記錄孩子結(jié)點位置的指針域。孩子兄弟表示法：又稱為二叉鏈表表示法，與二叉樹的二叉鏈表表示法存儲結(jié)構(gòu)完全相同，只是結(jié)點中指針域的含義有所不同（一個指針域指向該結(jié)點的第一個孩子結(jié)點，另一個指針域指向該結(jié)點的下一個兄弟結(jié)點）。16. 請簡述森林轉(zhuǎn)換為二叉樹的具體步驟。將森林中的每棵樹都用二叉鏈表表示法表示，并將各棵二叉樹的根結(jié)點看做是兄弟結(jié)點，在它們之間加上連線；將結(jié)

48、點到第一個孩子結(jié)點的連線作為左子樹的邊，結(jié)點到兄弟結(jié)點的連線作為右子樹的邊。17. 請簡述二叉樹轉(zhuǎn)化為樹或森林的具體步驟。將一個結(jié)點左子樹的邊作為該結(jié)點指向第一個孩子結(jié)點的連線，右子樹的邊作為該結(jié)點到兄弟結(jié)點的連線；在雙親結(jié)點和它的各孩子結(jié)點之間加上連線，并刪除兄弟結(jié)點之間的連線，得到一棵樹或一個包含若干棵樹的森林。第6章 圖1. 請簡述圖的結(jié)構(gòu)特性。圖G由頂點（圖中通常將結(jié)點稱為頂點）的非空有限集合V和邊的集合E組成，記為G=(V, E)。每一個頂點偶對就是圖中的一條邊，所以，E用于表示V上的連接關(guān)系。在一個圖中，至少要包含一個頂點，但可以沒有任何邊。2. 請解釋有向圖、無向圖、弧、弧尾、弧

49、頭、頂點的度、頂點的入度、頂點的出度、路徑、路徑長度、回路、簡單回路、連通圖、單向連通圖、強連通圖、子圖、連通分量、強連通分量、權(quán)、帶權(quán)圖、生成樹、最小生成樹等基本術(shù)語的含義。有向圖、弧、弧尾和弧頭：若E(G)中的頂點偶對是有序的，則這些有序偶對就形成了有向邊，此時圖G稱為有向圖。其中，有向邊也簡稱為弧。在有向圖G中，對于一條從頂點vi到頂點vj的弧，記為<vi, vj>并有<vi, vj>E(G)，稱vi為弧尾，vj為弧頭。無向圖：若E(G)中的頂點偶對是無序的，則這些無序偶對就形成了無向邊，此時圖G稱為無向圖。頂點的度、頂點的入度和頂點的出度：在無向圖中，與頂點vi

50、相關(guān)聯(lián)的邊的數(shù)目稱為頂點vi的度。在有向圖中，以頂點vi為弧頭的弧的數(shù)目稱為頂點vi的入度；以頂點vi為弧尾的弧的數(shù)目稱為vi的出度；頂點vi的入度和出度之和稱為vi的度。路徑和路徑長度：在圖G中，若存在一個頂點序列(, , )，使得對于任意0j<n-1有（若G為有向圖）或（若G為無向圖），則該序列是從頂點到頂點的一條路徑。一條路徑中邊的數(shù)目稱為路徑長度。回路和簡單回路：在一條路徑中，若組成路徑的頂點序列中第一個頂點與最后一個頂點相同，則該路徑稱為回路（或環(huán)）；在一個回路中，若除第一個頂點與最后一個頂點外，其他頂點只出現(xiàn)一次，則該回路稱為簡單回路（或簡單環(huán)）。連通圖：無向圖G中，若任意兩

51、個頂點都是連通的，則稱G為連通圖。單向連通圖和強連通圖：有向圖G中，若任意兩個頂點都是單向連通的，則稱G是單向連通圖；若任意兩個頂點都是強連通的，則稱G為強連通圖。子圖：對于圖G、G'，若滿足且，則G'是G的子圖。連通分量和強連通分量：一個無向圖的極大連通子圖稱為該無向圖的連通分量；一個有向圖的極大強連通子圖稱為該有向圖的強連通分量。權(quán)和帶權(quán)圖：可以為一個圖中的每條邊標上一個具有某種意義的實數(shù)，該實數(shù)就稱為是邊的權(quán)。邊上帶權(quán)的圖就稱為帶權(quán)圖。生成樹和最小生成樹：若無向圖G的一個子圖G'是一棵包含圖G所有頂點的樹，則G'稱為圖G的生成樹。在所有形式的生成樹中，邊上

52、的權(quán)之和最小的生成樹，稱為最小生成樹。3. 請列舉可以用圖來描述的實際問題。請參考例6-1和例6-2。4. 請簡述圖的基本操作及各操作的含義。創(chuàng)建圖：創(chuàng)建不包含任何頂點和邊的空圖。對圖作深度優(yōu)先遍歷：類似于樹的先序遍歷，即從某一個頂點開始訪問，訪問后將該頂點去除得到若干子圖，對每個子圖再依次進行深度優(yōu)先遍歷。對圖作廣度優(yōu)先遍歷：類似于樹的逐層遍歷，即先從某一個頂點開始訪問，然后訪問與該頂點相鄰接且未被訪問過的頂點集V1(G)，再訪問與V1(G)中頂點相鄰接且未被訪問過的頂點集V2(G)，重復該過程直至與初始頂點連通的所有頂點都被訪問完。對于非連通圖或非強連通圖，還要從某一個未被訪問的頂點開始重

53、復上一過程，直至所有頂點訪問完畢。獲取頂點數(shù)目：獲取圖中所包含的頂點的數(shù)目。獲取邊的數(shù)目：獲取圖中所包含的邊的數(shù)目。獲取與指定頂點相關(guān)聯(lián)的第一條邊：對無向圖，獲取到與指定頂點相關(guān)聯(lián)的第一條邊；對有向圖，獲取到以指定頂點作為弧尾的第一條弧。不同表示方法獲取到的結(jié)果會有所不同（鄰接矩陣法按頂點編號順序，鄰接壓縮表和鄰接鏈表按邊的添加順序）。獲取與指定邊有相同關(guān)聯(lián)頂點的下一條邊：對無向圖，獲取到與指定邊(nV1,nV2) 有相同關(guān)聯(lián)頂點nV1的下一條邊；對有向圖，獲取到與指定弧<nV1,nV2>有相同弧尾nV1的下一條弧。不同表示方法獲取到的結(jié)果會有所不同（鄰接矩陣法按頂點編號順序，鄰接

54、壓縮表和鄰接鏈表按邊的添加順序）。添加一個頂點：向圖中添加一個新頂點。添加一條邊：對無向圖，向圖中添加一條新邊；對有向圖，向圖中添加一條新弧。獲取一個頂點中存儲的數(shù)據(jù)：根據(jù)頂點編號獲取該頂點中存儲的數(shù)據(jù)。判斷一條邊是否存在：對無向圖，判斷兩個頂點nV1和nV2之間是否存在邊；對有向圖，判斷是否存在從頂點nV1到頂點nV2的弧。設(shè)置一條邊的權(quán)：對無向圖，設(shè)置指定邊(nV1,nV2)上的權(quán)；對有向圖，設(shè)置指定弧<nV1,nV2>上的權(quán)。獲取一條邊的權(quán)：對無向圖，獲取指定邊(nV1,nV2)上的權(quán)；對有向圖，獲取指定弧<nV1,nV2>上的權(quán)。5. 請簡述圖的三種常用表示方法

55、。鄰接矩陣法：用矩陣來表示各頂點之間的連接關(guān)系。對于有n個頂點的圖G=(V, E)，其鄰接矩陣A為n*n的方陣，元素Aij（0i,j<n）定義為：其中，wij為邊(vi, vj)或<vi, vj>上的權(quán)。鄰接壓縮表：鄰接矩陣的一種壓縮表示形式，使用3個順序表來表示圖中頂點之間的連接關(guān)系和權(quán)。設(shè)圖中共有n個頂點v0, v1, , vn-1，3個順序表分別為s、w和h。在s中依次記錄與頂點vi（i = 0, 1, , n-1）相關(guān)聯(lián)的頂點；在w中依次記錄s中存儲的各條邊的權(quán)；在h中依次記錄與頂點vi相關(guān)聯(lián)的頂點在s中的起始存儲位置。鄰接鏈表：圖的一種鏈式存儲結(jié)構(gòu)。每個頂點中設(shè)置一

56、個指向鏈表頭的指針，在鏈表中保存與該頂點相鄰接的頂點信息（包括頂點位置及兩個頂點形成的邊的權(quán)）。6. 請簡述圖的兩種常用遍歷方法及每一種遍歷方法中結(jié)點的訪問順序。廣度優(yōu)先遍歷：類似于樹的逐層遍歷，即先從某一個頂點開始訪問，然后訪問與該頂點相鄰接且未被訪問過的頂點集V1(G)，再訪問與V1(G)中頂點相鄰接且未被訪問過的頂點集V2(G)，重復該過程直至與初始頂點連通的所有頂點都被訪問完。對于非連通圖或非強連通圖，還要從某一個未被訪問的頂點開始重復上一過程，直至所有頂點訪問完畢。深度優(yōu)先遍歷：類似于樹的先序遍歷，即從某一個頂點開始訪問，訪問后將該頂點去除得到若干子圖，對每個子圖再依次進行深度優(yōu)先遍歷。7. 請列舉最小生成樹和最短路徑可以用于解決什么應用問題。請參考例6-1和例6-2。8. 請簡述Prim算法的作用和具體步驟。Prim算法用于最小生成樹問題求解。對于有n個頂點的圖G=(V, E)，Prim算法從空樹T開始，按照以下規(guī)則將n個頂點和n-1條邊依次添加到樹中，形成最小生成樹：（a）從某一頂點v0'開始，將該頂點作為樹的根結(jié)點加入到T中，使得T中的數(shù)據(jù)元素集合D=v0'，數(shù)據(jù)元素關(guān)系集合R=。（b）對于一個頂點在集合D中、另一個頂點在集合V-D中的那些邊，找出權(quán)最小的一條邊，將該邊在集合V-D