99年國立宜蘭大學資工所離散數學線上測驗

1.: Let n ∈ N, x ∈ R and y ∈ R. Then the (r + 1)th item of polynomial (x + y)n (arranged in the descending order of the powers of x) can be expressed as?
(A)
(B)
(C)
(D)

2.: Let U, V e arbitrary sets, then based on the De Morgan laws we have (U ∩ V)' = ?
(A): U' ∪ V'
(B): U' ∩ V'
(C): U ∪ V'
(D): U' ∩ V

3.: Let n be an integer represented in base 10 as a sequence of t decimal digitals, i.e., d₁d₂d₃...d_t. Then n mod 9 can be expressed as?
(A)
(B)
(C)
(D)

4.

Assume that n is an exact power of 2, which is the solution of the recurrence relation shown below?

(A)

Γ(n) = 2 lg n

(B)

Γ(n) = n lg n

(C)

Γ(n) = n lg lg n

(D)

Γ(n) = n lg lg lg n

5.: When use a binary search algorithm to find an element in an N-element list, how many elements in the list will be examined before the algorithm returns a failure in finding the element?
(A): N
(B): log N
(C): N/2
(D): log(N/2)

6.: Let k ∈ N, n ∈ N and r ∈ R. Then which summation formula below is wrong?
(A)
(B)
(C)
(D): None

7.: The edge connectivity of an undirected graph denotes the minimum number k of edges that must be removed to disconnect the graph. For example, the edge connectivity of a tree is 1. Accordingly, the edge connectivity of a cyclic chain of vertices is ____

8.

Visiting the tree below in postorder gives the result A_ _ _ _ _ _ _P

9.: If we flip a coin, there is probability p that it comes up heads and probability q that it comes up tails, where p + q = 1.0; i.e., the process have just two outcomes. If we toss the coin n times and assume that different coin tosses are always independent. Then the chance of obtaining exactly k tails in n tosses is _____.

11.

The harmonic number H_j, j = 1, 2, 3, … are defined as follows

12.: Given an undirected graph G = (V, E) with |V| nodes and |E| edges. To make sure that G is connected, the value of |E| is at least ______.

模擬測驗