1、數據庫系統工程師-數據結構與算法(二)(總分：59.95，做題時間：90分鐘)一、B選擇題/B(總題數：13,分數：60.00)1二叉樹的前序、中序和后序遍歷法最適合采用U (1) /U來實現。查找樹中，由根結點到所有其他結點的路徑長度的總和稱為U/U,而使上述路徑長度總和達到最小的樹稱為U (3) /U。它一定是U/U。在關于樹的幾個敘述中，只有U (5) /U 是正確的。(分數：5.00 )(1) .(1)(分數：1.00 )A. 遞歸程序VB. 迭代程序C. 隊列操作D. 棧操作解析：.(2)(分數：1.00 )A. 路徑和B. 內部路徑長度VC. 總深度D. 深度和解析：.(3)(分數

2、：1.00 )A. B-樹B. B+樹C. 豐滿樹 VD. 穿線樹解析：.(4)(分數：1.00 )A. B-樹B. 平衡樹 VC. 非平衡樹D. 穿線樹解析：(5).(5)(分數：1.00 )A. 用指針方式存儲有n個結點的二叉樹，至少要有 n+1個指針B. m階B-樹中，每個非葉子結點的后繼個數m/2C. m階B-樹中，具有k個后繼的結點，必含有 k-1個鍵值 VD. 平衡樹一定是豐滿樹解析：2棵查找二叉樹，其結點A、B C、D E、F依次存放在一個起始地址為n(假 定地址以字節為單位順序編號)的連續區域中，每個結點占4個字節：前二個字 節存放結點值，后二個字節依次放左指針、右指針。若該查

3、找二叉樹的根結點為 E,則它的一種可能的前序遍歷為(1)，相應的層次遍歷為 。在以上兩種遍歷情況下，結點C的左指針Lc的存放地址為，Lc的內容為。結點A的右指針Ra的內容為。(分數：5.00 )(1).(1)(分數:1.00 )A. EAFCBDB. EFACDBC. EABCFDD. EACBDF V解析：.(2)(分數:1.00 )A. EAFCBD VB. EFACDBC. EABCFDD. EACBDF解析：.(3)(分數:1.00 )A. n+9B. n+10 VC. n+12D. n+13解析：.(4)(分數:1.00 )A. n+4VB. n+8C. n+12D. n+16解析：

4、(5).(5)(分數:1.00 )A. n+4B. n+8VC. n+12D. n+16解析：3 對于給定的一組關鍵字(12,2,16,30,8,28,4,10,20,6,18) ，按照下列算法進 行遞增排序，寫出每種算法第一趟排序后得到的結果：希爾排序(增量為5)得到(1)，快速排序(選第一個記錄為基準元素)得到，基數(基數為10)排序得 到，二路歸并排序得到，堆排序得到。(分數：5.00 )(1).(1)(分數：1.00 )A. 2,4,6,8,10,12,16,18,20,28,30B. 6,2,10,4,8,12,28,30,20,16,18C. 12,2,10,20,6,18,4,1

5、6,30,8,28VD. 30,10,20,12,2,4,16,6,8,28,18解析：.(2)(分數：1.00 )A. 10,6,18,8,4,2,12,20,16,30,28B. 6,2,10,4,8,12,28,30,20,16,18VC. 2,4,6,8，10，12，16，18,20,28,30D. 6,10,8,28,20,18,2,4,12,30,16解析：(3) .(3) (分數： 1.00 )A. 10,6,18,8,4,2,12,20,16,30,28B. 1,12,10,20,6,18,4,16,30,8,28C. 2,4,6,8,10,12,16,18,20,28,30D

6、. 30,10,20,12,2,4,16,6,8,28,18V解析：(4) .(4) (分數： 1.00)A. 2,12,16,8,28,30,4,6,10,18,20B. 2,12,16,30,8,28,4,10,6,20,18VC. 12,2,16,8,28,30,4,6,10,28,18D. 12,2,10,20,6,18,4,16,30,8,28解析：(5) .(5) (分數： 1.00)A. 30,28,20,12,18,16,4,10,2,6,8B. 20,30,28,12,18,4,16,10,2,8,6C. 2,6,4,10,8,28,16,30,20,12,18VD. 2,4

7、,10,6,12,28,16,20,8,30,18解析：4在所有排序方法中， 關鍵字比較的次數與記錄的初始排列次序無關的是 U (1) /U 。從未排序序列中依次取出元素與已排序序列 (初始時為空 )中的元素進行比較，將 其放入已排序序列的正確位置上的方法，稱為 U (2) /U 。設有 1000個 無序的元素，希望用最快的速度挑選出其中前 10個最大的元素，最好選用 U (3) /U 排序法。(分數： 3.00 )(1) .(1) (分數： 1.00)A. 希爾排序B. 起泡排序C. 插入排序D. 選擇排序 V解析：(2) .(2) (分數： 1.00)A. 希爾排序B. 起泡排序C. 插入

8、排序 VD. 選擇排序解析：(3) .(3) (分數： 1.00)A. 起泡排序B. 快速排序C. 堆排序 VD. 基數排序解析：用某種排序方法對線性表 (25,84,21,47,15,27,68,35,20) 進行排序時，元素序列 的變化情況如下。25,84,21,47,15,27,68,35,2020,15,21,25,47,27,68,35,845,20,21,25,35,27,47,68,8415,20,21,25,27,35,47,68,84則所采用的排序方法是 U (1) /U 。不穩定的排序是 U (2) /U 。外排序是指U (3) /U。(分數:3.00 )(1).(1)(分

9、數:1.00 )A. 選擇排序B. 希爾排序C. 歸并排序D. 快速排序 V 解析：.(2)(分數:1.00)A. 直接插入排序B. 冒泡排序C. Shell 排序 VD. 歸并排序 解析：.(3)(分數：1.00 )A. 用機器指令直接對硬盤中需排序數據排序B. 把需排序數據，用其他大容量機器排序C. 把外存中需排序數據一次性調入內存，排好序后再存儲到外存D. 對外存中大于內存允許空間的待排序的數據，通過多次內外間的交換實現排序V解析：6 在內部排序中，通常要對被排序數據進行多次掃描。各種排序方法有不同的 排序實施過程和時間復雜性。對給定的整數數列(541,132,984,746,518,1

10、81,946,314,205,827)進行從小到大的排序時， 采用冒泡排序和簡單選擇排序時，若先選出大元素，則第一次掃描結果分別是_(!)_，采用快速排序(以中間元素518為基準)的第一次掃描結果是_(2_ o設被排序的序列有n個元素，冒泡排序和簡單選擇排序的時間復雜度是;快速排序的時間復雜度是o(分數：4.00 )和(541,132,827,746,518,181,946,314,205,984)和(541,132,827,746,518,181,946,314,205,984)V和(132,541,746,518,181,946,314,205,827,984)和(132,541,746,

11、518,181,946,314,205,827,984)(1).(1)(分數：1.00 )A. (181,132,314,205,541,518,946,827,746,984)B. (132,541,746,518,181,946,314,205,827,984)C. (205,132,314,181,518,746,946,984,541,827)D. (541,132,984,746,827,181,946,314,205,518) 解析：.(2)(分數：1.00 )A. (181,132,314,205,541,518,946,827,746,984)B. (541,132,827,7

12、46,518,181,946,314,205,984)C. (205,132,314,181,518,746,946,984,541,827)D. (541,132,984,746,827,181,946,314,205,518) 解析：.(3)(分數：1.00 )A. O(nlog 2B. O(C. log 2nD. O(n2)V解析：.(4)(分數：1.00 )A. O(nlog 2 VB. O(n 2log 2)C. O(logD. O(n2)解析:7.給定結點的關鍵字序列(F,B,J,G,E,A,I,D,C,H),對它按字母的字典順序進行 排列，采用不同方法，其最終結果相同，但中間結果

13、是不同的。Shell排序的第一趟掃描(步長為5)結果應為U (1) /U。冒泡排序(大數下沉)的第一趟冒泡的效果是U (2) /U。快速排序的第一次掃描結果是U (3) /U。二路歸并排序的第一趟結果是U (4) /U。若以層次序列來建立對應的完全二叉樹后，采用篩選法建堆，其第一趟建的堆是 U (5) /U。(分數：5.00)(1).(1)(分數：1.00)A. (B, F, G, J, A, D, I, E, H,B. (B, F, G, J, A, E, D, I, C,C. (A, B, D, C, E, F, I, J, G,D. (C, B, D, A, E, F, I, G, J,

14、 解析：.(2)(分數：1.00 )A. (A, B, D, C, F, E, I, J, H,B. (A, B, D, C, E, F, I, H, G,C. (B, F, G, E, A, I, D, C, H,VD. (B, F, G, J, A, E, D, I, C, 解析：.(3)(分數：1.00 )A. (C, B, D, A, F, E, I, J, G,B. (C, B, D, A, E, F, I, G, J,VC. (B, A, D, E, F, G, I, J, H,D. (B, C, D, A, E, F, I, J, G, 解析：.(4)(分數：1.00 )A. (

15、B, F, G, J, A, E, D, I, C,VB. (B, A, D, E, F, G, I, J, H,C. (A, B, D, C, E, F, I, J, G,D. (A, B, D, C, F, E, J, I, H,解析:(5).(5)A.B. VC.D.解析：8二叉樹(1)。在完全二叉樹中，若一個結點沒有 ，則它必定是葉結點。 每棵樹都能唯一地轉換成與它對應的二叉樹。由樹轉換成的二叉樹里，一個結點N的左子樹是N在原樹里對應結點的 ，而N的右子樹是它在原樹里對應結 點的。二叉排序樹的平均檢索長度為 。(分數：5.00 )(1).(1)(分數：1.00)A. 是特殊的樹B. 不

16、是樹的特殊形式VC. 是兩棵樹的總稱D. 是只有兩個根結點的樹狀結構解析：.(2)(分數：1.00 )A. 左子樹 VB. 右子樹C. 左子樹或沒有右子樹D. 兄弟解析：.(3)(分數：1.00 )A. 最左子樹VB. 最右子樹C. 最鄰近的右兄弟D. 最鄰近的左兄弟解析：.(4)(分數：1.00 )A. 最左子樹B. 最右子樹C. 最鄰近的右兄弟VD. 最鄰近的左兄弟解析：(5).(5)(分數：1.00 )A. O(n 2)B. O(C. O(log 2 VD. O(nlog 2解析：9 哈希存儲的基本思想是根據!1)_來決定，沖突(碰撞)指的是J3L, 越大，發生沖突的可能性也越大。處理沖

17、突的兩種主要方法是。(分數：5.00 )(1).(1)(分數：1.00 )A. 存儲地址B. 元素的序號C. 元素個數D. 關鍵碼值 V解析：.(2)(分數：1.00 )A. 存儲地址 VB. 元素的序號C. 元素個數D. 關鍵碼值解析：.(3)(分數：1.00 )A. 兩個元素具有相同序號B. 兩個元素的關鍵碼值不同，而非碼屬性相同C. 不同關鍵碼值對應到相同的存儲地址VD. 數據元素過多解析：(4) .(4) (分數： 1.00 )A. 非碼屬性B. 平均檢索長度C. 負載因子 VD. 哈希表空間解析：(5) .(5) (分數： 1.00 )A. 線性探查法和雙散列函數法B. 建溢出區法和

18、不建溢出區法C. 除余法和折疊法D. 拉鏈法和開放地址法V解析：10.設二維數組F的行下標為15,列下標為08, F的每個數據元素均占4 個字節。在按行存儲的情況下，已知數據元素 F2， 2 的第一個字節的地址是 1044,則F3,4和F4,3的第一個字節的地址分別為U/U和U (2) /U ，而數組的第一個數據元素的第一個字節和數組最后一個元素的最后 一個字節的地址分別為U (3) /U 和U (4) /U。對一般的二維數組G而言，當U (5) /U 時，其按行存儲的Gi , j的地 址與按列存儲的 Gj ，i 的地址相同。(分數： 5.00 )(1) .(1) (分數： 1.00 )A.

19、1088 VB. 1084C. 1092D. 1120解析：(2) .(2) (分數： 1.00 )A. 1092B. 1088C. 1120 VD. 1124解析：(3) .(3) (分數： 1.00 )A. 1004B. 1044C. 1000 VD. 984解析：(4) .(4) (分數： 1.00 )A. 1183B. 1179 VC. 1164D. 1187解析：(5) .(5) (分數： 1.00 )A. G 的列數與行數相同B. G的列的上界與G的行的上界相同C. G的列的上界與G的行的下界相同D. G的列的上下界與G的行的上下界相同V解析:11 某順序存儲的表格，其中有9000

20、0個元素，已按關鍵字遞增有序排列，現假 定對各個元素進行查找的概率是相同的，并且各個元素的關鍵字皆不相同。用順序查找法查找時，平均比較次數約為U (1) /U ，最大比較次數為 U (2) /U?，F把90000個元素按排列順序劃分成若干組，使每組有g個元素(最后一組可能不足g個)。查找時，先從第一組開始，通過比較各組的最后一個元素的關鍵字， 找到欲查找的元素所在的組，然后再用順序查找法找到欲查找的元素。在這種查 找法中，使總的平均比較次數最小的g是U (3) /U，此時的平均比較次數是U/U 。當g的值大于等于90000時，此方法的查找速度接近 于U (5) /U。(分數：5.00)(1).(

21、1)(分數：1.00)A. 25000B. 30000C. 45000 VD. 90000解析：.(2)(分數：1.00 )A. 25000B. 30000C. 45000D. 90000 V解析：.(3)(分數：1.00 )A. 100B. 200C. 300 VD. 400解析：.(4)(分數：1.00 )A. 100B. 200C. 300 VD. 400解析：(5).(5)(分數：1.00 )A. 快速分類法B. 斐波那契查找法C. 二分法D. 順序查找法V解析：已知無向圖的鄰接表如圖2-35所示此圖從F開始的深度優先遍歷為此鄰接表對應的無向圖為U (1) /UU (2) /U 。從F

22、開始的廣度優先遍歷為U (3) /U 。從F開始的 深度優先生成樹為U (4) /U 。從F開始的廣度優先生成樹為U (5) /U。(分數:(1).(1)(分數：5.00 )1.00 )A.B.C. V解析：.(2)(分數：1.00 )A. FGILJMKHB. FGILJKHM VC. FGILJKMHD. FGHMILJK解析：.(3)(分數：1.00 )A. FGILJKMHB. FGHMILJK VC. FGHILJKMD. FGHMKILJ(分數:.解析:1.00 )A. VB.C.1.00 )解析：(5).(5)A.B. VC.解析:13圖2-36是帶權的有向圖G的鄰接表。以結點V出發深度遍歷圖G所得的結 點序列為U (1) /U;廣度遍歷圖G所得的結點序列為U (2) /U;G的一種拓撲序列是U (3) /U;從結點V到V8結點的最短路徑是U/U;從結點V1到V8結點的關鍵路徑