102年 - 102 國立嘉義大學_碩士班招生考試試題_資訊工程學系：離散數學#146392

(a) Construct an optimal binary prefix code by usingHuffman’s algorithm. (10%)

(b) For each character in the above set, give thecorresponding Huffman code. (10%)

(c) Suppose that each symbol is encoded by 3 bits initially.Calculate the compression ratio if the above Huffman codes areused instead? (5%)

(a) Build a binary search tree. (5%)

(b) To find 56, how many comparisons do we require in the abovebinary search tree? (5%)

3 Determine the minimum spanning tree for the below graph. (10%)

4 Describe the language defined by the following grammar: (5%)

(a)

(b) .

6 Let be a connected undirected graph. What is the largestpossible value for if and for all ? Please draw agraph to demonstrate one of the possible case(s). (15%)

(a) Homogeneous recurrence relation:;

(b)Nonhomogeneous recurrence relation: .

(a) Please define the partial ordering relation R on a set S and usethe poset in the part (b) as an example to explain yourdefinition.

(b) Please draw the Hasse diagram for the poset ({1,2,4,5,12,20}, |), where means divides .