阿摩線上測驗
登入
首頁
>
公職◆資料結構
> 104年 - 104年地方三等-資料結構#35130
104年 - 104年地方三等-資料結構#35130
科目：
公職◆資料結構 |
年份：
104年 |
選擇題數：
0 |
申論題數：
10
試卷資訊
所屬科目：
公職◆資料結構
選擇題 (0)
申論題 (10)
⑴請使用 C 或 Java 語言，修改此二元搜尋法，使其能對未排序（unsorted）且長度為 n 的陣列 A[0:n−1]，以 divide-and-conquer 技巧，進行二元化搜尋。（15 分）
⑵請分析修改後的二元搜尋法其最差時間複雜度（worst case time complexity）以 order Θ 的方式表示。（5 分） （注意：不可將此陣列數值進行排序，請加註解說明程式碼作法）
二、請使用 C 或 Java 語言寫一副程式 void merge(int [] A, int [] B, int [] C, int n)，此副程式 將對兩個長度為 n 且已依小到大排序的整數陣列 A 與 B，合併至長度為 2n 且依小到 大排序的整數陣列 C，此副程式的時間複雜度需為 Θ(n)。（20 分） （注意：請加註解說明程式碼作法）
三、⑴請說明使用何種資料結構及其演算法，可有效判斷一運算式（expression）中的巢 狀（nested）括號是否正確配對（matched）。（10 分）
⑵請以兩個運算式實例{A*[B−(C+D)+8]−16}及{A+[B−(C+5])}，分別說明此演算法判 斷的過程及結果。（10 分） （注意：未說明判斷的過程，不予計分）
四、⑴一運算式（expression）為：–a+(z+f)/y–b*a/c+d，請依運算元優先順序，繪出其 二元樹（binary tree）。（10 分）
⑵請列出此二元樹的前序走訪（preorder traversal）。（5 分）
⑶請列出此二元樹的廣度優先走訪（breadth-first search traversal）。（5 分）
⑴請使用 Floyd 的方法，計算此圖形的最短路徑長度矩陣（shortest path length matrix）， 表示任兩頂點間最短路徑長度。請依序列出最短路徑長度矩陣變化過程。（15 分）
⑵請使用 Kruskal 的方法，依序繪出加入此圖形的最小成本擴張樹（minimum cost spanning tree）每一邊的過程。（5 分）
阿摩線上測驗
登入
阿摩線上測驗
登入