數(shù)據(jù)結(jié)構(gòu)》期終考試試卷（a）-清華大學-文庫吧
2024-12-22 06:19 本頁面
【正文】 次數(shù)為 )ihj( 2 j22j222j22)ih(22 1h 1j j1h1h 1j j1h1h 1j 1jh1h 1i 1i ??????????? ???? ????????? 代換 因為 2h1≤ n≤ 2h1，且 ????? ?1h1j jh 22jlim ，則 n42n22j22 1h1j j1h ?????? ???? 3 (5) 設(shè)有兩個分別有 n 個數(shù)據(jù)元素的有序表，現(xiàn)要對它們進行兩路歸并，生成一個有 2n 個數(shù)據(jù)元素的有序表。試問最大數(shù)據(jù)比較次數(shù)是多少？最少數(shù)據(jù)比較次數(shù)是多少？ (5) 兩個長度為 n 的有序表 ，當其中一個有序表的數(shù)據(jù)全部都小于另一個有序表的數(shù)據(jù)時， 關(guān)鍵碼的比較次數(shù)達到最?。?= n） 。 而當兩個有序表的數(shù)據(jù)交錯排列時 ， 關(guān)鍵碼的比較次數(shù)達到最大（ = 2n1） 。 二 、簡作題（每 小題 5 分，共 15 分） 針對如下的帶權(quán)無向圖 其中，每條邊上所注的 ei為該邊的編號，冒號后面是該邊所對應(yīng)的權(quán)值。 (1) 使用 Prim 算法，從頂點 A 出發(fā)求出上圖的最小生成樹。要求給出生成樹構(gòu)造過程中依次選擇出來的邊的序列（用邊的編號表示），權(quán)值相等時編號小的邊優(yōu)先。（不必畫圖） (2) 使用 Kruskal 算法求 出上圖的最小生成樹。要求給出生成樹構(gòu)造過程中依次選擇出來的邊的序列（用邊的編號表示），權(quán)值相等時編號小的邊優(yōu)先。（不必畫圖） (3) 上面求出的最小生成樹是唯一的嗎？試舉理由說明。 (1) 使用 Prim 算法 (2) e1 e5 e9 e7 e11 e15 e13 e2 e17 3 2 1 2 3 2 1 4 7 E F G A B C H I J D e2: 4 e3: 4 e8:4 e4:5 e6: 6 e12: 6 e17: 7 e19: 8 e10: 10 e14: 11 e18: 11 e1: 3 e11: 3 e16:3 e7: 2 e15: 2 e5: 2 e9: 1 e13: 1 E F G A B C H I J D e4:5 e2: 4 e3: 4 e8:4 e6: 6 e12: 6 e17: 7 e19: 8 e10: 10 e14: 11 e18: 11 e1: 3 e11: 3 e16:3 e7: 2 e15: 2 e5: 2 e9: 1 e13: 1 4 (2) 使用 Kruskal 算法 e9 e13 e5 e7 e15 e1 e11 e2 e17 1 1 2 2 2 3 3 4 7 (3) 這樣 選取的最小生成樹是唯 一的 。因為在邊上的權(quán)值相等時先選編號小的，限定了選擇的機會。假如不限定在具有相等權(quán)值的邊中的選擇次序，結(jié)果可能就可能不唯一了。 三 、簡 作題（共 10 分） 假設(shè)一個散列表中已裝入 100 個表項并采用線性探查法解決沖突，要求搜索到表中已有表項時的平均搜索次數(shù)不超過 4，插入表中沒有的表項時找到插入位置的平均探查次數(shù)不超過 。請根據(jù)上述要求確定散列
公司管理相關(guān)推薦
鄂ICP備17016276號-1