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

科目：研究所、轉學考(插大)-資料結構 | 年份：105年 | 選擇題數：0 | 申論題數：13

試卷資訊

所屬科目：研究所、轉學考(插大)-資料結構

選擇題 (0)

申論題 (13)

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%)
4. A binary tree with 10 nodes is given below. (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%)