數(shù)據(jù)結(jié)構(gòu) 課后習(xí)題答案 清華大學(xué)出版社 殷人昆

《數(shù)據(jù)結(jié)構(gòu) 課后習(xí)題答案 清華大學(xué)出版社 殷人昆》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu) 課后習(xí)題答案 清華大學(xué)出版社 殷人昆（152頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、第1章 緒論1-1什么是數(shù)據(jù)? 它與信息是什么關(guān)系?【解答】什么是信息？廣義地講，信息就是消息。宇宙三要素（物質(zhì)、能量、信息）之一。它是現(xiàn)實(shí)世界各種事物在人們頭腦中的反映。此外，人們通過科學(xué)儀器能夠認(rèn)識(shí)到的也是信息。信息的特征為：可識(shí)別、可存儲(chǔ)、可變換、可處理、可傳遞、可再生、可壓縮、可利用、可共享。什么是數(shù)據(jù)？因?yàn)樾畔⒌谋憩F(xiàn)形式十分廣泛，許多信息在計(jì)算機(jī)中不方便存儲(chǔ)和處理，例如，一個(gè)大樓中4部電梯在軟件控制下調(diào)度和運(yùn)行的狀態(tài)、一個(gè)商店中商品的在庫(kù)明細(xì)表等，必須將它們轉(zhuǎn)換成數(shù)據(jù)才能很方便地在計(jì)算機(jī)中存儲(chǔ)、處理、變換。因此，數(shù)據(jù)(data)是信息的載體，是描述客觀事物的數(shù)、字符、以及所有能輸入到

2、計(jì)算機(jī)中并被計(jì)算機(jī)程序識(shí)別和處理的符號(hào)的集合。在計(jì)算機(jī)中，信息必須以數(shù)據(jù)的形式出現(xiàn)。1-2什么是數(shù)據(jù)結(jié)構(gòu)? 有關(guān)數(shù)據(jù)結(jié)構(gòu)的討論涉及哪三個(gè)方面?【解答】數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)以及相互之間的關(guān)系。記為：數(shù)據(jù)結(jié)構(gòu) = D, R 。其中，D是某一數(shù)據(jù)對(duì)象，R是該對(duì)象中所有數(shù)據(jù)成員之間的關(guān)系的有限集合。有關(guān)數(shù)據(jù)結(jié)構(gòu)的討論一般涉及以下三方面的內(nèi)容： 數(shù)據(jù)成員以及它們相互之間的邏輯關(guān)系，也稱為數(shù)據(jù)的邏輯結(jié)構(gòu)，簡(jiǎn)稱為數(shù)據(jù)結(jié)構(gòu)； 數(shù)據(jù)成員極其關(guān)系在計(jì)算機(jī)存儲(chǔ)器內(nèi)的存儲(chǔ)表示，也稱為數(shù)據(jù)的物理結(jié)構(gòu)，簡(jiǎn)稱為存儲(chǔ)結(jié)構(gòu)； 施加于該數(shù)據(jù)結(jié)構(gòu)上的操作。數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲(chǔ)不是一碼事，是與計(jì)算機(jī)存儲(chǔ)無

3、關(guān)的。因此，數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題中抽象出來的數(shù)據(jù)模型，是數(shù)據(jù)的應(yīng)用視圖。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏輯數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中的實(shí)現(xiàn)（亦稱為映像），它是依賴于計(jì)算機(jī)的，是數(shù)據(jù)的物理視圖。數(shù)據(jù)的操作是定義于數(shù)據(jù)邏輯結(jié)構(gòu)上的一組運(yùn)算，每種數(shù)據(jù)結(jié)構(gòu)都有一個(gè)運(yùn)算的集合。例如搜索、插入、刪除、更新、排序等。1-3數(shù)據(jù)的邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩大類。線性結(jié)構(gòu)包括數(shù)組、鏈表、 棧、隊(duì)列、優(yōu)先級(jí)隊(duì)列等; 非線性結(jié)構(gòu)包括樹、圖等、這兩類結(jié)構(gòu)各自的特點(diǎn)是什么？【解答】線性結(jié)構(gòu)的特點(diǎn)是：在結(jié)構(gòu)中所有數(shù)據(jù)成員都處于一個(gè)序列中，有且僅有一個(gè)開始成員和一個(gè)終端成員，并且所有數(shù)據(jù)成員都最多有一個(gè)直接前驅(qū)和一個(gè)

4、直接后繼。例如，一維數(shù)組、線性表等就是典型的線性結(jié)構(gòu)非線性結(jié)構(gòu)的特點(diǎn)是：一個(gè)數(shù)據(jù)成員可能有零個(gè)、一個(gè)或多個(gè)直接前驅(qū)和直接后繼。例如，樹、圖或網(wǎng)絡(luò)等都是典型的非線性結(jié)構(gòu)。1-4什么是抽象數(shù)據(jù)類型？試用C+的類聲明定義“復(fù)數(shù)”的抽象數(shù)據(jù)類型。要求(1) 在復(fù)數(shù)內(nèi)部用浮點(diǎn)數(shù)定義它的實(shí)部和虛部。(2) 實(shí)現(xiàn)3個(gè)構(gòu)造函數(shù)：缺省的構(gòu)造函數(shù)沒有參數(shù)；第二個(gè)構(gòu)造函數(shù)將雙精度浮點(diǎn)數(shù)賦給復(fù)數(shù)的實(shí)部，虛部置為0；第三個(gè)構(gòu)造函數(shù)將兩個(gè)雙精度浮點(diǎn)數(shù)分別賦給復(fù)數(shù)的實(shí)部和虛部。(3) 定義獲取和修改復(fù)數(shù)的實(shí)部和虛部，以及+、-、*、/等運(yùn)算的成員函數(shù)。(4) 定義重載的流函數(shù)來輸出一個(gè)復(fù)數(shù)。【解答】抽象數(shù)據(jù)類型通常是指由用

5、戶定義，用以表示應(yīng)用問題的數(shù)據(jù)模型。抽象數(shù)據(jù)類型由基本的數(shù)據(jù)類型構(gòu)成，并包括一組相關(guān)的服務(wù)。/在頭文件complex.h中定義的復(fù)數(shù)類#ifndef _complex_h_#define _complex_h_#include class comlex public: complex ( ) Re = Im = 0; /不帶參數(shù)的構(gòu)造函數(shù) complex ( double r ) Re = r; Im = 0; /只置實(shí)部的構(gòu)造函數(shù) complex ( double r, double i ) Re = r; Im = i; /分別置實(shí)部、虛部的構(gòu)造函數(shù) double getReal ( )

6、return Re; /取復(fù)數(shù)實(shí)部 double getImag ( ) return Im; /取復(fù)數(shù)虛部 void setReal ( double r ) Re = r; /修改復(fù)數(shù)實(shí)部 void setImag ( double i ) Im = i; /修改復(fù)數(shù)虛部 complex& operator = ( complex& ob) Re = ob.Re; Im = ob.Im; /復(fù)數(shù)賦值 complex& operator + ( complex& ob );/重載函數(shù)：復(fù)數(shù)四則運(yùn)算 complex& operator ( complex& ob ); complex& ope

7、rator * ( complex& ob ); complex& operator / ( complex& ob ); friend ostream& operator ( ostream& os, complex& c );/友元函數(shù)：重載private: double Re, Im;/復(fù)數(shù)的實(shí)部與虛部;#endif /復(fù)數(shù)類complex的相關(guān)服務(wù)的實(shí)現(xiàn)放在C+源文件complex.cpp中#include #include #include “complex.h”complex& complex : operator + ( complex & ob ) /重載函數(shù)：復(fù)數(shù)加法運(yùn)算。c

8、omplex * result = new complex ( Re + ob.Re, Im + ob.Im );return *result; complex& complex : operator ( complex& ob ) /重載函數(shù)：復(fù)數(shù)減法運(yùn)算 complex * result = new complex ( Re ob.Re, Im ob.Im );return * result;complex& complex : operator * ( complex& ob ) /重載函數(shù)：復(fù)數(shù)乘法運(yùn)算complex * result = new complex ( Re * ob.R

9、e Im * ob.Im, Im * ob.Re + Re * ob.Im );return *result;complex& complex : operator / ( complex& ) /重載函數(shù)：復(fù)數(shù)除法運(yùn)算double d = ob.Re * ob.Re + ob.Im * ob.Im;complex * result = new complex ( ( Re * ob.Re + Im * ob.Im ) / d,( Im * ob. Re Re * ob.Im ) / d );return * result;friend ostream& operator ( ostream&

10、 os, complex & ob ) /友元函數(shù)：重載，將復(fù)數(shù)ob輸出到輸出流對(duì)象os中。 return os ob.Re = 0.0 ) ? “+” : “-” fabs ( ob.Im ) “i”;1-5 用歸納法證明：(1) (2) (3) 【證明】略1-6 什么是算法? 算法的5個(gè)特性是什么? 試根據(jù)這些特性解釋算法與程序的區(qū)別。【解答】通常，定義算法為“為解決某一特定任務(wù)而規(guī)定的一個(gè)指令序列?！币粋€(gè)算法應(yīng)當(dāng)具有以下特性： 有輸入。一個(gè)算法必須有0個(gè)或多個(gè)輸入。它們是算法開始運(yùn)算前給予算法的量。這些輸入取自于特定的對(duì)象的集合。它們可以使用輸入語(yǔ)句由外部提供，也可以使用賦值語(yǔ)句在算法內(nèi)

11、給定。 有輸出。一個(gè)算法應(yīng)有一個(gè)或多個(gè)輸出，輸出的量是算法計(jì)算的結(jié)果。 確定性。算法的每一步都應(yīng)確切地、無歧義地定義。對(duì)于每一種情況，需要執(zhí)行的動(dòng)作都應(yīng)嚴(yán)格地、清晰地規(guī)定。 有窮性。一個(gè)算法無論在什么情況下都應(yīng)在執(zhí)行有窮步后結(jié)束。 有效性。算法中每一條運(yùn)算都必須是足夠基本的。就是說，它們?cè)瓌t上都能精確地執(zhí)行，甚至人們僅用筆和紙做有限次運(yùn)算就能完成。算法和程序不同，程序可以不滿足上述的特性(4)。例如，一個(gè)操作系統(tǒng)在用戶未使用前一直處于“等待”的循環(huán)中，直到出現(xiàn)新的用戶事件為止。這樣的系統(tǒng)可以無休止地運(yùn)行，直到系統(tǒng)停工。此外，算法是面向功能的，通常用面向過程的方式描述；程序可以用面向?qū)ο蠓绞酱罱?/p>

12、它的框架。1-7 設(shè)n為正整數(shù), 分析下列各程序段中加下劃線的語(yǔ)句的程序步數(shù)。 (1) for (int i = 1; i = n; i+) (2) x = 0; y = 0; for (int j = 1; j = n; j+) for (int i = 1; i = n; i+) cij = 0.0; for (int j = 1; j = i; j+) for (int k = 1; k = n; k+) for (int k = 1; k = j; k+) cij = cij + aik * bkj; x = x + y; (3) int i = 1, j = 1; (4) int i

13、 =1; while (i=n & j=n) do i = i + 1; j = j + i; for (int j = 1; j = n; j+) i = i + j; while ( i arraySize或者對(duì)于某一個(gè)k (0 k n)，使得k!*2k maxInt時(shí)，應(yīng)按出錯(cuò)處理?？捎腥缦氯N不同的出錯(cuò)處理方式：(1) 用cerr及exit (1)語(yǔ)句來終止執(zhí)行并報(bào)告錯(cuò)誤；(2) 用返回整數(shù)函數(shù)值0, 1來實(shí)現(xiàn)算法，以區(qū)別是正常返回還是錯(cuò)誤返回；(3) 在函數(shù)的參數(shù)表設(shè)置一個(gè)引用型的整型變量來區(qū)別是正常返回還是某種錯(cuò)誤返回。試討論這三種方法各自的優(yōu)缺點(diǎn)，并以你認(rèn)為是最好的方式實(shí)現(xiàn)它?！?/p>

14、解答】#include iostream.h#define arraySize 100#define MaxInt 0x7fffffffint calc ( int T , int n ) int i, value = 1;if ( n != 0 ) int edge = MaxInt / n / 2;for ( i = 1; i edge ) return 0;value *= n * 2;Tn = value;cout A n = Tn endl;return 1;void main ( ) int AarraySize;int i;for ( i = 0; i arraySize; i+

15、 )if ( !calc ( A, i ) ) cout failed at i . endl;break;1-9 (1) 在下面所給函數(shù)的適當(dāng)?shù)胤讲迦胗?jì)算count的語(yǔ)句：void d (ArrayElement x , int n ) int i = 1; do xi += 2; i +=2; while (i = n ); i = 1; while ( i = (n/2) ) xi += xi+1; i+; (2) 將由(1)所得到的程序化簡(jiǎn)。使得化簡(jiǎn)后的程序與化簡(jiǎn)前的程序具有相同的count值。(3) 程序執(zhí)行結(jié)束時(shí)的count值是多少？(4) 使用執(zhí)行頻度的方法計(jì)算這個(gè)程序的程序步數(shù)

16、，畫出程序步數(shù)統(tǒng)計(jì)表。 【解答】(1) 在適當(dāng)?shù)牡胤讲迦胗?jì)算count語(yǔ)句void d ( ArrayElement x , int n ) int i = 1; count +; do xi += 2; count +;i += 2; count +; count +;/針對(duì)while語(yǔ)句 while ( i = n ); i = 1; count +; while ( i = ( n / 2 ) ) count +;/針對(duì)while語(yǔ)句xi += xi+1;count +;i +;count +; count +;/針對(duì)最后一次while語(yǔ)句(2) 將由(1)所得到的程序化簡(jiǎn)?；?jiǎn)后的程序

17、與原來的程序有相同的count值：void d ( ArrayElement x , int n ) int i = 1;do count += 3; i += 2; while ( i = n ); i = 1;while ( i = ( n / 2 ) ) count += 3; i +; count += 3;(3) 程序執(zhí)行結(jié)束后的count值為 3n + 3。當(dāng)n為偶數(shù)時(shí)，count = 3 * ( n / 2 ) + 3 * ( n / 2 ) + 3 = 3 * n + 3當(dāng)n為奇數(shù)時(shí)，count = 3 * ( ( n + 1 ) / 2 ) + 3 * ( ( n 1 ) /

18、 2 ) + 3 = 3 * n + 3(4) 使用執(zhí)行頻度的方法計(jì)算程序的執(zhí)行步數(shù)，畫出程序步數(shù)統(tǒng)計(jì)表：行 號(hào) 程 序 語(yǔ) 句一次執(zhí)行步數(shù)執(zhí)行頻度程序步數(shù) 1 2 3 4 5 6 7 8 9 10 11 12void d ( ArrayElement x , int n ) int i = 1; do xi += 2;i += 2; while ( i = n ); i = 1; while ( i m ) m = b; if ( c m ) m = c; return m; 【方案2】(此程序可修改循環(huán)終止變量擴(kuò)大到n個(gè)整數(shù))int max ( int a, int b, int c )

19、int data3 = a, b, c ; int m = 0;/開始時(shí)假定data0最大 for ( int i = 1; i datam ) m = i;/m記錄新的最大者 return datam;(2) 求3個(gè)整數(shù)中的最小整數(shù)的函數(shù)可將上面求最大整數(shù)的函數(shù)稍做修改，“”改為“”，可得求最小整數(shù)函數(shù)。 【方案1】int min ( int a, int b, int c ) int m = a; if ( b m ) m = b; if ( c m ) m = c; return m; 【方案2】(此程序可修改循環(huán)終止變量擴(kuò)大到n個(gè)整數(shù))int max ( int a, int b, i

20、nt c ) int data3 = a, b, c ; int m = 0;/開始時(shí)假定data0最小 for ( int i = 1; i 3; i+ )/與其他整數(shù)逐個(gè)比較if ( datai ”改為“”，可得求最小整數(shù)函數(shù)。 【方案1】int mid ( int a, int b, int c ) int m1 = a, m2; if ( b m1 ) m2 = m1; m1 = b; else m2 = b; if ( c m1 ) m2 = m1; m1 = c; else if ( c m2 ) m2 = c; return m2; 【方案2】(此程序可修改循環(huán)終止變量擴(kuò)大到n個(gè)

21、整數(shù)尋求次小元素)int mid ( int a, int b, int c ) int data3 = a, b, c ; int m1 = 0, m2 = -1; /m1指示最小整數(shù), m2指示次小整數(shù) for ( int i = 1; i 3; i+ )/與其他整數(shù)逐個(gè)比較if ( datai datam1 ) m2 = m1; m1 = i; /原來最小變?yōu)榇涡? m1指示新的最小 else if ( m2 = -1 | datai datam2 ) m2 = i;/m2記錄新的次小者 return datam2;第10章 索引與散列10-1 什么是靜態(tài)索引結(jié)構(gòu)？什么是動(dòng)態(tài)索引結(jié)構(gòu)？它

22、們各有哪些優(yōu)缺點(diǎn)？【解答】靜態(tài)索引結(jié)構(gòu)指這種索引結(jié)構(gòu)在初始創(chuàng)建，數(shù)據(jù)裝入時(shí)就已經(jīng)定型，而且在整個(gè)系統(tǒng)運(yùn)行期間，樹的結(jié)構(gòu)不發(fā)生變化，只是數(shù)據(jù)在更新。動(dòng)態(tài)索引結(jié)構(gòu)是指在整個(gè)系統(tǒng)運(yùn)行期間，樹的結(jié)構(gòu)隨數(shù)據(jù)的增刪及時(shí)調(diào)整，以保持最佳的搜索效率。靜態(tài)索引結(jié)構(gòu)的優(yōu)點(diǎn)是結(jié)構(gòu)定型，建立方法簡(jiǎn)單，存取方便；缺點(diǎn)是不利于更新，插入或刪除時(shí)效率低。動(dòng)態(tài)索引結(jié)構(gòu)的優(yōu)點(diǎn)是在插入或刪除時(shí)能夠自動(dòng)調(diào)整索引樹結(jié)構(gòu)，以保持最佳的搜索效率；缺點(diǎn)是實(shí)現(xiàn)算法復(fù)雜。10-2 設(shè)有10000個(gè)記錄對(duì)象, 通過分塊劃分為若干子表并建立索引, 那么為了提高搜索效率, 每一個(gè)子表的大小應(yīng)設(shè)計(jì)為多大? 【解答】每個(gè)子表的大小 s = n = 10

23、000 = 100 個(gè)記錄對(duì)象。10-3如果一個(gè)磁盤頁(yè)塊大小為1024 (=1K) 字節(jié)，存儲(chǔ)的每個(gè)記錄對(duì)象需要占用16字節(jié)，其中關(guān)鍵碼占4字節(jié)，其它數(shù)據(jù)占12字節(jié)。所有記錄均已按關(guān)鍵碼有序地存儲(chǔ)在磁盤文件中，每個(gè)頁(yè)塊的第1個(gè)記錄用于存放線性索引。另外在內(nèi)存中開辟了256K字節(jié)的空間可用于存放線性索引。試問：(1) 若將線性索引常駐內(nèi)存，文件中最多可以存放多少個(gè)記錄？(每個(gè)索引項(xiàng)8字節(jié)，其中關(guān)鍵碼4字節(jié)，地址4字節(jié))(2) 如果使用二級(jí)索引，第二級(jí)索引占用1024字節(jié)（有128個(gè)索引項(xiàng)），這時(shí)文件中最多可以存放多少個(gè)記錄？【解答】(1) 因?yàn)橐粋€(gè)磁盤頁(yè)塊大小為1024字節(jié)，每個(gè)記錄對(duì)象需要占用

24、16字節(jié)，則每個(gè)頁(yè)塊可存放1024 / 16 = 64個(gè)記錄，除第一個(gè)記錄存儲(chǔ)線性索引外，每個(gè)頁(yè)塊可存儲(chǔ)63個(gè)記錄對(duì)象。又因?yàn)樵诖疟P文件中所有記錄對(duì)象按關(guān)鍵碼有序存儲(chǔ)，所以線性索引可以是稀疏索引，每一個(gè)索引項(xiàng)存放一個(gè)頁(yè)塊的最大關(guān)鍵碼及該頁(yè)塊的地址。若線性索引常駐內(nèi)存，那么它最多可存放256 * (1024 / 8 ) = 256 * 128 = 32768個(gè)索引項(xiàng)，文件中可存放 32768 * 63 = 2064384個(gè)記錄對(duì)象。(2) 由于第二級(jí)索引占用1024個(gè)字節(jié)，內(nèi)存中還剩255K 字節(jié)用于第一級(jí)索引。第一級(jí)索引有255 * 128 = 32640個(gè)索引項(xiàng)，作為稀疏索引，每個(gè)索引項(xiàng)索引

25、一個(gè)頁(yè)塊，則索引文件中可存放32640 * 63 = 2056320。 397 Hello World! 82 XYZ 1038 This string is rather long 1037 This is Shorter 42 ABC 2222 Hello new World!10-4 假設(shè)在數(shù)據(jù)庫(kù)文件中的每一個(gè)記錄是由占2個(gè)字節(jié)的整型數(shù)關(guān)鍵碼和一個(gè)變長(zhǎng)的數(shù)據(jù)字段組成。數(shù)據(jù)字段都是字符串。為了存放右面的那些記錄，應(yīng)如何組織線性索引？【解答】將所有字符串依加入的先后次序存放于一個(gè)連續(xù)的存儲(chǔ)空間store中，這個(gè)空間也叫做“堆”，它是存放所有字符串的順序文件。它有一個(gè)指針free，指示在堆st

26、ore中當(dāng)前可存放數(shù)據(jù)的開始地址。初始時(shí)free置為0，表示可從文件的0號(hào)位置開始存放。線性索引中每個(gè)索引項(xiàng)給出記錄關(guān)鍵碼，字符串在store中的起始地址和字符串的長(zhǎng)度：索引表ID 堆store 關(guān)鍵碼串長(zhǎng)度串起始地址 0Hello World! XYZ This string is rather long This 4235682312is Shorter ABC Hello new World!free39712010371541103826152222165910-5 設(shè)有一個(gè)職工文件： 記錄地址 職工號(hào) 姓 名 性別 職 業(yè) 年齡 籍貫 月工資(元) 10032 034 劉激揚(yáng) 男 教

27、 師 29 山東720.00 10068 064 蔡曉莉 女 教 師 32 遼寧1200.00 10104 073 朱 力 男 實(shí)驗(yàn)員 26 廣東480.00 10140 081 洪 偉 男 教 師 36 北京1400.00 10176 092 盧聲凱 男 教 師 28 湖北720.00 10212 123 林德康 男 行政秘書 33 江西480.00 10248 140 熊南燕 女 教 師 27 上海 780.00 10284 175 呂 穎 女 實(shí)驗(yàn)員 28 江蘇480.00 10320 209 袁秋慧 女 教 師 24 廣東720.00其中，關(guān)鍵碼為職工號(hào)。試根據(jù)此文件，對(duì)下列查詢組織主

28、索引和倒排索引，再寫出搜索結(jié)果關(guān)鍵碼。(1) 男性職工；(2) 月工資超過800元的職工；(3) 月工資超過平均工資的職工；(4) 職業(yè)為實(shí)驗(yàn)員和行政秘書的男性職工；(5) 男性教師或者年齡超過25歲且職業(yè)為實(shí)驗(yàn)員和教師的女性職工?！窘獯稹?主索引 月工資 倒排索引 職務(wù) 倒排索引 職工號(hào)記錄地址月工資長(zhǎng)度指針職務(wù)長(zhǎng)度指針003410032480.3073教師6034106410068123064207310104175081308110140720.3034092409210176092140512310212209209614010248780.1140實(shí)驗(yàn)員207371751028412

29、00.10641758209103201400.1081行政秘書1123 性別 倒排索引 年齡 倒排索引性別長(zhǎng)度指針年齡長(zhǎng)度指針男5034241209073261073081271140092282092123175女4064291034140321064175331123209361081搜索結(jié)果： (1) 男性職工 (搜索性別倒排索引)：034, 073, 081, 092, 123(2) 月工資超過800元的職工 (搜索月工資倒排索引)：064, 081(3) 月工資超過平均工資的職工(搜索月工資倒排索引) 月平均工資776元：064, 081, 140(4) 職業(yè)為實(shí)驗(yàn)員和行政秘書的男

30、性職工(搜索職務(wù)和性別倒排索引)：073, 123, 175 & 034, 073, 081, 092, 123 = 073, 123(5) 男性教師 (搜索性別與職務(wù)倒排索引)：034, 073, 081, 092, 123 & 034, 064, 081, 092, 140, 209 = 034, 081, 092年齡超過25歲且職業(yè)為實(shí)驗(yàn)員和教師的女性職工 (搜索性別、職務(wù)和年齡倒排索引)：064, 140, 175, 209 & 034, 064, 073, 081, 092, 140, 175, 209 & 034, 064, 073, 081,092, 123, 140, 175

31、= 064, 140, 17510-6 倒排索引中的記錄地址可以是記錄的實(shí)際存放地址，也可以是記錄的關(guān)鍵碼。試比較這兩種方式的優(yōu)缺點(diǎn)。 【解答】在倒排索引中的記錄地址用記錄的實(shí)際存放地址，搜索的速度快；但以后在文件中插入或刪除記錄對(duì)象時(shí)需要移動(dòng)文件中的記錄對(duì)象，從而改變記錄的實(shí)際存放地址，這將對(duì)所有的索引產(chǎn)生影響：修改所有倒排索引的指針，不但工作量大而且容易引入新的錯(cuò)誤或遺漏，使得系統(tǒng)不易維護(hù)。記錄地址采用記錄的關(guān)鍵碼，缺點(diǎn)是尋找實(shí)際記錄對(duì)象需要再經(jīng)過主索引，降低了搜索速度；但以后在文件中插入或刪除記錄對(duì)象時(shí)，如果移動(dòng)文件中的記錄對(duì)象，導(dǎo)致許多記錄對(duì)象的實(shí)際存放地址發(fā)生變化，只需改變主索引中的

32、相應(yīng)記錄地址，其他倒排索引中的指針一律不變，使得系統(tǒng)容易維護(hù)，且不易產(chǎn)生新的錯(cuò)誤和遺漏。10-7 m = 2的平衡m路搜索樹是AVL樹，m = 3的平衡m路搜索樹是2-3樹。它們的葉結(jié)點(diǎn)必須在同一層嗎？m階B樹是平衡m路搜索樹，反過來，平衡m路搜索樹一定是B樹嗎？為什么？【解答】m = 3的平衡m路搜索樹的葉結(jié)點(diǎn)不一定在同一層，而m階B_樹的葉結(jié)點(diǎn)必須在同一層，所以m階B_樹是平衡m路搜索樹，反過來，平衡m路搜索樹不一定是B_樹。10-8 下圖是一個(gè)3階B樹。試分別畫出在插入65、15、40、30之后B樹的變化。5580 9045958560 705025 35【解答】插入65后：55 80

33、90654525 35506070859555 80 插入15后：906525 4515706095855035插入40后：55 80 906525 455035 401570609585插入30后：55 803545259065301540706095855010-9 下圖是一個(gè)3階B樹。試分別畫出在刪除50、40之后B樹的變化。503060 805520957040【解答】刪除50后： 5580309560 704020刪除40后：55 8020 3060 709510-10 對(duì)于一棵有1999999個(gè)關(guān)鍵碼的199階B樹，試估計(jì)其最大層數(shù)(不包括失敗結(jié)點(diǎn))及最小層數(shù)(不包括失敗結(jié)點(diǎn))?！?/p>

34、解答】設(shè)B樹的階數(shù)m = 199，則m/2 = 100。若不包括失敗結(jié)點(diǎn)層，則其最大層數(shù)為logm/2 (N+1)/2) + 1 = log100 1000000 +1 = 4若使得每一層關(guān)鍵碼數(shù)達(dá)到最大，可使其層數(shù)達(dá)到最小。第0層最多有(m-1)個(gè)關(guān)鍵碼，第1層最多有(m-1)2個(gè)關(guān)鍵碼，第h-1層最多有(m-1)h個(gè)關(guān)鍵碼。層數(shù)為h的B樹最多有(m-1) + (m-1)2 + + (m-1)h-1 = (m-1) ( (m-1)h 1 ) / (m-2)個(gè)關(guān)鍵碼。反之，若有n個(gè)關(guān)鍵碼，n (m-1) ( (m-1)h 1 ) / (m-2)，則 h log (m-1) (n(m-2)/(m

35、-1)+1)，所以，有1999999個(gè)關(guān)鍵碼的199階B樹的最小層數(shù)為log (m-1) (n*(m-2)/(m-1)+1) = log198 (1999999*197 / 198 +1) = log 198 1989899 10-11 給定一組記錄，其關(guān)鍵碼為字符。記錄的插入順序?yàn)?C, S, D, T, A, M, P, I, B, W, N, G, U, R, K, E, H, O, L, J ，給出插入這些記錄后的4階B+樹。假定葉結(jié)點(diǎn)最多可存放3個(gè)記錄。【解答】 插入C, S, D 插入T 插入A 插入M D S S S C D S D MS T A CA C D S T S T C

36、 D 插入P 插入ID M S D S M PD IS T A CD M PA CS T D M S U 插入B, W, N, G 插入U(xiǎn) D M S U W S T M N PD G IA B CD G IM N PS T W A B C 插入RP S U D M M N D G IA B CP R S T U W 插入KP S U D I M I K D G M N P R S T U W A B CP 插入ES U D I M D E G I K S T P R U W M N A B C 插入HP D G I M S U G H I K M N S T P R U W D E A B

37、C 插入O, LP D G I M S U M N O A B CI K L S T P R G H D E U W 插入JI P D G K M S U I J K L P R S T M N O U W G H D E A B C10-12 設(shè)有一棵B+樹，其內(nèi)部結(jié)點(diǎn)最多可存放100個(gè)子女，葉結(jié)點(diǎn)最多可存儲(chǔ)15個(gè)記錄。對(duì)于1, 2, 3, 4, 5層的B+樹，最多能存儲(chǔ)多少記錄，最少能存儲(chǔ)多少記錄?！窘獯稹恳粚覤+樹：根據(jù)B+樹定義，一層B+樹的結(jié)點(diǎn)只有一個(gè)，它既是根結(jié)點(diǎn)又是葉結(jié)點(diǎn)，最多可存儲(chǔ)m1 = 15個(gè)記錄，最少可存儲(chǔ) m1/2 = 8個(gè)記錄。二層B+樹：第0層是根結(jié)點(diǎn)，它最多有m

38、= 100棵子樹，最少有2個(gè)結(jié)點(diǎn)；第1層是葉結(jié)點(diǎn)，它最多有m個(gè)結(jié)點(diǎn)，最多可存儲(chǔ)m*m1 = 100*15 = 1500個(gè)記錄，最少有2個(gè)結(jié)點(diǎn)，最少可存儲(chǔ)2* m1/2 = 16個(gè)記錄。三層B+樹：第2層是葉結(jié)點(diǎn)。它最多有m2個(gè)結(jié)點(diǎn)，最多可存儲(chǔ)m2 * m1 = 150000個(gè)記錄。最少有2* m/2 = 100個(gè)結(jié)點(diǎn)，最少可存儲(chǔ)2* m/2 * m1/2 = 800個(gè)記錄。四層B+樹：第3層是葉結(jié)點(diǎn)。它最多有m3個(gè)結(jié)點(diǎn)，可存儲(chǔ)m3 * m1 = 15000000個(gè)記錄。最少有2* m/2 2 = 2 * 502 = 5000個(gè)結(jié)點(diǎn)，存儲(chǔ)2* m/2 2 * m1/2 = 40000個(gè)記錄。五層

39、B+樹：第4層是葉結(jié)點(diǎn)。它最多有m4個(gè)結(jié)點(diǎn)，可存儲(chǔ)m4 * m1 = 1500000000個(gè)記錄。最少有2* m/2 3 = 2 * 503 = 250000個(gè)結(jié)點(diǎn)，存儲(chǔ)2* m/2 3 * m1/2 = 2000000個(gè)記錄。10-13設(shè)散列表為HT13, 散列函數(shù)為 H (key) = key %13。用閉散列法解決沖突, 對(duì)下列關(guān)鍵碼序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。(1) 采用線性探查法尋找下一個(gè)空位, 畫出相應(yīng)的散列表, 并計(jì)算等概率下搜索成功的平均搜索長(zhǎng)度和搜索不成功的平均搜索長(zhǎng)度。(2) 采用雙散列法尋找下一個(gè)空位, 再散列

40、函數(shù)為 RH (key) = (7*key) % 10 + 1, 尋找下一個(gè)空位的公式為 Hi = (Hi-1 + RH (key) % 13, H1 = H (key)。畫出相應(yīng)的散列表, 并計(jì)算等概率下搜索成功的平均搜索長(zhǎng)度。【解答】使用散列函數(shù) H(key) = key mod 13，有H(12) = 12, H(23) = 10,H(45) = 6,H(57) = 5,H(20) = 7,H(03) = 3,H(78) = 0,H(31) = 5,H(15) = 2,H(36) = 10.(1) 利用線性探查法造表： 0 1 2 3 4 5 6 7 8 9 10 11 12 78 15

41、 03 57 45 20 31 23 36 12 (1) (1) (1) (1) (1) (1) (4) (1) (2) (1)搜索成功的平均搜索長(zhǎng)度為ASLsucc = (1 + 1 + 1 + 1 + 1 + 1 + 4 + 1 + 2 + 1) = 搜索不成功的平均搜索長(zhǎng)度為ASLunsucc = (2 + 1 + 3 + 2 + 1 + 5 + 4 + 3 + 2 + 1 + 5 + 4 + 3) = (2) 利用雙散列法造表：Hi = (Hi-1 + RH (key) % 13, H1 = H (key) 0 1 2 3 4 5 6 7 8 9 10 11 12 78 15 03 5

42、7 45 20 31 36 23 12 (1) (1) (1) (1) (1) (1) (3) (5) (1) (1)搜索成功的平均搜索長(zhǎng)度為ASLsucc = (1 + 1 + 1 + 1 + 1 + 1 + 3 + 5 + 1 + 1) = 10-14 設(shè)有150個(gè)記錄要存儲(chǔ)到散列表中, 要求利用線性探查法解決沖突, 同時(shí)要求找到所需記錄的平均比較次數(shù)不超過2次。試問散列表需要設(shè)計(jì)多大？ 設(shè)a是散列表的裝載因子，則有【解答】已知要存儲(chǔ)的記錄數(shù)為n = 150，查找成功的平均查找長(zhǎng)度為ASLsucc 2，則有ASLsucc = 2，解得 a 。又有a = ，則 m 225。10-15 若設(shè)散

43、列表的大小為m，利用散列函數(shù)計(jì)算出的散列地址為h = hash(x)。(1) 試證明：如果二次探查的順序?yàn)?h + q2), (h + (q-1)2), , (h+1), h, (h-1), , (h-q2)，其中， q = (m-1)/2。因此在相繼被探查的兩個(gè)桶之間地址相減所得的差取模(%m)的結(jié)果為m-2, m-4, m-6, , 5, 3, 1, 1, 3, 5, , m-6, m-4, m-2(2) 編寫一個(gè)算法，使用課文中討論的散列函數(shù)h(x)和二次探查解決沖突的方法，按給定值x來搜索一個(gè)大小為m的散列表。如果x不在表中，則將它插入到表中?！窘獯稹?1) 將探查序列分兩部分討論：

44、(h + q2), (h + (q-1)2), , (h+1), h 和 (h-1), (h-22), , (h-q2)。對(duì)于前一部分，設(shè)其通項(xiàng)為h + ( q d )2, d = 0, 1, , q，則相鄰兩個(gè)桶之間地址相減所得的差取模： ( h + (q (d -1) )2 ( h + (q d )2 ) ) % m = ( (q (d -1 ) )2 (q d )2 ) % m= (2*q -2*d +1) % m = ( m 2*d ) % m. ( 代換 q = (m-1)/2 )代入 d = 1, 2, , q，則可得到探查序列如下：m-2, m-4, m-6, , 5, 3, 1

45、。 ( m 2*q = m 2* (m-1)/2 = 1 )對(duì)于后一部分，其通項(xiàng)為h ( q d )2, d = q, q+1, , 2q，則相鄰兩個(gè)桶之間地址相減所得的差取模：( h ( q d )2 ( h ( q (d+1) )2 ) ) % m = ( ( q (d+1)2 (q d )2 ) % m= ( 2*d 2*q +1) % m = ( 2*d m + 2) % m ( 代換 q = (m-1)/2 )代入 d = q, q+1, , 2q-1，則可得到2*dm+2 = 2*q m +2 = m 1 m +2 = 1,2*dm+2 = 2*q + 2 m +2 = m 1 +

46、 2 m +2 = 3, , 2*dm+2 = 2*(2*q-1) m +2 = 2*(m11) m + 2 = 2*m 4 m +2 = m 2。證畢(2) 編寫算法下面是使用二次探查法處理溢出時(shí)的散列表類的聲明。template class HashTable /散列表類的定義public: enum KindOfEntry Active, Empty, Deleted ;/表項(xiàng)分類 (活動(dòng) / 空 / 刪) HashTable ( ) : TableSize ( DefaultSize ) AllocateHt ( ); CurrentSize = 0; /構(gòu)造函數(shù) HashTable

47、( ) delete ht; /析構(gòu)函數(shù) const HashTable & operator = ( const HashTable & ht2 );/重載函數(shù)：表賦值 int Find ( const Type & x );/在散列表中搜索x int IsEmpty ( ) return !CurrentSize ? 1 : 0; /判散列表空否，空則返回1 private: struct HashEntry /散列表的表項(xiàng)定義 Type Element;/表項(xiàng)的數(shù)據(jù), 即表項(xiàng)的關(guān)鍵碼 KindOfEntry info;/三種狀態(tài): Active, Empty, Deleted HashE

48、ntry ( ) : info (Empty ) /表項(xiàng)構(gòu)造函數(shù) HashEntry ( const Type &E, KindOfEntry i = Empty ) : Element (E), info (i) ; enum DefualtSize = 31; HashEntry *ht; /散列表存儲(chǔ)數(shù)組 int TableSize;/數(shù)組長(zhǎng)度，要求是滿足4k+3的質(zhì)數(shù)，k是整數(shù) int CurrentSize;/已占據(jù)散列地址數(shù)目 void AllocateHt ( ) ht = new HashEntryTableSize ; /為散列表分配存儲(chǔ)空間; int FindPos ( const Type & x )