110年 - 110 國立中央大學_碩士班招生考試_資工類：離散數學與線性代數#110537

1. Which of the following logic equivalence statements are incorrect? (A) (B)(C) (D) (E) （Assume that x does not occur as a free variable in A and the domain of x is nonempty.)

3. Which of the following statements about integers are incorrect? (A) If gcd(a,b) = 1, then for any non-zero integer n, there is a pair of integers p and a such that pa + qb = n. (B) The inverse of p module q exists only when ged(p,q) = 1 and q ＞ 1. (x = a (mod m.) (C) The system has a unique solution modulo m， where m i are primes and=m₁ m₂...m_n. (D) Ifp is prime, then for every integer a we have ≡1(mod p). (E) In RSA, if Alice wants to send a secret message to Bob, Alice uses Bob's private key to encrypt the message and then send the ciphertext message to Bob. After Bob receives the ciphertext, Bob can use his public key to decrypt the ciphertext.

4.Figure 1 shows the Hasse diagram of a binary relation R. Which of the following statements are incorrect?
  (A) cRh. (B) mRm. (C) dRa. (D) R is a minimal element. (E) R isa lattice.

5. Given the directed graph in Figure 2. Which of the following statements are correct? (A) G is strongly connected. (B) G is weakly connected. (C) Ghas a Euler path. (D) G has a Hamilton path. (E) G is a planar graph.

6.Considering relation R defined as :  x does not have more prime factors than y), Which of the following statements are true? (A) R is partial ordering. (B) R is total-ordered. (C) Ris reflexive. (D) R is an equivalence relation. (E) Only 1 weakly connected component in a directed graph that represents R.

7. Suppose the set of "valuable" problems is V, where each problem can be considered by human beings, and there is a bijection between V and R (real number). Suppose the set of all A.I. softwares is S, where each software can solve exactly one problem. Each software can be represented as a long binary string (machine code). Which of the following statement are true? (A) There is a bijection between S and R. (B) A.I. can solve all valuable problems, it just takes a long time to do it. (C) Without other restrictions, |S| is ∞. (D) |V|≠|S|, and |V|＞|S| (E) In terms of solving problems, A.I. may replace human beings someday.

8. The number of ways to buy n dollars of tickets is represented by an, if only 1- dollar and 2-dollar bills can be used. What of the following can be the recurrence relation for our question? (initial condition: a₀ =1；a₁ = 1；) (A) (B) (C)(D) (E) none of the above.

9. About algorithm complexity, which of the following claims are true?(A)merge sort is θ(nlogn). (B)Euclid's algorithm to find gcd(a,b) is e(log max(a, b)). (C) bubble sort is θ(nlogn), (D) Roy-Warshall Algorithm to compute transitive closure is θ(n²) (bit operations). (E) traveling sales problem is a NP-hard problem.

10. Solving the recurrence relation  using generating function G(z), which following parts are true?  (A) G(Z)=(1+2)/(1-z-20z²) (B) G(Z)=(-1-z)/(1-z-20z²)  (C) (D) (E)

11. A=PD.

14. A=

If nxn matrix A is diagonalizable, then

16. 0 is not the eigenvalue of A. (A) True. (B) False.

27. is not a unique solution. (A) True. (B) False.

29. A is not always in Col A.  (A) True. (B) False.

30. b - A is always in Nul A^T.  (A) True. (B) False.

39. Which vectors form the basis of null( A )?
(A) [-3,2,1, -1,1] (B) [-1,-2,1,0, 0] (C) [1,-3,0, -4,1] (D) [2,-1,0, 1, -1] (E) None

40. A python function Fun is designed to perform a certain matrix operation: What inputs make Fun output 0? (A)(B) (C) (D) (E) All