99年 - 99 淡江大學轉學考離散數學#55471

科目：轉學考-離散數學 | 年份：99年 | 選擇題數：10 | 申論題數：5

試卷資訊

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

選擇題 (10)

1. Multiple Choice (單選題）（25 pts)

(1) If k is the least numbers of integers must be selected from {1，3, 5,…，29} to make sure there is at least o： pair of these integers with the sum 26, then k is (A) 6-8 (B)9〜11 (C) 12〜14 (D) 14〜16 (E) none of above.

(2) If k is the maximum height of T where Tis a full binary tree with 101 vertices, then k is (A) 1~20 (B)21~40(C) 41~60 (D) 61~80 (E)≥81.

(3) If k is the smallest coefficient in the expansion of (2x + 3)⁵then k is (A) 1 〜20 (B)21 〜40 (C) 41 〜6 (D) 61 〜80 (E)≥81.

(4) In 0， 2ⁿ， n4ⁿ and (-4)ⁿ these four numbers, the number of correct answers for the recurrence relation a_n = 8a_n-1 - 16a_n-2 is (A) 0 (B) 1 (C) 2 (D) 3 (E) 4 (所給的 4 個數字中是答案的; 個）

(5)

these four statements, the number of correc statements is (A) 0 (B) 1 (C) 2 (D) 3 (E) 4

2. True or False (是非題）(10 pts)

for all real numbers. (A)O(B)X

(2)

is an one-to-one function. (A)O(B)X

(3) There are no integer solutions x and y to the equation 2x² + 5y² = 14. (A)O(B)X

(4) If the truth value for “ p→ q” is false then the truth v(A)O(B)Xalue of its converse “ q→ p” must be true.

(5) The negation of

. (A)O(B)X

申論題 (5)

3. Prove or disprove: If

(mod 4), where a and b are integers, then

(mod 4). (12 pts)

4. Find the smallest equivalence relation on {1,2,3} that contains (1,2). (12 pts) Justify your answer.

5. How many nonnegative integer solutions are there to the equation x₁ x₂+ x₃ + x₄ = 21 such that

(12 pts) Show enough work to get full credits.

6. Apply Dijkstra’s Algorithm to find a shortest path from a to f. Indicate what is your shortest path and the total weight of the path. You must show every step in order to get full credits. (14 pts)

7. Use mathematical induction to prove that 3 divides n³+2n whenever n is a nonnegative integer. (15 pts) (3整除n³+2n, n為非負整數）（必須以歸納證明的方法證得）