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

1. raw binary search trees of height 2 and 6, respectively, on the set of keys {1, 2, 3, 4, 5, 6,7}. (20%)

a. What is a hash function? (10%)

b. What is a one-way hash function used mostly for generating digital signatures? (10%)

3. Write the postfix and prefix forms of “ (A+B)*C+D/(E+A*C)+F“. (10%)

 a. Write out the low values of each vertex for the depth first spanning tree with root = 3 based on the equation low(u) = min{dfn(u), min{low(w)|w is a child of u}, min{dfn(w)|(u, w) is a back edge}}. (10%)

b. Give the rule to determine whether a vertex is an articulation point or not in a graph. (5%)

c. Show the articulation points of the graph G. (5%)

d. Is G a biconnected graph? (5%)

a. Suppose that we have a pattern shown below, to give the failure function of the pattern for each character. (15%)

b. Suppose that the lengths of the string and pattern are m and n. Give the time complexity of performing the KMP algorithm to accomplish a pattern matching. (10%)