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

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

3、性D. 正確性、可讀性和有效性若一個問題既可以用迭代方法也可以用遞歸方法求解，則( ) 的方法具有更高的時空效率。A. 迭代B.遞歸C. 先遞歸后迭代D.先迭代后遞歸一個遞歸算法必須包括 (A. 遞歸部分B.終止條件和遞歸部分C. 迭代部分D.終止條件和迭代部算法的時間復雜度與有關。A. 問題規模B.源程序長度C. 計算機硬件運行速度D.編譯后執行程序的5壬曰.質量 指出下列各算法的功能并求出其時間復雜度。Prime( int n)元素int i=2,x=( int )sqrt(n);D. 數據字段數據項B.數據記錄 C. 數 據順序表是線性表的( ) 存儲表示。A. 有序B. 連續C. 數組

4、D.順序存取若長度為n 的非空線性表采用順序存儲結構，在表中的第個位置插入一個數據元素， i 的合法值應該是A. 1 iB. 1 i n 1C. 0 i nD. 0 i n若設一個順序表的長度為n那么，在表中順序查找一個值為查找成功的數據平均比較次數為 ( )x 的元素時，在等概率的情況下，A. nB. n/ 2C. (n 1)/2D.(n 1)/2在長度為 n 的順序表的表尾插入一個新的元素的時間復雜度為數據結構反映了數據元素之間的結構關系。單鏈表是一種A. 順序存儲線性表 B. 非順序存儲非線性表 C. 順序存儲非線性表D.非順序存儲線性表6. 單鏈表又稱為線性鏈表，在單鏈表上實施插入和刪

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

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

7、 SXSSXSXX假設一個棧的輸入序列是 1，2，A. 1,2,3,4B. 4,1,2,3已知一個棧的進棧序列為A. j iB.已知一個棧的進棧序列為A. iB.已知一個棧的進棧序列為A. 一定是 2B.已知一個棧的進棧序列為A. 一定是 21,2,3,ni1,2,3,ni1,2,3,*曰定是3，4，,n ，,n，,n，p1, p2,p3,B. 可能是 2已知一個棧的進棧序列為p1,p2,p3,已知一個棧的進棧序列為p1,p2,p3,則不可能得到的輸出序列是C. 4,3,2,1其輸出序列的第一個元素是C. ji1D. 1,3,4,2其輸出序列是p1, p2,p3,i，, pn則第 j 個出棧元

8、素是 ( ) 。D.不確定C. ni1其輸出序列是p1, p2,p3,C. 可能是 1,pn,pn,pn，其輸出序列是C. 不可能是，其輸出序列是，其輸出序列是, pn1,2,3,1,2,3,1,2,3,。若 p1n ，則pi 的值是D.不確定。若 p13，則p2 的值是D.可能是 2,n 。若 p3 1，則D.*曰 O定是 3p1的值是,n 。若 p33，則宀曰 d定是 1,n 。若 pn 1，則p1的值是p1的值是A. 一定是 2B. 可能是 2C. 不可能是1D.7A. n i 1B. n iC. iD. 不確定259. 設棧S和隊列Q的初始狀態均為空， 元素1,2,3,4,5,6,7,

9、依次進入S。如果每個元素出棧后立即進入隊列Q,且7個元素的出隊順序為2,4,3,6,5,1,7 ，則棧S的容量至少是()A. 1B. 2C. 3D. 410. 對中綴表達式 3 2*(4 2*2 6*3) 5求值， 在求值過程中掃描到 6時，操作數棧和操作符棧的內 容分別是 ( )A. 3,2,4,2,2 和+,*,(,+,*B. 3,2,4,4和+,*,(,+C. 3,2,8 和+,*,( D.3,2,8,6 和+,*,(,-二、算法設計題1. 詳見數據結構題集 (C 語言版 ) 第 25 頁。2. 詳見數據結構題集(C語言版)第25頁。第四章作業11. 串是一種特殊的線性表，其特殊性體現在

10、 （ ）A. 可以順序存儲 B. 數據元素是一個字符 C. 可以鏈式存儲 D. 數據元素可以是多個 字符12. 設有兩個串T和P,求P在T中首次出現的位置的運算叫做（）。A. 求子串B. 模式匹配C. 串替換D. 串連接13. 下面關于串的敘述中，哪一個是不正確的（）A.串是字符的有限序列B.空串是由空格構成的串C.模式匹配是串的一種重要運算D.串既可以采用順序存儲，也可以采用鏈式存儲14. 串的長度是指（）A.串中所含不同字母的個數B.串中所含字符的個數C.串中所含不同字符的個數D.串中所含非空格字符的個數15. 兩個串相等的充分必要條件是（）A.串中所含的字符相同B.串中所含字符的個數相同

11、，且對應位置上的字符也相同C.串中所含的字符個數相同D.串中對應位置上的字符相同6. 已知 p=” abcaabbabcabaacbacb ”，求出 next 函數值。第五章作業、選擇題19.20.21.A. 80B. 100C. 240一個二維數組 A1020 按行存放于一個連續的存儲空間中， 組元素占 1 個存儲字，則 A62 的地址為 ( )A. 226B. 322C. 341一個二維數組 A1020 按列存放于一個連續的存儲空間中， 組元素占 1 個存儲字，則 A62 的地址為 (A. 226B. 322C. 341D. 270A00A00的存儲地址是 200，每個數D. 342的存儲

12、地址是 200，每個數D. 342在二維數組 這種情況下，A910 中，每個數組元素占用 元素 A85 的起始地址為 ( )3 個存儲單元，從首地址SA開始按行連續存放，在A. SA+141B. SA+144C. SA+222D. SA+25522.將一個么第 i的對稱矩陣A的下三角部分按存放在一個一維數組B中,行的對角元素 Ai i在B中的存放位置是()nnA00存放在B0 中，那23.A. (i3)i/2B. (i 1)i/2C. (2n i 1)i/2D.(2n i1)i/2將一個么第 in n 的對稱矩陣 A 的上三角部分按存放在一個一維數組 B 中，行的對角元素 Ai i 在B中的存

13、放位置是()A00存放在B0 中，那A. (i3)i/2B. (i 1)i/2C. (2n i 1)i/2D.(2n i1)i/2A. 順序存取B.直接存取C. 散列存取D.索引存取17. 多維數組實際上是由( )實現的。A. 一維數組B.多項式C. 三元組表D.簡單變量18. 在二維數組 A810中，每一個數組元素Aij 占用 3 個存儲空間，所有數組元素相繼存放于16. 數組通常具有的操作是 ( )一個連續的存儲空間中，則存放該數組至少需要的存儲空間是o( )24. 設A是一個n n的對稱矩陣，將 A的對角線及對角線上方的元素以列優先(以列為主序)的方式存放在一維數組Bn(n 1)/2中，

14、則矩陣中任一元素 aj(0 i, j n,i j)在B中的存放位置是()A. j(j 1)/2 iB. j( j 1)/2 i 1C. i(i 1)/2 jD. i(i 1)/2 j 125. 設n階三對角矩陣A的三條對角線上的元素被按行壓縮存儲到一維數組若某矩陣元素在B中存放的位置在k,那么該元素在原始矩陣中的行號B中，A00存放于 B0。A. (k 1)/3B. k/3C. (k 1)/3D. (k 1)/3、簡答題26. 設有一個 3 維數組 A10 2015 ，按行優先存放于一個連續的存儲空間中， 每個數組元素占 4個 存儲字，首元素 A000的存儲地址是1000，則A789存放于什么

15、地方。27. 設有一個二維數組 Am n ，假設 A00 存放位置在 644(10)， A22 存放在 676(10) ，每個元 素占 1 個存儲單元，問 A3 3 (10) 存放在什么位置腳注 (10)表示用十進制表示。28. 對于一個n n矩陣A的任一元素aij，按行存儲和按列存儲時的地址之差是多少(假設兩種存儲的開始存儲地址 LOC (0,0)以及元素所占存儲單元數d相同)29. 設有n階三對角矩陣 A，將其 3條對角線上的元素逐行存儲到數組B0:3n 3中，使得Bk Aij，且 B0A00，求(1) 用 i ， j 表示 k 的下標變換公式。(2) 用 k 表示 i ， j 的下表變換

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

17、)A. n h m B. h m 2n C. m h 134. 一顆有 124 個葉結點的完全二叉樹最多有 ( ) 個結點。A. 247B. 248C. 24935. 一顆有 129 個葉結點的完全二叉樹最少有 ( ) 個結點。A. 254B. 255C. 25736. 設完全二叉樹的第 6層有 24 個葉結點，則此樹最多有 ( ) 個結點。A. 55B. 79C. 8137. 具有 1000 個結點的完全二叉樹的次底層的葉結點個數為 ( ) 。A. 11B. 12C. 24D. 2nD. n 2h 1D. 250D. 258D. 127D. 3638. 用順序存儲的方法將n個結點的完全二叉樹

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

19、中序遍歷序列中A. n 在 m 右方B. n是m的祖先C. n 在 m 左方D. n是m的子孫42. 設一顆二叉樹的前序序列為abdec,中序序列為dbeac,則該二叉樹的后序遍歷順序是()43.44.45.46.47.48.二、49.50.51.52.A. abdecB. debacC. debcaD. abedc設一顆二叉樹的中序序列為badce，后序序列為bdeca，則該二叉樹的前序遍歷順序是()A. adbecB. decabC. debacD. abcde對二叉樹的結點從 1 開始連續編號，要求每個結點的編號大于其左、右孩子的編號，同一結點的 左、右孩子中，其左孩子編號小于其右孩子編

20、號，則可采用 ( ) 遍歷實現二叉樹的結點編號。A. 先序B. 中序C. 后序D. 層次序如果T2是由有序樹T轉換成的二叉樹，那么 順序。T 中結點的先根遍歷順序對應T2中結點的()遍歷A. 前序B. 中序C. 后序D. 層次序如果T2是由有序樹T轉換成的二叉樹，那么 順序。T 中結點的后根遍歷順序對應T2中結點的()遍歷A. 前序B. 中序C. 后序D. 層次序用 n 個權值構造出來的 Huffman 樹共有 ( ) 個結點。A. 2n 1 B. 2nC. 2n 1D. n 1由權值為 8,4,5,7 的 4 個葉結點構造一顆Huffman 樹，該樹的帶權路徑長度為A. 24B. 36C.

21、48D. 72簡答題 設二叉樹根結點所在層次為 1，樹的深度 d 為距離根最遠的葉結點所在的層次，試回答以下問題：(1) 試精確給出深度為 d 的完全二叉樹的不同二叉樹的棵數； (2) 試精確給出深度為 d 的滿二叉 樹的不同二叉樹棵數。如果一棵樹有ni個度為1的結點，有門2個度為2的結點，有nm個度為m的結點，試問有 多少個度為 0 的結點 已知一棵二叉樹的前序遍歷序列為 ABECDFGH沖序遍歷序列為 EBCDAFHIGJ(I)畫出這棵二叉 樹；(2) 給出這棵二叉樹后序遍歷序列； (3) 畫出這棵二叉樹轉換成對應的樹 (或森林)。假定用于通信的電文僅有 8 個字母 A,B,C,D,E,F

22、,G,H 組成，各字母在電文中出現的頻率分別為 5,25,3,6,10,11,36,4 。試為這 8 個字母設計不等長 Huffman 編碼，并給出該電文的總碼數。算法設計53. 設二叉樹的存儲結構為二叉鏈表，編寫一個遞歸算法，統計二叉樹中度為1 的結點個數。54. 設二叉樹的存儲結構為二叉鏈表，編寫一個遞歸算法，統計二叉樹中度為2 的結點個數。55. 設樹T以孩子-兄弟鏈表作為其存儲表示，編寫一個算法統計樹T的葉結點個數。56. 設樹T以孩子-兄弟鏈表作為其存儲表示，編寫一個算法計算樹T的高度。1.2.3.4.5.6.7.8.9.10.11.第七章作業選擇題具有 n 個頂點且每一對不同頂點間

23、都有一條邊的無向圖被稱為A. 完全無向圖B. 無向連通圖C. 無向強連通圖D. 無向樹圖一個有 n 個頂點的無向圖中邊數最多有 ( ) 條。A. nB. n(n 1)C. n(n 1)/2D. 2n對于具有 n(n 1) 個頂點的強連通圖，其有向邊條數至少是 ( )A. n 1B. nC. n 1D. n 2設G是一個非連通無向圖，有 15條邊，則該圖的頂點數至少有個。A. 5B. 6C. 7D. 8在一個具有 n 個頂點的有向圖中，若所有頂點的岀度之和為s，則所有頂點的入度之和為 ( ) 。A. sC. s+1D. n一個有 n 個頂點和 n 條邊的無向圖一定是A. 重連通圖B. 不連通圖C

24、. 無環的D. 有環的無向圖的鄰接矩陣是一個 ( ) 。A. 對稱矩陣B. 零矩陣C. 上三角矩陣D. 對角矩陣有 n 個頂點和 e 條邊的無向圖采用鄰接矩陣存儲，零元素的個數為A. eB. 2eC. n2D. n2 2e帶權有向圖G用鄰接矩陣A存儲，則頂點i的入度等于A 中( ) 。A.第i行非R的元素之和B. 第 i列非g的元素之和C.第i行非g且非0 的元素個數D. 第 i列非g且非0 的元素個數設圖有 n 個頂點和e 條邊，采用鄰接矩陣時，遍歷圖的頂點所需時間為A. O(n)B. O(n2 )C. O(e)D. O(ne)設圖有 n 個頂點和e 條邊，采用鄰接表時，遍歷圖的頂點所需時間

25、為A. O(n e)B. O(n2)C. 0(e)D.0( ne)12.圖的深度優先搜索類似于樹的 （）次序遍歷。A.先根B.中根C.后根D.層13.圖的廣度優先搜索類似于樹的 （）次序遍歷。A.先根B.中根C.后根D.層14.采用鄰接表存儲的圖的深度優先搜索算法類似于二叉樹的()。A.中序遍歷B.前序遍歷C.后序遍歷D.層次遍歷15.采用鄰接表存儲的圖的廣度優先搜索算法類似于二叉樹的()。A.中序遍歷B.前序遍歷C.后序遍歷D.層次遍歷16.如果從無向圖的任一頂點出發進行一次深度優先搜索即可訪問所有頂點，則該圖一定是（）A.強連通圖B.連通圖C.有回路D.一棵樹17.如果一個連通網絡G中各邊

26、權值互不相同，權重最小的邊一定包含在G的（）生成樹中。A.最小B.任何C.廣度優先D.深度優先18.任何一個連通圖的最小生成樹（）。A.只有一棵B.有一棵或多棵C.定有多棵D.可能不存在19. 一個有n個頂點和e條邊的連通圖的生成樹有（）條邊。A. nB. eC. n 1D.n 120.設一個n個頂點的帶權連通圖有、n log 2n條邊，則應該選通（）算法來求這個圖的最小生成樹從而使計算時間較少。A. PrimB. KruskalC. DFSD. BFS21.求最短路徑的Dijkstra 算法的時間復雜度為()。A. O( n)B. O(n e)C.O(n2)D.O( ne)22.求最短路徑的

27、Floyd算法的時間復雜度為（）。A. O( n)B. O(ne)C.O(n2)D.0(n3)23. 設有向圖具有n個頂點和e條邊，如果用鄰接表作為它的存儲結構，則拓撲排序的時間復雜度為（）。A. 0(n)B. 0(n e)C. 0(n2)D. 0(ne)24. 設有向圖具有n個頂點和e條邊，如果用鄰接矩陣作為它的存儲結構，則拓撲排序的時間復雜度為()。2A. 0(nge)B. 0(n e)C. 0(n)D. 0(ne)二、應用題25. 針對圖1所示的有向圖，畫出該圖的鄰接矩陣、鄰接表和逆鄰接表。26. 對圖2所示的無向圖，從頂點a開始進行深度優先遍歷，給出2個可得到的頂點訪問序列；從頂點a開

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

29、序查找法適用于線性表的 ( ) 。A. 散列存儲B. 壓縮存儲C. 索引存儲D. 順序或鏈接存儲32.A. nB. n/2C. (n 1)/2D. (n 1)/233.如果有 5 個關鍵嗎 a,b,c,d,e 放在順序表中， 他們的查找概率分別為 長度達到最小的存放方式是 ( ) 。,.015, ，可使平均查找A. d,a,b,c,eB. e,d,c,b,aC. a,b,c,d,eD. a,c,e,d,b采用順序查找方式查找長度為 n 的順序表時，平均查找長度為 ( )34.35.A. n/4B. n/2C. (n 1)/2D. (n 1)/2對線性表進行折半查找時，要求線性表必須A. 以順序

30、方式存儲B. 以鏈接方式存儲C. 以順序方式存儲，且結點按關鍵嗎有序排列D. 以鏈接方式存儲，且結點按關鍵嗎有序排列對于長度為 n 的有序單鏈表，若查找每個元素的概率相等，則順序查找表中任一元素的查找成功 的平均查找長度為 ( )36.37.A. O(n)B. O(log 2 n)C. O(n2)D. O(nlogn)對于長度為 18 的有序順序表，若采用折半查找，則查找第15 個元素的查找次數為 ( ) 。A. 3B. 4C. 5D. 638.已知有序順序表 (13,18,24,35,47,50,62,83,90,115,134)時，查找成功的數據比較次數為，若采用折半查找法查找值為 18

31、的元素39.A. 1B. 2C. 3D. 4使用散列法時確定元素存儲地址的依據是采用折半查找法查找長度為 n 的有序順序表時，平均查找長度為 ( )A. 元素的序號B. 元素個數C. 關鍵嗎D. 非碼屬性設一個散列表中有n 個元素，用散列法進行查找的平均查找長度是( ) 。A. O(1)B. O(n)C. O(log2n)D. O(n2)40.41.42.43.44.45.46.47.48.49.二、50.使用散列函數將元素的關鍵嗎映射為散列地址時，常會發生沖突。此時的沖突是指 ( ) 。A. 兩個元素具有相同的序號B. 兩個元素的關鍵碼不同，而非關鍵碼相同C. 不同關鍵碼對應到相同的存儲地址

32、D. 裝載因子過大，數據元素過多計算出的地址分布最均勻的散列函數是 ( ) 。A. 數值分析法B. 除留余數法C. 平方取中法D. 折疊法將 10 個元素散列到大小為 100000 個元素的散列表中， ( ) 產生沖突。A. 一定會B. 一定不會C. 仍可能會D. 以上都不對采用線性探測法解決沖突時計算出的一系列“下一個空位” ( ) 。A. 必須大于等于原散列地址B. 必須小于等于原散列地址C. 可以大于或小于但不等于原散列地址D. 對地址在何處沒有限制包含有 4 個結點的元素值互不相同的二叉查找樹有 ( ) 棵。A. 4B. 6C. 10 D. 14查找利用逐個數據插入的方法建立序列 35

33、,45,25,55,50,10,15,30,40,20 對應的二叉查找樹后， 元素 20 需要進行 ( ) 次元素之間的比較。A. 4B. 5C. 7 D. 10一顆高度為A. 2h 1 1高度為7的AVL樹最少有()A. 12B. 21高度為7的AVL樹最多有()A. 63B. 64應用題h的AVL樹，若其每個非葉子結點的平衡因子都是B. 2h1C.2h 1 1個結點。C.33個結點。C.650，則該樹共有 ( ) 個結點。D. 2h 1D. 54D. 127設有一個關鍵碼的輸入序列55,31,11,37,46,73,63 ，從空樹開始構造 AVL樹，畫出每加入一個1所示的AVL樹中)。圖1

34、新結點時二叉樹的形態。若發生不平衡，指明需做的平衡旋轉的類型及平衡旋轉的結果。如果有平衡化旋轉，注明相關結點平衡51. 分別畫出在圖1所示的AVL樹中插入15、36后樹的變化。因子的變化(注意，15和36是各自獨立插入到圖52. 已知含12個關鍵字的有序表及其相應的權值如下表，試按次優查找樹的構造算法，畫出由這12個關鍵字構造所得的次優查找樹，并計算它的PH值。關鍵字ABCDEFGHIJKL權值82349326711453. 對于23題有序表及其相應的權值，試按次優查找樹的構造算法并加適當調整，畫出由這12個關鍵字構造所得的次優查找樹，并計算它的PH值。通過適當調整后得到的次優查找樹是否更優5

35、4. 設哈希表HT15，哈希函數為 H(key) key% 13。用開放地址法解決沖突，對下列關鍵碼序列12,23,45,57,20,03,78,31,15,36造表。采用線性探測法尋找下一個空位，畫出相應的哈希表，并計算等概率下查找成功的平均查找長度和查找不成功的平均查找長度。55. 設哈希表HT15，哈希函數為 H (key) key% 13。用開放地址法解決沖突，對下列關鍵碼序列12,23,45,57,20,03,78,31,15,36造表。采用再哈希法尋找下一個空位，再哈希函數為RH (key) (7key)%10 1，尋找下一個空位置的公式為H (H i !RH(key)%15，H。

36、 H (key)。畫出相應的哈希表，并計算等概率下查找成功的平均查找長度。63.29第十章作業、選擇題56. 排序算法的穩定性是指 ( ) 。A. 經過排序后，能使值相同的數據保持原順序中的相對位置不變B. 經過排序后，能使值相同的數據保持原順序中的絕對位置不變C. 經過排序后，數據序列的存放數組的結構保持不變D. 經過排序后，數據序列的存放數組的結構隨之變化57. 若要求在最壞情況下也能盡快地對序列進行穩定的排序，則應選 ( ) 。A. 起泡排序 B. 快速排序 C. 歸并排序 D. 堆排序58.每次從未排序的序列中取出一個元素與已排序的序列中的元素依次進行比較，然后把它插入到已排序序列中的適當位置，此種排序方法叫做 ( )A. 起泡排序B. 直接插入排序C. 簡單選擇排序D. 二路歸并排序59.60.A. 8B. 10C. 15D. 25直接插入排序在最好情況下的時間復雜度是 ( )A. O (log 2 n)B. O(n)C. O(n log2 n)D.O(n2)對 5 個不同數據元素做直接插入排序，其數