99年國立政治大學資科所離散數學

1.

If f is a numeric function such that f(n) = Θ(n²), then f(n) = O(n³).

2.

(p ∨ q) → r logically implies (p → r) ∧ (q → r).

3.

Every irreflexive and transitive relation is antisymmetric

4.

Every simple graph has a chromatic number ≤ 4.

5.

Two graphs with different number of edges are not isomorphic.

6.

There is no simple circuit of non-zero length in a tree.

7.

~∀x ∃y P(x, y) logically implies ∀y ∃x ~P(x, y).

8.

Every function from int to int can be implemented as a Java method or C function.

9.

The poset (N, |) of non-negative integers N under the dividability relation | is a lattice but is not bounded since it has no greatest element.

10.

A binary relation R is transitive if and only if R² ⊆ R.

11.

Which of the following propositional formulas is not logical equivalent to the implication p → q?

(A)

(~p) ∨ q

(B)

(~q) → (~p)

(C)

~(p ∧ ~q)

(D)

p ↔ (~q)

12.

Let G = (N, T, S, P) be a context free grammar, where N = {S, A, B} is the set of nonterminal symbols, T = {0, 1} is the set of terminal symbols, S is the start symbol and the set of productions P is given as follows: {S → 0A, S → 1A, A → 0B, B → 1, B → 1A}. Then which of the followings is the language generated by G?

(A)

{01}{0, 1}^*{01}

(B)

{0, 1}{01}^*{01}

(C)

{0,1}{01}^*{0,1}

(D)

{01}{0, 1}^*

13.

Let R = {(1, 1), (2, 1), (3, 2), (2, 3), (4, 3)}. Then which of the following statements is not correct?

(A)

(2, 2) ∈ R²

(B)

(4, 3) ∈ R³

(C)

(2, 4) ∈ R^*

(D)

(4, 1) ∈ R⁺

14.

In the expansion of (w + x + y + z)²⁰, the coefficient of the term w²x⁴y⁶z⁸ is _______ and there are totally ________ different terms.

15.

The sum of the degrees of all vertices of a tree with n vertices is ______.

16.

What is the least positive integer x satisfying the following system of congruence equations: x ≡ 5 (mod 7), x ≡ 4 (mod 9), and x ≡ 3 (mod 13)? ______

17.

Let K_n denote a complete simple graph with n > 0 vertices. Then what is the length of a shortest circuit containing all edges of the graph K_2n? _____

18.

If f is an increasing function satisfying the recurrence relation: f(n) = 9f(n/3) + 2n², then the asymptotic order of f(n) = Θ( ______ ).

19.

A deterministic finite automata (DFA) M is a tuple (Q, Σ, δ, s, F), where Q is the set of states, Σ is the set of input symbols, s ∈ Q is the initial state, F ⊆ Q is the set of final states and δ: Q × Σ → Q is a state transition function. Suppose now |Q| = n and |Σ| = m. Then there are ______ different DFAs in which Q is the set of states and Σ the set of input symbols.

Let Σ = {0, 1} and A ⊆ Σ^* be a set of bit strings defined inductively by the following rules:
      Basis case: ε ∈ A, where ε is the empty string.
      Inductive case: If x ∈ A and y ∈ A, then so are 0x1, 1x0 and xy.
Moreover, for each bit string z, let f₀(z) and f₁(z) denote the number of 0s and 1s
occurring in z respectively. So, for example, if z = '1001', then z ∈ A and f₀(z) = f₁(z) = 2.

20.

According to the above definition explain briefly why the string '1001" belongs to A.

Let Σ = {0, 1} and A ⊆ Σ^* be a set of bit strings defined inductively by the following rules:
      Basis case: ε ∈ A, where ε is the empty string.
      Inductive case: If x ∈ A and y ∈ A, then so are 0x1, 1x0 and xy.
Moreover, for each bit string z, let f₀(z) and f₁(z) denote the number of 0s and 1s
occurring in z respectively. So, for example, if z = '1001', then z ∈ A and f₀(z) = f₁(z) = 2.

21.

Prove by structural induction that for all bit strings z, if z ∈ A then f₀(z) = f₁(z).

Let Σ = {0, 1} and A ⊆ Σ^* be a set of bit strings defined inductively by the following rules:
      Basis case: ε ∈ A, where ε is the empty string.
      Inductive case: If x ∈ A and y ∈ A, then so are 0x1, 1x0 and xy.
Moreover, for each bit string z, let f₀(z) and f₁(z) denote the number of 0s and 1s
occurring in z respectively. So, for example, if z = '1001', then z ∈ A and f₀(z) = f₁(z) = 2.

22.

On the other hand, show that if z is a bit string such that f₀(z) = f₁(z), then z ∈ A.

23.

Let G = (V, E) be a directed multigraph such that E ≠ ∅ and for all vertices x ∈ V, in-degree(x) = out-degree(x). Show that there exists a simple circuit of length > 0 in G.