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

科目：研究所、轉學考(插大)◆離散數學 | 年份：104年 | 選擇題數：16 | 申論題數：6

試卷資訊

所屬科目：研究所、轉學考(插大)◆離散數學

選擇題 (16)

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) (B) (C) (D) .
4. How many subsets are there of a set consisting of *n* elements?
(A) (B) (C) (D) .
5. 嘉義大學規定研究所的課程至少要有兩位研究生選修才能開課，資工系本學期開了15門課供研究生選修，請問至少要有多少位研究生才能保證至少有一門課能開成？
(A) 3 (B) 16 (C) 31 (D) 30
6. 某同學本學期選修離散數學、機率論、以及線性代數三門課。他決定發憤圖強，每周一到週五這五天放學後，一定要花兩小時來研讀這三門課的其中一門。若每門課至少分到一天，請問有多少種安排的方法？
(A) 15 (B) 243 (C) 150 (D) 125
1. A relation R on a set A is called an equivalence relation iff it is reflexive, symmetric and transitive.(A)O(B)X
2. [(1,5)] ∩[(1,-2)] = Ø.(A)O(B)X
3. A relation R on a set A is called a partial order iff it is reflexive, antisymmetric and transitive.(A)O(B)X
4. The real numbers in the interval (0,1)⊆ R are countable.(A)O(B)X
5. The Boolean values in the interval (0,1) are countable.(A)O(B)X
6. A simple graph *G* is bipartite if *V* can be partitioned into two disjoint subsets *V_{1}* and *V_{2}* such that every edge connects a vertex in *V_{1}* and a vertex in *V_{2}*.(A)O(B)X
7. If G = (V, E) is an undirected graph with m edges, then *2m=Σ_{v∈V} deg*(*v*).(A)O(B)X
8. In social network, edges represent individuals or organizations and vertices represent relationships between them.(A)O(B)X
9. 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
10. 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

申論題 (6)

三、簡答題

1. 設集合、，以表列法明確寫出積集合(product set)。(10%)
2. 使用矛盾證法證明是無理數。(10%)
3. Let a_{n}=2^{n}+5*3^{n} for n=0, 1, 2,..
(a) Find a_{0}, a_{1}, a_{2}, a_{3} and a_{4}.(5%)
(b) Show that a_{2}=5a_{1}-6a_{0}, a_{3}=5a_{2}-6a_{1}, and a_{4}=5a_{3}-6a_{2}.(5%)
4. How many solutions are there for the map-coloring problem for the following figure?

(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%)