104年 - [非官方正解]104 國立嘉義大學_碩士班(甲組)招生考試試題_生物機電工程學系：資料結構#145956

1. The pseudo codes shown below are a sorting algorithm. What kind of sorting algorithm is it? (10%)
(A) bubble sort
(B) heap sort
(C) quick sort
(D) merge sort

2. The pseudo codes shown below are an algorithm of producing minimum cost spanning trees. What kind of algorithm is it? (10%)
(A) Kruskal’s Algorithm
(B) Prim’s Algorithm
(C) Sollin’s Algorithm
(D) Knuth–Morris–Pratt Algorithm

3. Which of the description about a max heap is not the correct one?(10%)
(A) a complete binary tree
(B) a finite set of one or more nodes
(C) the key value in each node is no smaller than the key values in its children
(D) the keys in the right subtree are larger than the key in the root

(a) Give the binary tree T1 of the input list when the input order is from
left to right.

(b) Give the max heap T2 after adjust the binary tree T1 into a max heap.

2. The figure and pseudo codes are shown below. What is the result of executing the pseudo codes? (10%)

(a) Array

(b) Stack

(c) Queue

(d) Linked list

(a) Use an example to describe a quick sort algorithm. (10%)

(b) Show that the worst-case time complexity of quick sort is O(n2). (10%)

5. Use an example to describe the operations of a priority queue. (10%)