數(shù)據(jù)結(jié)構(gòu) 課后習(xí)題答案 清華大學(xué)出版社 殷人昆
《數(shù)據(jù)結(jié)構(gòu) 課后習(xí)題答案 清華大學(xué)出版社 殷人昆》由會員分享,可在線閱讀,更多相關(guān)《數(shù)據(jù)結(jié)構(gòu) 課后習(xí)題答案 清華大學(xué)出版社 殷人昆(152頁珍藏版)》請?jiān)谘b配圖網(wǎng)上搜索。
1、第1章 緒論 1-1什么是數(shù)據(jù)? 它與信息是什么關(guān)系? 【解答】 什么是信息?廣義地講,信息就是消息。宇宙三要素(物質(zhì)、能量、信息)之一。它是現(xiàn)實(shí)世界各種事物在人們頭腦中的反映。此外,人們通過科學(xué)儀器能夠認(rèn)識到的也是信息。信息的特征為:可識別、可存儲、可變換、可處理、可傳遞、可再生、可壓縮、可利用、可共享。 什么是數(shù)據(jù)?因?yàn)樾畔⒌谋憩F(xiàn)形式十分廣泛,許多信息在計(jì)算機(jī)中不方便存儲和處理,例如,一個大樓中4部電梯在軟件控制下調(diào)度和運(yùn)行的狀態(tài)、一個商店中商品的在庫明細(xì)表等,必須將它們轉(zhuǎn)換成數(shù)據(jù)才能很方便地在計(jì)算機(jī)中存儲、處理、變換。因此,數(shù)據(jù)(data)是信息的載體,是描述客觀事物的數(shù)、字
2、符、以及所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序識別和處理的符號的集合。在計(jì)算機(jī)中,信息必須以數(shù)據(jù)的形式出現(xiàn)。 1-2什么是數(shù)據(jù)結(jié)構(gòu)? 有關(guān)數(shù)據(jù)結(jié)構(gòu)的討論涉及哪三個方面? 【解答】 數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)以及相互之間的關(guān)系。記為:數(shù)據(jù)結(jié)構(gòu) = { D, R }。其中,D是某一數(shù)據(jù)對象,R是該對象中所有數(shù)據(jù)成員之間的關(guān)系的有限集合。 有關(guān)數(shù)據(jù)結(jié)構(gòu)的討論一般涉及以下三方面的內(nèi)容: ① 數(shù)據(jù)成員以及它們相互之間的邏輯關(guān)系,也稱為數(shù)據(jù)的邏輯結(jié)構(gòu),簡稱為數(shù)據(jù)結(jié)構(gòu); ② 數(shù)據(jù)成員極其關(guān)系在計(jì)算機(jī)存儲器內(nèi)的存儲表示,也稱為數(shù)據(jù)的物理結(jié)構(gòu),簡稱為存儲結(jié)構(gòu); ③ 施加于該數(shù)據(jù)結(jié)構(gòu)上的操作。 數(shù)據(jù)的邏
3、輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù),它與數(shù)據(jù)的存儲不是一碼事,是與計(jì)算機(jī)存儲無關(guān)的。因此,數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題中抽象出來的數(shù)據(jù)模型,是數(shù)據(jù)的應(yīng)用視圖。數(shù)據(jù)的存儲結(jié)構(gòu)是邏輯數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)存儲器中的實(shí)現(xiàn)(亦稱為映像),它是依賴于計(jì)算機(jī)的,是數(shù)據(jù)的物理視圖。數(shù)據(jù)的操作是定義于數(shù)據(jù)邏輯結(jié)構(gòu)上的一組運(yùn)算,每種數(shù)據(jù)結(jié)構(gòu)都有一個運(yùn)算的集合。例如搜索、插入、刪除、更新、排序等。 1-3數(shù)據(jù)的邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩大類。線性結(jié)構(gòu)包括數(shù)組、鏈表、 棧、隊(duì)列、優(yōu)先級隊(duì)列等; 非線性結(jié)構(gòu)包括樹、圖等、這兩類結(jié)構(gòu)各自的特點(diǎn)是什么? 【解答】 線性結(jié)構(gòu)的特點(diǎn)是:在結(jié)構(gòu)中所有數(shù)據(jù)成員都處于
4、一個序列中,有且僅有一個開始成員和一個終端成員,并且所有數(shù)據(jù)成員都最多有一個直接前驅(qū)和一個直接后繼。例如,一維數(shù)組、線性表等就是典型的線性結(jié)構(gòu) 非線性結(jié)構(gòu)的特點(diǎn)是:一個數(shù)據(jù)成員可能有零個、一個或多個直接前驅(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òu)造函數(shù):缺省的構(gòu)造函數(shù)沒有參數(shù);第二個構(gòu)造函數(shù)將雙精度浮點(diǎn)數(shù)賦給復(fù)數(shù)的實(shí)部,虛部置為0;第三個構(gòu)造函數(shù)將兩個雙精度浮點(diǎn)數(shù)分別賦給復(fù)數(shù)的實(shí)部和虛部。 (3) 定義獲取和修改
5、復(fù)數(shù)的實(shí)部和虛部,以及+、-、*、/等運(yùn)算的成員函數(shù)。
(4) 定義重載的流函數(shù)來輸出一個復(fù)數(shù)。
【解答】
抽象數(shù)據(jù)類型通常是指由用戶定義,用以表示應(yīng)用問題的數(shù)據(jù)模型。抽象數(shù)據(jù)類型由基本的數(shù)據(jù)類型構(gòu)成,并包括一組相關(guān)的服務(wù)。
//在頭文件complex.h中定義的復(fù)數(shù)類
#ifndef _complex_h_
#define _complex_h_
#include
6、le r ) { Re = r; Im = 0; } //只置實(shí)部的構(gòu)造函數(shù) complex ( double r, double i ) { Re = r; Im = i; } //分別置實(shí)部、虛部的構(gòu)造函數(shù) double getReal ( ) { 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
7、 = 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& operator * ( complex& ob ); complex& operator / ( complex& ob ); friend ostream& operator
8、 << ( 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
9、sult = 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 * re
10、sult = new complex ( Re * ob.Re – 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
11、) / d ); return * result; } friend ostream& operator << ( ostream& os, complex & ob ) { //友元函數(shù):重載<<,將復(fù)數(shù)ob輸出到輸出流對象os中。 return os << ob.Re << ( ob.Im >= 0.0 ) ? “+” : “-” << fabs ( ob.Im ) << “i”; } 1-5 用歸納法證明: (1) (2) (3) 【證明】略 1-6 什么是算法? 算法的5個特性是什么? 試根據(jù)這些特性解釋算法與程序的區(qū)別。
12、 【解答】 通常,定義算法為“為解決某一特定任務(wù)而規(guī)定的一個指令序列?!币粋€算法應(yīng)當(dāng)具有以下特性: ① 有輸入。一個算法必須有0個或多個輸入。它們是算法開始運(yùn)算前給予算法的量。這些輸入取自于特定的對象的集合。它們可以使用輸入語句由外部提供,也可以使用賦值語句在算法內(nèi)給定。 ② 有輸出。一個算法應(yīng)有一個或多個輸出,輸出的量是算法計(jì)算的結(jié)果。 ③ 確定性。算法的每一步都應(yīng)確切地、無歧義地定義。對于每一種情況,需要執(zhí)行的動作都應(yīng)嚴(yán)格地、清晰地規(guī)定。 ④ 有窮性。一個算法無論在什么情況下都應(yīng)在執(zhí)行有窮步后結(jié)束。 ⑤ 有效性。算法中每一條運(yùn)算都必須是足夠基本的。就是說,它們原則上
13、都能精確地執(zhí)行,甚至人們僅用筆和紙做有限次運(yùn)算就能完成。 算法和程序不同,程序可以不滿足上述的特性(4)。例如,一個操作系統(tǒng)在用戶未使用前一直處于“等待”的循環(huán)中,直到出現(xiàn)新的用戶事件為止。這樣的系統(tǒng)可以無休止地運(yùn)行,直到系統(tǒng)停工。 此外,算法是面向功能的,通常用面向過程的方式描述;程序可以用面向?qū)ο蠓绞酱罱ㄋ目蚣堋? 1-7 設(shè)n為正整數(shù), 分析下列各程序段中加下劃線的語句的程序步數(shù)。 (1) for (int i = 1; i <= n; i++) (2) x = 0; y = 0; for (int j = 1; j <= n; j++)
14、{ for (int i = 1; i <= n; i++) c[i][j] = 0.0; for (int j = 1; j <= i; j++) for (int k = 1; k <= n; k++) for (int k = 1; k <= j; k++) c[i][j] = c[i][j] + a[i][k] * b[k][j]; x = x + y; }
15、 (3) int i = 1, j = 1; (4) int i =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 < 100 + n ); 【解答】 (1) (2) (3) i = 1時,i =
16、2,j = j + i = 1 + 2 = 2 + 1, i = 2時,i = 3,j = j + i = ( 2 + 1 ) + 3 = 3 + 1 + 2, i = 3時,i = 4,j = j + i = ( 3 + 1 + 2 ) + 4 = 4 + 1 + 2 + 3, i = 4時,i = 5,j = j + i = ( 4 + 1 + 2 + 3 ) + 5 = 5 + 1 + 2 + 3 + 4, …… i = k時,i = k + 1,j = j + i = ( k + 1 ) + ( 1 + 2 + 3 + 4 + … + k ), 解出滿足上述不等式的k值,即
17、為語句i = i + 1的程序步數(shù)。 (4) 一般地, 求出滿足此不等式的k值,即為語句i = i + j的程序步數(shù)。 1-8 試編寫一個函數(shù)計(jì)算n!*2n的值,結(jié)果存放于數(shù)組A[arraySize]的第n個數(shù)組元素中,0 n arraySize。若設(shè)計(jì)算機(jī)中允許的整數(shù)的最大值為maxInt,則當(dāng)n > arraySize或者對于某一個k (0 k n),使得k!*2k > maxInt時,應(yīng)按出錯處理。可有如下三種不同的出錯處理方式: (1) 用cerr<<及exit (1)語句來終止執(zhí)行并報(bào)告錯誤; (2) 用返回整數(shù)函
18、數(shù)值0, 1來實(shí)現(xiàn)算法,以區(qū)別是正常返回還是錯誤返回; (3) 在函數(shù)的參數(shù)表設(shè)置一個引用型的整型變量來區(qū)別是正常返回還是某種錯誤返回。 試討論這三種方法各自的優(yōu)缺點(diǎn),并以你認(rèn)為是最好的方式實(shí)現(xiàn)它。 【解答】 #include "iostream.h" #define arraySize 100 #define MaxInt 0x7fffffff int calc ( int T[ ], int n ) { int i, value = 1; if ( n != 0 ) { int edge = MaxInt / n / 2; for ( i = 1; i
19、< n; i++ ) { value *= i*2; if ( value > edge ) return 0; } value *= n * 2; } T[n] = value; cout << "A[" << n << "]=" << T[n] << endl; return 1; } void main ( ) { int A[arraySize]; int i; for ( i = 0; i < arraySize; i++ ) if ( !calc ( A, i ) ) { cout
20、 << "failed at " << i << " ." << endl; break; } } 1-9 (1) 在下面所給函數(shù)的適當(dāng)?shù)胤讲迦胗?jì)算count的語句: void d (ArrayElement x[ ], int n ) { int i = 1; do { x[i] += 2; i +=2; } while (i <= n ); i = 1; while ( i <= (n/2) ) { x[i] += x[i+1]; i++; } }
21、(2) 將由(1)所得到的程序化簡。使得化簡后的程序與化簡前的程序具有相同的count值。 (3) 程序執(zhí)行結(jié)束時的count值是多少? (4) 使用執(zhí)行頻度的方法計(jì)算這個程序的程序步數(shù),畫出程序步數(shù)統(tǒng)計(jì)表。 【解答】 (1) 在適當(dāng)?shù)牡胤讲迦胗?jì)算count語句 void d ( ArrayElement x [ ], int n ) { int i = 1; count ++; do { x[i] += 2; count ++; i += 2; count ++; count ++; //針對while語句
22、 } while ( i <= n ); i = 1; count ++; while ( i <= ( n / 2 ) ) { count ++; //針對while語句 x[i] += x[i+1]; count ++; i ++; count ++; } count ++; //針對最后一次while語句 } (2) 將由(1)所得到的程序化簡?;喓蟮某绦蚺c原來的程序有相同的count值: void d ( ArrayElement x [ ], int n ) {
23、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ù)時,count = 3 * ( n / 2 ) + 3 * ( n / 2 ) + 3 = 3 * n + 3 當(dāng)n為奇數(shù)時,count = 3 * ( ( n + 1 ) / 2 ) + 3 *
24、( ( n – 1 ) / 2 ) + 3 = 3 * n + 3 (4) 使用執(zhí)行頻度的方法計(jì)算程序的執(zhí)行步數(shù),畫出程序步數(shù)統(tǒng)計(jì)表: 行 號 程 序 語 句 一次執(zhí)行步數(shù) 執(zhí)行頻度 程序步數(shù) 1 2 3 4 5 6 7 8 9 10 11 12 void d ( ArrayElement x [ ], int n ) { int i = 1; do { x[i] += 2; i += 2; } while ( i <= n ); i =
25、 1; while ( i <= ( n / 2 ) ) { x[i] += x[i+1]; i ++; } } 0 1 0 1 1 1 1 1 1 1 0 0 1 1 (n+1)/2 (n+1)/2 (n+1)/2 (n+1)/2 1 n/2+1 n/2 n/2 n/2 1 0 1 0 (n+1)/2 (n+1)
26、/2 (n+1)/2 1 n/2+1 n/2 n/2 0 0 ( n 0 ) 3n + 3 1-10 設(shè)有3個值大小不同的整數(shù)a、b和c,試求 (1) 其中值最大的整數(shù); (2) 其中值最小的整數(shù); (3) 其中位于中間值的整數(shù)。 【解答】 (1) 求3個整數(shù)中的最大整數(shù)的函數(shù) 【方案1】 int max ( int a, int b, int c ) { int m = a; if ( b > m ) m = b; if ( c > m ) m = c; return
27、 m; } 【方案2】(此程序可修改循環(huán)終止變量擴(kuò)大到n個整數(shù)) int max ( int a, int b, int c ) { int data[3] = { a, b, c }; int m = 0; //開始時假定data[0]最大 for ( int i = 1; i < 3; i++ ) //與其他整數(shù)逐個比較 if ( data[i] > data[m] ) m = i; //m記錄新的最大者 return data[m]; } (2) 求3個整數(shù)中的最小整數(shù)的函數(shù) 可將上面求最大整數(shù)的函數(shù)稍做修改,“>”
28、改為“<”,可得求最小整數(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個整數(shù)) int max ( int a, int b, int c ) { int data[3] = { a, b, c }; int m = 0; //開始時假定data[0]最小 for ( int i = 1; i < 3; i+
29、+ ) //與其他整數(shù)逐個比較 if ( data[i] < data[m] ) m = i; //m記錄新的最小者 return data[m]; } (3) 求3個整數(shù)中具有中間值的整數(shù) 可將上面求最大整數(shù)的函數(shù)稍做修改,“>”改為“<”,可得求最小整數(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
30、 = c; } else if ( c < m2 ) { m2 = c; } return m2; } 【方案2】(此程序可修改循環(huán)終止變量擴(kuò)大到n個整數(shù)尋求次小元素) int mid ( int a, int b, int c ) { int data[3] = { a, b, c }; int m1 = 0, m2 = -1; //m1指示最小整數(shù), m2指示次小整數(shù) for ( int i = 1; i < 3; i++ ) //與其他整數(shù)逐個比較 if ( data[i] < data[m1] ) { m2 = m1;
31、 m1 = i; } //原來最小變?yōu)榇涡? m1指示新的最小 else if ( m2 == -1 || data[i] < data[m2] ) m2 = i; //m2記錄新的次小者 return data[m2]; } 第10章 索引與散列 10-1 什么是靜態(tài)索引結(jié)構(gòu)?什么是動態(tài)索引結(jié)構(gòu)?它們各有哪些優(yōu)缺點(diǎn)? 【解答】 靜態(tài)索引結(jié)構(gòu)指這種索引結(jié)構(gòu)在初始創(chuàng)建,數(shù)據(jù)裝入時就已經(jīng)定型,而且在整個系統(tǒng)運(yùn)行期間,樹的結(jié)構(gòu)不發(fā)生變化,只是數(shù)據(jù)在更新。動態(tài)索引結(jié)構(gòu)是指在整個系統(tǒng)運(yùn)行期間,樹的結(jié)構(gòu)隨數(shù)據(jù)的增刪及時調(diào)整,以保持最佳的搜索效率。靜態(tài)索引結(jié)構(gòu)的優(yōu)點(diǎn)是結(jié)構(gòu)定型,
32、建立方法簡單,存取方便;缺點(diǎn)是不利于更新,插入或刪除時效率低。動態(tài)索引結(jié)構(gòu)的優(yōu)點(diǎn)是在插入或刪除時能夠自動調(diào)整索引樹結(jié)構(gòu),以保持最佳的搜索效率;缺點(diǎn)是實(shí)現(xiàn)算法復(fù)雜。 10-2 設(shè)有10000個記錄對象, 通過分塊劃分為若干子表并建立索引, 那么為了提高搜索效率, 每一個子表的大小應(yīng)設(shè)計(jì)為多大? 【解答】 每個子表的大小 s = n = 10000 = 100 個記錄對象。 10-3如果一個磁盤頁塊大小為1024 (=1K) 字節(jié),存儲的每個記錄對象需要占用16字節(jié),其中關(guān)鍵碼占4字節(jié),其它數(shù)據(jù)占12字節(jié)。所有記錄均已按關(guān)鍵碼有序地存儲在磁盤文件中,每個頁塊的第1個記錄用于存放線
33、性索引。另外在內(nèi)存中開辟了256K字節(jié)的空間可用于存放線性索引。試問: (1) 若將線性索引常駐內(nèi)存,文件中最多可以存放多少個記錄?(每個索引項(xiàng)8字節(jié),其中關(guān)鍵碼4字節(jié),地址4字節(jié)) (2) 如果使用二級索引,第二級索引占用1024字節(jié)(有128個索引項(xiàng)),這時文件中最多可以存放多少個記錄? 【解答】 (1) 因?yàn)橐粋€磁盤頁塊大小為1024字節(jié),每個記錄對象需要占用16字節(jié),則每個頁塊可存放1024 / 16 = 64個記錄,除第一個記錄存儲線性索引外,每個頁塊可存儲63個記錄對象。又因?yàn)樵诖疟P文件中所有記錄對象按關(guān)鍵碼有序存儲,所以線性索引可以是稀疏索引,每一個索引項(xiàng)存放一個頁塊的
34、最大關(guān)鍵碼及該頁塊的地址。若線性索引常駐內(nèi)存,那么它最多可存放256 * (1024 / 8 ) = 256 * 128 = 32768個索引項(xiàng),文件中可存放 32768 * 63 = 2064384個記錄對象。 (2) 由于第二級索引占用1024個字節(jié),內(nèi)存中還剩255K 字節(jié)用于第一級索引。第一級索引有255 * 128 = 32640個索引項(xiàng),作為稀疏索引,每個索引項(xiàng)索引一個頁塊,則索引文件中可存放32640 * 63 = 2056320。 397 Hello World! 82 XYZ 1038 This string is rath
35、er long 1037 This is Shorter 42 ABC 2222 Hello new World! 10-4 假設(shè)在數(shù)據(jù)庫文件中的每一個記錄是由占2個字節(jié)的整型數(shù)關(guān)鍵碼和一個變長的數(shù)據(jù)字段組成。數(shù)據(jù)字段都是字符串。為了存放右面的那些記錄,應(yīng)如何組織線性索引? 【解答】 將所有字符串依加入的先后次序存放于一個連續(xù)的存儲空間store中,這個空間也叫做“堆”,它是存放所有字符串的順序文件。它有一個指針free,指示在堆store中當(dāng)前可存放數(shù)據(jù)的開始地址。初始時free置為0,表示可從文件的0號位置開始存放。線性索引中每個索引項(xiàng)給出記錄關(guān)
36、鍵碼,字符串在store中的起始地址和字符串的長度: 索引表ID 堆store 關(guān)鍵碼 串長度 串起始地址 0 Hello World! XYZ This string is rather long This 42 3 56 82 3 12 is Shorter ABC Hello new World! free 397 12 0 1037 15 41 1038 26 15 2222 16 59
37、 10-5 設(shè)有一個職工文件: 記錄地址 職工號 姓 名 性別 職 業(yè) 年齡 籍貫 月工資(元) 10032 034 劉激揚(yáng) 男 教 師 29 山東 720.00 10068 064 蔡曉莉 女 教 師 32 遼寧 1200.00 10104 073 朱 力 男 實(shí)驗(yàn)員 26 廣東 480.00 10140 081 洪
38、偉 男 教 師 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 10
39、320 209 袁秋慧 女 教 師 24 廣東 720.00 其中,關(guān)鍵碼為職工號。試根據(jù)此文件,對下列查詢組織主索引和倒排索引,再寫出搜索結(jié)果關(guān)鍵碼。(1) 男性職工;(2) 月工資超過800元的職工;(3) 月工資超過平均工資的職工;(4) 職業(yè)為實(shí)驗(yàn)員和行政秘書的男性職工;(5) 男性教師或者年齡超過25歲且職業(yè)為實(shí)驗(yàn)員和教師的女性職工。 【解答】 主索引 月工資 倒排索引 職務(wù) 倒排索引 職工號 記錄地址 月工資 長度 指針 職務(wù) 長度 指針
40、 0 034 10032 480. 3 073 教師 6 034 1 064 10068 123 064 2 073 10104 175 081 3 081 10140 720. 3 034 092 4 092 10176 092 140 5 123 10212 209 209 6 140 10248 780. 1 140 實(shí)驗(yàn)員 2 073 7
41、 175 10284 1200. 1 064 175 8 209 10320 1400. 1 081 行政秘書 1 123 性別 倒排索引 年齡 倒排索引 性別 長度 指針 年齡 長度 指針 男 5 034 24 1 209 073 26 1 073 081 27 1 140 092 28 2 092 123 175 女 4 064 29 1 034 140
42、 32 1 064 175 33 1 123 209 36 1 081 搜索結(jié)果: (1) 男性職工 (搜索性別倒排索引):{034, 073, 081, 092, 123} (2) 月工資超過800元的職工 (搜索月工資倒排索引):{064, 081} (3) 月工資超過平均工資的職工(搜索月工資倒排索引) {月平均工資776元}: {064, 081, 140} (4) 職業(yè)為實(shí)驗(yàn)員和行政秘書的男性職工(搜索職務(wù)和性別倒排索引): {073, 123, 175} && {034, 073, 081, 092, 123} =
43、{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} = {064, 140, 175} 10-6 倒排索引中的記
44、錄地址可以是記錄的實(shí)際存放地址,也可以是記錄的關(guān)鍵碼。試比較這兩種方式的優(yōu)缺點(diǎn)。 【解答】 在倒排索引中的記錄地址用記錄的實(shí)際存放地址,搜索的速度快;但以后在文件中插入或刪除記錄對象時需要移動文件中的記錄對象,從而改變記錄的實(shí)際存放地址,這將對所有的索引產(chǎn)生影響:修改所有倒排索引的指針,不但工作量大而且容易引入新的錯誤或遺漏,使得系統(tǒng)不易維護(hù)。 記錄地址采用記錄的關(guān)鍵碼,缺點(diǎn)是尋找實(shí)際記錄對象需要再經(jīng)過主索引,降低了搜索速度;但以后在文件中插入或刪除記錄對象時,如果移動文件中的記錄對象,導(dǎo)致許多記錄對象的實(shí)際存放地址發(fā)生變化,只需改變主索引中的相應(yīng)記錄地址,其他倒排索引中的指針一律不
45、變,使得系統(tǒng)容易維護(hù),且不易產(chǎn)生新的錯誤和遺漏。 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 下圖是一個3階B樹。試分別畫出在插入65、15、40、30之后B樹的變化。 55 80 90 45 95 85 60 70 50 25
46、 35 【解答】 插入65后: 55 80 90 65 45 25 35 50 60 70 85 95 55 80 插入15后: 90 65 25 45 15 70 60 95 85 50 35 插入40后: 55 80 90 65 25 45 50 35 40 15 70 60 95 85 插入30后: 55 80 35 45 25 90 65 30 1
47、5 40 70 60 95 85 50 10-9 下圖是一個3階B樹。試分別畫出在刪除50、40之后B樹的變化。 50 30 60 80 55 20 95 70 40 【解答】 刪除50后: 55 80 30 95 60 70 40 20 刪除40后: 55 80 20 30 60 70 95 10-10 對于一棵有1999999個關(guān)鍵碼的199階B樹,試估計(jì)其最大層數(shù)(不包括失敗結(jié)點(diǎn))及最小層數(shù)(不包括失敗結(jié)點(diǎn))。 【解答】
48、 設(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)個關(guān)鍵碼,第1層最多有(m-1)2個關(guān)鍵碼,,第h-1層最多有(m-1)h個關(guān)鍵碼。層數(shù)為h的B樹最多有(m-1) + (m-1)2 + … + (m-1)h-1 = (m-1) ( (m-1)h – 1 ) / (m-2)個關(guān)鍵碼。反之,若有n個關(guān)鍵碼,n ≤ (m-1) ( (m-1)h – 1 ) / (m-2),則 h ≥ l
49、og (m-1) (n(m-2)/(m-1)+1),所以,有1999999個關(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個記錄。 【解答】 插入C, S, D 插入T
50、插入A 插入M D S S S C D S D M S T A C A C D S T S T C D 插入P 插入I D M S D S M P D I S T A C D M P A C S T D M S U 插入B, W, N, G 插入U(xiǎn) D M S U W S
51、 T M N P D G I A B C D G I M N P S T W A B C 插入R P S U D M M N D G I A B C P R S T U W 插入K P S U D I M I K D G M N P R S T U W A B C P
52、 插入E S U D I M D E G I K S T P R U W M N A B C 插入H P D G I M S U G H I K M N S T P R U W D E A B C 插入O, L P D G I M S U M N O A B C I K L S T P R G
53、 H D E U W 插入J I 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 C 10-12 設(shè)有一棵B+樹,其內(nèi)部結(jié)點(diǎn)最多可存放100個子女,葉結(jié)點(diǎn)最多可存儲15個記錄。對于1, 2, 3, 4, 5層的B+樹,最多能存儲多少記錄,最少能存儲多少記錄。 【解答】 一層B+樹:根據(jù)B+樹定義,一層B+樹的結(jié)點(diǎn)只有一個,它既是根結(jié)點(diǎn)又是葉結(jié)點(diǎn),最多可存儲m1 = 15個記錄,最少可存儲 m1/2 =
54、 8個記錄。 二層B+樹:第0層是根結(jié)點(diǎn),它最多有m = 100棵子樹,最少有2個結(jié)點(diǎn);第1層是葉結(jié)點(diǎn),它最多有m個結(jié)點(diǎn),最多可存儲m*m1 = 100*15 = 1500個記錄,最少有2個結(jié)點(diǎn),最少可存儲2* m1/2 = 16個記錄。 三層B+樹:第2層是葉結(jié)點(diǎn)。它最多有m2個結(jié)點(diǎn),最多可存儲m2 * m1 = 150000個記錄。最少有2* m/2 = 100個結(jié)點(diǎn),最少可存儲2* m/2 * m1/2 = 800個記錄。 四層B+樹:第3層是葉結(jié)點(diǎn)。它最多有m3個結(jié)點(diǎn),可存儲m3 * m1 = 15000000個記錄。最少有2* m/2 2 = 2 * 502 = 5000個結(jié)點(diǎn)
55、,存儲2* m/2 2 * m1/2 = 40000個記錄。 五層B+樹:第4層是葉結(jié)點(diǎn)。它最多有m4個結(jié)點(diǎn),可存儲m4 * m1 = 1500000000個記錄。最少有2* m/2 3 = 2 * 503 = 250000個結(jié)點(diǎn),存儲2* m/2 3 * m1/2 = 2000000個記錄。 10-13設(shè)散列表為HT[13], 散列函數(shù)為 H (key) = key %13。用閉散列法解決沖突, 對下列關(guān)鍵碼序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。 (1) 采用線性探查法尋找下一個空位, 畫出相應(yīng)的散列表, 并計(jì)算等概率下搜索成功
56、的平均搜索長度和搜索不成功的平均搜索長度。 (2) 采用雙散列法尋找下一個空位, 再散列函數(shù)為 RH (key) = (7*key) % 10 + 1, 尋找下一個空位的公式為 Hi = (Hi-1 + RH (key)) % 13, H1 = H (key)。畫出相應(yīng)的散列表, 并計(jì)算等概率下搜索成功的平均搜索長度。 【解答】 使用散列函數(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) =
57、 5, H(15) = 2, H(36) = 10. (1) 利用線性探查法造表: 0 1 2 3 4 5 6 7 8 9 10 11 12 78 15 03 57 45 20 31 23 36 12 (1) (1) (1) (1) (1) (1) (4) (1) (2) (1) 搜索成功的平均搜索長度為 ASLsucc = (1 + 1 + 1 + 1 + 1 + 1 + 4 + 1 + 2 + 1) =
58、 搜索不成功的平均搜索長度為 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 57 45 20 31 36 23 12 (1) (1) (1) (1) (1)
59、 (1) (3) (5) (1) (1) 搜索成功的平均搜索長度為 ASLsucc = (1 + 1 + 1 + 1 + 1 + 1 + 3 + 5 + 1 + 1) = 10-14 設(shè)有150個記錄要存儲到散列表中, 要求利用線性探查法解決沖突, 同時要求找到所需記錄的平均比較次數(shù)不超過2次。試問散列表需要設(shè)計(jì)多大? 設(shè)a是散列表的裝載因子,則有 【解答】 已知要存儲的記錄數(shù)為n = 150,查找成功的平均查找長度為ASLsucc 2,則有ASLsucc = 2,解得 a 。又有a = ,則 m 225。 10-15 若設(shè)散
60、列表的大小為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。因此在相繼被探查的兩個桶之間地址相減所得的差取模(%m)的結(jié)果為 m-2, m-4, m-6, …, 5, 3, 1, 1, 3, 5, …, m-6, m-4, m-2 (2) 編寫一個算法,使用課文中討論的散列函數(shù)h(x)和二次探查解決沖突的方法,按給定值x來搜索一個大小為m的散列表。如果x不在表中,則將它插入到表中。 【解答】
61、 (1) 將探查序列分兩部分討論: (h + q2), (h + (q-1)2), …, (h+1), h 和 (h-1), (h-22), …, (h-q2)。 對于前一部分,設(shè)其通項(xiàng)為h + ( q – d )2, d = 0, 1, …, q,則相鄰兩個桶之間地址相減所得的差取模: ( 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
62、-1)/2 ) 代入 d = 1, 2, …, q,則可得到探查序列如下: m-2, m-4, m-6, …, 5, 3, 1。 ( m – 2*q = m – 2* (m-1)/2 = 1 ) 對于后一部分,其通項(xiàng)為h – ( q – d )2, d = q, q+1, …, 2q,則相鄰兩個桶之間地址相減所得的差取模: ( 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
63、 ( 代換 q = (m-1)/2 )
代入 d = q, q+1, …, 2q-1,則可得到
2*d–m+2 = 2*q – m +2 = m – 1 – m +2 = 1,
2*d–m+2 = 2*q + 2 – m +2 = m – 1 + 2 – m +2 = 3, ……,
2*d–m+2 = 2*(2*q-1) – m +2 = 2*(m–1–1) – m + 2 = 2*m – 4 – m +2 = m – 2?!甲C畢〗
(2) 編寫算法
下面是使用二次探查法處理溢出時的散列表類的聲明。
template
64、hTable { //散列表類的定義 public: enum KindOfEntry { Active, Empty, Deleted }; //表項(xiàng)分類 (活動 / 空 / 刪) HashTable ( ) : TableSize ( DefaultSize ) { AllocateHt ( ); CurrentSize = 0; } //構(gòu)造函數(shù) ~HashTable ( ) { delete [ ] ht; } //析構(gòu)函數(shù) const HashTable & operator = ( const HashTable &
65、 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, De
66、leted HashEntry ( ) : info (Empty ) { } //表項(xiàng)構(gòu)造函數(shù) HashEntry ( const Type &E, KindOfEntry i = Empty ) : Element (E), info (i) { } }; enum { DefualtSize = 31; } HashEntry *ht; //散列表存儲數(shù)組 int TableSize; //數(shù)組長度,要求是滿足4k+3的質(zhì)數(shù),k是整數(shù) int CurrentSize; //已占據(jù)散列地址數(shù)目 void AllocateHt ( ) { ht = new HashEntry[TableSize ]; } //為散列表分配存儲空間; int FindPos ( const Type & x )
- 溫馨提示:
1: 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 110中國人民警察節(jié)(筑牢忠誠警魂感受別樣警彩)
- 2025正字當(dāng)頭廉字入心爭當(dāng)公安隊(duì)伍鐵軍
- XX國企干部警示教育片觀后感筑牢信仰之基堅(jiān)守廉潔底線
- 2025做擔(dān)當(dāng)時代大任的中國青年P(guān)PT青年思想教育微黨課
- 2025新年工作部署會圍繞六個干字提要求
- XX地區(qū)中小學(xué)期末考試經(jīng)驗(yàn)總結(jié)(認(rèn)真復(fù)習(xí)輕松應(yīng)考)
- 支部書記上黨課筑牢清廉信念為高質(zhì)量發(fā)展?fàn)I造風(fēng)清氣正的環(huán)境
- 冬季消防安全知識培訓(xùn)冬季用電防火安全
- 2025加強(qiáng)政治引領(lǐng)(政治引領(lǐng)是現(xiàn)代政黨的重要功能)
- 主播直播培訓(xùn)直播技巧與方法
- 2025六廉六進(jìn)持續(xù)涵養(yǎng)良好政治生態(tài)
- 員工職業(yè)生涯規(guī)劃方案制定個人職業(yè)生涯規(guī)劃
- 2024年XX地區(qū)黨建引領(lǐng)鄉(xiāng)村振興工作總結(jié)
- XX中小學(xué)期末考試經(jīng)驗(yàn)總結(jié)(認(rèn)真復(fù)習(xí)輕松應(yīng)考)
- 幼兒園期末家長會長長的路慢慢地走