96年私立靜宜大學資管所離散數學

1.

若L(x, y)表示"x loves y", 請用quantifier 來表示這個句子"There is somebody whom everybody loves."

(A)

∃x ∀y L(x, y)

(B)

∀y ∃x L(y, x)

(C)

∃x ∀y L(y, x)

(D)

∀y ∃x L(x y)

2.

P(S)表示S 這個集合的Power Set. 若S = {0, ∅, {0, ∅}}, 則P(S)包含幾個元素?

(A)

3

(B)

4

(C)

6

(D)

8

3.

以下敘述何者錯誤?

(A)

2ⁿ⁺¹ is O(2ⁿ)

(B)

n! is O(2ⁿ)

(C)

log²n is O(n)

(D)

log n! is O(n log n)

4.

A palindrome is a string whose reversal is identical to the string. How many bit strings of length n are palindromes? (Let n be an odd integer)

(A)

(B)

2ⁿ

(C)

C(n, (n + 1)/2)

(D)

n²

5.

以下relation 那一個不是transitive? (令x, y ∈ Z)

(A)

{(x, y) | xy ≥ 1}

(B)

{(x, y) | x = y + 1 or x = y − 1}

(C)

{(x, y) | x ≥ y2}

(D)

{(x, y) | x ≡ y (mod 7)}

6.

How many relations are there on the set {a, b, c, d}

(A)

256

(B)

16

(C)

64

(D)

65536

7.

How many edges does the graph Q_n has (Q_n 是一個n-Cube)?

(A)

2ⁿ ⋅ (n − 1)

(B)

n²

(C)

2ⁿ⁻¹ ⋅ n

(D)

8.

Which of the following graphs has an Euler circuit? (K_n : complete graph, W_n : wheel, Q_n : n-cube)

(A)

K₇

(B)

W₄

(C)

K₆

(D)

Q₃

9.

由a, b, c 三個字元所構成, 且長度為10的子串中, 恰包含3個a 或恰包含4個b的字串共有多少個?

(A)

24600

(B)

330

(C)

210

(D)

12460

10.

以下各個函數(f : Z × Z → Z)那一個不是映成(onto)函數?

(A)

f(x, y) = x + y

(B)

f(x, y) = x

(C)

f(x, y) = |x| − |y|

(D)

f(x, y) = x² − y²

11.

利用數學歸納法證明:

12.

A 是bit strings 所構成的集合, 其recursive definition 如下 :
(0 ∈ A), if (x ∈ A) then (x0 ∈ A ∧ 1x ∈ A) (其中x0 表示字串x 與0 連接)。請問集合A 中長度為4 的字串有那些?

13.

Use structural induction to show that n(T) ≥ 2h(T) + 1, where T is a full binary tree.(n(T)表示node number, h(T)表示tree 的高度)

14.

假設集合S 有n 個元素. 則總共有多少個可能的ordered pairs (A, B), A ⊆ S, B ⊆ S, 而且A ⊆ B? (Hint: 考慮S 的任一個元素可能在A, B − A, 或S − B 中)

一個relation R 假設我們用以下的矩陣W₀ 來表示

15.

請模擬Warshall's Algorithm 來求取R 的transitive closure

一個relation R 假設我們用以下的矩陣W₀ 來表示

16.

Warshall's Algorithm 的Time Complexity 為何?

17.

Find a recurrence relation for the number of bit strings of length n that do not contain three consecutive 0s. (在此我們用a_n 代表長度是n, 且符合這個條件的string 個數)

18.

a₁, a₂, a₃ 與a₄ 的值各為何?

19.

我們必須任意選出幾個整數, 才能確定其中有兩個數a, b 符合a ≡ b (mod 3)而且 a ≡ b (mod 7)?

20.

假設T(n)的recurrence relation 為T(n) = 4T(n/2) + n, 則T(n)函數的複雜度(Θ)為何?