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

(a) What is the value of A(1,1)? (10 Points)

(b) What is the value of A(2,2)? (10 Points)

(a) What is the minimum height of a binary tree of m-nodes and
justify your answer? (5 Points)

(b) What is the maximum height of a binary tree of m-nodes and
justify your answer? (5 Points)

三、Draw the 10-entry hash table that results from using the hash
function h(i) = (3i+4) mode 12, to hash the keys 13, 44, 17, 88, 23,
95, 20, 16, 8 and 67. Assuming the collisions are handled by linear
probing. (20 Points)

(a) The following is the problem of sorting records on several
keys. Please use the radix sort to sort 10 numbers {269, 184,
57, 587, 4, 53, 508, 263, 309, 482} in the range [0, 999].
(10 Points)

(b) Please analyze the time complexity of the radix sort. Is it
possible that the radix sort is faster than the Quick Sort, in
which the latter has only comparison and interchange
operations permitted on keys, under some restricted
conditions? Please describe your opinions. (10 Points)

五、Stack and Expression: The following is an infix form of the
expression:
(A/B*C+D)+E/(F/(G-H))
Please use the stack method to transform it to the postfix one. You must list the contents of the stack as each operator and operand are read. (10 Points)

(a) Is the undirected graph G in Figure 1 bipartite? Please explain your answer. (10 Points)

Figure 1: The undirected graph G

(b) The following is an adjacency matrix of the simple graph:

Please describe how many different paths of length 4 from vertex d to vertex b. (10 Points)