110年 - 110 國立中央大學_碩士班招生考試_資訊管理暨大數據分析類:資料結構#103860

(a) Please show the process in detail and the result of Quick Sort (use pivot). (6%)

(b) Please show the process in detail and the result of Bubble Sort. (6%)

(c) Please show the process in detail and the result of Heap Sort. (6%)

(d) Please use the hash function h(m)=m%11 and linear probing collision resolution to create a hash table with 11 elements. Then, show this bash table. (7%)

(a) What is the maximum number of leaves? (1%)

(b) Prove your answer to (a). (8%)

(a) Please briefly explain linked list (3%) and doubly linked list (3%) by drawing their structures.

(b) Please use C code (ANSI C) to implement corresponding functions for inserting node at the head of linked list(4%) and doubly linked list(5%).

(a) According to the binary tree shown below, please provide final results of pre-order (3%), in-order (3%), and post-order (3%) traversals.

(b) As mentioned above, please use C code (ANSI C) to implement corresponding functions for printing visited elements by using pre-order(3%), in-order (3%), and post-order (3%).

(a) It is common to implement the DFS algorithm with a Stack. However, the stack may be used differently in different implementations. You are tasked to implement the DFS algorithm for any given graphs. Explain how you are going to use the stack in your implementation.(7%)

(b) Next, write down the pseudocode for your DFS algorithm following implementation specifications below. You must include your idea given in (a) in your pseudocode. You may include any additional functions required for your implementation. Note: your pseudocode should be clearly written so that any programmer is able to read and implement your pseudocode. (20%)

(c) Refer to the pseudocode below for this question. Given a graph G, use your pseudocode in part (b) above to traverse G and print the order in which the vertices are visited. Your answer should be printed like this: (6%)

110年 - 110 國立中央大學_碩士班招生考試_資訊管理暨大數據分析類:資料結構#103860

試卷資訊

選擇題 (0)

申論題 (13)