九九年專利商標審查人員三等資料結構
一、下圖為一網路流量圖 (network flow diagram)，每一線段上面標示該線段所能承載最大流量，箭頭代表流向。
(一)請問由 S 到 T 的最大流量為多少？每個線段流量各為多少？（10分）
(二)如線段沒有流向限制，S 到 T 的最大流量為多少？每個線段流量與方向各為何？（10分）
二、下圖為一個二元樹 (binary tree)，非葉 (non-leaf) 節點為運算子 (operator)，葉節點 (leaf) 為整數運算元 (operand)。假設X為運算子，T1 與 T2 為其左右部分樹 (subtree)，則 X 這個節點可以被 X (T1, T2) 取代。請寫一個程式，輸入該二元樹，輸出其計算結果。（20分）
三、請計算以下反覆函數 (recurrence function) 的時間複雜度 (time complexity)Θ()：
(一) T(n) = 8T(n/2) + 且 T(1) = 1（10分）
(二) T(n) = 4T(n - 1) - 3T(n - 2) + 1且 T(1) = 1，T(0) = 1（10分）
四、考慮一個表格 (table) T(A, B, C, D, E)，其函數相關性 (functional dependencies) 如下：AB→E, CD→E, A→C, C→A.
(一)請找出 T 所有之候選鍵 (candidate keys)，並列出推導過程。（10分）
(二) T 是不是 BCNF (Boyce-Codd Normal Form)？如是，請解釋。如不是，請分解其為符合BCNF的多個表格。（10分）
五、有一個程式使用二元樹 (binary tree) 資料結構來解決問題，為避免資料遺失，二元樹的資料儲存在資料庫。二元樹節點之定義如下：
struct node{
char Cname[20];
int Ccode;
float CGA;
struct node *left;
struct node *right;
};
(一)請設計關聯資料庫，包括表格、鍵 (key) 等必要元素，來儲存該二元樹。（10分）
(二)請寫一程式 ReadTreeFromDB() 從資料庫讀取一棵完整二元樹之資料。（10分）
一、下圖為一網路流量圖 (network flow diagram)，每一線段上面標示該線段所能承載最大流量，箭頭代表流向。
(一)請問由 S 到 T 的最大流量為多少？每個線段流量各為多少？（10分）
(二)如線段沒有流向限制，S 到 T 的最大流量為多少？每個線段流量與方向各為何？（10分）
二、下圖為一個二元樹 (binary tree)，非葉 (non-leaf) 節點為運算子 (operator)，葉節點 (leaf) 為整數運算元 (operand)。假設X為運算子，T1 與 T2 為其左右部分樹 (subtree)，則 X 這個節點可以被 X (T1, T2) 取代。請寫一個程式，輸入該二元樹，輸出其計算結果。（20分）
三、請計算以下反覆函數 (recurrence function) 的時間複雜度 (time complexity)Θ()：
(一) T(n) = 8T(n/2) + 且 T(1) = 1（10分）
(二) T(n) = 4T(n - 1) - 3T(n - 2) + 1且 T(1) = 1，T(0) = 1（10分）
四、考慮一個表格 (table) T(A, B, C, D, E)，其函數相關性 (functional dependencies) 如下：AB→E, CD→E, A→C, C→A.
(一)請找出 T 所有之候選鍵 (candidate keys)，並列出推導過程。（10分）
(二) T 是不是 BCNF (Boyce-Codd Normal Form)？如是，請解釋。如不是，請分解其為符合BCNF的多個表格。（10分）
五、有一個程式使用二元樹 (binary tree) 資料結構來解決問題，為避免資料遺失，二元樹的資料儲存在資料庫。二元樹節點之定義如下：
struct node{
char Cname[20];
int Ccode;
float CGA;
struct node *left;
struct node *right;
};
(一)請設計關聯資料庫，包括表格、鍵 (key) 等必要元素，來儲存該二元樹。（10分）
(二)請寫一程式 ReadTreeFromDB() 從資料庫讀取一棵完整二元樹之資料。（10分）
全站熱搜
留言列表
國考資訊處理解答 (7)
