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

1、-. z.第1章 概 論1.數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)構(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ù)構(gòu)造：數(shù)據(jù)元素之間的關(guān)系+運(yùn)算，是以數(shù)據(jù)為成員的構(gòu)造，是帶構(gòu)造的數(shù)據(jù)元素的集合，數(shù)據(jù)元素之間存在著一種或多種特定的關(guān)系。數(shù)據(jù)類型：數(shù)據(jù)類型是用來區(qū)分不同的數(shù)據(jù)；由于數(shù)據(jù)在存儲(chǔ)時(shí)所需要的容量各不一樣，不同的數(shù)據(jù)就必須要分配不同大小的存空間來存儲(chǔ)，所有就要將數(shù)據(jù)劃分成不同的數(shù)據(jù)類型。數(shù)據(jù)類型包含取值圍和根本運(yùn)算等概念。2.什么是數(shù)據(jù)的邏輯構(gòu)造？什么是數(shù)據(jù)的物理構(gòu)

2、造？數(shù)據(jù)的邏輯構(gòu)造與物理構(gòu)造的區(qū)別和聯(lián)系是什么？邏輯構(gòu)造：數(shù)據(jù)的邏輯構(gòu)造定義了數(shù)據(jù)構(gòu)造中數(shù)據(jù)元素之間的相互邏輯關(guān)系。數(shù)據(jù)的邏輯構(gòu)造包含下面兩個(gè)方面的信息： = 1 * GB3 數(shù)據(jù)元素的信息； = 2 * GB3 各數(shù)據(jù)元素之間的關(guān)系。物理構(gòu)造：也叫儲(chǔ)存構(gòu)造，是指邏輯構(gòu)造的存儲(chǔ)表示，即數(shù)據(jù)的邏輯構(gòu)造在計(jì)算機(jī)存儲(chǔ)空間中的存放形式，包括結(jié)點(diǎn)的數(shù)據(jù)和結(jié)點(diǎn)間關(guān)系的存儲(chǔ)表示。數(shù)據(jù)的邏輯構(gòu)造和存儲(chǔ)構(gòu)造是密不可分的，一個(gè)操作算法的設(shè)計(jì)取決于所選定的邏輯構(gòu)造，而算法的實(shí)現(xiàn)依賴于所采與的存儲(chǔ)構(gòu)造。采用不同的存儲(chǔ)構(gòu)造，其數(shù)據(jù)處理的效率是不同的。因此，在進(jìn)展數(shù)據(jù)處理時(shí)，針對(duì)不同問題，選擇合理的邏輯構(gòu)造和存儲(chǔ)構(gòu)造非常

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

4、數(shù)據(jù)類型，因此，不管ADT的部構(gòu)造如何變化，只要其數(shù)據(jù)構(gòu)造的特性不變，都不影響其外部使用。對(duì)抽象數(shù)據(jù)類型的描述一般用D,R,P)三元組表示，抽象數(shù)據(jù)類型的定義格式為：ADT數(shù)據(jù)對(duì)象D：數(shù)據(jù)關(guān)系R：根本操作P：ADT其中，D是數(shù)據(jù)對(duì)象，R是D上的關(guān)系集，P是對(duì)D的根本操作集。數(shù)據(jù)對(duì)象和數(shù)據(jù)關(guān)系的定義用偽代碼來描述。根本操作的定義格式為：根本操作名參數(shù)表初始條件：操作結(jié)果：初始條件說明操作執(zhí)行之前數(shù)據(jù)構(gòu)造和參數(shù)應(yīng)滿足的條件；操作結(jié)果說明操作完成后，數(shù)據(jù)構(gòu)造的變化狀況和應(yīng)返回的結(jié)果。5.什么是算法？算法的根本特征是什么？算法：是在有限的步驟解決數(shù)學(xué)問題的過程，是以一步接一步的方式來詳細(xì)描述計(jì)算機(jī)如何

5、將輸入轉(zhuǎn)化為所要求的輸出的過程，即算法是對(duì)計(jì)算機(jī)上執(zhí)行的計(jì)算過程的具體描述。一個(gè)有效的算法必須滿足的五個(gè)重要特性： = 1 * GB3 有窮性：算法必須能在有限的時(shí)間做完，即在任何情況下，算法必須能在執(zhí)行有限個(gè)步驟之后終止，都不能陷入無窮循環(huán)中。 = 2 * GB3 確定性：算法中的每一個(gè)步驟，必須經(jīng)過明確的定義，并且能夠被計(jì)算機(jī)所理解和執(zhí)行，而不能是抽象和模糊的概念，更不允許有二義性。 = 3 * GB3 輸入：算法有0個(gè)或多個(gè)輸入值，來描述算法開場前運(yùn)算對(duì)象的初始情況，這是算法執(zhí)行的起點(diǎn)或是依據(jù)。0個(gè)輸入是指算法本身給出了運(yùn)算對(duì)象的初始條件。 = 4 * GB3 輸出：算法至少有1個(gè)或多個(gè)

6、輸出值，反映對(duì)運(yùn)算對(duì)象的處理結(jié)果，沒有輸出的算法沒有任何意義。 = 5 * GB3 可行性：算法中要做的運(yùn)算都是根本運(yùn)算，能夠被準(zhǔn)確地進(jìn)展。即算法中執(zhí)行的任何計(jì)算都可以被分解為根本的運(yùn)算步，每個(gè)根本的運(yùn)算步都可以在有限的時(shí)間完成。6.什么是算法分析？算法分析主要考慮哪幾方面的容？算法的研究與實(shí)際問題直接相關(guān)，用來解一個(gè)問題可以有很多不同的算法，他們之間的效果可能會(huì)有很大差異。算法設(shè)計(jì)者最關(guān)心的就是什么是有效的算法，如何評(píng)價(jià)一個(gè)算法的優(yōu)劣，如何從多種算法中選擇好的算法。除了要首先考慮算法的正確性外，還要分析和評(píng)價(jià)算法的性能。分析和評(píng)價(jià)算法的性能主要要考慮以下兩個(gè)方面： = 1 * GB3 時(shí)間代

7、價(jià)：執(zhí)行算法所消耗的時(shí)間。一個(gè)好的算法首先應(yīng)該比其他算法的運(yùn)行時(shí)間代價(jià)要小。算法的時(shí)間代價(jià)的大小用算法的時(shí)間復(fù)雜度來度量。 = 2 * GB3 空間代價(jià)：執(zhí)行算法所消耗的存儲(chǔ)空間，主要是輔助空間。算法運(yùn)行所需的空間消耗是衡量算法優(yōu)劣的另一個(gè)重要因素。算法的空間代價(jià)的大小用算法的空間復(fù)雜度來度量。7.分析下面算法的時(shí)間復(fù)雜度。1答：時(shí)間復(fù)雜度為n22時(shí)間復(fù)雜度：n3時(shí)間復(fù)雜度：4時(shí)間復(fù)雜度：n25時(shí)間復(fù)雜度：O(log2n)8.算法設(shè)計(jì)中的遞歸、窮舉、遞推和迭代等算法的根本思想是什么？遞推法：是利用問題本身所具有的一種遞推關(guān)系求解問題的一種方法。它把問題求解分成假設(shè)干步，找出相鄰幾步的關(guān)系，從而

8、到達(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ī)模更小的問題，并從這些更小問題的解構(gòu)造出較大規(guī)模問題的解。窮舉法：窮舉搜索法也稱窮舉法或搜索法是對(duì)

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

10、策一旦做出，就不能再更改。它是通過假設(shè)干次的貪心選擇而得出最優(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)程中，先選擇*一種可能情況向前探索，當(dāng)發(fā)現(xiàn)所選用的試探性操作不是最正確選擇，需退回一步，重新選擇繼續(xù)進(jìn)展試探，

11、直到找到問題的解或者證明問題無解。分支定界策略也經(jīng)常被稱為分支限界策略，它的根本思想是：首先確定目標(biāo)值的上下界，然后一邊搜索一邊剪掉空間樹的*些不可能產(chǎn)生最優(yōu)解的分支，提高搜索效率。-. z.第二章 線性表1具有什么特征的數(shù)據(jù)構(gòu)造被稱為線性表？線性表是一種最常用、最簡單的典型線性數(shù)據(jù)構(gòu)造，應(yīng)用非常廣泛。線性表是由nn0個(gè)數(shù)據(jù)元素組成的一個(gè)有限序列，線性表中數(shù)據(jù)元素的個(gè)數(shù)n稱為線性表的長度。當(dāng)n=0時(shí)，稱為空表。對(duì)于非空線性表，數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系，具體特性如下：第一個(gè)數(shù)據(jù)元素沒有前驅(qū)；最后一個(gè)數(shù)據(jù)元素沒有后繼外；其他數(shù)據(jù)元素都是首尾相接、有且只有一個(gè)前驅(qū)和后繼。2如何實(shí)現(xiàn)線性表的順序存

12、儲(chǔ)構(gòu)造？把線性表的結(jié)點(diǎn)按邏輯順序依次存放在一組地址連續(xù)的存儲(chǔ)單元里就構(gòu)成了線性表的順序存儲(chǔ)，采用順序存儲(chǔ)構(gòu)造的線性表簡稱順序表。線性表的順序存儲(chǔ)構(gòu)造有如下特點(diǎn)：線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的；線性表的邏輯順序與物理順序一致；數(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如何實(shí)現(xiàn)線性表的4種鏈?zhǔn)酱鎯?chǔ)構(gòu)造？數(shù)據(jù)構(gòu)造中的每一個(gè)數(shù)據(jù)元素對(duì)應(yīng)于一個(gè)存儲(chǔ)單元，這種存儲(chǔ)單元稱為存儲(chǔ)結(jié)點(diǎn)，簡稱結(jié)

13、點(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)按其邏輯構(gòu)造連接在一起的數(shù)據(jù)存儲(chǔ)構(gòu)造，稱為鏈?zhǔn)酱鎯?chǔ)構(gòu)造。單向鏈表：在線性鏈表中，用一個(gè)專門的指針指向線性表中第一個(gè)結(jié)點(diǎn)，每一個(gè)結(jié)點(diǎn)的指針都指向它的下一個(gè)邏輯結(jié)點(diǎn)，線性鏈表的最后一個(gè)結(jié)點(diǎn)的指針為空用NULL或0表示，表示鏈表終止，這樣的線性鏈表稱為單向鏈表。下列圖是單向鏈表示意圖。firste1e2 ei en NULLNULL NULL線性表的單向鏈?zhǔn)酱鎯?chǔ)循環(huán)鏈表：

14、將單向鏈表最后一個(gè)結(jié)點(diǎn)的指針指向頭結(jié)點(diǎn)，這樣整個(gè)鏈表就構(gòu)成一個(gè)循環(huán)，這種鏈?zhǔn)酱鎯?chǔ)構(gòu)造稱為單向循環(huá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)；另一個(gè)指針指向其后繼結(jié)點(diǎn)。雙向鏈表結(jié)點(diǎn)的構(gòu)造下列圖a所示。e2enb雙向鏈表e1e2enc雙向循環(huán)鏈表prev data

15、 ne*ta雙向鏈表結(jié)點(diǎn)構(gòu)造firstfirste1end雙向循環(huán)鏈表：如果將雙向鏈表第一個(gè)結(jié)點(diǎn)的prev指針指向最后一個(gè)結(jié)點(diǎn)，將最后一個(gè)結(jié)點(diǎn)的ne*t指針與指向第一個(gè)結(jié)點(diǎn)，就構(gòu)成了雙向循環(huán)鏈表。下列圖b和c是雙向鏈表和雙向循環(huán)表的邏輯構(gòu)造示意圖。圖雙向鏈表結(jié)點(diǎn)構(gòu)造及雙向鏈表4順序表和線性鏈表分別有哪些優(yōu)點(diǎn)和缺點(diǎn)？線性表的順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)比擬比擬容順序存儲(chǔ)鏈?zhǔn)酱鎯?chǔ)結(jié)點(diǎn)存儲(chǔ)空間少不需要為表示結(jié)點(diǎn)的邏輯關(guān)系增加開銷多需要增加指針域來表示結(jié)點(diǎn)之間的邏輯關(guān)系空間利用率低采用數(shù)組，按表的最大長度靜態(tài)分配存儲(chǔ)空間高根據(jù)表的實(shí)際長度動(dòng)態(tài)分配存儲(chǔ)空間插入、刪除操作慢需要大量移動(dòng)元素快僅更改指針指向，不需要移

16、動(dòng)元素訪問元素快直接訪問慢通過指針移動(dòng)才能訪問實(shí)現(xiàn)難易程度相對(duì)容易基于數(shù)組操作，一般高級(jí)語言都提供數(shù)組類型相對(duì)困難基于指針操作5請(qǐng)列舉出一些線性表問題的實(shí)例。= 1 * GB3按員工號(hào)排序的員工根本情況表；= 2 * GB3奧運(yùn)會(huì)各項(xiàng)比賽日程；= 3 * GB3按*記錄的學(xué)生的成績單；等等。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 Count(const T&*); /返回*出現(xiàn)的次數(shù)在教材的【描述2-2】中，增加查找重復(fù)元素個(gè)數(shù)的成員函數(shù)的實(shí)現(xiàn)：/實(shí)現(xiàn)統(tǒng)計(jì)重復(fù)元素個(gè)數(shù)

17、templateint LinearList:Count(const T& *)int count=0;for (int i=0; ilength; i+)if(elementi=*)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&*); /返回*出現(xiàn)的次數(shù)在教材的【描述2-4】中，增加查找重復(fù)元素個(gè)數(shù)的成員函數(shù)的實(shí)現(xiàn)：/實(shí)現(xiàn)統(tǒng)計(jì)重復(fù)元素個(gè)數(shù)templateint LinkList:Count(const T& *)LinkNode * p=head-ne*t;int

18、 count=0;while (p!=NULL & )if (p-data =*)count+;p=p-ne*t;return count;-. z.第3章 棧和隊(duì)列1具有什么特征的數(shù)據(jù)構(gòu)造被稱為棧和隊(duì)列？先進(jìn)后出、棧頂、棧底、先進(jìn)先出、隊(duì)頭、隊(duì)尾的概念是什么？棧：一種插入和刪除都只能在表的同一端進(jìn)展的線性表。隊(duì)列：一種只允許在表的一端進(jìn)展插入操作，而在表的另一端進(jìn)展刪除操作的線性表。先進(jìn)后出：元素是以e1，e2，en順序進(jìn)入數(shù)據(jù)構(gòu)造，以相反的順序即en，en-1，e1離開數(shù)據(jù)構(gòu)造。棧頂：允許進(jìn)展插入和刪除操作的一端。棧底：棧中與棧頂相對(duì)的另一端。先進(jìn)先出：元素是以e1，e2，en順序進(jìn)入數(shù)據(jù)

19、構(gòu)造，以一樣的順序即e1，e2，en。 離開數(shù)據(jù)構(gòu)造。隊(duì)頭：允許刪除操作的一端。隊(duì)尾：允許插入操作的一端。 2簡述在順序棧的棧頂插入一個(gè)元素的操作過程。在插入元素之前，首先要判斷棧是否為滿，如果棧滿，返回沾滿無法插入等錯(cuò)誤提示信息；否則讓top指針指向當(dāng)前順序棧的棧頂向后移動(dòng)一個(gè)元素空間元素大小，將要插入的元素放入top指針指向的存單元中。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

20、、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ì)列的存儲(chǔ)空間。兩種判斷隊(duì)列是空還是滿的方法：一是約定少用一個(gè)元素空間；二是使用計(jì)數(shù)器size記錄當(dāng)前隊(duì)列的實(shí)際長度。5. 簡述在棧中插入一個(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，Las

21、t 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 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ù)構(gòu)造被稱為數(shù)組？數(shù)組可以看成是形如inde*，value的數(shù)據(jù)集合，其中，inde*是元素的索引，表示數(shù)據(jù)的邏輯位置，任意兩個(gè)數(shù)

22、據(jù)的inde*都不一樣；value表示數(shù)據(jù)元素的值。2.設(shè)有二維數(shù)組a56，每個(gè)元素占相鄰的8個(gè)字節(jié)，存儲(chǔ)器按字節(jié)編址，a的起始地址是1000，試計(jì)算：1數(shù)組a的最后一個(gè)元素起始地址；1000+30-1*8=1232。2按行序優(yōu)先時(shí)，元素a35的起始地址；1000+3*6+5*8=11843按行列序優(yōu)先時(shí)，元素a43的起始地址。1000+3*5+4*8=11523.請(qǐng)簡述數(shù)組和矩陣的關(guān)系。矩陣是指縱橫排列的二維數(shù)據(jù)表格。在高級(jí)語言編程中，通常用二維數(shù)組來描述一個(gè)矩陣，從而可以對(duì)矩陣中的元素進(jìn)展隨機(jī)存取。但矩陣的索引通常從1而不是像數(shù)組那樣從0開場，并且使用Ai，j而不是Ai，j的形式來引用矩陣

23、中的元素。4.矩陣有哪些根本運(yùn)算？矩陣的操作包括轉(zhuǎn)置、加法、減法和乘法等。5.稀疏矩陣的特點(diǎn)是什么？為什么要對(duì)稀疏矩陣采用壓縮存儲(chǔ)技術(shù)？稀疏矩陣的特點(diǎn)是矩陣中非零元素個(gè)數(shù)遠(yuǎn)遠(yuǎn)少于矩陣零元素個(gè)數(shù)。采用壓縮存儲(chǔ)技術(shù)主要是為了節(jié)省空間。6.設(shè)A和B是稀疏矩陣，都以三元組作為存儲(chǔ)構(gòu)造，請(qǐng)寫出矩陣相加的算法C=A+B。/稀疏矩陣的三元組表示#include using namespace std;#define M 50#define N 50#define Ma*Size 20typedef int ElemType; typedef structint r;int c;ElemType d; Tup

24、Node;typedef structint rows;int cols;int nums;TupNode dataMa*Size; TSMatri*;int AMN,BMN;/建立三元組void CreateMat(int AMN,TSMatri* &t,int row,int col)int i,j;t.rows=row;t.cols=col;t.nums=0;for(i=0;iM;i+) for(j=0;jN;j+)if(Aij!=0)t.datat.nums.r=i;t.datat.nums.c=j;t.datat.nums.d=Aij;t.nums+; /矩陣相加int MatAdd

25、(TSMatri* &a,TSMatri* &b,TSMatri* &c) int i=0,j=0,k=0;ElemType v;if(a.rows!=b.rows|a.cols!=b.cols) return 0;c.rows=a.rows;c.cols=a.cols;while(ia.nums & jb.nums)if(a.datai.r=b.dataj.r)if(a.datai.cb.dataj.c) c.datak.r=b.dataj.r;c.datak.c=b.dataj.c;c.datak.d=b.dataj.d;j+;k+; elsev=a.datai.d+b.dataj.d;i

26、f(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.rb.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+; if (i=a.nums)while (jb.nums)c.datak.r=b.dataj.r;c.datak.c=b.dataj.

27、c;c.datak.d=b.dataj.d;j+;k+;if (j=b.nums)while (ia.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(TSMatri* t) int i;if(t.nums=0) cout此矩陣所有元素都為endl;return;coutt.rowstt.colstt.numsendl;cout-endl;for(i=0;it.nums;i+)coutt.datai.rtt.datai.ctt

28、.datai.dendlendl; /主函數(shù)int main()int row,col,i,j;TSMatri* a,b,c;coutrowcol;cout請(qǐng)輸入矩陣A的元素：n;for(i=0;irow;i+)for(j=0;jAij; cout請(qǐng)輸入矩陣B的元素：n;for(i=0;irow;i+)for(j=0;jBij; 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相加后得到

29、的三元組表示為：n;DispMat(c);return 0;7.簡述字符串與一維字符型數(shù)組的區(qū)別與聯(lián)系。字符串簡稱串，它是一種以字符為元素的特殊線性表。字符串可以看成是以字符為元素的一維數(shù)組。具體實(shí)現(xiàn)時(shí)，在C/C+中的字符串使用為字符型數(shù)組來表示。為了便于確定字符串的結(jié)尾，在字符型數(shù)組中使用0就是0作為字符串的截止符。8.列舉一些需要進(jìn)展字符串模式匹配的應(yīng)用場景。例如，在文本編輯中經(jīng)常要查找*一特定單詞或者一段話在整篇文章中出現(xiàn)的位置，按照查找*個(gè)學(xué)生、員工、居民。有效的模式匹配能極提高文本編輯程序的能力。9.列舉幾個(gè)字符串的其他操作。求字符串中*個(gè)子串出現(xiàn)的次數(shù)，刪除滿足條件的子串，字符串字

30、符移位等。10.什么是廣義表？廣義表與線性表的區(qū)別是什么？廣義表又稱列表，是由nn0個(gè)元素組成的有窮序列：GL=e1，e2，en，但與線性表不同的是，廣義表中的元素允許以不同的形式出現(xiàn)：它可以是一個(gè)原子邏輯上不能再分解的元素，也可以是另一個(gè)廣義表。11.一個(gè)廣義表是(a, (a, b, c), d, e, (m, n),(w, (i, j), *)，請(qǐng)問該廣義表的長度、深度分別是多少？請(qǐng)畫出該廣義表的單鏈表存儲(chǔ)構(gòu)造示意圖。該廣義表的深度是3，長度是6。該廣義表的單鏈表存儲(chǔ)構(gòu)造示意圖如下：12請(qǐng)列舉出一些可以歸納成數(shù)組、矩陣、字符串和廣義表數(shù)據(jù)構(gòu)造的實(shí)際問題。線性表的順序存儲(chǔ)、學(xué)生編號(hào)和的問題、

31、各班級(jí)的學(xué)生編號(hào)和的問題等，都可以歸結(jié)為數(shù)組。不同物品所需原材料的數(shù)量、不同產(chǎn)地原材料的價(jià)格、不同類型的住宅需要的物品數(shù)量等，不同學(xué)生的計(jì)算機(jī)成績，不同職工的工資等都可以歸結(jié)為矩陣。學(xué)生的和*、學(xué)?；蚋鲉挝坏拿Q、國家名稱、一篇文章、一個(gè)高級(jí)語言源程序等，都可歸結(jié)為字符串。應(yīng)用高斯消元法求解方程組可以歸結(jié)為廣義表。-. z.第5章 樹和二叉樹1. 請(qǐng)簡述樹、二叉樹、滿二叉樹和完全二叉樹的構(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)的二叉樹，除了最后一層的

32、結(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層完全一樣，只是在第k層上有可能缺少右邊假設(shè)干個(gè)結(jié)點(diǎn)。2. 請(qǐng)解釋結(jié)點(diǎn)的度、樹的度、結(jié)點(diǎn)的層、樹的深度、分支、路徑、路徑長度、樹的路徑長度、葉子結(jié)點(diǎn)、分支結(jié)點(diǎn)、部結(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)的層等于其前

33、驅(qū)結(jié)點(diǎn)的層加1，樹中各結(jié)點(diǎn)的層的最大值稱為樹的深度。分支、路徑、路徑長度和樹的路徑長度：從一個(gè)結(jié)點(diǎn)到其后繼結(jié)點(diǎn)之間的連線稱為一個(gè)分支，從一個(gè)結(jié)點(diǎn)*到另一個(gè)結(jié)點(diǎn)Y所經(jīng)歷的所有分支構(gòu)成結(jié)點(diǎn)*到結(jié)點(diǎn)Y的路徑，一條路徑上的分支數(shù)目稱為路徑長度，從樹的根結(jié)點(diǎn)到其他各個(gè)結(jié)點(diǎn)的路徑長度之和稱為樹的路徑長度。葉子結(jié)點(diǎn)、分支結(jié)點(diǎn)和部結(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)也稱為部結(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)的孩子。兄弟和堂兄弟：

34、同一雙親的孩子結(jié)點(diǎn)之間互稱為兄弟，不同雙親但在同一層的結(jié)點(diǎn)之間互稱為堂兄弟。祖先和子：從樹的根結(jié)點(diǎn)到*一個(gè)結(jié)點(diǎn)*的路徑上經(jīng)歷的所有結(jié)點(diǎn)包括根結(jié)點(diǎn)但不包括結(jié)點(diǎn)*稱為結(jié)點(diǎn)*的祖先，以*一結(jié)點(diǎn)*為根的子樹上的所有非根結(jié)點(diǎn)即除結(jié)點(diǎn)*外稱為結(jié)點(diǎn)*的子。有序樹和無序樹：對(duì)于樹中的任一結(jié)點(diǎn)，如果其各棵子樹的相對(duì)次序被用來表示數(shù)據(jù)之間的關(guān)系，即交換子樹位置會(huì)改變樹所表示的容，則稱該樹為有序樹；否則稱為無序樹。森林：mm0棵互不相交的樹的集合就構(gòu)成了森林。3. 請(qǐng)簡述二叉樹的五條根本性質(zhì)。性質(zhì)1：在二叉樹的第i層上至多有2i-1個(gè)結(jié)點(diǎn)i1。性質(zhì)2：深度為k的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)。性質(zhì)3：在二叉樹中，假設(shè)度

35、為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(wèi)og2n表示不大于log2n的最大整數(shù)。性質(zhì)5：采用順序編號(hào)的完全二叉樹具有如下性質(zhì)：假設(shè)一個(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；反之，假設(shè)一個(gè)非根結(jié)點(diǎn)的編號(hào)為i，則其雙親結(jié)點(diǎn)的編號(hào)為i/2其中i/2表示不大于i/2的最大整數(shù)。4. 請(qǐng)簡述二叉樹的常用操作及各操作的含義。創(chuàng)立一棵空二叉樹：創(chuàng)立一棵沒有任何結(jié)點(diǎn)的二叉樹。在順序表示中，根據(jù)樹的深度為結(jié)點(diǎn)分配存；在二叉鏈表表示中，將指向根結(jié)點(diǎn)的指針賦

36、值為NULL。刪除一棵二叉樹：將二叉樹各結(jié)點(diǎn)所占據(jù)的存釋放。清空二叉樹：將二叉樹的所有結(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)的左、右子樹。中序遍歷二叉樹：也稱為

37、中根遍歷，其訪問方式遞歸定義如下：對(duì)于一棵二叉樹，先訪問根結(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)為

38、根的子樹：將以指定結(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)的元素值修改為指定值。計(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é)點(diǎn)的編號(hào)規(guī)則。順序表示的二叉樹中各結(jié)點(diǎn)的編號(hào)與一樣深度的完全二叉樹中對(duì)應(yīng)結(jié)點(diǎn)的編號(hào)一樣。6. 請(qǐng)簡述二叉鏈表表示和三叉鏈

39、表表示的二叉樹中結(jié)點(diǎn)的構(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. 請(qǐng)簡述二叉樹的四種遍歷方式及每一種遍歷方式中結(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ì)

40、于左、右子樹中的結(jié)點(diǎn)仍然是按照中序遍歷方式訪問。后序遍歷二叉樹：也稱為后根遍歷，其訪問方式遞歸定義如下：對(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)給

41、出該二叉樹的先序遍歷結(jié)果。A、B、D、G、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)簡述哈夫曼樹的構(gòu)造特性。哈夫曼樹，又稱最優(yōu)二叉樹，是指在由n個(gè)葉子結(jié)點(diǎn)構(gòu)成的一類二叉樹中具有最短帶權(quán)路徑長度的二叉樹。12. 請(qǐng)簡述結(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)賦予一個(gè)具有*種意義的實(shí)數(shù)，該實(shí)數(shù)就稱為是結(jié)點(diǎn)的權(quán)。結(jié)點(diǎn)的帶權(quán)路徑長度是指從樹根到該結(jié)點(diǎn)的

42、路徑長度與結(jié)點(diǎn)的權(quán)的乘積。樹的帶權(quán)路徑長度：是指樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和，記為其中，n為葉子結(jié)點(diǎn)的數(shù)目，Wi為第i個(gè)葉子結(jié)點(diǎn)的權(quán)，Li為根結(jié)點(diǎn)到第i個(gè)葉子結(jié)點(diǎn)的路徑長度，可知WiLi為第i個(gè)葉子結(jié)點(diǎn)的帶權(quán)路徑長度。13. 請(qǐng)簡述哈夫曼樹的構(gòu)造方法。哈夫曼樹的構(gòu)造方法如下：an個(gè)權(quán)值為Wii=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兩

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

44、雙親表示法：在孩子結(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ǔ)構(gòu)造完全一樣，只是結(jié)點(diǎn)中指針域的含義有所不同一個(gè)指針域指向該結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)，另一個(gè)指針域指向該結(jié)點(diǎn)的下一個(gè)兄弟結(jié)點(diǎn)。16. 請(qǐng)簡述森林轉(zhuǎn)換為二叉樹的具體步驟。將森林中的每棵樹都用二叉鏈表表示法表示，并將各棵二叉樹的根結(jié)點(diǎn)看做是兄弟結(jié)點(diǎn)，在它們之間加上連線；將結(jié)點(diǎn)

45、到第一個(gè)孩子結(jié)點(diǎn)的連線作為左子樹的邊，結(jié)點(diǎn)到兄弟結(jié)點(diǎn)的連線作為右子樹的邊。17. 請(qǐng)簡述二叉樹轉(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è)包含假設(shè)干棵樹的森林。-. z.第6章 圖1. 請(qǐng)簡述圖的構(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)解釋有向圖、無向圖、弧、弧尾、

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

47、點(diǎn)vi為弧頭的弧的數(shù)目稱為頂點(diǎn)vi的入度；以頂點(diǎn)vi為弧尾的弧的數(shù)目稱為vi的出度；頂點(diǎn)vi的入度和出度之和稱為vi的度。路徑和路徑長度：在圖G中，假設(shè)存在一個(gè)頂點(diǎn)序列(, , )，使得對(duì)于任意0jn-1有假設(shè)G為有向圖或假設(shè)G為無向圖，則該序列是從頂點(diǎn)到頂點(diǎn)的一條路徑。一條路徑中邊的數(shù)目稱為路徑長度?；芈泛秃唵位芈罚涸谝粭l路徑中，假設(shè)組成路徑的頂點(diǎn)序列中第一個(gè)頂點(diǎn)與最后一個(gè)頂點(diǎn)一樣，則該路徑稱為回路或環(huán)；在一個(gè)回路中，假設(shè)除第一個(gè)頂點(diǎn)與最后一個(gè)頂點(diǎn)外，其他頂點(diǎn)只出現(xiàn)一次，則該回路稱為簡單回路或簡單環(huán)。連通圖：無向圖G中，假設(shè)任意兩個(gè)頂點(diǎn)都是連通的，則稱G為連通圖。單向連通圖和強(qiáng)連通圖：有向圖

48、G中，假設(shè)任意兩個(gè)頂點(diǎn)都是單向連通的，則稱G是單向連通圖；假設(shè)任意兩個(gè)頂點(diǎn)都是強(qiáng)連通的，則稱G為強(qiáng)連通圖。子圖：對(duì)于圖G、G，假設(shè)滿足且，則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)圖。生成樹和最小生成樹：假設(shè)無向圖G的一個(gè)子圖G是一棵包含圖G所有頂點(diǎn)的樹，則G稱為圖G的生成樹。在所有形式的生成樹中，邊上的權(quán)之和最小的生成樹，稱為最小生成樹。3. 請(qǐng)列舉可以用圖來描述的實(shí)際問題。請(qǐng)參考例6-1和例6-

49、2。4. 請(qǐng)簡述圖的根本操作及各操作的含義。創(chuàng)立圖：創(chuàng)立不包含任何頂點(diǎn)和邊的空?qǐng)D。對(duì)圖作深度優(yōu)先遍歷：類似于樹的先序遍歷，即從*一個(gè)頂點(diǎn)開場訪問，訪問后將該頂點(diǎn)去除得到假設(shè)干子圖，對(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)開場重復(fù)上一過程，直至所有頂點(diǎn)訪問完畢。獲取頂點(diǎn)數(shù)目：獲取圖中所包含的頂點(diǎn)的數(shù)目。獲取邊的數(shù)目：獲取圖

50、中所包含的邊的數(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的下一條弧。不同表示方法獲取到的結(jié)果會(huì)有所不同鄰接矩陣法按頂點(diǎn)編號(hào)順序，鄰接壓縮表和鄰接鏈表按邊的添加順序。添加一個(gè)頂點(diǎn)：向圖中添加一個(gè)新頂點(diǎn)。添加一條邊：對(duì)無向圖，向圖中添加一條新邊；對(duì)有向圖，向圖中添加一

51、條新弧。獲取一個(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è)置指定弧上的權(quán)。獲取一條邊的權(quán)：對(duì)無向圖，獲取指定邊(nV1,nV2)上的權(quán)；對(duì)有向圖，獲取指定弧上的權(quán)。5. 請(qǐng)簡述圖的三種常用表示方法。鄰接矩陣法：用矩陣來表示各頂點(diǎn)之間的連接關(guān)系。對(duì)于有n個(gè)頂點(diǎn)的圖G=(V, E)，其鄰接矩陣A為n*n的方陣，元素Aij0i,jn定義為：其中，wij為邊(vi, vj)或上的權(quán)。鄰接壓縮表：

52、鄰接矩陣的一種壓縮表示形式，使用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)vii = 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ǔ)構(gòu)造。每個(gè)頂點(diǎn)中設(shè)置一個(gè)指向鏈表頭的指針，在鏈表中保存與該頂點(diǎn)相鄰接的頂點(diǎn)信息包括頂點(diǎn)位置及兩個(gè)頂點(diǎn)形成的邊的權(quán)。6. 請(qǐng)簡述圖的兩種常用遍歷方法及每一種遍歷方法中結(jié)點(diǎn)的訪問順序。廣度優(yōu)先遍歷：類似于樹的逐層遍歷，即先從*一個(gè)頂點(diǎn)開場訪問，然后訪問與該頂點(diǎn)相鄰

53、接且未被訪問過的頂點(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)去除得到假設(shè)干子圖，對(duì)每個(gè)子圖再依次進(jìn)展深度優(yōu)先遍歷。7. 請(qǐng)列舉最小生成樹和最短路徑可以用于解決什么應(yīng)用問題。請(qǐng)參考例6-1和例6-2。8. 請(qǐng)簡述Prim算法的作用和具體步驟。Prim算法用于最小生成樹問題求解。對(duì)于有n個(gè)頂點(diǎn)的圖G=(V, E)，Prim算法從空樹T開場，按照以下規(guī)則

54、將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中的頂點(diǎn)vii=1,2,n-1參加到集合D中，并將頂點(diǎn)間關(guān)系jD(vj,vi)+D(vi,vk)，則說明路徑(vj, , vi, , vk)的長度更短，此時(shí)令D(vj,vk)=D(vj,vi)+D(vi,vk)并更新從頂點(diǎn)vj到頂點(diǎn)vk的路徑。-. z.第7章 排序算法1. 請(qǐng)簡述排序的作用。排序的作用是將一個(gè)待排序元素集合按關(guān)鍵字遞增

55、或遞減順序整理為一個(gè)有序序列。2. 請(qǐng)簡述穩(wěn)定排序和不穩(wěn)定排序的含義。假設(shè)采用*種排序算法對(duì)任一組元素進(jìn)展排序，在排序前后，那些具有一樣關(guān)鍵字值的元素之間的相對(duì)次序都保持不變，則將這種排序算法稱為是穩(wěn)定的，否則稱為是不穩(wěn)定的。3. 請(qǐng)簡述各種排序算法的適用圍。排序算法的適用圍如下：a直接插入排序、簡單項(xiàng)選擇擇排序和冒泡排序都是簡單排序算法，它們的時(shí)間復(fù)雜度和空間復(fù)雜度分別為O(n2)和O(1)。假設(shè)待排序元素?cái)?shù)量n較小，可以選用直接插入排序和冒泡排序。另外，當(dāng)待排序元素根本有序時(shí)，也應(yīng)選用直接插入排序和冒泡排序，此時(shí)時(shí)間復(fù)雜度都能到達(dá)O(n)。假設(shè)元素本身數(shù)據(jù)量較大，元素移動(dòng)操作代價(jià)較高，則應(yīng)

56、選用平均移動(dòng)元素次數(shù)最少的簡單項(xiàng)選擇擇排序。希爾排序是對(duì)直接插入排序算法的改良，大大降低了時(shí)間復(fù)雜度，但它是一種不穩(wěn)定的排序算法。b堆排序、快速排序和歸并排序主要適用于待排序元素?cái)?shù)量n較大的情況，當(dāng)待排序元素?cái)?shù)量n較小時(shí)，它們的性能有可能劣于簡單排序算法。因此，在實(shí)際應(yīng)用時(shí)，快速排序算法和歸并排序算法經(jīng)常與簡單排序算法結(jié)合使用例如，可以先用快速排序算法將集合劃分為規(guī)模更小的子集合，對(duì)于元素?cái)?shù)量較小的子集合，則用直接插入排序算法進(jìn)展排序。在所有平均時(shí)間復(fù)雜度為O(nlog2n)的算法中，盡管快速排序在最壞情況下時(shí)間復(fù)雜度較高，但它通常被認(rèn)為是平均性能最好的一種算法，并且通過優(yōu)化可以降低最壞情況出

57、現(xiàn)的概率。歸并排序是一種穩(wěn)定的排序算法，其時(shí)間性能一般要優(yōu)于堆排序，但它所需要的輔助空間較多，當(dāng)應(yīng)用環(huán)境要求排序前后具有一樣值的元素相對(duì)次序不能改變時(shí)可以考慮使用。堆排序所需的輔助空間最少，當(dāng)可用空間非常有限時(shí)可以考慮使用。c箱排序和基數(shù)排序的時(shí)間復(fù)雜度最低，但它們的空間復(fù)雜度最高。箱排序主要適用于待排序元素長度即d值較小的情況，在實(shí)際中應(yīng)用不多；基數(shù)排序是箱排序的改良，主要適用于整數(shù)或字符串的排序，或者與其他排序算法結(jié)合進(jìn)展實(shí)數(shù)的排序例如，可以先用基數(shù)排序算法按整數(shù)局部將元素分成假設(shè)干個(gè)子集合，再對(duì)每個(gè)子集合應(yīng)用直接插入排序算法進(jìn)展排序。5. 請(qǐng)簡述插入排序、選擇排序、交換排序、歸并排序和分

58、配排序的原理。插入排序：按關(guān)鍵字大小每次將一個(gè)待排序的元素插入到已排序的序列中，直至所有元素都插入完畢。選擇排序：每次從待排序的元素中選擇具有最小或最大關(guān)鍵字的元素放到已排序序列的尾部或頭部，直至所有元素都排序完畢。交換排序：從待排序的元素中選擇兩個(gè)次序相反的元素進(jìn)展交換，直至任意兩個(gè)元素的次序都正確。K路歸并排序：每次將KK2個(gè)已排序的子序列組合在一起，形成一個(gè)有序的序列，重復(fù)該過程直至得到一個(gè)包含所有待排序元素的有序序列。分配排序：根據(jù)元素本身所具有的值將各元素逐一映射到一組有序空間中，最后再依次從有序空間中將各元素取出即形成了排序結(jié)果。5. 請(qǐng)簡述直接插入排序的具體步驟。直接插入排序是一

59、種簡單排序算法，其具體步驟為：a初始已排序區(qū)為空，將第一個(gè)待排序的元素插入到已排序區(qū)中。b將后繼每一個(gè)待排序的元素依次取出，并按照關(guān)鍵字大小將其插入到已排序區(qū)中的適當(dāng)位置，使該序列仍然有序。c重復(fù)上一步驟直至將待排序的元素都插入到已排序序列中。6. 請(qǐng)簡述希爾排序的具體步驟。希爾排序，又稱為縮小增量排序，其具體步驟為：a令n為待排序元素?cái)?shù)目，設(shè)置增量序列d0, d1, , dk，其中nd0d1dk=1。b按增量dii依次取值為0, 1, , k將待排序元素分為di組，將所有下標(biāo)距離為di的倍數(shù)的元素放在同一組中，即R1, R1+ di, R1+2*di, 在第一組中，R2, R2+ di, R

60、2+2*di, 在第二組中，依此類推。然后分別在各組進(jìn)展直接插入排序。c重復(fù)上一步驟直至最后以1為增量對(duì)所有待排序元素進(jìn)展直接插入排序。7. 請(qǐng)簡述簡單項(xiàng)選擇擇排序的具體步驟。簡單項(xiàng)選擇擇排序是一種簡單排序算法，其具體步驟為：a初始已排序區(qū)為空，待排序區(qū)包含所有待排序元素。b從待排序區(qū)中選擇具有最小關(guān)鍵字的元素，將其與待排序區(qū)的第一個(gè)元素交換位置，并將該位置加到已排序區(qū)中。c重復(fù)上一步驟直至所有元素都排序完畢。8. 請(qǐng)簡述堆的定義和堆的構(gòu)建過程。堆的定義：對(duì)于包含n個(gè)元素的集合R=R1, R2, , Rn，假設(shè)滿足：1RiR2*i且RiR2*i+1即R所表示的完全二叉樹中每一棵子樹的根結(jié)點(diǎn)的值