99年國立台北科技大學資工所離散數學

For the following problems, please select the correct answers. In each problem, you must have all the correct ones selected to have the full credits. Otherwise, no credits will be given.

1.

Which of the following linear equations CANNOT be solved in integers?

(A)

154x + 260y = 5

(B)

108x + 30y = 7

(C)

45x + 14y = 1

(D)

621x + 736y = 46

For the following problems, please select the correct answers. In each problem, you must have all the correct ones selected to have the full credits. Otherwise, no credits will be given.

2.

Which of the following statements is true?

Note that, giving two relations R and S where R is from set A to set B and S is from set B to set C. The composition of R and S, denoted by R o S, is the relation from A to C and, for all a ∈ A, c ∈C, a(S o R)c if there exists some b ∈ B such that aRb and bSc

(A)

The intersection of two equivalence relations is again an equivalence relation.

(B)

The union of two equivalence relations is again an equivalence relation.

(C)

If R₁ and R₂ are two symmetric relations on a set, then so is R₁ o R₂.

(D)

If R is a reflexive and transitive relation, then R o R is transitive.

Consider the following expressions in an infix form: 6 + 5 ∗ 3 − 4 − 8 + 6 ∗ 2

3.

Please convert it in a postfix form.

Consider the following expressions in an infix form: 6 + 5 ∗ 3 − 4 − 8 + 6 ∗ 2

4.

Please convert it in a prefix form.

Consider the following expressions in an infix form: 6 + 5 ∗ 3 − 4 − 8 + 6 ∗ 2

5.

Please use the postfix form to evaluate this expression. You NEED to draw the sequence of stack configurations in the evaluation.

For a binary tree T, we use |T| to denote the number of nodes of T. If |T| = 0 or |T| = 1, there is only one binary tree. If |T| = 2, then there are two distinct binary trees. Please answer the following questions:

6.

When |T| = 3, how many distinct binary trees are there? Please draw them.

For a binary tree T, we use |T| to denote the number of nodes of T. If |T| = 0 or |T| = 1, there is only one binary tree. If |T| = 2, then there are two distinct binary trees. Please answer the following questions:

7.

In general, we would like to find the total number of distinct binary trees when |T| = n. Let B_n denote this number. Please write a recurrence equation of B_n.

For a binary tree T, we use |T| to denote the number of nodes of T. If |T| = 0 or |T| = 1, there is only one binary tree. If |T| = 2, then there are two distinct binary trees. Please answer the following questions:

8.

Please obtain B_n in explicit form using the recurrence equation in (b).

9.

Show that the language
    L = {a^mb^mc^m | m ≥ 1}
over the alphabet Σ = {a, b, c} is not a context-free language.

10.

Solve the recurrence relation a_n − 6a_n−1 + 9a_n−2 = 2ⁿ, if n ≥ 2, with initial conditions, a₀ = 4 and a₁ = 9