99年私立靜宜大學資工所離散數學

1.

請計算31¹⁰¹ (mod 100)的值

2.

請計算C(7, 5)以及C(0.5, 2)其中C(x, y)是binomial coefficient

3.

請求出以下recurrence relation的通解 a_n = 6a_n−1 − 11a_n−2 + 6a_n−3, 如果其前三項的值為a₀ = 1, a₁ = 2, a₃ = 6

4.

若R是集合{1, 2, 3, 4, 5}上的一個relation, 且此relation包含(1, 3), (2, 4), (3, 1), (3, 5), (4, 3), (5, 1), (5, 2), (5, 4), 請計算R^[2].

如果R是一個集合A = {1, 2, …, 1000}上的relation, 且這個relation分別為 _______ 請問表示R的矩陣中各有多少個非0 的元素?

5.

{(a, b) | a ≤ b}

如果R是一個集合A = {1, 2, …, 1000}上的relation, 且這個relation分別為 _______ 請問表示R的矩陣中各有多少個非0 的元素?

6.

{(a, b) | a = b ± 1}

在1000到9999之間的正整數中(含頭尾兩數),

7.

有多少個可以被9整除?

在1000到9999之間的正整數中(含頭尾兩數),

8.

有多少個是偶數?

在1000到9999之間的正整數中(含頭尾兩數),

9.

有多少個不能被3整除?

在1000到9999之間的正整數中(含頭尾兩數),

10.

有多少個可以被5或7 整除?

11.

若Q(x, y)表示x + y = x − y且假設x, y的domain包含所有整數, 請寫出以下各項的真值
(a) Q(1, 1), (b) Q(2, 0), (c) ∀y Q(1, y), (d) ∃x Q(x, 2), (e) ∃x ∃y Q(x, y),(f) ∀x ∃y Q(x, y), (g) ∃x ∀y Q(x, y), (h) ∀x ∀y Q(x, y)

從集合A = {1, 2, …, 5}對應到集合B = {x, y, z}的各個不同函數中,

12.

有多少個會將A中的1和5對應到B中的z去呢?

從集合A = {1, 2, …, 5}對應到集合B = {x, y, z}的各個不同函數中,

13.

有多少個是映成(onto)函數?

以下graphs各有多少個節點和多少個邊? (K_m,n表示complete bipartite graph, Q_n 表示n-cube)

14.

K_m,n

以下graphs各有多少個節點和多少個邊? (K_m,n表示complete bipartite graph, Q_n 表示n-cube)

15.

Q_n

請計算

16.

請計算

17.

請寫出以下函數的最小big-O

18.

(n!+2ⁿ )(n³ + log(n² +1)) .

請寫出以下函數的最小big-O

19.

(n log n + n² )(n³ + 2(log n)⁴ )

20.

一個含有100個節點的full 3-ary tree共有多少個樹葉?

21.

請求出K₄中, 兩個不同節點間長度是3 的路徑個數

22.

如果集合A 內包含有10 個1 到50 之間的不同整數, 請證明A 的所有含5 個元素的子集中, 至少有兩個子集其5 個元素的和(sum)相等

23.

請問x₁ + x₂ + x₃ ≤ 6有多少個非負整數解? (求出數字答案)

24.

以下用prefix expression表示的運算式, 其運算結果為何? + − × 8 3 × 2 5 / 6 − 4 2?