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

千里之行，始于足下讓知識(shí)帶有溫度。第第2頁/共2頁精品文檔推薦數(shù)據(jù)結(jié)構(gòu)習(xí)題參考答案第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ù)；因?yàn)閿?shù)據(jù)在存儲(chǔ)時(shí)所需要的容量各不相同，不同的數(shù)據(jù)就必需要分配不同大小的內(nèi)存空間來存儲(chǔ)，全部就要將數(shù)據(jù)劃分成不同的數(shù)據(jù)類型。數(shù)據(jù)類型包含取值范圍和基本運(yùn)算等概念。

2.什么是數(shù)據(jù)的規(guī)律結(jié)構(gòu)？什么是數(shù)據(jù)的物理結(jié)構(gòu)？數(shù)據(jù)的規(guī)律結(jié)構(gòu)與物理結(jié)構(gòu)的區(qū)分和聯(lián)系是什么？

規(guī)律結(jié)構(gòu)：數(shù)據(jù)的規(guī)律結(jié)構(gòu)定義了數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)元素之間的互相規(guī)律關(guān)系。數(shù)據(jù)的規(guī)律結(jié)構(gòu)包含下面兩個(gè)方面的信息：

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

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

物理結(jié)構(gòu)：也叫儲(chǔ)存結(jié)構(gòu)，是指規(guī)律結(jié)構(gòu)的存儲(chǔ)表示，即數(shù)據(jù)的規(guī)律結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式，包括結(jié)點(diǎn)的數(shù)據(jù)和結(jié)點(diǎn)間關(guān)系的存儲(chǔ)表示。

數(shù)據(jù)的規(guī)律結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)是密不行分的，一個(gè)操作算法的設(shè)計(jì)取決于所選定的規(guī)律結(jié)構(gòu)，而算法的實(shí)現(xiàn)依靠于所采與的存儲(chǔ)結(jié)構(gòu)。采納不同的存儲(chǔ)結(jié)構(gòu)，其數(shù)據(jù)處理的效率是不同的。因此，在舉行數(shù)據(jù)處理時(shí)，針對(duì)不同問題，挑選合理的規(guī)律結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)十分重要。

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

對(duì)于各種數(shù)據(jù)結(jié)構(gòu)而言，他們?cè)诨静僮魃鲜窍嘞竦?，最常用的操作有?/p>

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

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

●插入：在數(shù)據(jù)結(jié)構(gòu)中增強(qiáng)新的結(jié)點(diǎn)；

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

●拜訪：對(duì)數(shù)據(jù)結(jié)構(gòu)中的結(jié)點(diǎn)舉行拜訪；

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

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

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

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

抽象數(shù)據(jù)類型（AbstractDataType簡(jiǎn)稱ADT）是指一個(gè)數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作。ADT是與詳細(xì)的物理存儲(chǔ)無關(guān)的數(shù)據(jù)類型，因此，不論ADT的內(nèi)部結(jié)構(gòu)如何變化，只要其數(shù)據(jù)結(jié)構(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)系的定義用偽代碼來描述?；静僮鞯亩x格式為：

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

初始條件：

操作結(jié)果：

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

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

算法：是在有限的步驟內(nèi)解決數(shù)知識(shí)題的過程，是以一步接一步的方式來具體描述計(jì)算機(jī)如何將輸入轉(zhuǎn)化為所要求的輸出的過程，即算法是對(duì)計(jì)算機(jī)上執(zhí)行的計(jì)算過程的詳細(xì)描述。一個(gè)有效的算法必需滿足的五個(gè)重要特性：

①有窮性：算法必需能在有限的時(shí)光內(nèi)做完，即在任何狀況下，算法必需能在執(zhí)行有限個(gè)步驟之后終止，都不能陷入無窮循環(huán)中。

②確定性：算法中的每一個(gè)步驟，必需經(jīng)過明確的定義，并且能夠被計(jì)算機(jī)所理解和執(zhí)行，而不能是抽象和含糊的概念，更不允許有二義性。

③輸入：算法有0個(gè)或多個(gè)輸入值，來描述算法開頭前運(yùn)算對(duì)象的初始狀況，這是算法執(zhí)行的起點(diǎn)或是依據(jù)。0個(gè)輸入是指算法本身給出了運(yùn)算對(duì)象的初始條件。

④輸出：算法至少有1個(gè)或多個(gè)輸出值，反映對(duì)運(yùn)算對(duì)象的處理結(jié)果，沒有輸出的算法沒有任何意義。

⑤可行性：算法中要做的運(yùn)算都是基本運(yùn)算，能夠被精確地舉行。即算法中執(zhí)行的任何計(jì)算都可以被分解為基本的運(yùn)算步，每個(gè)基本的運(yùn)算步都可以在有限的時(shí)光內(nèi)完成。

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

算法的討論與實(shí)際問題直接相關(guān)，用來解一個(gè)問題可以有無數(shù)不同的算法，他們之間的效果可能會(huì)有很大差異。算法設(shè)計(jì)者最關(guān)懷的就是什么是有效的算法，如何評(píng)價(jià)一個(gè)算法的優(yōu)劣，如何從多種算法中挑選好的算法。除了要首先考慮算法的正確性外，還要分析和評(píng)價(jià)算法的性能。分析和評(píng)價(jià)算法的性能主要要考慮以下兩個(gè)方面：

①時(shí)光代價(jià)：執(zhí)行算法所耗費(fèi)的時(shí)光。一個(gè)好的算法首先應(yīng)當(dāng)比其他算法的運(yùn)行時(shí)光代價(jià)要小。算法的時(shí)光代價(jià)的大小用算法的時(shí)光復(fù)雜度來度量。

②空間代價(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ù)雜度：n

（4）時(shí)光復(fù)雜度：n2

（5）時(shí)光復(fù)雜度：O(log2n)

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

遞推法：是利用問題本身所具有的一種遞推關(guān)系求解問題的一種辦法。它把問題求解分成若干步，找出相鄰幾步的關(guān)系，從而達(dá)到求解問題的目的。具有如下性質(zhì)的問題可以采納遞推法：當(dāng)?shù)玫絾栴}規(guī)模為i-1的解后，由問題的遞推性質(zhì)，能構(gòu)造出問題規(guī)模為i的解。因此，程序可以從i=0或i=1動(dòng)身，由已知i-1規(guī)模的解，通過遞推，獲得問題規(guī)模為i的解，直至得到問題規(guī)模為n的解。

遞歸法：遞歸策略是利用函數(shù)直接或間接地調(diào)用自身來完成某個(gè)計(jì)算過程。能采納遞歸描述的算法通常有這樣的特征：為求解規(guī)模為n的問題，設(shè)法將它分解成規(guī)模較小的問題，然后從這些小問題的解便利地構(gòu)造出更大問題的解，并且這些規(guī)模較小的問題也能采納同樣的分解和綜合辦法，分解成規(guī)模更小的問題，并從這些更小問題的解構(gòu)造出較大規(guī)模問題的解。

窮舉法：窮舉搜尋法也稱窮舉法或搜尋法是對(duì)可能是解的眾多候選解按某種挨次舉行逐一枚舉和檢驗(yàn)，并從中找出那些符合要求的候選解作為問題的解。

迭代法：數(shù)值分析中通過從一個(gè)初始估量動(dòng)身尋覓一系列近似解來解決問題（普通是解方程或者方程組）的過程，為實(shí)現(xiàn)這一過程所使用的辦法統(tǒng)稱為迭代法。

9.算法設(shè)計(jì)中的分治策略、貪心策略、動(dòng)態(tài)規(guī)劃策略、回溯策略以及分支定界策略的基本思想是什么？

分治策略的基本思想是把一個(gè)規(guī)模為n的問題劃分為若干個(gè)規(guī)模較小、且與原問題相像的子問題，然后分離求解這些子問題，最后把各子結(jié)果合并得到囫圇問題的解。分解的子問題通常與原問題相像，所以可以遞歸地使用分治策略來求解。

貪心策略的基本思想是把一個(gè)整體最優(yōu)問題分解為一系列的最優(yōu)挑選問題，決策一旦做出，就不能再更改。它是通過若干次的貪心挑選而得出最優(yōu)解（或較優(yōu)解）的一種解題策略。

動(dòng)態(tài)規(guī)劃策略與貪心策略類似，將一個(gè)問題劃分為重復(fù)的子問題，通過對(duì)相同子問題的求解來解決較大問題，即將一個(gè)問題的解決計(jì)劃視為一系列決策的結(jié)果。不同的是，在貪心策略中，每采納一次貪心準(zhǔn)則便做出一個(gè)不行撤回的決策，可能得不到問題的最優(yōu)解。而在動(dòng)態(tài)規(guī)劃中，處理要根據(jù)某種規(guī)章舉行挑選，還要考察每個(gè)最優(yōu)決策序列中是否包含一個(gè)最優(yōu)子序列，目的是得到問題的最優(yōu)解。

回溯策略也叫摸索法，它的基本思想是：在一些問題求解進(jìn)程中，先挑選某一種可能狀況向前探究，當(dāng)發(fā)覺所選用的摸索性操作不是最佳挑選，需退回一步，重新挑選繼續(xù)舉行摸索，直到找到問題的解或者證實(shí)問題無解。

分支定界策略也常常被稱為分支限界策略，它的基本思想是：首先確定目標(biāo)值的上下界，然后一邊搜尋一邊剪掉空間樹的某些不行能產(chǎn)生最優(yōu)解的分支，提高搜尋效率。

其次章線性表

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

線性表是一種最常用、最容易的典型線性數(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)系，詳細(xì)特性如下：

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

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

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

2．如何實(shí)現(xiàn)線性表的挨次存儲(chǔ)結(jié)構(gòu)？

把線性表的結(jié)點(diǎn)按規(guī)律挨次依次存放在一組地址延續(xù)的存儲(chǔ)單元里就構(gòu)成了線性表的挨次存儲(chǔ)，采納挨次存儲(chǔ)結(jié)構(gòu)的線性表簡(jiǎn)稱挨次表。線性表的挨次存儲(chǔ)結(jié)構(gòu)有如下特點(diǎn)：

●線性表中全部元素所占的存儲(chǔ)空間是延續(xù)的；

●線性表的規(guī)律挨次與物理挨次全都；

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

存儲(chǔ)地址（指第一個(gè)字節(jié)的地址，即首地址）為L(zhǎng)OC(e1)，每一個(gè)數(shù)據(jù)元素占k個(gè)

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

LOC(ei)=LOC(e1)+(i-1)k

3．如何實(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)在規(guī)律上相連的其他結(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)按其規(guī)律結(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è)規(guī)律結(jié)點(diǎn)，線性鏈表的最后一個(gè)結(jié)點(diǎn)的指針為空（用NULL或0表示），表示鏈表終止，這樣的線性鏈表稱為單向鏈表。下圖是單向鏈表暗示圖。

線性表的單向鏈?zhǔn)酱鎯?chǔ)

循環(huán)鏈表：將單向鏈表最后一個(gè)結(jié)點(diǎn)的指針指向頭結(jié)點(diǎn)，這樣囫圇鏈表就構(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)。惟獨(dú)頭結(jié)點(diǎn)的循環(huán)鏈表稱為空循環(huán)鏈表。下圖是帶頭結(jié)點(diǎn)的非空循環(huá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)的結(jié)構(gòu)下圖（a）所示。

雙向循環(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)表的規(guī)律結(jié)構(gòu)暗示圖。

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

4．挨次表和線性鏈表分離有哪些優(yōu)點(diǎn)和缺點(diǎn)？

線性表的挨次存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)比較

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

①按員工號(hào)排序的員工基本狀況表；

②奧運(yùn)會(huì)各項(xiàng)競(jìng)賽日程；

③按學(xué)號(hào)記錄的同學(xué)的成果單；

等等。

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

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

（a）雙向鏈表結(jié)點(diǎn)結(jié)構(gòu)

在挨次表中實(shí)現(xiàn)統(tǒng)計(jì)重復(fù)元素個(gè)數(shù)的操作：

在教材的【描述2-1】中，增強(qiáng)一個(gè)統(tǒng)計(jì)重復(fù)元素個(gè)數(shù)的成員函數(shù)：intCount(constT//返回x浮現(xiàn)的次數(shù)

在教材的【描述2-2】中，增強(qiáng)查找重復(fù)元素個(gè)數(shù)的成員函數(shù)的實(shí)現(xiàn)：//實(shí)現(xiàn)統(tǒng)計(jì)重復(fù)元素個(gè)數(shù)

template

intLinearList::Count(constT

for(inti=0;i

intLinkList::Count(constT

intcount=0;

while(p!=NULL

p=p->next;

}

returncount;

}

第3章棧和隊(duì)列

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

棧：一種插入和刪除都只能在表的同一端舉行的線性表。

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

先進(jìn)后出：元素是以e1，e2，……en挨次進(jìn)入數(shù)據(jù)結(jié)構(gòu)，以相反的挨次即en，en-1，……

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

棧頂：允許舉行插入和刪除操作的一端。

棧底：棧中與棧頂相對(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)前挨次棧的棧頂）向后移動(dòng)一個(gè)元素空間（元素大?。?，將要插入的元素放入top指針指向的內(nèi)存單元中。

3.一個(gè)棧的輸入序列為1、2、3，試給出所有可能的出棧序列。

可分為三種狀況：

①、當(dāng)惟獨(dú)一個(gè)存儲(chǔ)空間時(shí)，惟獨(dú)一種出棧序列：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ì)列的存儲(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，LastInFirstOut）的實(shí)際問題都可以用棧表示。棧的應(yīng)用主要有：數(shù)制的轉(zhuǎn)換、括號(hào)的匹配檢查、行編輯處理、表達(dá)式求解、走迷宮以及高級(jí)語言中函數(shù)的嵌套調(diào)用和遞歸的實(shí)現(xiàn)等。

全部“先進(jìn)先出”(FIFO，F(xiàn)irstInFirstOut）的實(shí)際問題都可以用隊(duì)列表示。如日常中的排隊(duì)問題，隊(duì)列的應(yīng)用主要有：操作系統(tǒ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ù)的規(guī)律位置，隨意兩個(gè)數(shù)據(jù)的index都不相同；value表示數(shù)據(jù)元素的值。

2.設(shè)有二維數(shù)組a[5][6]，每個(gè)元素占相鄰的8個(gè)字節(jié)，存儲(chǔ)器按字節(jié)編址，已知a的起始地址是1000，試計(jì)算：

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

1000+（30-1）*8=1232。

（2）按行序優(yōu)先時(shí)，元素a[3][5]的起始地址；

1000+（3*6+5）*8=1184

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

1000+（3*5+4）*8=1152

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

矩陣是指縱橫羅列的二維數(shù)據(jù)表格。在高級(jí)語言編程中，通常用二維數(shù)組來描述一個(gè)矩陣，從而可以對(duì)矩陣中的元素舉行隨機(jī)存取。但矩陣的索引通常從1而不是像數(shù)組那樣從0開頭，并且使用A（i，j）而不是A[i，j]的形式來引用矩陣中的元素。

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ǔ)結(jié)構(gòu)，請(qǐng)寫出矩陣相加的算法C=A+B。

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

#include

usingnamespacestd;

#defineM50

#defineN50

#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.rows=row;t.cols=col;t.nums=0;

for(i=0;ib.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>row>>col;

cout>A[i][j];

cout>B[i][j];

CreateMat(A,a,row,col);

CreateMat(B,b,row,col);

cout并有∈E(G)，稱vi為弧尾，vj為弧頭。

無向圖：若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的度。在有向圖中，以頂點(diǎn)vi為弧頭的弧的數(shù)目稱為頂點(diǎn)vi的入度；以頂點(diǎn)vi為弧尾的弧的數(shù)目稱為vi的出度；頂點(diǎn)vi的入度和出度之和稱為vi的度。

路徑和路徑長(zhǎng)度：在圖G中，若存在一個(gè)頂點(diǎn)序列(0iv,1iv,…,1-niv)，使得對(duì)于隨意

0≤j∈有相同弧尾nV1的下一條弧。不同表示辦法獵取到的結(jié)果會(huì)有所不同（鄰接矩陣法按頂點(diǎn)編號(hào)挨次，鄰接壓縮表和鄰接鏈表按邊的添加挨次）。

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

添加一條邊：對(duì)無向圖，向圖中添加一條新邊；對(duì)有向圖，向圖中添加一條新弧。獵取一個(gè)頂點(diǎn)中存儲(chǔ)的數(shù)據(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)簡(jiǎn)述圖的三種常用表示辦法。

鄰接矩陣法：用矩陣來表示各頂點(diǎn)之間的銜接關(guān)系。對(duì)于有n個(gè)頂點(diǎn)的圖G=(V,E)，其鄰接矩陣A為n*n的方陣，元素A[i][j]（0≤i,j∈上的權(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è)置一個(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è)子圖再依次舉行深度優(yōu)先遍歷。

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

請(qǐng)參考例6-1和例6-2。

8.請(qǐng)簡(jiǎn)述Prim算法的作用和詳細(xì)步驟。

Prim算法用于最小生成樹問題求解。對(duì)于有n個(gè)頂點(diǎn)的圖G=(V,E)，Prim算法從空樹T開頭，根據(jù)以下規(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中的頂點(diǎn)vi'（i=1,2,…,n-1）加入到集合D中，并將頂點(diǎn)間關(guān)系（jD(vj',vi')+D(vi',vk')，

則表明路徑(vj',…,vi',…,vk')的長(zhǎng)度更短，此時(shí)令D(vj',vk')=D(vj',vi')+D(vi',vk')并更新從頂點(diǎn)vj'到頂點(diǎn)vk'的路徑。

第7章排序算法

1.請(qǐng)簡(jiǎn)述排序的作用。

排序的作用是將一個(gè)待排序元素集合按關(guān)鍵字遞增（或遞減）挨次收拾為一個(gè)有序序列。

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

若采納某種排序算法對(duì)任一組元素舉行排序，在排序前后，那些具有相同關(guān)鍵字值的元素之間的相對(duì)次序都保持不變，則將這種排序算法稱為是穩(wěn)定的，否則稱為是不穩(wěn)定的。3.請(qǐng)簡(jiǎn)述各種排序算法的適用范圍。

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

（a）直接插入排序、容易挑選排序和冒泡排序都是容易排序算法，它們的時(shí)光復(fù)雜度和空間復(fù)雜度分離為O(n2)和O(1)。若待排序元素?cái)?shù)量n較小，可以選用直接插入排序和冒泡排序。另外，當(dāng)待排序元素基本有序時(shí)，也應(yīng)選用直接插入排序和冒泡排序，此時(shí)時(shí)光復(fù)雜度都能達(dá)到O(n)。若元素本身數(shù)據(jù)量較大，元素移動(dòng)操作代價(jià)較高，則應(yīng)選用平均移動(dòng)元素次數(shù)最少的容易挑選排序。希爾排序是對(duì)直接插入排序算法的改進(jìn)，大大降低了時(shí)光復(fù)雜度，但它是一種不穩(wěn)定的排序算法。

（b）堆排序、迅速排序和歸并排序主要適用于待排序元素?cái)?shù)量n較大的狀況，當(dāng)待排序元素?cái)?shù)量n較小時(shí)，它們的性能有可能劣于容易排序算法。因此，在實(shí)際應(yīng)用時(shí)，迅速排序算法和歸并排序算法常常與容易排序算法結(jié)合使用（例如，可以先用迅速排序算法將集合劃分為規(guī)模更小的子集合，對(duì)于元素?cái)?shù)量較小的子集合，則用直接插入排序算法舉行排序）。在全部平均時(shí)光復(fù)雜度為O(nlog2n)的算法中，盡管迅速排序在最壞狀況下時(shí)光復(fù)雜度較高，但它通常被認(rèn)為是平均性能最好的一種算法，并且通過優(yōu)化可以降低最壞狀況浮現(xiàn)的概率。歸并排序是一種穩(wěn)定的排序算法，其時(shí)光性能普通要優(yōu)于堆排序，但它所需要的輔助空間較多，當(dāng)應(yīng)用環(huán)境要求排序前后具有相同值的元素相對(duì)次序不能轉(zhuǎn)變時(shí)可以考慮使用。堆排序所需的輔助空間最少，當(dāng)可用空間十分有限時(shí)可以考慮使用。

（c）箱排序和基數(shù)排序的時(shí)光復(fù)雜度最低，但它們的空間復(fù)雜度最高。箱排序主要適用于待排序元素長(zhǎng)度（即d值）較小的狀況，在實(shí)際中應(yīng)用不多；基數(shù)排序是箱排序的改進(jìn)，主要適用于整數(shù)或字符串的排序，或者與其他排序算法結(jié)合舉行實(shí)數(shù)的排序（例如，可以先用基數(shù)排序算法按整數(shù)部分將元素分成若干個(gè)子集合，再對(duì)每個(gè)子集合應(yīng)用直接插入排序算法舉行排序）。

5.請(qǐng)簡(jiǎn)述插入排序、挑選排序、交換排序、歸并排序和分配排序的原理。

插入排序：按關(guān)鍵字大小每次將一個(gè)待排序的元素插入到已排序的序列中，直至全部元素都插入完畢。

挑選排序：每次從待排序的元素中挑選具有最?。ɑ蜃畲螅╆P(guān)鍵字的元素放到已排序序列的尾部（或頭部），直至全部元素都排序完畢。

交換排序：從待排序的元素中挑選兩個(gè)次序相反的元素舉行交換，直至隨意兩個(gè)元素的次序都正確。

K路歸并排序：每次將K（K≥2）個(gè)已排序的子序列組合在一起，形成一個(gè)有序的序列，重復(fù)該過程直至得到一個(gè)包含全部待排序元素的有序序列。

分配排序：按照元素本身所具有的值將各元素逐一映射到一組有序空間中，最后再依次從有序空間中將各元素取出即形成了排序結(jié)果。

5.請(qǐng)簡(jiǎn)述直接插入排序的詳細(xì)步驟。

直接插入排序是一種容易排序算法，其詳細(xì)步驟為：

（a）初始已排序區(qū)為空，將第一個(gè)待排序的元素插入到已排序區(qū)中。

（b）將后繼每一個(gè)待排序的元素依次取出，并根據(jù)關(guān)鍵字大小將其插入到已排序區(qū)中的適當(dāng)位置，使該序列仍然有序。

（c）重復(fù)上一步驟直至將待排序的元素都插入到已排序序列中。

6.請(qǐng)簡(jiǎn)述希爾排序的詳細(xì)步驟。

希爾排序，又稱為“縮小增量排序”，其詳細(xì)步驟為：

（a）令n為待排序元素?cái)?shù)目，設(shè)置增量序列{d0,d1,…,dk}，其中n>d0>d1>…>dk=1。

（b）按增量di（i依次取值為0,1,…,k）將待排序元素分為di組，將全部下標(biāo)距離為di的倍數(shù)的元素放在同一組中，即R[1],R[1+di],R[1+2*di],…在第一組中，R[2],R[2+di],R[2+2*di],……在其次組中，……，依此類推。然后分離在各組內(nèi)舉行直接插入排序。

（c）重復(fù)上一步驟直至最后以1為增量對(duì)全部待排序元素舉行直接插入排序。

7.請(qǐng)簡(jiǎn)述容易挑選排序的詳細(xì)步驟。

容易挑選排序是一種容易排序算法，其詳細(xì)步驟為：

（a）初始已排序區(qū)為空，待排序區(qū)包含全部待排序元素。

（b）從待排序區(qū)中挑選具有最小關(guān)鍵字的元素，將其與待排序區(qū)的第一個(gè)元素交換位置，并將該位置加到已排序區(qū)中。

（c）重復(fù)上一步驟直至全部元素都排序完畢。

8.請(qǐng)簡(jiǎn)述堆的定義和堆的構(gòu)建過程。

堆的定義：

對(duì)于包含n個(gè)元素的集合R={R[1],R[2],…,R[n]}，若滿足：

（1）R[i]≤R[2*i]且R[i]≤R[2*i+1]（即R所表示的徹低二叉樹中每一棵子樹的根結(jié)點(diǎn)的值均不大于其孩子結(jié)點(diǎn)的值）。

（2）或R[i]≥R[2*i]且R[i]≥R[2*i+1]（即R所表示的徹低二叉樹中每一棵子樹的根結(jié)點(diǎn)的值均不小于其孩子結(jié)點(diǎn)的值）。

則稱集合R為堆。若滿足前一個(gè)條件則稱R為小根堆，滿足后一個(gè)條件則稱R為大根堆。

堆的構(gòu)建過程：

堆普通采納自底向上的構(gòu)建辦法，即在將以某一結(jié)點(diǎn)為根結(jié)點(diǎn)的二叉樹構(gòu)建成堆之前，先將其左子樹和右子樹構(gòu)建成堆。以葉子結(jié)點(diǎn)為根的子樹必定是堆，因此，對(duì)于由n個(gè)元素構(gòu)成的徹低二叉樹，其對(duì)應(yīng)的堆的構(gòu)建過程從R[?n/2?]作為根結(jié)點(diǎn)的子樹開頭，依次對(duì)R[?n/2?-1]、R[?n/2?-2]、…、R[1]作為根結(jié)點(diǎn)的樹舉行堆的構(gòu)建。

在將一棵R[i]作為根結(jié)點(diǎn)的子樹收拾為堆時(shí)，惟獨(dú)根結(jié)點(diǎn)不滿足堆的條件，因此，需將根結(jié)點(diǎn)與后繼層中的結(jié)點(diǎn)依次比較并不斷將根結(jié)點(diǎn)下移直至該子樹滿足堆的條件，這里以大根堆構(gòu)建為例介紹其詳細(xì)過程：

（a）若R[i]存在左孩子R[2*i]，則令j=2*i；若R[i]存在右孩子R[2*i+1]且R[2*i+1]>R[2*i]，則令j=2*i+1。將R[j]與R[i]比較，若R[i]較小，則將R[i]和R[j]交換，并令i=j。

（b）重復(fù)上述步驟直至R[i]無孩子結(jié)點(diǎn)或R[i]比其孩子結(jié)點(diǎn)都大，此時(shí)該子樹即為堆。

9.請(qǐng)簡(jiǎn)述堆排序的詳細(xì)步驟。

堆排序的詳細(xì)過程：

（a）采納自底向上的辦法將包含n個(gè)元素的待排序集合R={R[1],R[2],…,R[n]}收拾為大根堆，其元素?cái)?shù)目i=n，初始時(shí)已排序集合R'為空集；

（b）將R[1]與R[i]交換，并將i算作已排序集合中的元素位置，更新待排序集合中最后一個(gè)元素的位置i=i-1，此時(shí)待排序集合R={R[1],R[2],…,R[i]}，已排序集合R'={R[i+1],

R[i+2],…,R[n]}。明顯，待排序集合R={R[1],R[2],…,R[i]}中惟獨(dú)根結(jié)點(diǎn)R[1]不滿足大根堆的條件，通過下移R[1]重新將R收拾為大根堆；

（c）重復(fù)上一步驟直至待排序集合R={R[1]}，此時(shí)直接將R[1]作為已排序集合R'中的元素，堆排序過程結(jié)束。

10.請(qǐng)簡(jiǎn)述冒泡排序的詳細(xì)步驟。

冒泡排序是一種容易排序算法，其詳細(xì)步驟為：

（a）初始已排序區(qū)為空，待排序區(qū)包含全部待排序元素。

（b）在一輪排序中，對(duì)待排序區(qū)全部相鄰元素先前至后舉行兩兩比較，若相鄰兩個(gè)元素次序相反（即前一個(gè)元素的關(guān)鍵字值大于后一個(gè)元素的關(guān)鍵字值），則交換它們的位置。每輪排序后，待排序區(qū)中的最大元素會(huì)移到待排序區(qū)的尾部，將待排序區(qū)的最后一個(gè)元素放到已排序區(qū)的頭部。

（c）重復(fù)上一步驟直至待排序區(qū)中只剩下一個(gè)元素或者在一輪排序中沒有浮現(xiàn)相鄰元素交換的狀況，此時(shí)直接將待排序區(qū)中的全部元素按原次序放到已排序區(qū)的頭部，冒泡排序結(jié)束。

11.請(qǐng)簡(jiǎn)述迅速排序中劃分的含義和過程。

劃分的含義：

劃分是以指定元素x為基準(zhǔn)將一個(gè)集合R分為兩個(gè)子集R1和R2，其中R1中的元素都小于或等于x，R2中的元素都大于或等于x。

劃分的過程：

對(duì)于包含(high-low+1)個(gè)元素的待排序集合R={R[low],R[low+1],…,R[high]}，以R[k]（low≤k≤high）為基準(zhǔn)對(duì)其舉行劃分的詳細(xì)過程為：

（a）令i、j分離指向集合R的第一個(gè)元素和最后一個(gè)元素（即i=low、j=high），并將R[k]與R[i]交換（即初始基準(zhǔn)元素在i所指向的位置，此時(shí)基準(zhǔn)元素前面沒有任何元素，下面向基準(zhǔn)元素后面、位置在i+1到j(luò)之間的元素根據(jù)從后至前的挨次逐一檢查其是否大于或等于基準(zhǔn)元素）。

（b）若j!=i且R[j]≥R[i]，則令j=j-1，重復(fù)直至R[j]R[j]或i==j。上述處理后，若i!=j（即通過R[i]>R[j]這個(gè)條件退出循環(huán)）則將R[i]與R[j]交換、j=j-1，并回到上一步（該步處理結(jié)束后，基準(zhǔn)元素在i所指向的位置，此時(shí)基準(zhǔn)元素前面的元素都小于或等于基準(zhǔn)元素，而位置j后面的元素都大于或等于基準(zhǔn)元素，下面繼續(xù)對(duì)基準(zhǔn)元素后面、位置在i+1到j(luò)之間的元素根據(jù)從后至前的挨次逐一檢查其是否大于或等于基準(zhǔn)元素）；否則集合劃分操作結(jié)束。

12.請(qǐng)簡(jiǎn)述迅速排序的詳細(xì)步驟。

迅速排序就是對(duì)集合不斷劃分的過程：通過劃分可以將一個(gè)集合分為兩個(gè)子集合，若子集合中元素?cái)?shù)目大于1則再對(duì)子集合分離舉行劃分，重復(fù)該過程直至終于每個(gè)子集合中元素?cái)?shù)目都小于或等于1時(shí)迅速排序結(jié)束。

13.請(qǐng)簡(jiǎn)述二路歸并排序的詳細(xì)步驟。

二路歸并排序的詳細(xì)步驟為：

（a）對(duì)于包含n個(gè)元素的待排序集合，將其分為n個(gè)長(zhǎng)度為1的子序列。

（b）將每?jī)蓚€(gè)相鄰的子序列舉行歸并，得到?n/2?個(gè)長(zhǎng)度為2的子序列和0或1個(gè)長(zhǎng)

度為1的子序列。

（c）在此基礎(chǔ)上，再對(duì)每?jī)蓚€(gè)相鄰的子序列舉行歸并，得到?n/4?個(gè)長(zhǎng)度為4的子序列和0或1個(gè)長(zhǎng)度小于4的子序列。

（d）重復(fù)該過程直至得到一個(gè)長(zhǎng)度為n的有序序列為止。

14.請(qǐng)簡(jiǎn)述箱排序的詳細(xì)步驟。

箱排序的詳細(xì)步驟為：

（1）假設(shè)待排序元素的取值范圍為m~m+n-1，則箱子數(shù)量為n，設(shè)置包含n個(gè)元素的隊(duì)列集合B={B[0],B[1],…,B[n-1]}代表n個(gè)箱子。

（2）依次取出每一個(gè)待排序元素，若其值為m+i（i=0,1,…,n-1），則通過入隊(duì)操作將其放在箱子B[i]中。

（3）從B[0]開頭，依次檢查集合B中每一個(gè)隊(duì)列所代表的箱子，若箱子不為空，則通過出隊(duì)操作將箱子中的元素逐個(gè)取出并依次加到已排序集合中。

15.請(qǐng)簡(jiǎn)述基數(shù)排序的詳細(xì)步驟。

基數(shù)排序是對(duì)箱排序的改進(jìn)和推廣，它先將待排序元素按規(guī)章分解得到多個(gè)重量、再按照每一個(gè)重量對(duì)元素舉行多次箱排序。

（a）對(duì)于數(shù)字排序問題，基數(shù)排序辦法先將每一個(gè)數(shù)字寫成以r為基數(shù)的按權(quán)綻開式形式：N=an-1*rn-1+…+a0*r0+a-1*r-1+…+a-m*r-m；再根據(jù)從低位到高位（即從r-m開頭到rn-1）的挨次舉行n+m次箱排序。

（b）對(duì)于字符串排序問題，基數(shù)排序辦法根據(jù)從后至前的挨次對(duì)字符串中的每個(gè)字符分離舉行箱排序。若待排序字符串中最長(zhǎng)的字符串長(zhǎng)度為n，則需舉行n次箱排序；若某一字符串長(zhǎng)度為m（0≤m≤n），則該字符串在前(n-m)次箱排序中對(duì)應(yīng)的字符值為'\0'。

第8章查找算法

1.請(qǐng)簡(jiǎn)述查找的作用。

查找的作用是按照給定值從一個(gè)數(shù)據(jù)集合中搜尋某個(gè)元素。若某個(gè)元素的關(guān)鍵字值與給定值相等，則查找勝利；否則查找失敗。

2.請(qǐng)簡(jiǎn)述靜態(tài)查找和動(dòng)態(tài)查找的含義。

靜態(tài)查找只按照給定值在數(shù)據(jù)集合中按關(guān)鍵字查找匹配元素、拜訪匹配元素的屬性，而不對(duì)數(shù)據(jù)集合舉行插入元素、刪除元素等操作；而動(dòng)態(tài)查找可能會(huì)在查找過程中向數(shù)據(jù)集合中插入一個(gè)新元素或從數(shù)據(jù)集合中刪除一個(gè)已有元素。

3.請(qǐng)簡(jiǎn)述各種查找算法的適用范圍。

各種查找算法的適用范圍：

（a）挨次查找雖然查找效率最低，但其對(duì)待查找數(shù)據(jù)集合的存儲(chǔ)結(jié)構(gòu)無特殊要求，在對(duì)數(shù)據(jù)集合舉行增、刪、改等操作時(shí)效率較高，因此，按照那些不需要常常作查找操作的關(guān)鍵字舉行查找時(shí)，普通采納挨次查找算法。若常常作查找操作，則應(yīng)使用效率較高的其他查找算法。

（b）折半查找和分塊查找主要適用于數(shù)據(jù)集合增、刪、改等操作較少的狀況；二叉排序樹查找則適用于數(shù)據(jù)集合變化較頻繁的狀況。

（c）哈希查找雖然在理論上具有最短的平均查找長(zhǎng)度，但它占用的存儲(chǔ)空間較多，且在實(shí)際中惟獨(dú)哈希函數(shù)構(gòu)造得好才干達(dá)到常量級(jí)的平均查找長(zhǎng)度。而要想構(gòu)造出好的哈希函數(shù)，必需以大量數(shù)據(jù)為基礎(chǔ)，因此，哈希查找主要適用于數(shù)據(jù)分布已知的狀況。

4.請(qǐng)簡(jiǎn)述挨次查找對(duì)待查找數(shù)據(jù)集合的要求及挨次查找的詳細(xì)步驟。

挨次查找是一種最容易、直觀的查找算法，適用于采納任何存儲(chǔ)結(jié)構(gòu)的數(shù)據(jù)集合，其詳細(xì)步驟為：

（a）按預(yù)先規(guī)定的挨次依次將數(shù)據(jù)集合中每個(gè)元素的關(guān)鍵字與給定值舉行比較，若某個(gè)元素的關(guān)鍵字與給定值相同，則查找勝利；

（b）若遍歷全部元素后，仍沒有找到關(guān)鍵字與給定值相同的元素，則查找失敗。

5.請(qǐng)簡(jiǎn)述折半查找對(duì)待查找數(shù)據(jù)集合的要求及折半查找的詳細(xì)步驟。

折半查找，又稱二分查找，它要求數(shù)據(jù)集合采納挨次表存儲(chǔ)結(jié)構(gòu)，且數(shù)據(jù)集合中的元素是按關(guān)鍵字大小有序羅列的。假設(shè)數(shù)據(jù)集合的元素按關(guān)鍵字遞增羅列，折半查找算法的詳細(xì)步驟為：

（a）對(duì)于包含n個(gè)元素的遞增數(shù)據(jù)集合R={R[1],R[2],…,R[n]}（R[i]≤R[i+1]），按照給定元素K舉行折半查找，初始化待查找數(shù)據(jù)集合的下標(biāo)起始位置low=1和結(jié)束位置high=n。

（b）計(jì)算中間元素下標(biāo)mid=?(low+high)/2?，若R[mid]==K，則查找勝利，折半查找算法結(jié)束；若R[mid]K，則令high=mid-1。

（c）若新的待查找數(shù)據(jù)集合不為空，即low≤high，則返回到上一步在新的數(shù)據(jù)集合（R[low],R[low+1],…,R[high]）上繼續(xù)舉行折半查找；否則查找失敗。

6.請(qǐng)簡(jiǎn)述分塊查找對(duì)待查找數(shù)據(jù)集合的要求及分塊查找的詳細(xì)步驟。

在分塊查找算法中，除了待查找的數(shù)據(jù)集合外，還需建立一個(gè)索引表。待查數(shù)據(jù)集合與索引表的關(guān)系描述如下：（a）將包含n個(gè)元素的待查找數(shù)據(jù)集合勻稱分為b塊（即b個(gè)子集合），前b-1塊中元素?cái)?shù)目s=?n/b?，最后一塊中元素?cái)?shù)目小于等于s。（b）分塊后塊內(nèi)元素可以無序，但塊間必需有序，這里假設(shè)塊間為遞增羅列，即第i+1塊中的任一元素大于第i塊中的任一元素（i<b）。（c）構(gòu)造一個(gè)包含b個(gè)元素的索引表，用于記錄每塊的起始

位置和最大元素值。

分塊查找算法的詳細(xì)步驟為：（a）在索引表中查找，確定待查找元素在哪一塊，因?yàn)樗饕碛行颍虼丝梢允褂枚植檎宜惴ā＃╞）在已確定的塊中，舉行挨次查找。

7.請(qǐng)簡(jiǎn)述二叉排序樹的定義。

二叉排序樹，又稱二叉查找樹，它或者是一棵空樹，或者是具有如下性質(zhì)的二叉樹：（a）若它的左子樹非空，則左子樹上全部結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值。

（b）若它的右子樹非空，則右子樹上全部結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值。

（c）左、右子樹也分離是二叉排序樹。

8.請(qǐng)簡(jiǎn)述二叉排序樹的插入和創(chuàng)建過程。

二叉排序樹的插入過程：

在二叉排序樹中插入一個(gè)新結(jié)點(diǎn)，應(yīng)保證插入新結(jié)點(diǎn)后的二叉樹仍然是一棵二叉排序樹。對(duì)于一個(gè)給定元素K，將其插入到二叉排序樹中的詳細(xì)步驟如下：

（a）若二叉排序樹為一棵空樹，則將元素K作為二叉排序樹的根結(jié)點(diǎn)。

（b）若K等于根結(jié)點(diǎn)的值，則該元素已經(jīng)是二叉排序樹中的結(jié)點(diǎn)，不需重復(fù)插入，直接返回；若K小于根結(jié)點(diǎn)的值，則將K插入到左子樹中；若K大于根結(jié)點(diǎn)的值，則將K插入到右子樹中。重復(fù)該步驟，直至要插入的子樹為空，此時(shí)將K作為該子樹的根結(jié)點(diǎn)。

二叉排序樹的創(chuàng)建過程就是不斷插入新結(jié)點(diǎn)的過程。

9.請(qǐng)簡(jiǎn)述二叉排序樹的查找過程。

對(duì)于給定值K，先將K與根結(jié)點(diǎn)的值比較，若相等則查找勝利；若K小于根結(jié)點(diǎn)的值，則在左子樹中繼續(xù)舉行二叉排序樹的查找；否則，若K大于根結(jié)點(diǎn)的值，則在右子樹中繼續(xù)舉行二叉排序樹的查找。重復(fù)該過程，直至找到匹配的結(jié)點(diǎn)，查找勝利；或者子樹為空，查找失敗。

10.請(qǐng)簡(jiǎn)述哈希表的元素存儲(chǔ)原理。

確定一函數(shù)h，對(duì)于關(guān)鍵字值是k的元素，以k為自變量計(jì)算函數(shù)值h(k)，這個(gè)函數(shù)值被解釋為一片延續(xù)存儲(chǔ)空間中的一個(gè)地址（即數(shù)組中的一個(gè)下標(biāo)值），元素即被存入到這個(gè)地址中。

11.請(qǐng)簡(jiǎn)述常用的四種哈希函數(shù)及其計(jì)算規(guī)章。

除余法：選取一個(gè)適當(dāng)?shù)恼麛?shù)p（通常p為不大于哈希表存儲(chǔ)空間尺寸的最大素?cái)?shù)），以元素的關(guān)鍵字值k除以p，得到的余數(shù)作為元素的存儲(chǔ)地址，即h(k)=k%p。

數(shù)字分析法：若元素的關(guān)鍵字由多位組成，且關(guān)鍵字的位數(shù)比存儲(chǔ)空間地址碼位數(shù)多、每一位的取值范圍及關(guān)鍵字的取值分布狀況預(yù)先知道，則可以對(duì)元素關(guān)鍵字的各位舉行分析，去掉分布較集中的位、保留分布較勻稱的位。

折疊法：若元素的關(guān)鍵字由多位組成，且關(guān)鍵字的位數(shù)比存儲(chǔ)空間地址碼位數(shù)多，但關(guān)鍵字的取值分布狀況未知，則可以用折疊法將關(guān)鍵字分為幾段（除了最后一段位數(shù)可以少一些，其他各段的位數(shù)均等于存儲(chǔ)空間地址碼位數(shù)），并將全部段的值做疊加求和運(yùn)算，將疊加和的最高位進(jìn)位舍去后取剩余部分作為元素的存儲(chǔ)地址。

平方取中法：對(duì)元素的關(guān)鍵字值求平方，并取中間幾位作為元素的存儲(chǔ)地址。

12.請(qǐng)簡(jiǎn)述常用的兩種哈希表矛盾處理辦法。

開放定址法：根據(jù)某個(gè)探查序列在哈希表中舉行搜尋，直至找到一個(gè)空閑的地址，將發(fā)生矛盾的新元素存儲(chǔ)在該地址中。

拉鏈法：將全部同義詞存儲(chǔ)在一個(gè)線性鏈表中，從而避開開放定址法中的“二次聚攏”現(xiàn)象。用拉鏈法構(gòu)造的哈希表，若其有m個(gè)存儲(chǔ)地址（下標(biāo)為0,1,…,m-1），則每個(gè)地址存儲(chǔ)一個(gè)線性鏈表的頭指針，映射到地址i的元素以結(jié)點(diǎn)的方式插入到地址i所對(duì)應(yīng)的鏈表中。

第9章文件

1.請(qǐng)簡(jiǎn)述文件的定義。

文件，是由大量具有相同性質(zhì)的記錄組成的集合。

2.請(qǐng)簡(jiǎn)述文件的組成。

文件是大量性質(zhì)相同的數(shù)據(jù)記錄的集合，即一個(gè)文件包含一條或多條記錄。

記錄是一個(gè)實(shí)體的全部數(shù)據(jù)項(xiàng)的集合，即一條記錄包含一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)。

數(shù)據(jù)項(xiàng)（也稱為字段或?qū)傩裕┦欠从硨?shí)體某一方面屬性的數(shù)據(jù)表示，是文件存取最基本的操作對(duì)象。

3.請(qǐng)簡(jiǎn)述文件的分類。

按文件中記錄的信息長(zhǎng)度，可以將文件分為定長(zhǎng)記錄文件和不定長(zhǎng)記錄文件。若每個(gè)記錄含有相同長(zhǎng)度的信息，則稱這類記錄為定長(zhǎng)記錄；否則，若每個(gè)記錄含有不同長(zhǎng)度的信息，則稱這類記錄為不定長(zhǎng)記錄。由定長(zhǎng)記錄組成的文件稱為定長(zhǎng)文件；由不定長(zhǎng)記錄組成的文件則稱為不定長(zhǎng)文件。

按記錄中關(guān)鍵字的數(shù)目，可以將文件分為單關(guān)鍵字文件和多關(guān)鍵字文件。若文件中的記錄惟獨(dú)一個(gè)用于唯一標(biāo)識(shí)記錄的主關(guān)鍵字，則這類文件稱為單關(guān)鍵字文件；若文件中的記錄除了含有一個(gè)主關(guān)鍵字之外，還包含若干次關(guān)鍵字，則這類文件稱為多關(guān)鍵字文件。

4.請(qǐng)簡(jiǎn)述文件檢索操作中的四種查詢方式。

按照檢索條件的不同可以分為以下4種查詢方式：

（a）容易查詢：按照給定值x按單個(gè)關(guān)鍵字查詢關(guān)鍵字值k等于x的記錄。

（b）區(qū)域查詢：按照給定取值范圍按單個(gè)關(guān)鍵字查詢滿足條件的記錄。

（c）函數(shù)查詢：按照統(tǒng)計(jì)函數(shù)計(jì)算的值查詢記錄。

（d）布爾查詢：將以上3種查詢用規(guī)律運(yùn)算符(包括規(guī)律與、規(guī)律或、規(guī)律非)銜接起來所形成的查詢。

5.請(qǐng)簡(jiǎn)述文件各維護(hù)操作的含義和過程。

文件維護(hù)是指對(duì)文件中記錄所舉行的插入、刪除、修改等操作。這些操作的詳細(xì)含義和操作過程描述如下：

（a）插入：向文件中添加一條新的記錄。若文件按某個(gè)關(guān)鍵字挨次羅列，則插入記錄前普通要先通過檢索確定插入點(diǎn)的位置。

（b）刪除：從文件中刪除一條記錄。刪除記錄前普通要先通過檢索確定所要?jiǎng)h除記錄的位置。

（c）修改：對(duì)記錄中的一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)舉行修改。若文件按某個(gè)關(guān)鍵字挨次羅列，且對(duì)關(guān)鍵字值舉行了修改操作，則修改后還需將記錄移動(dòng)到正確的位置（普通采納先刪除再插入的方式實(shí)現(xiàn)）。

6.請(qǐng)簡(jiǎn)述文件的四種基本組織方式。

挨次結(jié)構(gòu)、索引結(jié)構(gòu)、散列結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)。

7.請(qǐng)簡(jiǎn)述磁盤的規(guī)律結(jié)構(gòu)。

磁盤的結(jié)構(gòu)如下：

（a）一個(gè)磁盤包含若干個(gè)盤片，全部盤片組成了盤片組；每個(gè)盤片有上下兩面，稱為盤面；每個(gè)盤面上有無數(shù)同心圓形式的磁道，數(shù)據(jù)就存放在這些磁道上；每個(gè)磁道又可以劃分為若干段，稱為扇區(qū)，一個(gè)扇區(qū)就是一次讀寫的最小數(shù)據(jù)量。

（b）每個(gè)盤面都配有一個(gè)讀寫磁頭，通過讀寫磁頭可以對(duì)磁道上的數(shù)據(jù)舉行讀寫操作；

全部讀寫磁頭都安裝在動(dòng)臂上，通過動(dòng)臂可以將讀寫磁頭移動(dòng)到任一磁道上；全部盤面上具有相同半徑的磁道就構(gòu)成了圓柱面，一個(gè)磁盤上圓柱面的個(gè)數(shù)就是一個(gè)盤面上的磁道數(shù)，同一時(shí)刻全部讀寫磁頭都位于一個(gè)圓柱面上。

（c）主軸帶動(dòng)全部盤面高速旋轉(zhuǎn)，使得讀寫磁頭可以拜訪到一個(gè)磁道上的全部扇區(qū)。

8.請(qǐng)簡(jiǎn)述對(duì)磁盤存儲(chǔ)器舉行一次讀寫操作的詳細(xì)過程。

對(duì)磁盤存儲(chǔ)器舉行一次讀寫操作的詳細(xì)步驟為：

（a）按照待讀寫數(shù)據(jù)所處的柱面，用動(dòng)臂將讀寫磁頭移動(dòng)到此柱面上。

（b）按照待讀寫數(shù)據(jù)所處的扇區(qū)，用主軸帶動(dòng)盤面將該扇區(qū)轉(zhuǎn)到讀寫磁頭下面。

（c）用指定盤面上的讀寫磁頭讀寫所需數(shù)據(jù)。

9.請(qǐng)簡(jiǎn)述在磁盤上存儲(chǔ)信息的原則。

盤面的轉(zhuǎn)速很快，磁盤讀寫數(shù)據(jù)的時(shí)光大部分花在柱面定位上。尋查時(shí)光的長(zhǎng)短取決于讀寫磁頭移過的柱面數(shù)，所以在磁盤上存儲(chǔ)信息時(shí)應(yīng)盡量將相關(guān)的信息放在同一柱面或者鄰近柱面上，以削減尋查時(shí)光。

10.請(qǐng)簡(jiǎn)述挨次文件的定義和分類。

挨次文件的定義：

挨次文件是結(jié)構(gòu)最容易的文件，文件中記錄的物理挨次與規(guī)律挨次全都，即記錄按其規(guī)律挨次依次存放在文件中。

挨次文件的分類：

根據(jù)存儲(chǔ)方式的不同，挨次文件可以分為延續(xù)挨次文件和串聯(lián)挨次文件。在延續(xù)挨次文件中，所有記錄挨次地存放在外存的一片延續(xù)存儲(chǔ)空間中。延續(xù)挨次文件的優(yōu)點(diǎn)是存取速度快，缺點(diǎn)是存儲(chǔ)空間尺寸需預(yù)先確定。在串聯(lián)挨次文件中，以塊為單位將記錄存儲(chǔ)在外存上，塊中的各記錄挨次存放在一片延續(xù)存儲(chǔ)空間中，但塊與塊之間可以不延續(xù)，通過鏈指針將各塊按一定挨次銜接起來。串聯(lián)挨次文件的優(yōu)點(diǎn)是文件便于擴(kuò)充，缺點(diǎn)是存取速度慢。

根據(jù)記錄是否有序，挨次文件可以分為有序挨次文件和無序挨次文件。在有序挨次文件中，所有記錄按主關(guān)鍵字有序羅列；在無序挨次文件中，記錄按實(shí)際插入挨次羅列。有序挨次文件的優(yōu)點(diǎn)是若記錄定長(zhǎng)則按主關(guān)鍵字檢索時(shí)速度較快，無序挨次文件的優(yōu)點(diǎn)是插入記錄時(shí)效率較高。

11.請(qǐng)簡(jiǎn)述挨次文件批量處理的步驟。

將待處理的挨次文件稱為主文件，主文件按主關(guān)鍵字大小挨次羅列；對(duì)文件的插入、刪除、修改等操作哀求所有放在事務(wù)文件中。按照事務(wù)文件中的操作對(duì)主文件舉行更新生成新的主文件，詳細(xì)處理步驟如下：

（a）對(duì)事務(wù)文件根據(jù)主文件中主關(guān)鍵字的挨次舉行排序（對(duì)于修改主關(guān)鍵字值的操作，應(yīng)轉(zhuǎn)為刪除記錄和插入記錄兩個(gè)操作）。

（b）挨次讀出主文件與事務(wù)文件中的記錄，比較它們的主關(guān)鍵字值：

①若主文件記錄的關(guān)鍵字值小于事務(wù)文件記錄的關(guān)鍵字值，則說明沒有對(duì)該主文件記錄做任何操作，此時(shí)將主文件記錄直接寫入新的主文件中，并讀取下一條主文件記錄。

②若關(guān)鍵字值相同，則依據(jù)事務(wù)文件記錄舉行更改或刪除操作，若為刪除操作，則主文件記錄不需要寫入新的主文件中，若為修改操作則要將修改后的記錄寫入新的主文件中，操作完畢后分離讀取下一條主文件記錄和事務(wù)文件記錄。

③若主文件記錄的關(guān)鍵字值大于事務(wù)文件記錄的關(guān)鍵字值，則為插入操作，需將事務(wù)文件中的記錄直接寫入到新的主文件中，并讀取下一條事務(wù)文件記錄。

12.請(qǐng)簡(jiǎn)述索引文件的構(gòu)成。

索引文件由主文件和索引表兩部分構(gòu)成。主文件中存儲(chǔ)了全部的數(shù)據(jù)記錄；索引表是一個(gè)映射關(guān)系表，存儲(chǔ)了規(guī)律記錄和物理記錄的一一對(duì)應(yīng)關(guān)系。

13.請(qǐng)簡(jiǎn)述索引文件（即索引非挨次文件）和索引挨次文件的區(qū)分。

索引非挨次文件的主文件中各記錄是無序的；索引挨次文件的主文件中各記錄是按主關(guān)鍵字有序羅列的。

14.請(qǐng)簡(jiǎn)述索引文件的檢索過程。

索引文件的檢索過程為：

（a）將索引表讀入內(nèi)存中，并按照檢索條件在索引表中舉行查找（因?yàn)樗饕?xiàng)按關(guān)鍵字有序羅列，因此在索引表上可以采納折半查找算法）。

（b）若索引表中存在匹配項(xiàng)，則按照匹配索引項(xiàng)中存儲(chǔ)的物理地址直接讀取外存上的相應(yīng)記錄；若索引表中不存在該記錄，則說明外存上也不存在該記錄、不需做外存拜訪操作。

15.請(qǐng)簡(jiǎn)述索引文件插入、刪除、修改等維護(hù)操作的過程。

插入：在索引文件中插入一條新的記錄時(shí)，直接將該記錄寫入主文件的末尾，并在索引表中插入索引項(xiàng)。

刪除：在刪除一條記錄時(shí)，只需在索引表中刪除對(duì)應(yīng)的索引項(xiàng)即可。

修改：在修改記錄時(shí)，需將修改后的記錄寫入主文件的末尾，并同時(shí)對(duì)索引表舉行修改、將索引項(xiàng)中的物理地址改為修改后記錄的存儲(chǔ)地址。

16.請(qǐng)簡(jiǎn)述稠密索引和稀疏索引的區(qū)分。

在索引非挨次文件中，記錄沒有按關(guān)鍵字有序羅列，因此在建立索引表時(shí)，每個(gè)記錄都必需對(duì)應(yīng)一個(gè)索引項(xiàng)，這樣建立的索引表稱為稠密索引。這類索引表雖然管理成本較高，但它的優(yōu)點(diǎn)是按照索引表即可確定待檢索記錄是否存在并可以按照索引項(xiàng)直接定位到記錄，削減了外存操作。

在索引挨次文件中，記錄按關(guān)鍵字有序羅列，因此可以對(duì)文件中的記錄分塊，每塊對(duì)應(yīng)一個(gè)索引項(xiàng)，這樣建立的索引表稱為稀疏索引。在做檢索操作時(shí)，這類索引表只能給出匹配記錄可能在哪個(gè)范圍中，無法直接定位到記錄，但它占用的存儲(chǔ)空間小、便于管理。

17.請(qǐng)簡(jiǎn)述ISAM文件的組織辦法。

在ISAM文件中，每個(gè)柱面的磁道被分為3個(gè)部分：

（a）一部分磁道作為記錄存儲(chǔ)的基本區(qū)，其中每一磁道將記錄按主關(guān)鍵字大小舉行有序挨次存儲(chǔ)。

（b）一部分磁道作為記錄存儲(chǔ)的溢出區(qū)，在一個(gè)已滿磁道中插入新記錄時(shí)，就會(huì)產(chǎn)生溢出的記錄（即該磁道容納不下的記錄），這些溢出記錄以鏈表形式存儲(chǔ)在溢出區(qū)中。

（c）一部分磁道作為索引區(qū)，用于存儲(chǔ)磁道索引表。與基本區(qū)和溢出區(qū)相對(duì)應(yīng)，表中的每一索引項(xiàng)又由基本索引項(xiàng)和溢出索引項(xiàng)組成?；舅饕?xiàng)用來存放基本區(qū)一個(gè)磁道中記錄的最大關(guān)鍵字值和第一個(gè)記錄的位置；溢出索引項(xiàng)用來存放從該磁道溢出記錄的最大關(guān)鍵字值和該磁道在溢出區(qū)中的第一個(gè)溢出記錄的位置。

18.請(qǐng)簡(jiǎn)述VSAM文件的組織辦法。

VSAM文件由索引集、挨次集和數(shù)據(jù)集三部分組成。文件的記錄都存放在數(shù)據(jù)集中，數(shù)據(jù)集中的每一個(gè)結(jié)點(diǎn)稱為一個(gè)控制區(qū)間，該區(qū)間是一片延續(xù)的存儲(chǔ)空間、按關(guān)鍵字挨次存儲(chǔ)若干條記錄；挨次集中存放每一控制區(qū)間的索引項(xiàng)，索引項(xiàng)包括兩部分內(nèi)容：控制區(qū)間的最大關(guān)鍵字值和指向該控制區(qū)間的指針，若干規(guī)律上相鄰的控制區(qū)間的索引項(xiàng)就構(gòu)成了挨次集中的一個(gè)結(jié)點(diǎn)；索引集是按樹型層次結(jié)構(gòu)組織的索引集合，雙親結(jié)點(diǎn)包含了指向孩子結(jié)點(diǎn)的指針及該孩子結(jié)點(diǎn)中的最大關(guān)鍵字值，以挨次集中的結(jié)點(diǎn)作為葉子結(jié)點(diǎn)，可以構(gòu)造一棵以索引集為非葉子結(jié)點(diǎn)的B+樹。

19.請(qǐng)簡(jiǎn)述散列文件的組織辦法。

散列文件中的記錄是以桶為單位成組存放的。若一個(gè)桶能存放m條記錄，則當(dāng)桶中已有m條同義詞記錄時(shí)，再存放第m+1條同義詞記錄就會(huì)發(fā)生“溢出”。在散列文件中，通

常采納拉鏈法作為矛盾處理辦法，即將第m+1條同義詞記錄存放到另一個(gè)稱為“溢出桶”的桶中，相應(yīng)地，將存放前m條同義詞記錄的桶稱為“基桶”，在基桶中設(shè)置一個(gè)指向溢出桶的指針。

20.請(qǐng)簡(jiǎn)述多關(guān)鍵字文件