108年 - 108 國立臺北大學_日間學士班轉學生招生考試試題_資訊工程學系日間學士班3年級：資料結構#147610

1. (10 分) (A)使用 quick sort 排序數列 60 80 45 2 36 98 11 47 52 89 75 63 7。並且說明每次移動數字時，所使用的條件和基準。

(B)使用 binary search 在排序好的數列尋找數字，比如 36，並說明為何能達到 O(log N)的速度，N 是數列的數字個數。

2. (20 分) (A)將此 inorder statement: \( \mathrm{A}^{*}(\mathrm{B} + \mathrm{C}) + \mathrm{E}^{*}\mathrm{F} - \mathrm{H} / \mathrm{I} \) 轉為 postorder，並畫出它的二元樹。

(B)設計一個算法使用 stack 來實現上述 inorder 轉 postorder，並且以上述 statement 說明如何使用 stack 來做轉換。

3. (20 分) 使用 linked list 實作 stack，運用以下 C 語言程式：

4. (28 分) (A)Find all articulation points in Figure 1.

(B)Describe the two rules for finding the articulation points.

(C)Show the formula for low(w) value for node w.

(D)Show the \( dfn \) and low values in the table. The node's order of Depth First Search is 1-2-4-5-3-6-8-9-7.

5. (10 分) Give the adjacency multilists graph representation for the graph in Figure 2.

(A)Column Major

(B) Row Major.