110年 - 110 國立中山大學_碩士暨碩士專班招生考試_資管系/乙組:資料結構#105545

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

試卷資訊

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

選擇題 (0)

申論題 (19)

(A) Please draw the result of inserting the keys 6,5,3,9,10 into an empty AVL tree.

(B) Please draw the result after inserting the keys 7,8,11 into the AVL tree from (A).

(C) Please draw the result after removing the key 6 from the AVL tree from (B).

(D) Please draw the result after removing the key 11 from the AVL tree from (C).

(A) What is the minimum number of nodes in an AVL tree to achieve the height = 9?

(B) What is the maximum number of nodes in an AVL tree with height = 8? Note that the height is 1 for a tree with only one node.

(4%) (A) Dijkstra's algorithm will fail in what kind of situation?

(4%) (B) Floyd-Warshall algorithm will fail in what kind of situation?

(6%) (C) Complete the following pseudo code of Floyd-Warshall algorithm.

4.(10%) Given the frequencies of characters shown in the following table, please encode these characters to binary codes using Huffiman coding.

(6%) (A) Write a procedure to reverse an array of integers.

(6%) (B) Analyze the time complexity (runtime formula) of your answer in (A)?

(6%) (C) Write a procedure to calculate n! for a given integer n and analyze the time complexity of your procedure?

(6%) (D) How many disk moves are needed in the recursive procedure for solving the n-disk Hanoi tower problem? Prove your answer.

(5%) (A) Use Prim's algorithm to find the minimum spanning tree of G and give the cost.

(5%) (B) How to detect a cycle in the above algorithm?

(6%) (C) Starting from node 1, use Depth First Search (DFS) and Breadth First Search (BFS) to determine the minimum spanning tree of graph G.

(4%) (D) Can DFS or BFS guarantee to find the optimal solution? Why?

(6%) (E) Write a procedure to find (list) all connected components of a graph.