加載中. ..
PDF
107年公務人員高等考試三級考試試題 代號：36350 全一頁
類科： 資訊處理
科目： 資料結構
考試時間： 2 小時 座號：
※注意：
禁止使用電子計算器。
不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
本科目除專門名詞或數理公式外，應使用本國文字作答。
（請接背面）
一、
請說明並比較二分搜尋（binary search）與一般二元搜尋樹（binary search tree）兩
者在儲存鍵值並應用來進行搜尋鍵值功能時，在'建置'與'搜尋'程序上作法與效能的
差異（13 分）。
若有 n個鍵值，以下列甲和乙兩種資料結構策略儲存：
策略甲：由小到大依序儲存在一陣列中
策略乙：以 AVL tree 架構儲存
請以 Big-O 觀念比較後續六種不同功能獨立運作時，這兩種策略何者效能較優或
兩者效能相近：
尋找特定鍵值 k；
尋找排序為 j的鍵值；
刪除特定鍵值 k；
刪除排序為 j的鍵值；
插入新鍵值；
依序輸出所有鍵值。（12 分）
二、一非空的二元樹（binary tree），如果有 n0個葉節點（leaf node）且 n2個節點之分支
度（degree）為 2，請證明 n0 = n 2+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 分）
四、對稱式最小-最大堆積（Symmetric Min-Max Heap，簡稱 SMMH）是一種優先佇列
（priority queue），請回答下列與 SMMH 相關的問題。
請說明 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 分）