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

1、第1章 概 論1.數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)類型的含義分別是什么？數(shù)據(jù)：對(duì)客觀事物的符號(hào)表示，在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并由計(jì)算機(jī)程序處理的符號(hào)的總稱。數(shù)據(jù)元素：數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體考慮。數(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ù)在存儲(chǔ)時(shí)所需要的容量各不相同，不同的數(shù)據(jù)就必須要分配不同大小的內(nèi)存空間來存儲(chǔ)，所有就要將數(shù)據(jù)劃分成不同的數(shù)據(jù)類型。數(shù)據(jù)類型包含取值范圍和基本運(yùn)算等概念。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)包含下面兩個(gè)方面的信息： 數(shù)據(jù)元素的信息； 各數(shù)據(jù)元素之間的關(guān)系。物理結(jié)構(gòu)：也叫儲(chǔ)存結(jié)構(gòu)，是指邏輯結(jié)構(gòu)的存儲(chǔ)表示，即數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式，包括結(jié)點(diǎn)的數(shù)據(jù)和結(jié)點(diǎn)間關(guān)系的存儲(chǔ)表示。數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)是密不可分的，一個(gè)操作算法的設(shè)計(jì)取決于所選定的邏輯結(jié)構(gòu)，而算法的實(shí)現(xiàn)依賴于所采與的存儲(chǔ)結(jié)構(gòu)。采用不同的存儲(chǔ)結(jié)構(gòu)，其數(shù)據(jù)處理的效率是不同的。因此，在進(jìn)行數(shù)據(jù)處理時(shí)，針對(duì)不同問題，選擇合理的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)非常重要。3.數(shù)據(jù)結(jié)構(gòu)的主要操作包括哪些？對(duì)于

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

4、型，因此，不論ADT的內(nèi)部結(jié)構(gòu)如何變化，只要其數(shù)據(jù)結(jié)構(gòu)的特性不變，都不影響其外部使用。對(duì)抽象數(shù)據(jù)類型的描述一般用（D,R,P)三元組表示，抽象數(shù)據(jù)類型的定義格式為：ADT<抽象數(shù)據(jù)類型名>數(shù)據(jù)對(duì)象D：<數(shù)據(jù)對(duì)象的定義>數(shù)據(jù)關(guān)系R：<數(shù)據(jù)關(guān)系的定義>基本操作P：<基本操作的定義>ADT<抽象數(shù)據(jù)類型名>其中，D是數(shù)據(jù)對(duì)象，R是D上的關(guān)系集，P是對(duì)D的基本操作集。數(shù)據(jù)對(duì)象和數(shù)據(jù)關(guān)系的定義用偽代碼來描述?；静僮鞯亩x格式為：基本操作名（參數(shù)表）初始條件：<初始條件描述>操作結(jié)果：<操作結(jié)果描述>初始條件說明操作執(zhí)行

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

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

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

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

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

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

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

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

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

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

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

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

17、nt(const T&x); /返回x出現(xiàn)的次數(shù)在教材的【描述2-2】中，增加查找重復(fù)元素個(gè)數(shù)的成員函數(shù)的實(shí)現(xiàn)：/實(shí)現(xiàn)統(tǒng)計(jì)重復(fù)元素個(gè)數(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;在順序表中實(shí)現(xiàn)統(tǒng)計(jì)重復(fù)元素個(gè)數(shù)的操作：在教材的【描述2-3】中，增加一個(gè)統(tǒng)計(jì)重復(fù)元素個(gè)數(shù)的成員函數(shù)：int Count(const T&x); /返回x出現(xiàn)的次數(shù)

18、在教材的【描述2-4】中，增加查找重復(fù)元素個(gè)數(shù)的成員函數(shù)的實(shí)現(xiàn)：/實(shí)現(xiàn)統(tǒng)計(jì)重復(fù)元素個(gè)數(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章 棧和隊(duì)列1具有什么特征的數(shù)據(jù)結(jié)構(gòu)被稱為棧和隊(duì)列？先進(jìn)后出、棧頂、棧底、先進(jìn)先出、隊(duì)頭、隊(duì)尾的概念是什么？棧：一種插入和刪

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

20、后移動(dòng)一個(gè)元素空間（元素大?。瑢⒁迦氲脑胤湃雝op指針指向的內(nèi)存單元中。3. 一個(gè)棧的輸入序列為1、2、3，試給出全部可能的出棧序列?？煞譃槿N情況：、當(dāng)只有一個(gè)存儲(chǔ)空間時(shí)，只有一種出棧序列：1、2、3.、當(dāng)有兩個(gè)存儲(chǔ)空間時(shí)，有：1、2、3， 2、1、3， 2、3、1等3種出棧序列、當(dāng)存儲(chǔ)空間大于等于三個(gè)時(shí)，有：1、2、3， 2、1、3， 2、3、1， 3、2、1等4種出棧序列。4循環(huán)隊(duì)列的優(yōu)點(diǎn)是什么？在循環(huán)隊(duì)列中，僅依據(jù)頭尾指針相等，無法判斷隊(duì)列是“空”還是“滿”。要解決這個(gè)問題，常用的兩種方法是什么？循環(huán)隊(duì)列的優(yōu)點(diǎn)有兩點(diǎn)：一是可以避免發(fā)生順序隊(duì)列的“假上溢”現(xiàn)象；二是充分利用隊(duì)列的存

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

22、Out）的實(shí)際問題都可以用隊(duì)列表示。如日常中的排隊(duì)問題，隊(duì)列的應(yīng)用主要有：操作系統(tǒng)中各種資源請(qǐng)求排隊(duì)和各種緩沖區(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ù)的邏輯位置，任意兩個(gè)數(shù)據(jù)的index都不相同；value表示數(shù)據(jù)元素的值。2.設(shè)有二維數(shù)組a56，每個(gè)元素占相鄰的8個(gè)字節(jié)，存儲(chǔ)器按字節(jié)編址，已知a的起始地址是1000，試計(jì)算：（1）數(shù)組a的最后一個(gè)元素起始地址；1000+（30-1）*8=

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

24、個(gè)數(shù)。采用壓縮存儲(chǔ)技術(shù)主要是為了節(jié)省空間。6.設(shè)A和B是稀疏矩陣，都以三元組作為存儲(chǔ)結(jié)構(gòu)，請(qǐng)寫出矩陣相加的算法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<<"請(qǐng)輸入矩陣的行、列數(shù)：n"cin>>row>>col;cout<<"請(qǐng)輸入矩陣A的元素：n"for(i=0;i<row;i+)for(j=0;j<col;j+)cin>>Aij; cout<<"請(qǐng)輸入矩陣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.簡(jiǎn)述字符串與一維字符型數(shù)組的區(qū)別與聯(lián)系。字符串簡(jiǎn)稱串，它是一種以字符為元素的特殊線性表。字符串可以看成是以字符為元素的一維數(shù)組。具體實(shí)現(xiàn)時(shí)，在C/C+中的字符串使用為字符

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

33、再分解的元素），也可以是另一個(gè)廣義表。11.一個(gè)廣義表是(a, (a, b, c), d, e, (m, n),(w, (i, j), x)，請(qǐng)問該廣義表的長(zhǎng)度、深度分別是多少？請(qǐng)畫出該廣義表的單鏈表存儲(chǔ)結(jié)構(gòu)示意圖。該廣義表的深度是3，長(zhǎng)度是6。該廣義表的單鏈表存儲(chǔ)結(jié)構(gòu)示意圖如下：12請(qǐng)列舉出一些可以歸納成數(shù)組、矩陣、字符串和廣義表數(shù)據(jù)結(jié)構(gòu)的實(shí)際問題。線性表的順序存儲(chǔ)、學(xué)生編號(hào)和姓名的問題、各班級(jí)的學(xué)生編號(hào)和姓名的問題等，都可以歸結(jié)為數(shù)組。不同物品所需原材料的數(shù)量、不同產(chǎn)地原材料的價(jià)格、不同類型的住宅需要的物品數(shù)量等，不同學(xué)生的計(jì)算機(jī)成績(jī)，不同職工的工資等都可以歸結(jié)為矩陣。學(xué)生的姓名和學(xué)號(hào)、學(xué)

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

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

36、條路徑上的分支數(shù)目稱為路徑長(zhǎng)度，從樹的根結(jié)點(diǎn)到其他各個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和稱為樹的路徑長(zhǎng)度。葉子結(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)。孩子和雙親：在樹中，一個(gè)結(jié)點(diǎn)的后繼結(jié)點(diǎn)稱為該結(jié)點(diǎn)的孩子，相應(yīng)地，一個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)稱為該結(jié)點(diǎn)的雙親，即一個(gè)結(jié)點(diǎn)是其孩子結(jié)點(diǎn)的雙親、其雙親結(jié)點(diǎn)的孩子。兄弟和堂兄弟：同一雙親的孩子結(jié)點(diǎn)之間互稱為兄弟，不同雙親但在同一層的結(jié)點(diǎn)之間互稱為堂兄弟。祖先和子孫：從樹的根結(jié)點(diǎn)到某一個(gè)結(jié)點(diǎn)X的路徑上經(jīng)歷的所有結(jié)點(diǎn)（包括根結(jié)點(diǎn)但不包括結(jié)點(diǎn)X）稱為結(jié)點(diǎn)X的祖先，以某一結(jié)點(diǎn)

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

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

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

40、根結(jié)點(diǎn)左子樹，再訪問根結(jié)點(diǎn)，最后訪問右子樹；對(duì)于左、右子樹中的結(jié)點(diǎn)仍然是按照中序遍歷方式訪問。后序遍歷二叉樹：也稱為后根遍歷，其訪問方式遞歸定義如下：對(duì)于一棵二叉樹，先訪問根結(jié)點(diǎn)的左子樹，后訪問右子樹，最后訪問根結(jié)點(diǎn)；對(duì)于左、右子樹中的結(jié)點(diǎn)仍然是按照后序遍歷方式訪問。逐層遍歷二叉樹：從第1層開始依次對(duì)每層中的結(jié)點(diǎn)按照從左至右的順序進(jìn)行訪問。獲取指定結(jié)點(diǎn)的雙親結(jié)點(diǎn)：根據(jù)指定結(jié)點(diǎn)獲取其雙親結(jié)點(diǎn)。在順序表示中，可以直接根據(jù)指定結(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)（包括指

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

42、親結(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. 請(qǐng)簡(jiǎn)述二叉樹的四種遍歷方式及每一種遍歷方式中結(jié)點(diǎn)的訪問順序。先序遍歷二叉樹：也稱為先根遍歷，其訪問方式遞歸定義如下：對(duì)于一棵二叉樹，先訪問其根結(jié)點(diǎn)，再訪問根結(jié)點(diǎn)的左、右子樹；對(duì)于左、右子樹中的結(jié)點(diǎn)仍然是按照先序遍歷方式訪問，即先訪問根結(jié)點(diǎn)，再訪問根結(jié)點(diǎn)的左、右子樹。中序遍歷二叉樹：也稱為中根遍歷，其訪問方式遞歸定義如下：對(duì)于一棵二叉樹，先訪問根結(jié)點(diǎn)左子樹，再訪問根結(jié)點(diǎn)，最后訪問右子樹；對(duì)于左、右子樹中的結(jié)點(diǎn)仍然是按照中序遍歷方式訪問。

43、后序遍歷二叉樹：也稱為后根遍歷，其訪問方式遞歸定義如下：對(duì)于一棵二叉樹，先訪問根結(jié)點(diǎn)的左子樹，后訪問右子樹，最后訪問根結(jié)點(diǎn)；對(duì)于左、右子樹中的結(jié)點(diǎn)仍然是按照后序遍歷方式訪問。逐層遍歷二叉樹：從第1層開始依次對(duì)每層中的結(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，請(qǐng)給出該二叉樹的后序遍歷結(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，請(qǐng)給出該二叉樹的先序遍歷結(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，請(qǐng)給出該二叉樹的中序遍歷結(jié)果。D、G、B、A、E、C、H、F、I11. 請(qǐng)簡(jiǎn)述哈夫曼樹的結(jié)構(gòu)特性。哈夫曼樹，又稱最優(yōu)二叉樹，是指在由n個(gè)葉子結(jié)點(diǎn)構(gòu)成的一類二叉樹中具有最短帶權(quán)路徑長(zhǎng)度的二叉樹。12. 請(qǐng)簡(jiǎn)述結(jié)點(diǎn)的權(quán)、結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度、樹的帶權(quán)路徑長(zhǎng)度等基本術(shù)語的含義。結(jié)點(diǎn)的權(quán)和結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度：在實(shí)際應(yīng)用中，往往給樹中的結(jié)點(diǎn)賦予一個(gè)具有某種意義的實(shí)數(shù)，該實(shí)數(shù)就稱為是結(jié)點(diǎn)的權(quán)。結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度是指從樹根到該結(jié)點(diǎn)的路徑長(zhǎng)度與結(jié)點(diǎn)的權(quán)的乘積。樹的帶權(quán)路

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

46、權(quán)值之和。以合并后生成的新二叉樹替代森林F中的原有二叉樹Tp和Tq。重復(fù)該步驟直至森林F中只存在一棵二叉樹。14. 請(qǐng)簡(jiǎn)述哈夫曼碼的作用及其編碼方法。哈夫曼編碼是指將用其他編碼法表示的字符序列轉(zhuǎn)成用哈夫曼碼表示以減少存儲(chǔ)空間，其具體方法為：（a）以要編碼的字符集C=c1, c2, , cn作為葉子結(jié)點(diǎn)、字符出現(xiàn)的頻度或次數(shù)W=w1, w2, , wn作為結(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)所對(duì)應(yīng)字符的哈夫曼碼。15. 請(qǐng)簡(jiǎn)述樹的四種常用表示方式。雙

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

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

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

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

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

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

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

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

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

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