104年 - [無官方正解]104 國立嘉義大學_碩士班招生考試試題_資訊工程學系：離散數學#146849

1. The postfix expression: a b d e * + a d * f - / - b -. Then the infix expression is (A) b - (d + b * e) / (a * d –f) - a (B) a - (b + d * e) / (a * d –f) - b (C) b - (a + d * f) / (b * d –e) - a (D) a - (f + d * a) / (e * d –b) – b.

2. How many positive integers less than 30 that are relatively prime to 20? (A) 9 (B) 10 (C) 11 (D) 12.

3. What is the maximum number of edges in the tree with *n* vertices? (A)n (B)n² (C)n-1 (D)(n-1)² .

4. How many subsets are there of a set consisting of *n* elements? (A)n (B)n-1 (C)n² (D)2ⁿ .

5. 嘉義大學規定研究所的課程至少要有兩位研究生選修才能開課，資工系本學期開了15門課供研究生選修，請問至少要有多少位研究生才能保證至少有一門課能開成？ (A) 3 (B) 16 (C) 31 (D) 30

6. 某同學本學期選修離散數學、機率論、以及線性代數三門課。他決定發憤圖強，每周一到週五這五天放學後，一定要花兩小時來研讀這三門課的其中一門。若每門課至少分到一天，請問有多少種安排的方法？ (A) 15 (B) 243 (C) 150 (D) 125

7. A relation R on a set A is called an equivalence relation iff it is reflexive, symmetric and transitive.(A)O(B)X

8. [(1,5)] ∩[(1,-2)] = Ø.(A)O(B)X

9. A relation R on a set A is called a partial order iff it is reflexive, antisymmetric and transitive.(A)O(B)X

10. The real numbers in the interval (0,1)⊆ R are countable.(A)O(B)X

11. The Boolean values in the interval (0,1) are countable.(A)O(B)X

12. A simple graph *G* is bipartite if V can be partitioned into two disjoint subsets V₁ and V₂ such that every edge connects a vertex in V₁ and a vertex in V₂.(A)O(B)X

13. If G = (V, E) is an undirected graph with m edges, then 2m=Σ_v∈V deg(v).(A)O(B)X

14. In social network, edges represent individuals or organizations and vertices represent relationships between them.(A)O(B)X

15. A Hamiltonian cycle in a graph is a cycle that starts at some vertex v, visits every other vertex exactly once, and ends at v. True or false: every graph contains a Hamiltonian cycle.(A)O(B)X

16. Suppose every edge in an undirected graph has a unique weight. Then there must be a minimum-cost spanning tree that does not include the edge with maximum weight.(A)O(B)X

三、簡答題
17. 設集合，以表列法明確寫出積集合(product set)。(10%)

18. 使用矛盾證法證明√3是無理數。(10%)

(a) Find a₀, a₁, a₂, a₃ and a₄.(5%)

(b) Show that a₂=5a₁-6a₀, a₃=5a₂-6a₁, and a₄=5a₃-6a₂.(5%)

(a) The constraint is that adjacent regions must have different colors using three colors.(10%)

(b) The constraint is that all regions must have different colors using three colors.(10%)