114年 - 114 國立嘉義大學_碩士班招生考試試題_資訊工程學系：資料結構#144138

1. How many children does a binary tree have? (10%)

a. What is the output value given by f(300,65)? (10%)

b. What is the output value given by f(2477,127)? (10%)

a. The core data structure of Depth-First Search is a list. (4%)

b. One can reverse the order of the elements in a linked list in time O(n). (4%)

c. Returning the maximum element in a max-heap (but not deleting it from the heap) can be
done in time O(1). (4%)

d. One can implement a stack (of unbounded size) based on an array so that each individual
push/pop operation is time O(1). (4%)

e. One can implement a stack based on a linked list so that each individual push/pop
operation is time O(1). (4%)

4. Kruskal’s algorithm builds a minimum cost spanning tree T by adding edges to T one at a time. The following is Kruskal’s algorithm and the original graph with weighted values. Show the minimum cost spanning tree T by means of Kruskal’s algorithm.(10%)

a. Obtain its adjacency-matrix

b. Obtain its adjacency-list representation

c. Obtain its inverse adjacency-list representation.

d. Obtain its adjacency-multilist representation

a. What is the purpose of carrying out the above pseudo program?

b. Give the time complexity of the program in terms of big oh.