99年國立清華大學資應所離散數學

Answer the following short questions about trees.

1.

Give the definition of a tree. (Please be as precise as you can.)

Answer the following short questions about trees.

2.

A binary tree has 300 leaves. How many internal nodes does this binary tree have?

Answer the following short questions about trees.

3.

Consider the problem of connecting 200 lamps to a single electric outlet by using extension cords each of which has 4 outlets. How many extension cords are needed?

Answer the following short questions about trees.

4.

A regular m-ary tree of height h has z leaves. What are the maximum and minimum values of z?

Answer the following short questions about trees.

5.

Draw the binary tree of which the preorder traversal is a, b, d, g, e, h, i, c, f, and the inorder traversal is g, d, b, h, e, i, a, c, f.

Answer the following short questions about trees.

6.

Suppose we are given the preorder traversal and the postorder traversal of a binary tree. Can we reconstruct the tree? If so, give an algorithm for doing so. If not, give a counterexample.

Answer the following short questions about trees.

7.

Use the procedure invented by Huffman to construct an optimal tree for a given set of weights: 1, 2, 3, 4, 5, 6, 7, 8.

8.

Let I denote the sum of the path lengths of all the branch nodes and E denote the sum of the path lengths of the leaves in a rooted tree. Show that for a regular m-ary tree, E = (m − 1)I + mi, where i is the number of branch nodes.

9.

Determine a minimum spanning tree for the following graph.

10.

A three-state finite state machine has {0, 1} as its input and output alphabets. Given the following input sequence and its corresponding output sequence, determine the machine

11.

Let f and g be functions on {1, 2, 3, …}. Define f(n) = O(g(n)), f(n) = Ω(g(n)), and f(n) = Θ(g(n)), respectively.

12.

Show that postage of 24 cents or more can be achieved by using only 5-cent and 7-cent stamps

13.

Show that for any set X, X is not equivalent to the power set of X.

14.

What is the order of n! in the best big Oh notation as a function of n?

15.

What is the order of lg(n!) in the best big Oh notation as a function of n?

16.

Find the solution to an = 2a_n−1 + 5a_n−2 − 6a_n−3 with a₀ = 7, a₁ = −4, and a₂ = 8.

17.

Consider the relation on the set of integers R = {(x, y) | x − y is an integer}. Show that R is an equivalence relation.

18.

Find the transitive closure of the relation {(1, 1), (1, 3), (2, 1), (2, 3), (2, 4), (3, 2), (3, 4), (4, 1)}.

Construct an Eulerian tour or open Eulerian trail for the following graphs, respectively.

19.

Construct an Eulerian tour or open Eulerian trail for the following graphs, respectively.

20.

21.

The coloring number of an acquaintance network tells the minimum number of groups into which the persons in that network must be partitioned so that no two persons in a group have prior acquaintance. Calculate the coloring number of the following acquaintance network.