99年國立中央大學資工所離散數學

Let R be the set of all real number, N be the set of all natural numbers, Z is the set of all integer numbers. Which of the following statements are true?

Let Q be the set of all integer pairs (n, m), we can prove |Q| > |N|.

The diagonalization method that is used to prove |R| > |N| is a kind of contradiction proof.

There exists an onto function f : Z → Q.

There exists a program to determine whether or not any arbitrary program can stop, and this program has to execute with exponential time complexity.

None of the above.

Suppose x and y are integer numbers, and we define the following predicates:
         D(x, y) : y is a multiple of x; E(x) : x is even; O(x) : x is odd
Which of the following clauses are correct interpretations of the logical statement:
         ∃x, y, O(x) ∧ ¬E(y) → ¬D(x, y)

No odd integer can divide any even integer.

If y is a multiple of x, it is not possible that x is odd and y is not even

It is possible that some not-even number is not a multiple of some odd number

Some odd integer is not equal to an even integer.

None of the above

To analyze the complexity of the following procedure P. We will use the following assumptions: Suppose P and B are both procedures. B take Θ(m) time to compute, where m is the size of input; each statement line in and outside the loop counts 1 step.

Suppose n is a multiple of 3, which of the following relations on Cn can describe the complexity of procedure P with respect to problem size n?

None of the above

What is the time complexity level of the procedure P in question 3?

O(n log n)

O(n^{log n} )

O(n²)

None of the above.

Letthe matrix to represent a binary relation R on a four-element set. Which of the following statement are true?

There are seven 1's in the matrix that represents the symmetric closure of R.

R is a partial ordering relation.

R is reflexive.

The directed graph of R does not have a strongly connected component

None of the above.

The Towers of Hanoi is a popular puzzle. It consists of three pegs and a number of discs of differing diameters, each with a hole in the center. The discs initially sit on one of the pegs in order of decreasing diameter (smallest at top, largest at bottom), thus forming a triangular tower. The object is to move the tower to one of the other pegs by transferring the discs only to an adjacent peg one at a time in such a way that no disc is ever placed upon a smaller one. Solve the puzzle and find the solution for an, the number of moves required to transfer n discs from one peg to another.

When there are n = 2 discs, three moves are required.

When there are n = 3 discs, thirteen moves are required.

The recurrence relation is a_n = 2a_n−1 + 1.

The recurrence relation is a_n = 4a_n−1 + 1.

The explicit formula for a_n is

You and your buddy return home after a semester at college and are greeted at the airport by your mothers and your buddy's two sisters. Not uncharacteristically, there is a certain amount of hugging! Later, the other five people tell you the number of hugs they got and, curiously, these numbers are all different. Assume that you and your buddy did no hug each other, your mothers did not hug each other, and your buddy's sisters did not hug each other. Assume also that the same two people hugged at most once.

You hugged three people.

Your buddy hugged two people.

Your buddy hugged four people.

Your mother hugged five people

You hugged two people

Which of the following statements are true?

A Hamiltonian graph contains no proper cycles.

Every vertex in a Hamiltonian graph has degree 2.

Every Eulerian graph is Hamiltonian.

Every Hamiltonian graph is Eulerian.

A connected graph G has 11 vertices and 53 edges. G is Hamiltonian but not Eulerian.

Define f : A → B by f(x) = x² − 14x − 51.

A = N, B = {b ∈ Z | b ≥ −100}, f is not onto, but it is one-to-one.

A = Z, B = {b ∈ Z | b ≥ −100}, f is neither onto nor one-to-one.

A = R, B = {b ∈ Z | b ≥ −100}, f is neither onto nor one-to-one.

A = Z, B = Z, f is not onto, but it is one-to-one

A = R, B = R, f is not onto, but it is one-to-one.

Let A = {1, 2, 4, 6, 8, 10}, B = A², and for a = (a₁, a₂) and b = (b₁, b₂) in B, define a relation R by a R b if and only if a₁ ≤ b₁ and a₁ + a₂ ≤ b₁ + b₂.

R is reflexive and transitive.

R defines an equivalence relation on B.

R defines a partial order on B.

There is no maximum element in this partially ordered set.

This partially ordered set is a lattice.