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

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

試卷資訊

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

選擇題 (0)

申論題 (12)

一、簡答題 50 分 每小題 10 分

1. 使用 merge sort 排序數列 60 80 45 2 36 98 11 47 52 89 75 63 7。並且說明每次移動數字時，所使用的條件和基準。
2. 使用 binary search 在排序好的數列尋找數字，比如 36，並說明為何能達到 \(O(\log N)\) 的速度，N 是數列的數字個數。
3. 將此 inorder statement: \(A^{*}(B + C) + E^{*}F - H / I\) 轉為 postorder，並畫出它的二元樹。
4. 設計一個算法使用 stack 來實現上述 inorder 轉 postorder，並且以上述 statement 說明如何使用 stack 來做轉換。
5. 使用 linked list 實作 stack，運用以下 C 語言程式：

typedef struct node { int value; node *next;}

void push (node **top, int new_value) { // assume top is not null

node *new_node = (node *) malloc (sizeof (node));

// 實作以下敘述

// add new_node to stack by top

}
二、(12分) 解釋名詞 (a) Describe the property of B-tree of order m (b) Quadratic probing 平方探測法 (c) Time Complexity: \(\Omega\) (Omega)
三、(14分)Insert 12,8,9,52 and 55 into the AVL tree as shown in Figure 1.
四、(24 分) (a) For the AOE network as shown in Figure 2 obtain the earliest start time e(), and latest start time l(), for each activity.
(b) What is the earliest time the project can finish?
(c) Which activities are critical?
(d) Is there any activity whose speed up would result in a reduction of the project length?
試題隨卷繳交