103年 - 103 淡江大學 轉學考 離散數學#55464

科目：轉學考-離散數學 | 年份：103年 | 選擇題數：8 | 申論題數：8

試卷資訊

所屬科目：轉學考-離散數學

選擇題 (8)

1. Multiple Choice (單選題 3pt@8=24pts ) 
(a) Find a relationship to best describe the relation for the pair of sets: A ∪ B， A∪ (B -A). 
(b)Defme a functionf: N→ N such that f(n) = 4n2 + I. Then,fis one to one.(A) True (B)False. (N is the set of natural numbers)
(c) The negation of “Some people like pizza.” is (A) Some people like spaghetti.(B) Some people do not like pizza.(C)Everyone likes pizza.(D)Everyone does not like pizza.(E) None of above.
(d)Let A={a，{a}，{a，{a}}}. Then |A| =(A) 1 (B) 2 (C) 3 (D) 4 (E) None of above.
(e) Consider a rule for generating the terms of the sequence that begins 1,3,4, 8, 15, 27, 50, 92, , find the next term of the sequence.(A) 144 (B) 169 (C) 196 (D) 225 (E)None of above.
(f) The coefficient of x2y in (x + 2y- 5)4 is (A) 10 (B)-10 (C) 24 (D)-24 (E) None of above.
(g) The number of non-negative integer solutions in x+y+z = 8 is (A) 45 (B) 85 (C) 125 (D) 165 (E) None of above.
(h) Let =(A) 16 (B)24 (C)40 (D)48 (E)None of above.

申論題 (8)

2. Determine whether  is a tautology by constructing a truth table. (l0pts)
3. Prove by induction:  for all positive integer n. (l0pts)
(a) How many permutations are there to arrange a〜e in a row such that a and e are not together;
(b) find the number of the onto functions/from S to {1,2, 3} such that f(a) =1.
(a) Show the relation R is an equivalence relation;
(b) indicate the corresponding partition on A.
(a) Use Dijkstra’s algorithm to find the length a shortest path between the vertices a and i.(必須標示出每一個步驟的結果）
(b) Use Kruskal’s algorithm to find a minimum spanning tree. (必須標示出邊被選擇的順序）