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

1. Explain the following terminologies: space complexity, time complexity, and asymptotic analysis. (10%)

2. Three matrices A, B, C are defined by "int A[15][10], B[10][12], C[15][12];". Write a program segment to multiply A[15][10] by B[10][12] and store their product into C[15][12]. (10%)

3. Let the value of the six variables A, B, C, D, E, F are 5, 4, 2, 6, 3, 7 respectively. First, use a stack to transform the infix expression \( (\mathrm{A} + \mathrm{B})\mathrm{xC} - \mathrm{D} / \mathrm{E} + \mathrm{F} \) into a postfix expression. Then, use a stack to evaluate the obtained postfix expression. (15%)

(a) Use a linked list structure to represent the binary tree. (5%)

(b) Briefly describe the pre-order traversal algorithm and show the outcome of pre-order traversal. (5%)

(c) Briefly describe the post-order traversal algorithm and show the outcome of post-order traversal. (5%)

二、 1. Adjacency Matrix 與 Adjacency List 是兩種常見的 Graph 表示法。若考慮儲存全台灣大學生之間的社交網路關係，請問用哪一種表示法比較合適？(2%) 為什麼？(3%)

2. 圖一是一範例 Graph。請畫出該 Graph 的 Minimal Cost Spanning Tree。(5%)

3. Quick Sort 是常見的排序方法，其平均複雜度為 \( O(n \log n) \)，在最糟實況的複雜度為 \( O(n^2) \)。請問要如何避免 Quick Sort 排序法陷入最糟實況？(5%)

4. 將下列鍵值依序建立AVL-tree，請畫出其結果。(10%)

5. 將下列鍵值依序建立 Red-Black Tree，請畫出其結果。(10%)

6. AVL Tree 與 Red-Black Tree 都是一種自平衡二元搜尋樹 (Self-Balancing Binary Search Tree)，請比較 AVL Tree 與 Red-Black Tree 的優劣。(5%)

7. 假設今有一鍵值 \( k = 123443246 \)，若使用邊界摺疊 (Folding at the boundary)法，並假設一段的長度為3，請問Hash後的結果是？(10%)