阿摩線上測驗 登入

102年 - 102年司法人員特考三等資料結構#44087

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

試卷資訊

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

選擇題 (0)

申論題 (11)

⑴假設有 8 個排序好的數列（如圖 1），請建構一 loser tree 並顯示取出前 4 個最小 值之 loser tree 變化。（16 分）
⑵請說明 loser tree 和 winner tree 差異為何？（4 分）
⑴請利用 dfn（depth-first number）及 low（the lowest depth-first number）值，找出 圖 2 所有之關節點（articulation points）。假設利用深度優先搜尋法（depth first search）讀取節點之順序為 4-2-1-3-5-6-8-9-7，也就是節點 4 之 dfn 值為 1，節點 2 之 dfn 值為 2，節點 1 之 dfn 值為 3，依此類推。（15 分）
⑵請說明如何判斷那一節點為關節點？low 計算之公式為何？（5 分）
⑴請以 3-tuple form（i, j, value）來表示此矩陣 M。（6 分）
⑵針對⑴之 3-tuple form，請設計一有效率而時間複雜度不大於 O（columns＋terms） 之快速矩陣轉置（fast matrix transposing）演算法。其中 columns 為欄的數目， terms 為非零項目的數目。以圖 3 所示，columns＝4、terms＝6。（14 分）
⑴請設計一演算法，將一個二元樹（binary tree）每一節點之左子樹和右子樹對調（swap）， 如下圖 4 所示。（8 分）
⑵假設一 n 個 nodes 之 k-ary tree（即分支度為 k 之樹）T，每一個 node 有一固定大 小之欄位如下，請說明共有多少欄位是 Null？（8 分）
⑴請說明紅黑樹（red-black tree）之特性。（4 分）
⑵建立一紅黑樹，其數字依序為 10、72、14、68、20、58、30、50、65、63。（10 分）
⑶請一步一步刪除圖 5 紅黑樹之節點，依序為 10、18、3、16、13、12、17。其中 在圖 5 之節點 7、12、20 為紅色節點。（10 分）