數(shù)據(jù)結構各章作業(yè)題目

1、第一章作業(yè)一、 選擇題1. 被計算機加工的數(shù)據(jù)元素不是孤立的，它們彼此之間一般存在某種關系，通常把數(shù)據(jù)元素之間的這種關系稱為( )。A. 規(guī)則B. 結構C. 集合D. 運算2. 在Data_Structure=(D,S)中，D是( )的有限集合。A. 數(shù)據(jù)元素B. 算法C. 數(shù)據(jù)操作D.數(shù)據(jù)對象3. 計算機所處理的數(shù)據(jù)一般具有某種關系，這是指( )之間存在的某種關系。A. 數(shù)據(jù)與數(shù)據(jù)B. 數(shù)據(jù)元素與數(shù)據(jù)元素C. 元素內數(shù)據(jù)項與數(shù)據(jù)項D. 數(shù)據(jù)文件內記錄與記錄4. 順序存儲表示中數(shù)據(jù)元素之間的邏輯關系是由( )表示的。A. 指針B. 邏輯順序C. 存儲位置D. 問題上下文5. 鏈接存儲表示中數(shù)據(jù)

2、元素之間的邏輯關系是由( )表示的。A. 指針B. 邏輯順序C. 存儲位置D. 問題上下文6. 從邏輯上可將數(shù)據(jù)結構分為( )。A. 動態(tài)結構和靜態(tài)結構B. 緊湊結構和非緊湊結構C. 內部結構和外部結構D. 線性結構和非線性結構7. 以下選項屬于線性結構的是( )。A. 廣義表B. 二叉樹C. 串D. 稀疏數(shù)組8. 以下選項屬于非線性結構的是( )。A. 廣義表B. 隊列C. 優(yōu)先隊列D. 棧9. 以下屬于邏輯結構的是( )A. 順序表B. 散列表C. 有序表D. 單鏈表10. 一個完整的算法應該具有( )等特性。A. 可執(zhí)行性、可修改性和可維護性B. 可行性、確定性和有窮性C. 確定性、有窮

3、性和可靠性D. 正確性、可讀性和有效性11. 若一個問題既可以用迭代方法也可以用遞歸方法求解，則( )的方法具有更高的時空效率。A. 迭代B. 遞歸C. 先遞歸后迭代D. 先迭代后遞歸12. 一個遞歸算法必須包括( )A. 遞歸部分B. 終止條件和遞歸部分C. 迭代部分D. 終止條件和迭代部分13. 算法的時間復雜度與( )有關。A. 問題規(guī)模B. 源程序長度C. 計算機硬件運行速度D. 編譯后執(zhí)行程序的質量二、指出下列各算法的功能并求出其時間復雜度。(1)int Prime(int n)int i=2,x=(int)sqrt(n); /sqrt(n)為求n的平方根while(i<=x)

4、if(n%i=0)break;i+;if(i>x) return 1;else return 0;(2)int sum1(int n)int p=1,s=0;for(int i=1;i<=n;i+)p*=i;s+=p;return s;(3)int sum2(int n)int s=0;for(int i=1;i<=n;i+)int p=1;for(int j=1;i<=i;j+) p*=j;s+=p;return s;(4)int fun(int n)int i=1,s=1;while(s<n) s+=+i;return i;(5)void mtable(int

5、 n)for(int i=1;i<=n;i+)for(int j=i;j<=n;j+)cout<<i<<"*"<<j<<"="<<setw(2)<<i*j<<" "cout<<endl;第二章作業(yè)一、選擇題1. 在線性表中的每一個表元素都是不可再分的( )A. 數(shù)據(jù)項B. 數(shù)據(jù)記錄C. 數(shù)據(jù)元素D. 數(shù)據(jù)字段2. 順序表是線性表的( )存儲表示。A. 有序B. 連續(xù)C. 數(shù)組D. 順序存取3. 若長度為n的非空線性表采用順序存儲

6、結構，在表中的第i個位置插入一個數(shù)據(jù)元素，i的合法值應該是( )A. B. C. D. 4. 若設一個順序表的長度為n，那么，在表中順序查找一個值為x的元素時，在等概率的情況下，查找成功的數(shù)據(jù)平均比較次數(shù)為( )A. B. C. D. 5. 在長度為n的順序表的表尾插入一個新的元素的時間復雜度為( )A. B. C. D. 6. 數(shù)據(jù)結構反映了數(shù)據(jù)元素之間的結構關系。單鏈表是一種( )。A. 順序存儲線性表B. 非順序存儲非線性表C. 順序存儲非線性表D. 非順序存儲線性表7. 單鏈表又稱為線性鏈表，在單鏈表上實施插入和刪除操作( )A. 不需移動結點，不需改變結點指針B. 不需移動結點，只需

7、改變結點指針C. 只需移動結點，不需改變結點指針D. 既需移動結點，又需改變結點指針8. 已知L是帶頭結點的單鏈表，則刪除首元素結點的語句是( )A. L=L->next;B. L->next=L->next->next;C. L=L->next->next;D. L->next=L;9. 已知單鏈表A長度為m，單鏈表B長度為n，若將B鏈接在A的末尾，在沒有鏈尾指針的情況下，算法的時間復雜度應為( )。A. B. C. D. 10. 給定有n個元素的一維數(shù)組，建立一個有序單鏈表的時間復雜度是( )A. B. C. D. 二、算法設計1. 設計一個算法，

8、從順序表L中(SqList L)刪除具有給定值x(ElemType x)的所有元素。2. 設計一個算法，從有序順序表中刪除所有其值重復的元素，使表中所有元素的值均不相同。3. 設計一個算法，在非遞減有序的帶頭結點的單鏈表中刪除值相同的多余結點。第三章作業(yè)一、選擇題1. 用S表示進棧操作，用X表示出棧操作，若元素的進棧順序是1234，為了得到1342的出棧順序，相應的S和X的操作序列為( )A. SXSXSSXXB. SSSXXSXXC. SXSSXXSXD. SXSSXSXX2. 假設一個棧的輸入序列是1，2，3，4，則不可能得到的輸出序列是( )A. 1,2,3,4B. 4,1,2,3C.

9、4,3,2,1D. 1,3,4,23. 已知一個棧的進棧序列為1,2,3,n，其輸出序列的第一個元素是i，則第j個出棧元素是( )。A. B. C. D. 不確定4. 已知一個棧的進棧序列為，其輸出序列是。若，則的值是( )A. B. C. D. 不確定5. 已知一個棧的進棧序列為，其輸出序列是。若，則的值是( )A.一定是2B. 一定是1C.可能是1D. 可能是26. 已知一個棧的進棧序列為，其輸出序列是。若，則的值是( )A.一定是2B. 可能是2C.不可能是2D. 一定是37. 已知一個棧的進棧序列為，其輸出序列是。若，則的值是( )A.一定是2B. 可能是2C.不可能是1D. 一定是1

10、8. 已知一個棧的進棧序列為，其輸出序列是。若，則的值是( )A. B. C. D. 不確定9. 設棧S和隊列Q的初始狀態(tài)均為空，元素1,2,3,4,5,6,7，依次進入S。如果每個元素出棧后立即進入隊列Q，且7個元素的出隊順序為2,4,3,6,5,1,7，則棧S的容量至少是( )A. 1B. 2C. 3D. 410. 對中綴表達式求值，在求值過程中掃描到6時，操作數(shù)棧和操作符棧的內容分別是( )A. 3,2,4,2,2和+,*,(,+,*B. 3,2,4,4和+,*,(,+C. 3,2,8和+,*,(D. 3,2,8,6和+,*,(,-二、算法設計題1. 詳見數(shù)據(jù)結構題集(C語言版)第25頁

11、3.24。2. 詳見數(shù)據(jù)結構題集(C語言版)第25頁3.25。第四章作業(yè)11. 串是一種特殊的線性表，其特殊性體現(xiàn)在( )A. 可以順序存儲B. 數(shù)據(jù)元素是一個字符C. 可以鏈式存儲D. 數(shù)據(jù)元素可以是多個字符12. 設有兩個串T和P，求P在T中首次出現(xiàn)的位置的運算叫做( )。A. 求子串B. 模式匹配C. 串替換D. 串連接13. 下面關于串的敘述中，哪一個是不正確的？（ ）A串是字符的有限序列 B空串是由空格構成的串C模式匹配是串的一種重要運算 D串既可以采用順序存儲，也可以采用鏈式存儲14. 串的長度是指（ ）A串中所含不同字母的個數(shù) B串中所含字符的個數(shù)C串中所含不同字符的個數(shù) D串中

12、所含非空格字符的個數(shù)15. 兩個串相等的充分必要條件是（）A串中所含的字符相同 B串中所含字符的個數(shù)相同，且對應位置上的字符也相同C串中所含的字符個數(shù)相同 D串中對應位置上的字符相同6. 已知p=”abcaabbabcabaacbacb”，求出next函數(shù)值。第五章作業(yè)一、選擇題16. 數(shù)組通常具有的操作是( )A. 順序存取B. 直接存取C. 散列存取D. 索引存取17. 多維數(shù)組實際上是由( )實現(xiàn)的。A. 一維數(shù)組B. 多項式C. 三元組表D. 簡單變量18. 在二維數(shù)組A810中，每一個數(shù)組元素Aij占用3個存儲空間，所有數(shù)組元素相繼存放于一個連續(xù)的存儲空間中，則存放該數(shù)組至少需要的存

13、儲空間是( )。A. 80B. 100C. 240D. 27019. 一個二維數(shù)組A1020按行存放于一個連續(xù)的存儲空間中，A00的存儲地址是200，每個數(shù)組元素占1個存儲字，則A62的地址為( )A. 226B. 322C. 341D. 34220. 一個二維數(shù)組A1020按列存放于一個連續(xù)的存儲空間中，A00的存儲地址是200，每個數(shù)組元素占1個存儲字，則A62的地址為( )A. 226B. 322C. 341D. 34221. 在二維數(shù)組A910中，每個數(shù)組元素占用3個存儲單元，從首地址SA開始按行連續(xù)存放，在這種情況下，元素A85的起始地址為( )A. SA+141B. SA+144C

14、. SA+222D. SA+25522. 將一個的對稱矩陣A的下三角部分按存放在一個一維數(shù)組B中，A00存放在B0中，那么第i行的對角元素Aii在B中的存放位置是( )A. B. C. D. 23. 將一個的對稱矩陣A的上三角部分按存放在一個一維數(shù)組B中，A00存放在B0中，那么第i行的對角元素Aii在B中的存放位置是( )A. B. C. D. 24. 設A是一個的對稱矩陣，將A的對角線及對角線上方的元素以列優(yōu)先(以列為主序)的方式存放在一維數(shù)組中，則矩陣中任一元素在B中的存放位置是( )A. B. C. D. 25. 設n階三對角矩陣A的三條對角線上的元素被按行壓縮存儲到一維數(shù)組B中，A0

15、0存放于B0。若某矩陣元素在B中存放的位置在k，那么該元素在原始矩陣中的行號i是( )A. B. C. D. 二、簡答題26. 設有一個3維數(shù)組，按行優(yōu)先存放于一個連續(xù)的存儲空間中，每個數(shù)組元素占4個存儲字，首元素的存儲地址是1000，則存放于什么地方。27. 設有一個二維數(shù)組，假設存放位置在，存放在，每個元素占1個存儲單元，問存放在什么位置？腳注(10)表示用十進制表示。28. 對于一個矩陣A的任一元素，按行存儲和按列存儲時的地址之差是多少？(假設兩種存儲的開始存儲地址以及元素所占存儲單元數(shù)d相同)29. 設有n階三對角矩陣A，將其3條對角線上的元素逐行存儲到數(shù)組中，使得，且，求(1) 用i

16、，j表示k的下標變換公式。(2) 用k表示i，j的下表變換公式。30. 設有一個的對稱矩陣A，將其下三角部分按行壓縮存放于一個一維數(shù)組B中，存放于B0，試問：(1) 一維數(shù)組B有多少個元素？(2) A中的任意一個元素應存于一維數(shù)組B的什么下標位置？31. 設有一個的對稱矩陣A，將其上三角部分按列壓縮存放于一個一維數(shù)組B中，存放于B0，試問：(1) 一維數(shù)組B有多少個元素？(2) A中的任意一個元素應存于一維數(shù)組B的什么下標位置？第六章作業(yè)一、選擇題 32. 一顆有n個結點的樹的所有結點的度數(shù)之和為( )。A. B. C. D. 33. 設一顆高度為h的滿二叉樹有n個結點，其中有m個葉結點，則(

17、 )A. B. C. D. 34. 一顆有124個葉結點的完全二叉樹最多有( )個結點。A. 247B. 248C. 249D. 25035. 一顆有129個葉結點的完全二叉樹最少有( )個結點。A. 254B. 255C. 257D. 25836. 設完全二叉樹的第6層有24個葉結點，則此樹最多有( )個結點。A. 55B. 79C. 81D. 12737. 具有1000個結點的完全二叉樹的次底層的葉結點個數(shù)為( )。A. 11B. 12C. 24D. 3638. 用順序存儲的方法將n個結點的完全二叉樹中所有結點按層逐個順序存放在一維數(shù)組中，當編號為0的根結點存放于時，若結點有左孩子，則左孩

18、子是( )。A. B. C. D. 39. 用順序存儲的方法將n個結點的完全二叉樹中所有結點按層逐個順序存放在一維數(shù)組中，當編號為0的根結點存放于時，若結點有右孩子，則右孩子是( )。A. B. C. D. 40. 二叉樹的葉結點在前序、中序和后序遍歷過程中的相對順序( )。A. 發(fā)生改變B. 不發(fā)生變化C. 無法確定D. 以上均不對41. 設n，m為一顆二叉樹上的兩個結點，在該二叉樹的中序遍歷序列中n在m前的條件是( )。A. n在m右方B. n是m的祖先C. n在m左方D. n是m的子孫42. 設一顆二叉樹的前序序列為abdec，中序序列為dbeac，則該二叉樹的后序遍歷順序是( )。A.

19、 abdecB. debacC. debcaD. abedc43. 設一顆二叉樹的中序序列為badce，后序序列為bdeca，則該二叉樹的前序遍歷順序是( )。A. adbecB. decabC. debacD. abcde44. 對二叉樹的結點從1開始連續(xù)編號，要求每個結點的編號大于其左、右孩子的編號，同一結點的左、右孩子中，其左孩子編號小于其右孩子編號，則可采用( )遍歷實現(xiàn)二叉樹的結點編號。A. 先序B. 中序C. 后序D. 層次序45. 如果T2是由有序樹T轉換成的二叉樹，那么T中結點的先根遍歷順序對應T2中結點的( )遍歷順序。A. 前序B. 中序C. 后序D. 層次序46. 如果T

20、2是由有序樹T轉換成的二叉樹，那么T中結點的后根遍歷順序對應T2中結點的( )遍歷順序。A. 前序B. 中序C. 后序D. 層次序47. 用n個權值構造出來的Huffman樹共有( )個結點。A. B. C. D. 48. 由權值為8,4,5,7的4個葉結點構造一顆Huffman樹，該樹的帶權路徑長度為( )。A. 24B. 36C. 48D. 72二、簡答題49. 設二叉樹根結點所在層次為1，樹的深度d為距離根最遠的葉結點所在的層次，試回答以下問題：(1) 試精確給出深度為d的完全二叉樹的不同二叉樹的棵數(shù)；(2) 試精確給出深度為d的滿二叉樹的不同二叉樹棵數(shù)。50. 如果一棵樹有個度為1的結

21、點，有個度為2的結點，有個度為m的結點，試問有多少個度為0的結點？51. 已知一棵二叉樹的前序遍歷序列為ABECDFGHIJ，中序遍歷序列為EBCDAFHIGJ。(1)畫出這棵二叉樹；(2)給出這棵二叉樹后序遍歷序列；(3)畫出這棵二叉樹轉換成對應的樹(或森林)。52. 假定用于通信的電文僅有8個字母A,B,C,D,E,F,G,H組成，各字母在電文中出現(xiàn)的頻率分別為5,25,3,6,10,11,36,4。試為這8 個字母設計不等長Huffman編碼，并給出該電文的總碼數(shù)。三、算法設計53. 設二叉樹的存儲結構為二叉鏈表，編寫一個遞歸算法，統(tǒng)計二叉樹中度為1的結點個數(shù)。54. 設二叉樹的存儲結構

22、為二叉鏈表，編寫一個遞歸算法，統(tǒng)計二叉樹中度為2的結點個數(shù)。55. 設樹T以孩子-兄弟鏈表作為其存儲表示，編寫一個算法統(tǒng)計樹T的葉結點個數(shù)。56. 設樹T以孩子-兄弟鏈表作為其存儲表示，編寫一個算法計算樹T的高度。第七章作業(yè)一、選擇題 1. 具有n個頂點且每一對不同頂點間都有一條邊的無向圖被稱為( )。A. 完全無向圖B. 無向連通圖C. 無向強連通圖D. 無向樹圖2. 一個有n個頂點的無向圖中邊數(shù)最多有( )條。A. B. C. D. 3. 對于具有個頂點的強連通圖，其有向邊條數(shù)至少是( )A. B. C. D. 4. 設G是一個非連通無向圖，有15條邊，則該圖的頂點數(shù)至少有( )個。A.

23、5B. 6C. 7D. 85. 在一個具有n個頂點的有向圖中，若所有頂點的岀度之和為s，則所有頂點的入度之和為( )。A. sB.s-1C. s+1D. n6. 一個有n個頂點和n條邊的無向圖一定是( )。A. 重連通圖B. 不連通圖C. 無環(huán)的D. 有環(huán)的7. 無向圖的鄰接矩陣是一個( )。A. 對稱矩陣B. 零矩陣C. 上三角矩陣D. 對角矩陣8. 有n個頂點和e條邊的無向圖采用鄰接矩陣存儲，零元素的個數(shù)為( )。A. B. C. D. 9. 帶權有向圖G用鄰接矩陣A存儲，則頂點i的入度等于A中( )。A. 第i行非的元素之和B. 第i列非的元素之和C. 第i行非且非0的元素個數(shù)D. 第i

24、列非且非0的元素個數(shù)10. 設圖有n個頂點和e條邊，采用鄰接矩陣時，遍歷圖的頂點所需時間為( )。A. B. C. D. 11. 設圖有n個頂點和e條邊，采用鄰接表時，遍歷圖的頂點所需時間為( )。A. B. C. D. 12. 圖的深度優(yōu)先搜索類似于樹的( )次序遍歷。A. 先根B. 中根C. 后根D. 層13. 圖的廣度優(yōu)先搜索類似于樹的( )次序遍歷。A. 先根B. 中根C. 后根D. 層14. 采用鄰接表存儲的圖的深度優(yōu)先搜索算法類似于二叉樹的( )。A. 中序遍歷B. 前序遍歷C. 后序遍歷D. 層次遍歷15. 采用鄰接表存儲的圖的廣度優(yōu)先搜索算法類似于二叉樹的( )。A. 中序遍歷

25、B. 前序遍歷C. 后序遍歷D. 層次遍歷16. 如果從無向圖的任一頂點出發(fā)進行一次深度優(yōu)先搜索即可訪問所有頂點，則該圖一定是( )。A. 強連通圖B. 連通圖C. 有回路D. 一棵樹17. 如果一個連通網(wǎng)絡G中各邊權值互不相同，權重最小的邊一定包含在G的( )生成樹中。A. 最小B. 任何C. 廣度優(yōu)先D. 深度優(yōu)先18. 任何一個連通圖的最小生成樹( )。A. 只有一棵B. 有一棵或多棵C. 一定有多棵D. 可能不存在19. 一個有n個頂點和e條邊的連通圖的生成樹有( )條邊。A. B. C. D. 20. 設一個n個頂點的帶權連通圖有條邊，則應該選通( )算法來求這個圖的最小生成樹，從而

26、使計算時間較少。A. PrimB. KruskalC. DFSD. BFS21. 求最短路徑的Dijkstra算法的時間復雜度為( )。A. B. C. D. 22. 求最短路徑的Floyd算法的時間復雜度為( )。A. B. C. D. 23. 設有向圖具有n個頂點和e條邊，如果用鄰接表作為它的存儲結構，則拓撲排序的時間復雜度為( )。A. B. C. D. 24. 設有向圖具有n個頂點和e條邊，如果用鄰接矩陣作為它的存儲結構，則拓撲排序的時間復雜度為( )。A. B. C. D. 二、應用題25. 針對圖1所示的有向圖，畫出該圖的鄰接矩陣、鄰接表和逆鄰接表。 圖1圖226. 對圖2所示的無

27、向圖，從頂點a開始進行深度優(yōu)先遍歷，給出2個可得到的頂點訪問序列；從頂點a開始進行廣度優(yōu)先遍歷，給出2個可得到的頂點訪問序列。27. 已知一個帶權連通圖如圖3所示，分別使用Prim算法和Kruskal算法求其最小生成樹。圖3圖428. 已知一個帶權有向圖如圖4所示，用Dijkstra算法求從頂點a到其余各頂點的最短路徑及路徑長度。29. 如圖所示的AOE網(wǎng)，求(1) 完成此工程最少要多少天(設弧上的權值為天數(shù))；(2) 每項活動的最早開始時間和最遲開始時間；(3) 哪些是關鍵活動；(4) 是否存在某些活動，當其提高速度后能使整個工程縮短工期?圖5第九章作業(yè)一、選擇題 30. 順序查找算法適用于

28、( )。A. 線性表B. 查找樹C. 查找網(wǎng)D. 連通圖31. 順序查找法適用于線性表的( )。A.散列存儲B.壓縮存儲C. 索引存儲D. 順序或鏈接存儲32. 采用順序查找方式查找長度為n的順序表時，平均查找長度為( )A. B. C. D. 33. 如果有5個關鍵嗎a,b,c,d,e放在順序表中，他們的查找概率分別為0.35,0.25,0.20,.015,0.05，可使平均查找長度達到最小的存放方式是( )。A. d,a,b,c,eB. e,d,c,b,aC. a,b,c,d,eD. a,c,e,d,b34. 對于長度為n的有序單鏈表，若查找每個元素的概率相等，則順序查找表中任一元素的查找

29、成功的平均查找長度為( )A. B. C. D. 35. 對線性表進行折半查找時，要求線性表必須( )A. 以順序方式存儲B. 以鏈接方式存儲C. 以順序方式存儲，且結點按關鍵嗎有序排列D. 以鏈接方式存儲，且結點按關鍵嗎有序排列36. 采用折半查找法查找長度為n的有序順序表時，平均查找長度為( )A. B. C. D. 37. 對于長度為18的有序順序表，若采用折半查找，則查找第15個元素的查找次數(shù)為( )。A. 3B. 4C. 5D. 638. 已知有序順序表(13,18,24,35,47,50,62,83,90,115,134)，若采用折半查找法查找值為18的元素時，查找成功的數(shù)據(jù)比較次

30、數(shù)為( )。A. 1B. 2C. 3D. 439. 使用散列法時確定元素存儲地址的依據(jù)是( )。A. 元素的序號B. 元素個數(shù)C. 關鍵嗎D. 非碼屬性40. 設一個散列表中有n個元素，用散列法進行查找的平均查找長度是( )。A. B. C. D. 41. 使用散列函數(shù)將元素的關鍵嗎映射為散列地址時，常會發(fā)生沖突。此時的沖突是指( )。A. 兩個元素具有相同的序號B. 兩個元素的關鍵碼不同，而非關鍵碼相同C. 不同關鍵碼對應到相同的存儲地址D. 裝載因子過大，數(shù)據(jù)元素過多42. 計算出的地址分布最均勻的散列函數(shù)是( )。A. 數(shù)值分析法B. 除留余數(shù)法C. 平方取中法D. 折疊法43. 將10

31、個元素散列到大小為100000個元素的散列表中，( )產(chǎn)生沖突。A. 一定會B. 一定不會C. 仍可能會D. 以上都不對44. 采用線性探測法解決沖突時計算出的一系列“下一個空位”( )。A. 必須大于等于原散列地址B. 必須小于等于原散列地址C. 可以大于或小于但不等于原散列地址D. 對地址在何處沒有限制45. 包含有4個結點的元素值互不相同的二叉查找樹有( )棵。A. 4B. 6C. 10D. 1446. 利用逐個數(shù)據(jù)插入的方法建立序列35,45,25,55,50,10,15,30,40,20對應的二叉查找樹后，查找元素20需要進行( )次元素之間的比較。A. 4B. 5C. 7D. 10

32、47. 一顆高度為h的AVL樹，若其每個非葉子結點的平衡因子都是0，則該樹共有( )個結點。A. B. C. D. 48. 高度為7的AVL樹最少有( )個結點。A. 12B. 21C. 33D. 5449. 高度為7的AVL樹最多有( )個結點。A. 63B. 64C. 65D. 127二、應用題50. 設有一個關鍵碼的輸入序列55,31,11,37,46,73,63，從空樹開始構造AVL樹，畫出每加入一個新結點時二叉樹的形態(tài)。若發(fā)生不平衡，指明需做的平衡旋轉的類型及平衡旋轉的結果。51. 分別畫出在圖1所示的AVL樹中插入15、36后樹的變化。如果有平衡化旋轉，注明相關結點平衡因子的變化(

33、注意，15和36是各自獨立插入到圖1所示的AVL樹中)。圖152. 已知含12個關鍵字的有序表及其相應的權值如下表，試按次優(yōu)查找樹的構造算法，畫出由這12個關鍵字構造所得的次優(yōu)查找樹，并計算它的PH值。關鍵字ABCDEFGHIJKL權值82349326711453. 對于23題有序表及其相應的權值，試按次優(yōu)查找樹的構造算法并加適當調整，畫出由這12個關鍵字構造所得的次優(yōu)查找樹，并計算它的PH值。通過適當調整后得到的次優(yōu)查找樹是否更優(yōu)？54. 設哈希表HT15，哈希函數(shù)為。用開放地址法解決沖突，對下列關鍵碼序列12,23,45,57,20,03,78,31,15,36造表。采用線性探測法尋找下一

34、個空位，畫出相應的哈希表，并計算等概率下查找成功的平均查找長度和查找不成功的平均查找長度。55. 設哈希表HT15，哈希函數(shù)為。用開放地址法解決沖突，對下列關鍵碼序列12,23,45,57,20,03,78,31,15,36造表。采用再哈希法尋找下一個空位，再哈希函數(shù)為，尋找下一個空位置的公式為，。畫出相應的哈希表，并計算等概率下查找成功的平均查找長度。第十章作業(yè)一、選擇題 56. 排序算法的穩(wěn)定性是指( )。A. 經(jīng)過排序后，能使值相同的數(shù)據(jù)保持原順序中的相對位置不變B. 經(jīng)過排序后，能使值相同的數(shù)據(jù)保持原順序中的絕對位置不變C. 經(jīng)過排序后，數(shù)據(jù)序列的存放數(shù)組的結構保持不變D. 經(jīng)過排序后，數(shù)據(jù)序列的存放數(shù)組的結構隨之變化57. 若要求在最壞情況下也能盡快地對序列進行穩(wěn)定的排序，則應選( )。A.起泡排序B.快速排序C. 歸并排序D. 堆排序58. 每次從未排序的序列中取出一個元素與已排序的序列中的元素依次進行比較，然后把它插入到已排序序列中的適當位置，此種排序方法叫做( )A. 起泡排序B. 直接插入排序C. 簡單選擇排序D. 二路歸并排序59. 對5個不同數(shù)據(jù)元素做直接插入排序，其數(shù)據(jù)比較次數(shù)最多是( )。A. 8B. 10C. 15D. 2560. 直接插入排序在最好情