107年 - 107 高考三級資料結構#70742

科目：公職◆資料結構 | 年份：107年 | 選擇題數：0 | 申論題數：7

試卷資訊

所屬科目：公職◆資料結構

選擇題 (0)

申論題 (7)

一、⑴請說明並比較二分搜尋（binary search）與一般二元搜尋樹（binary search tree）兩者在儲存鍵值並應用來進行搜尋鍵值功能時，在'建置'與'搜尋'程序上作法與效能的差異（13 分）。

⑵若有 n 個鍵值，以下列甲和乙兩種資料結構策略儲存：

策略甲：由小到大依序儲存在一陣列中

策略乙：以 AVL tree 架構儲存

請以 Big-O 觀念比較後續六種不同功能獨立運作時，這兩種策略何者效能較優或兩者效能相近：

1.尋找特定鍵值 k；2.尋找排序為 j 的鍵值；3.刪除特定鍵值 k； 4..刪除排序為 j 的鍵值；5.插入新鍵值；6.依序輸出所有鍵值。（12 分）

二、一非空的二元樹（binary tree），如果有 n₀ 個葉節點（leaf node）且 n₂ 個節點之分支度（degree）為 2，請證明 n₀ = n₂+1。（25 分）

三、一無向圖 G 之節點集合為 G(V)={0,1,2,3,4,5,6,7,8,9}，邊集合為 G(E)={(0,1), (1,2), (1,3), (2,4), (3,4), (3,5), (5,6), (5,7), (6,7), (7,8), (7,9)}；請列出 G 之接合點（articulation point）和畫出 G 的所有雙連通元件（biconnected component），雙連通元件須以節點和邊構成之子圖方式表示。（20 分）

⑴請說明 SMMH 特性並說明以 SMMH 建構之優先佇列與以一般的堆積（heap）建構之優先佇列功能有何不同？並從一個空的 SMMH 開始，依序插入 30,20,50,5,4,9,70,2,80。請畫出最後 SMMH 的樹狀結構圖。（10 分）

⑵請畫出第⑴小題建構的 SMMH，刪除數字 2 後 SMMH 的樹狀結構圖。（5 分）

⑶請以一維陣列設計一資料結構儲存 SMMH，該資料結構可以使節點透過其對應之陣列索引值 x 構成的數學式計算出其祖父節點 g、父節點 p、左子節點 l、右子節點 r 與兄弟節點 s 等在陣列中的索引值。假設一維陣列之起始索引值為 0，請列出由 x 構成之計算 g、p、l、r、s 的數學式。並請畫出以此一維陣列儲存第⑴小題建構完成的 SMMH 的結果。（15 分）