數(shù)據(jù)結(jié)構(gòu)問答題

1、數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題：緒論問答題1、 當(dāng)你為解決某一問題而選擇數(shù)據(jù)結(jié)構(gòu)時，應(yīng)從哪些方面考慮？答：通常從兩方面考慮：第一是算法所需的存儲空間量；第二是算法所需的時間。對算法所需的時間又涉及 以下三點：（1）程序運行時所需輸入的數(shù)據(jù)總量。（2）計算機(jī)執(zhí)行每條指令所需的時間。（3）程序中指令重復(fù)執(zhí)行的次數(shù)。2、 簡述邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)的關(guān)系答：數(shù)據(jù)的邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的邏輯關(guān)系（即數(shù)據(jù)元素之間的關(guān)聯(lián)方式或鄰接關(guān)系”，數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)在計算機(jī)中的表示，包括數(shù)據(jù)元素的表示及其關(guān)系的表示。3、 數(shù)據(jù)運算是數(shù)據(jù)結(jié)構(gòu)的一個重要方面，試舉例說明兩個數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和存儲方式完全相同，只是對于運算的定義

2、不同，因而兩個結(jié)構(gòu)具有顯著不同的特性，則這兩個數(shù)據(jù)結(jié)構(gòu)是不同的答：棧和隊列的邏輯結(jié)構(gòu)相同，其存儲表示也可相同（順序存儲和鏈?zhǔn)酱鎯Γ捎谄溥\算集合不同而成為不同的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題：線性表問答題1、線性表有兩種存儲結(jié)構(gòu)：一是順序表，二是鏈表。試問：（1）兩種存儲表示各有哪些主要優(yōu)缺點 ？（2）如果有n個線性表同時并存，并且在處理過程中各表的長度會動態(tài)發(fā)生變化，線性表的總數(shù)也會自動地改變。在此情況下，應(yīng)選用哪種存儲結(jié)構(gòu)？為什么？（3）若線性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除，但要求以最快的速度存取線性表中的元素，那 么，應(yīng)采用哪種存儲結(jié)構(gòu) ？為什么？答：順序存儲是按索引（隱含的）直接

3、存取數(shù)據(jù)元素，方便靈活，效率高，但插入、刪除操作時將引起元 素移動，因而降低效率；鏈接存儲內(nèi)存采用動態(tài)分配，利用率高，但需增設(shè)指示結(jié)點之間有序關(guān)系的指針域， 存取數(shù)據(jù)元素不如順序存儲方便，但結(jié)點的插入、刪除操作十分簡單。（2）應(yīng)選用鏈接表存儲結(jié)構(gòu)。其理由是，鏈?zhǔn)酱鎯Y(jié)構(gòu)用一組任意的存儲單元依次存儲線性表里各元素， 這里存儲單元可以是連續(xù)的，也可以是不連續(xù)的。這種存儲結(jié)構(gòu)，在對元素作插入或刪除運算時，不需要移 動元素，僅修改指針即可。所以很容易實現(xiàn)表的容量擴(kuò)充。（3）應(yīng)選用順序存儲結(jié)構(gòu)。其理由是，每個數(shù)據(jù)元素的存儲位置和線性表的起始位置相差一個和數(shù)據(jù)元 素在線性表中的序號成正比的常數(shù)。由此，只要

4、確定了起始位置，線性表中任一數(shù)據(jù)元素都可隨機(jī)存取，所 以線性表的順序存儲結(jié)構(gòu)是一種隨機(jī)存取的存儲結(jié)構(gòu)。而鏈表則是一種順序存取的存儲結(jié)構(gòu)。2、 用線性表的順序結(jié)構(gòu)來描述一個城市的設(shè)計和規(guī)劃合適嗎？為什么？不合適。因為一個城市的設(shè)計和規(guī)劃涉及非常多的項目，很復(fù)雜，經(jīng)常需要修改、擴(kuò)充和刪除各種信息，才能適應(yīng)不斷發(fā)展的需要。有鑒于此，順序線性表不能很好適應(yīng)其需要，故是不合適的。3、 在單鏈表和雙向表中，能否從當(dāng)前結(jié)點出發(fā)訪問到任一結(jié)點？在單鏈表中只能由當(dāng)前結(jié)點訪問其后的任一結(jié)點，因為沒有指向其前驅(qū)結(jié)點的指針。而在雙向鏈表中，既有指向后繼結(jié)點的指針又有指向前驅(qū)結(jié)點的指針，故可由當(dāng)前結(jié)點出發(fā)訪問鏈表中任一

5、結(jié)點。4、 對鏈表設(shè)置頭結(jié)點的作用是什么 ?（至少說出兩條好處）答：(1)對帶頭結(jié)點的鏈表，在表的任何結(jié)點之前插入結(jié)點或刪除表中任何結(jié)點，所要做的都是修改前一結(jié) 點的指針域，因為任何元素結(jié)點都有前驅(qū)結(jié)點。若鏈表沒有頭結(jié)點，則首元素結(jié)點沒有前驅(qū)結(jié)點，在其前插 入結(jié)點或刪除該結(jié)點時操作會復(fù)雜些。(2)對帶頭結(jié)點的鏈表，表頭指針是指向頭結(jié)點的非空指針，因此空表與非空表的處理是一樣的。5、 在單鏈表、雙鏈表和單循環(huán)表中，若僅知道指針p指向某結(jié)點，不知道頭指針，能否將結(jié)點*p從相應(yīng)的鏈表中刪去？若可以，其時間復(fù)雜度各為多少？答：1.單鏈表。當(dāng)我們知道指針 p指向某結(jié)點時，能夠根據(jù)該指針找到其直接后繼，但

6、是由于不知道其頭指 針，所以無法訪問到 p指針指向的結(jié)點的直接前趨。因此無法刪去該結(jié)點。2. 雙鏈表。由于這樣的鏈表提供雙向鏈接，因此根據(jù)已知結(jié)點可以查找到其直接前趨和直接后繼，從而可以刪除該結(jié)點。其時間復(fù)雜度為0(1)。3. 單循環(huán)鏈表。根據(jù)已知結(jié)點位置，我們可以直接得到其后相鄰的結(jié)點位置(直接后繼)，又因為是循環(huán)鏈表，所以我們可以通過查找，得到p結(jié)點的直接前趨。因此可以刪去p所指結(jié)點。其時間復(fù)雜度應(yīng)為0(n)。6、簡述順序表和鏈表存儲方式的特點。答：順序表可以直接存取數(shù)據(jù)元素，方便靈活、效率高，但插入、刪除操作時將會引起元素的大量移動，因 而降低效率；而鏈表內(nèi)存采用動態(tài)分配，利用率高，但需

7、增設(shè)指示結(jié)點之間關(guān)系的指針域，存取數(shù)據(jù)元素不 如順序表方便，但結(jié)點的插入、刪除操作較簡單。數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題：棧和隊列問答題1、試述棧的基本性質(zhì)？答：由棧的定義可知，這種結(jié)構(gòu)的基本性質(zhì)綜述如下：(1) 集合性。棧是由若干個元素集合而成，當(dāng)沒有元素的空集合稱為空棧；(2) 線性結(jié)構(gòu)。除棧底元素和棧頂元素外，棧中任一元素均有唯一的前驅(qū)元素和后繼元素；(3) 受限制的運算。只允許在棧頂實施壓入或彈出操作，且棧頂位置由棧指針?biāo)甘荆?4) 數(shù)學(xué)性質(zhì)。當(dāng)多個編號元素依某種順序壓入，且可任意時刻彈出時，所獲得的編號元素排列的數(shù)目，恰好滿足卡塔南數(shù)列的計算，即：C n =C n 2n /(n + 1)其中，n為

8、編號元素的個數(shù)，Cn是可能的排列數(shù)目。4、 為什么說棧是一種后進(jìn)先出表？棧是允許在同一端進(jìn)行插入和刪除操作的特殊線性表。允許進(jìn)行插入和刪除操作的一端稱為棧頂(top)，另一端為棧底(bottom);棧底固定，而棧頂浮動；棧中元素個數(shù)為零時稱為空棧。插入一般稱為進(jìn)棧(PUSH ),刪除則稱為退棧(POP )。棧也稱為后進(jìn)先出表(LIFO-Last IN First Out 表)。5、 對于一個棧，給出輸入項A,B,C。如果輸入項序列由 A,B,C所組成，試給出全部可能的輸出序列。ABC,BAC,CBA6、 有字符串次序為 3*y-a/y f 2式利用棧給出將次序改變?yōu)?y-*ay2 f/勺操作步

9、驟。(可用X代表掃描該字符串函數(shù)中順序取一字符進(jìn)棧的操作，用S代表從棧中取出一個字符加到新字符串尾的出棧的操作)。例如:ABC變?yōu)锽CA,則操作步驟為XXSXX。X:進(jìn)棧 S:出棧 XSXXXSSSXXSXXSXXSSSS7、跟蹤以下代碼，顯示每次調(diào)用后隊列中的內(nèi)容。In itQueue(qu);En Queue(qu,'A');En Queue(qu,'B);En Queue(qu,'C);En Queue(qu,x;En Queue(qu,x;En Queue(qu,'D);En Queue(qu,'E);En Queue(qu,'F

10、);En Queue(qu,x)En Queue(qu,'G);En Queue(qu,X)En Queue(qu,X)En Queue(qu,X)答：InitQueue(qu);隊列為空En Queue(qu,'A');隊列為AEn Queue(qu,'B);隊列為ABEn Queue(qu,'C);隊列為ABCEn Queue(qu,x;隊列為ABCxEn Queue(qu,x;隊列為ABCxxEn Queue(qu,'D);隊列為ABCxxDEn Queue(qu,'E);隊列為ABCxxDEEn Queue(qu,'F);

11、隊列為ABCxxDEFEn Queue(qu,x)隊列為ABCxxDEFxEn Queue(qu,'G);隊列為 ABCxxDEFxGEn Queue(qu,X)隊列為 ABCxxDEFxGXEn Queue(qu,X)隊列為 ABCxxDEFxGXXEn Queue(qu,X)隊列為 ABCxxDEFxGXXX8、假設(shè) QO.1O是-個線性隊列，初始狀態(tài)為情況,若不能入隊，請指出其兀素，并說明理由。front=rear=0,畫出做完下列操作后隊列的頭尾指針的狀態(tài)變化d,e,b,g,h 入隊d,e出隊i,j,k,l,m 入隊n,o,p入隊解答：d,e,b,g,h入隊deb ghFrd,

12、e出隊bghFri,j,k,l,m 入隊b g h ij k lmFrn,o,p入隊b g h ij k lm n o pF9、假設(shè)CQO.1O是一個環(huán)形隊列,初始狀態(tài)為front=rear=0,畫出做完下列操作后隊列的頭尾指針的狀態(tài)變化 情況,若不能入隊，請指出其元素，并說明理由。d,e,b,g,h 入隊d,e出隊i, j,k,l,m 入隊b出隊n,o,p入隊 解答：圖略。p不能入隊，共有11個地址，p為第12個元素，故不能入隊10、 有5個元素，其進(jìn)棧次序為A、B、C、D、E,在各種可能的出棧次序中，以元素C、D最先出棧(即C第 個且D第一個出棧)的次序有哪幾個？答：三個：CDEBA，CD

13、BEA，CDBAE11、 設(shè)輸入元素為1、2、3、P和A,入棧次序為123PA,元素經(jīng)過棧后到達(dá)輸出序列，當(dāng)所有元素均到達(dá)輸出 序列后，有哪些序列可以作為高級語言的變量名？答：一般說，高級語言的變量名是以字母開頭的字母數(shù)字序列。故本題答案是：AP321,PA321,P3A21,P32A1,P321A。12、 簡要敘述棧和隊列的特點.答：棧和隊列都是插入和刪除操作的位置受限制的線性表。棧是限定僅在表尾進(jìn)行插入和刪除的線性表，是 后進(jìn)先出的線性表，而隊列是限定在表的一端進(jìn)行插入，在另一端進(jìn)行刪除的線性表，是先進(jìn)先出的線性表數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題：樹和二叉樹問答題1、對于二叉排序樹，當(dāng)所有結(jié)點的權(quán)都相等的情

14、況下，最佳二叉排序樹有何特點。其特點是只有最下面的二層結(jié)點可以小于2,其它結(jié)點的度數(shù)必須為23、已知一組元素為(46、25、78、62、18、34、12、40、73)，試畫出按元素排列順序輸入而生成的一棵二 叉排序樹。解答：得到的二叉排序樹如下圖所示。4625781834621240734、已知一棵樹的邊的集合表示為：(L,N),(G,K),(G,L),(G,M),(B,E),(B,F),(D,G),(D,H),(D,I),(D,J),(A,B),(A,C),(A,D)畫出這棵樹，并回答下列問題：(1) 樹根是哪個結(jié)點？哪些是葉子結(jié)點？哪些是非終端結(jié)點？(2) 樹的度是多少？各個結(jié)點的度是多少

15、？(3) 樹的深度是多少？各個結(jié)點的層數(shù)是多少？以結(jié)點G為根的子樹的深度是多少？(4) 對于結(jié)點G,它的雙親是哪個結(jié)點？它的祖先是哪些結(jié)點？它的孩子是哪些結(jié)點？它的子孫是哪些結(jié)點？它的兄弟和堂兄弟分別是哪些結(jié)點？解答：(1)樹的根是A，而E、F、C、H、I、J、K、M、N是葉子結(jié)點，其它為非終端結(jié)點。(2) 樹的度為 4。deg(A) = 3,deg(B) = 2,deg(D) = 4,deg(G) = 3,deg(L) = 1，其它各葉子結(jié)點的度均為0。(3) 樹的深度為 5(設(shè)根結(jié)點的深度為 1 )°level(A) = 1,level(B) = 2,level(C) = 2,l

16、evel(G)= 3,level(K) =4,，level(N) = 5。(4) D是G的雙親；A、D是G的祖先；K、L、M是G的孩子；K、L、M和N是G的子孫；H、I、J是G的兄弟；E、F是G的堂兄弟。5、 設(shè)高度為h的二叉樹上只有度為 0和度為2的結(jié)點，問該二叉樹的結(jié)點數(shù)可能達(dá)到的最大值和最小值。 解答：最大值(高度為h的滿二叉樹)20 + 21 + 22 + 2h-1 = 2h - 1最小值：第一層只有一個結(jié)點，其余的h-1層各有2個結(jié)點，所以最小值為2h-1個。6、設(shè)二叉樹BT的存儲結(jié)構(gòu)如下：(1) 畫出圖。(2) 寫出前序、中序、后序遍歷次序。 解答：見下圖。ABCDEFGHIJ(2

17、) 前序遍歷：ABCEDFHGIJ 中序遍歷：ECBHFDJIGA 后序遍歷：ECHFJIGDBA7、已知一棵二叉樹先序遍歷結(jié)果為 ABCDEFGHIJ，中序遍歷的結(jié)果為 CBEDAHGIJF，試畫出該二叉樹。 解答：由前序遍歷結(jié)果可知該二叉樹的根結(jié)點為A。由此及中序遍歷結(jié)果可知，該二叉樹在中序遍歷下的左、右子樹為CBED 和 HGIJF依此可推出前序遍歷的左、右子樹的結(jié)點序列為BCDE 和 FGHIJB和F又分別為左、右子樹的根結(jié)點，進(jìn)而又可推出以B為根結(jié)點的左、右子樹，以及以F為根結(jié)點的左、右子樹。依此類推，可推出二叉樹見下圖。CD GE HIJ8、 設(shè)a是含有n個元素的整數(shù)數(shù)組，寫出一個

18、求n個元素的平均值的遞歸定義。解答：#include <stdio.h>#defi ne AVE(A,B) aver(A,B,O)double aver(float *a,i nt n ,i nt t)if (t!=n) retur n (at/n+aver(a ,n ,t+1);else return 0;int main( void)float a=1,5,9,13,17;prin tf("%f",AVE(a,5);return 0;9、設(shè)a是含有n個元素的整數(shù)數(shù)組：(1) 寫出求該數(shù)組中最大元素的遞歸定義。(2) 寫出求該數(shù)組中最小元素的遞歸定義。答：(1

19、)int A : Max (int n) / 遞歸求最大值if (n=1) return E0;int t=Max ( n-1 );if (E n-1>t) return En-1;else retur n t;int A : Mi n (i nt n) / 遞歸求最小值if (n=1) return E0;int t=Mi n ( n-1 );if (E n-1>t) return En-1;else retur n t;10、設(shè)a是含有n個元素的整數(shù)數(shù)組：(1) 寫出求n個整數(shù)之和的遞歸定義。(2) 寫出求n個整數(shù)之積的遞歸定義。解答：(1) int A : Sum (int

20、n) /遞歸求數(shù)組之和if (n=1) return E0;else return En-1+Sum (n-1);(2) int A : Multi (int n) / 遞歸求整數(shù)之積if (n=1) return E0;else return En-1*Multi (n-1);11、二維數(shù)組 A44(即 A0.30.3)的元素起始地址是 loc(A00)=1000,元素的長度為 2,則 LOC(A22)的地址為多少？答：LOC(A22)= loc(A00)+( 2*4+2)*2=1000+20=1020數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題：圖問答題1、無向圖G如下圖：BE/ /ADG / /C試給出F(1) 該圖

21、的鄰接矩陣。(2) 該圖的鄰接表。(3) 從A出發(fā)的 深度優(yōu)先”遍歷序列。(4)從A出發(fā)的 廣度優(yōu)先”遍歷序列。解答：(1)圖G的鄰接矩陣廠0110000n11001000|11001000|A =|0110110|0001001|0001001|L0000110(2)鄰接表如見：II II I III I1 Ia| +He |+Hep IIIIIIIIII2 |B |+ta | +tD | 人 |3|C |A |D 丨人 |4 |D |B |c | + Te |人卜TF | 人 |(3) 從頂點A出發(fā)按深度優(yōu)先遍歷序列 (不是唯一的)為A、B、D、C、E、G、F(4) 從頂點A出發(fā)按廣度優(yōu)先

22、遍歷序列 (不是唯一的)為A、B、C、D、E、F、G2、 用鄰接矩陣表示圖時，矩陣元素的個數(shù)與頂點個數(shù)是否相關(guān)？與邊的條數(shù)是否有關(guān)？答：設(shè)圖的頂點個數(shù)為 n(n >0)則鄰接矩陣元素個數(shù)為n2，即頂點個數(shù)的平方，與圖的邊數(shù)無關(guān)。3、 對于稠密圖和稀疏圖，就存儲空間而言，采用鄰接矩陣和鄰接表哪個更好些？ 答：稠密圖采用鄰接矩陣好，稀疏圖采用鄰接表好4、 請回答下列關(guān)于圖的一些問題：(1) 有n個頂點的有向強(qiáng)連通圖最多有多少條邊？這樣的圖應(yīng)該是什么形狀？(2) 有n個頂點的有向強(qiáng)連通圖最少有多少條邊？這樣的圖應(yīng)該是什么形狀？(3) 表示一個有1000個頂點、1000條邊的有向圖的鄰接矩陣有多

23、少個矩陣元素？是否為稀疏矩陣？答：(1)最多有n(n-1)條邊(2) 最少有n條邊(3) 106，不一定是稀疏矩陣(稀疏矩陣的定義是非零個數(shù)遠(yuǎn)小于該矩陣元素個數(shù)，且分布無規(guī)律)5、 對n個頂點的無向圖和有向圖，采用鄰接矩陣和鄰接表表示時，如何判別下列有關(guān)問題 ？(1) 圖中有多少條邊？(2) 任意兩個頂點i和j是否有邊相連？(3) 任意一個頂點的度是多少？答：無向圖采用鄰接表時，邊表中的結(jié)點個數(shù)之和除以2。 第i個邊表中是否含有結(jié)點j。 該頂點所對應(yīng)的邊表中所含結(jié)點個數(shù)。6、 己知一棵二叉樹的中序序列為cbedahgijf，后序序列為cedbhjigfa，畫出該二叉樹的先序線索二叉樹 答：二叉

24、樹及線索二叉樹(略)。先序序列為：abcdefghij7、 下列整數(shù)序列由選序遍歷一棵二叉排序樹得到：50,40,30,45,65,55,70,80.試構(gòu)造一棵這樣的二叉排序樹80答：數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題：內(nèi)部排序問答題1、設(shè)有5000個無序的元素，希望用最快速度挑選出其中前10個最大的元素。在以下的排序方法中，采用哪種方法最好？為什么？快速排序，堆排序，歸并排序，基數(shù)排序的Shell排序。1、上面所列的幾種排序方法的速度都很塊，但快速排序、歸并排序、基數(shù)排序和希爾排序都是在排序結(jié)束后才能確定數(shù)據(jù)元素的全部順序，而無法知道排序過程中部分元素的有序性。而堆排序則每次輸入一個最大(或最小)的元素，然后對

25、堆進(jìn)行調(diào)整，保證堆頂?shù)脑乜偸怯嘞略刂凶畲?或最小)的。根據(jù)題意，只要選 取前10個最大的元素，故采用堆排序方法是合適的2、判斷下列序列是否是堆。若不是堆，則把它們依次調(diào)整為堆。(1) (100，85，98，77, 80，60，82，40，20，10，66)。(2) (100，98，85，82，80，77，66，60，40，20，10)。(3) (100，85，40，77，80，60，66，98，82，10，20)。(10，20，40，60，66，77，80，82，85，98，100)。解答：根據(jù)堆的定義可知堆中元素滿足下面中的某一個式子的關(guān)系，廠w k2i廠k2i ki或 kiL<

26、k21L> k2M因此(1)、(2)和(4)序列是堆。(3)不是堆。(3) 調(diào)整為 100,98,66,85,80,60,40,77,82,10,20后成為堆。3、什么是內(nèi)部排序？什么是排序方法的穩(wěn)定性和不穩(wěn)定性？解答：假設(shè)給定含有 n個記錄(R1 ，R2，Rn )的文件，其相應(yīng)的關(guān)鍵字為(K1 ，K2，Kn )，則排序是確定一個排列P(1)，P(2)，P(n)，使得KP(1) w KP(2)，KP( n)，從而得到有序文件(RP(1) ，RP(2)，RP(n)。整個排序過程都在內(nèi)存進(jìn)行的排序稱為內(nèi)部排序。假設(shè)在待排序的文件中，存在兩個或兩個以上的記錄具有相同的關(guān)鍵字，在用某種排 序法排

27、序后，若這些相同關(guān)鍵字的記錄的相對次序仍然保持不變，則這種排序方法是穩(wěn)定的，否則稱這種排序方法是不穩(wěn)定的。4、 輸入一個正整數(shù)序列40,28,6,72,100,3,54,1,80,91,38,建立一棵二叉排序樹，然后刪除結(jié)點 72,分別畫出該二叉樹及刪除結(jié)點72后的二叉樹。5、設(shè)數(shù)據(jù)集合d=1,12,5,8,3,10,7,13,9,試完成下列各題：(1) 依次取d中各數(shù)據(jù)，構(gòu)造一棵二叉排序樹bt;(2) 如何依據(jù)此二叉樹 bt得到d的一個有序序列； 畫出在二叉樹bt中刪除"12"后的樹結(jié)構(gòu)。解答：(1) (3)圖略。(2)根據(jù)二叉排序樹中左子樹，根結(jié)點，右子樹的排列順序，有

28、序序列：1，3，5，7，8，9，10，12，136、 對給定的數(shù)列 R=7,16,4,8,20,9,6,18,5,構(gòu)告一棵二叉排序樹，并且(1) 給出按中序遍歷得到的數(shù)列R1(2) 給出按后序遍歷得到的數(shù)列R2解答：圖略。中序遍歷序列R1 : 5,6,4,7,8,9,16,18,20后序遍歷序列 R2: 5,6,4,9,8,18,20,16,77、設(shè)有一組關(guān)鍵字19,01,23,14,55,20,84,27,68,11,10,77, 采用散列函數(shù)：H(key)=key%13采用開放地址法的線性探測再散列方法解決沖突，試在018的散列地址空間中對該關(guān)鍵字序列構(gòu)造散列表。解答：H(19)=19 M

29、OD 13=6H(01)=01 MOD 13=1H(23)=23 MOD 13=10H(14)=14 MOD 13=1( 沖突)H(14)=(1+1) MOD 19=2H(55)=55 MOD 13=3H(20)=20 MOD 13=7H(84)=84 MOD 13=6 ( 沖突)H(84)=(6+1) MOD 19=7 ( 仍沖突)H(84)=(6+2) MOD 19=8H(27)=27 MOD 13=1 ( 沖突)H(27)=(1+1) MOD 19=2 ( 沖突)H(27)=(1+2) MOD 19=3 ( 仍沖突)H(27)=(1+3) MOD 19=4H(68)=68 MOD 13=

30、3 ( 沖突)H(68)=(3+1) MOD 19=4 ( 仍沖突)H(68)=(3+2) MOD 19=5H(11)=11 MOD 13=11H(10)=10 MOD 13=10 ( 沖突)H(10)=(10+1) MOD 19=11 ( 仍沖突)H(10)=(10+2) MOD 19=12H(77)=77 MOD 13=12 ( 沖突)H(77)=(12+1) MOD 19=13因此，各關(guān)鍵字相應(yīng)的地址分配如下：address(01)=1address(14)=2address(55)=3addre8、 線性表的關(guān)鍵字集合87,25,310,08,27,132,68,95,187,123,

31、70,63,47, 共有13個元素,己知散列函數(shù) 為:H(key)=k%13采用拉鏈法處理沖突。設(shè)計出這種鏈表結(jié)構(gòu)，并計算該表的成功查找的平均查找長度。9、 己知序列17,18,60,40,7,32,73,65,85,請給出采用冒泡排序法對該序列作為升序排序時的每一趟的結(jié)果。解答:初始：17，18，60，40，7，32，73，65，85第1趟:17，18，40，7，32，60，65，73，85第2趟:17，18，7，32，40，60，65，73，85第3趟:17，7，18，32，40，60，65，73，85第4趟:7,17，18，32，40，60，65，73，85第5趟：7,17，18，32，

32、40，60，65，73，85第5趟無元素交換，則排序結(jié)束。10、己知序列 503，87，512，61，908，170，897，275，653，462，請給出采用快速排序法對該序列 作升序排序時的每一趟結(jié)果。解答：原始序列：503，87，512，61，908，170，897，275，653，462第 1 趟： 462，87，275，61，170503897 ，908，653，512第 2 趟： 170，87，275，61 462，503897，908，653，512第 3 趟： 87，61170275 462 ，503897，908，653，512第 4 趟： 61 87170275 462，5

33、03897，908，653，512第 5 趟： 61 ，87，170，275 462，503897，908，653，512第6趟：61，87，170，275，462，第7趟：61，87，170，275，462，第8趟：61，87，170，275，462，第9趟：61，87，170，275，462，第10趟：61，87，170，275，462，503897，908，653，512503512，653897908503，512，653 897908503，653，89790811、己知序列503,87,512,61,908,170,897,275,653,462,請給出采用的基數(shù)排序法對該序列作升

34、序排序時的每一趟的結(jié)果。解答：依題意，采用基數(shù)排序法排序的各趟的結(jié)果如下：初始：503，87，1趟（按個位排序）2趟（按十位排序）3趟（按百位排序）512 , 61 , 908 , 170 , 897 , 275 , 653 , 462:170 , 61 , 462 , 512 , 503 , 653 , 275 , 87, 897 ,:503 , 908 , 512 , 653 , 61 , 462 , 170 , 275 , 87,:61 , 87 , 170 , 275 , 462 , 503 , 512 , 653 , 897 ,908897908503，653，897，90883，1

35、00，65，10，32，7，983，100，65，10，32，7，83，100，65，10，32，7，70，83，100，10，32，7，65，70， 83， 100，32，7，32，65，70，83，100，7，10，32，65，70，83，100，70 ,70 ,70 ,65 ,10 ,10 ,7,99999912、 己知序列70,83,100,65,10,32,7,9,請給出采用直接插入排序法對該序列作升序排序時的每一趟的結(jié)果。 解答：原始序列第1趟結(jié)果第2趟結(jié)果第3趟結(jié)果：第4趟結(jié)果第5趟結(jié)果第6趟結(jié)果7 , 9 , 10, 32, 65, 70, 83, 100第7趟結(jié)果13、 己知

36、序列10,18,4,3,6,12,1,9,18,8,請給出采用希爾排序法對該序列作升序排序時的每一趟結(jié)果。解答：原始序列：10,18,4,3,6,12,1,9,18,8分成5個子序列的結(jié)果：10，1，4，3，6，12，18，9，18，8 再分為2個子序列的結(jié)果：10，1，4，3，6，12，18，9，18，8最后結(jié)果：1，3，4，6，8，9，10，12， 18，1814、己知序列10,18,4,3,6,12,1,9,18,8,請給出采用歸并排序法對該序列作作升序排序時的每一趟的結(jié)果。解答：采用2路歸并排序的結(jié)果如下：初始狀態(tài)：10 ,18 ,4 ,3 ,6 ,12 ,1 ,9 ,18,8第 1

37、趟歸并后：10，18，3，4，6，12，1，9，8，18第 2 趟歸并后：3，4，10，18，1，6，9，12，8，18第 3 趟歸并后：1，3，4，6，9，10，12，18，8，18最后 1 趟歸并得結(jié)果：1，3，4，6，8，9，10，12，18，1815、 在冒泡排序過程中，有的關(guān)鍵字在某趟排序中朝著與最終排序相反的方向移動。試舉例說明之?？焖倥判?過程中有沒有這種現(xiàn)象 ？在逆序時排序碼會朝著與最終位置相反的方向移動。例如（5，4，2，1），第一趟冒泡排序后為（4，2，1，5），關(guān)鍵字4的位置被移動到首位，朝著與最終排序相反的方向移動?？焖倥判驔]有這種現(xiàn)象。16、 如果在10A6個記錄中找

38、到兩個最小的記錄，你認(rèn)為可采用下列方法中的什么關(guān)的排序方法所需的關(guān)鍵字 比較次數(shù)最少？共計多少？根據(jù)堆排序的特點，每次都是輸出一個堆頂元素，然后對堆進(jìn)行再調(diào)整，保證堆頂元素總是當(dāng)前剩下元素的最大或最小，從而可知，欲在一個大量數(shù)據(jù)的文件中，如10A6個記錄中找到兩個最小的記錄，可采用堆排序。17、 如果只想得到一個序列中第 k個最小元素之前的部分排序序列 ，最好采用什么排序方法 ？為什么？如由這樣 的一個序列：57,40,38,11,13,34,84,75,25,6,19,9,7 得到其第4個最小元素之前的部分序列 6,7,9,11,使用所 選擇的算法實現(xiàn)時，要執(zhí)行多少次比較？解答：采用堆排序最

39、合適，依題意可知只需取得第k個最小元素之前的排序序列時，堆排序的時間復(fù)雜度0(n+klog2n)，若k< nlog2n,則得到的時間復(fù)雜性是O (n)。對于上述序列得到其前 4個最小元素，使用堆排序?qū)崿F(xiàn)時，執(zhí)行的比較次數(shù)如下：初始建堆：比較 20次，得到6 ;第一次調(diào)整：比較 5次，得到7;第二次調(diào)整：比較 4次，得到9;第三次調(diào)整：比較 5次，得到11。18、 對于快速排序的非遞歸算法，可以用隊列(而不用棧)實現(xiàn)嗎？若能,說明理由；若不能，也要說明理由。 可以用隊列來代替。在快速排序的過程中，通過一趟劃分，可以把一個待排序區(qū)間分為兩個子區(qū)間，然后分 別對這兩個子區(qū)間施行同樣的劃分。棧的

40、作用是在處理一個子區(qū)間時，保存另一個區(qū)間的上界和下界。這個功能利用隊列可以實現(xiàn)，只不過是處理子區(qū)間的順序有所變動而已。19、 己知下列各種初始狀態(tài)(長度為n)的元素，試問當(dāng)利用直接插入法進(jìn)行排序時，至少需要進(jìn)行多少次比較(要求排序后的文件按關(guān)鍵字從小到大順序排列)?解答：依題意，最好情況下的比較次數(shù)即為最少比較次數(shù)。 插入第i (2< i個元素的比較次數(shù)為1,因此總的比較次數(shù)為：1+1 +1=n -1 插入第i (2< i個元素的比較次數(shù)為i,因此總的比較次數(shù)為：2+3+n=( n-1)( n+2)/2 比較次數(shù)最少的情況是所有記錄關(guān)鍵碼按升序排列，總的比較次數(shù)為：n-1 在后半部

41、分元素的關(guān)鍵碼均大于前半部分元素的關(guān)鍵碼時需要的比較次數(shù)最少，總的比較次數(shù)為：n-120、 若對具有n個元素的有序的順序表和無序的順序表分別進(jìn)行順序查找，試在下述兩種情況下分別討論兩者在等概率時的平均查找長度：(1) 查找不成功，即表中無關(guān)鍵字等于給定值k的記錄.(2) 查找成功，即表中有關(guān)鍵字等于給定值k的記錄.答：(1)有序和無序都是 n+1(2)有序和無序都是(n+1 ) /221、 己知一個有序表為12,18,20,25,29,32,40,62,83,90,95,98,當(dāng)二分查找法為 29和90的元素時，分別需要多少次比較才能查找成功？若采用順序查找時，分別需要多少次比較才能查找成功？

42、答：二分法查29時，需要比較3次才能查找成功。二分法查90時，需要比較3次才能查找成功；順序查找29時，需要比較5次才能查找成功。順序查找90時，需要比較10次才能查找成功。22、關(guān)鍵字序列7,4,1,14,100,30,5,9,20,134, 設(shè)哈希函數(shù)為 h(key)=Key Mod 13,試給出表長為13的哈希表(用線性探測開放定址法處理沖突),并求出在等概率情況下，查找成功時和查找不成功時的平衡查找長度答：k741141003059 20134k%13641 1945 974散列地址01 2345678910 1112關(guān)鍵字1144307520100 9134成功到位次數(shù)1212132

43、128不成功到位次數(shù)1321987654321查找成功的平均查找長度為(1+2+1+2+1+3+2+1+2+8) /10=23/10查找不成功的平均查找長度為(1+3+2+1+9+8+7+6+5+4+3+2+1) /13=423、比較直接插入排序和希爾排序的不同點答：直接插入排序：每次從無序表中取出第一個元素，把它插入到有序表的合適位置，使有序表仍然有序。 希爾排序：是針對直接插入排序算法的改進(jìn)，該方法又稱縮小增量排序。該方法實質(zhì)上是一種分組插入方法24、給出關(guān)鍵字序列17, 8，21，35，32，15，21，25，12，23的直接插入排序過程答：(8，17)21，35，32，15，21，25

44、，12，23(8， 17， 21) 35， 32，(8， 17， 21， 35) 32，(8， 17， 21， 32， 35)(8， 15， 17， 21， 32，(8，15，17，21，21，(8，15，17，21，21，(8，12，15，17，21，(8，12，15，17，21，15，21，25，12，2315，21，25，12，2315，21，25，12，2335)21，25，12，2332，35)25，12，2325， 32， 35) 12， 2321，25，32，35)2321，23，25，32，35)25、指出堆和二叉排序樹的區(qū)別答：在二叉排序樹中，每個結(jié)點的值均大于其左子樹上所有

45、結(jié)點的值，小于其右子樹上所有結(jié)點的值，對二 叉排序樹進(jìn)行中序遍歷得到一個有序序列。所以，二叉排序樹是結(jié)點之間滿足一定次序關(guān)系的二叉樹；堆是一個完全二叉樹，并且每個結(jié)點的值都大于或等于其左右孩子結(jié)點的值(這里的討論以大根堆為例)，所以,堆是結(jié)點之間滿足一定次序關(guān)系的完全二叉樹。26、 堆排序是否是一種穩(wěn)定的排序方法？為什么？試舉例說明。答：堆排序不是穩(wěn)定的排序方法。因為堆排序再調(diào)整堆時，有可能使原來鍵值相等的元素的相對位置改變，所以是不穩(wěn)定排序。例如對鍵值序列7，4，2，2 ，建小根堆由小到大排序的結(jié)果是2，2，4，7，兩個2的相對位置改變了。27、 對于n個元素組成的線性表進(jìn)行快速排序，所需要

46、進(jìn)行的比較次數(shù)與這n個元素的初始排列有關(guān)。問： (1)當(dāng)n=7時，最好情況下需進(jìn)行多少次比較？請說明理由。當(dāng)n=7時，給出一個最好情況的初始排列的實例。(3) 當(dāng)n=7時，在最壞情況下需進(jìn)行多少次比較？請說明理由。(4) 當(dāng)n=7時，給出一個最壞情況的初始排序的實例。答：(1)在最好情況下，假設(shè)每次劃分能得到兩個長度相等的子文件，文件的長度n=2k-1，那么第一遍劃分得到兩個長度均為？n/2?的子文件，第二遍劃分得到4個長度均為？n/4?的子文件，以此類推，總共進(jìn)行k=log2(n+1)遍劃分，各子文件的長度均為1，排序完畢。當(dāng)n=7時，k=3，在最好情況下，第一遍需比較6次，第二遍分別對兩個

47、子文件(長度均為3，k=2 )進(jìn)行排序，各需 2次，共10次即可。 在最好情況下快速排序的原始序列實例：4,1,3,2,6,5,7。(3) 在最壞情況下，若每次用來劃分的記錄的關(guān)鍵字具有最大值(或最小值)，那么只能得到左(或右)子文件，其長度比原長度少1。因此，若原文件中的記錄按關(guān)鍵字遞減次序排列，而要求排序后按遞增次序排列時，快速排序的效率與冒泡排序相同，其時間復(fù)雜度為0(n2)。所以當(dāng)n=7時，最壞情況下的比較次數(shù)為21次。(4) 在最壞情況下快速排序的初始序列實例：7,6,5,4,3,2,1，要求按遞增排序。28、 已知503,87,512,61,908,170,897,275,653,

48、462，采用二路歸并排序法對該序列作升序排序時的每一趟 的結(jié)果。答：初始關(guān)鍵字：503，87，512，61，908，170，897，275，653，462一趟歸并之后：87，503，61，512，170，908，275，897，462，653兩趟歸并之后：61，87，503，512，170，275，897，908，462，653三趟歸并之后：61，87，170，275，503，512，897，908，462，653四趟歸并之后：61，87，170，275，462，503，512，653，897，90829、 在堆排序、快速排序和歸并排序中：(1) 若只從存儲空間考慮，則應(yīng)首先選取哪能種排序方法

49、，其次選取哪種排序方法，最后選取哪種排序方法？(2) 若只從排序結(jié)果的穩(wěn)定性考慮，則應(yīng)選取哪種排序方法？若只從平均情況下排序最快考慮，則應(yīng)選取哪種排序方法？(4) 若只從最壞情況下排序最快并且要節(jié)省內(nèi)存考慮，則應(yīng)選取哪種排序方法？答：(1)堆排序，快速排序，歸并排序(2) 歸并排序(3) 快速排序(4) 堆排序30、 有一個有序表 R1.13=1,3,9,12,32,41,45,62,75,77,82,95,100,當(dāng)用二分查找法查找關(guān)鍵字為82的結(jié)點時，經(jīng)多少次比較后查找成功儂次與哪些關(guān)鍵字進(jìn)行比較？答：經(jīng)4次比較后查找成功，依次與關(guān)鍵字 45，77，95，82進(jìn)行比較。31、 以關(guān)鍵字序列265,301,751,129,937,863,742,694,76,438 為例，給出歸并排序算法的各趟排序結(jié)束時，關(guān) 鍵字序列的狀態(tài)答：初始關(guān)鍵字：265，301，751，129，937，863，742，694，76，438一趟歸并之后：265，301，129，751，863，937，694，742，76，438兩趟歸并之后：1