1_计算机学院_离散数学期末考试_2011年春季_试卷a1

电子科技大学 2010 -2011 学年第 2 学期期 末 考试 A 卷 课程名称：_离散数学(双语) 考试形式： 闭卷 考试日期： 2011 年 月 日 考试时长：_120 分钟 课程成绩构成：平时 10 %， 期中 10%， 实验 10%， 期末 70% 本试卷试题由_7 _部分构成，共_6 _页。 题号 一 二 三 四 五 六 七 八 九 十 合计 得分 I. Multiple Choice (20%, 10 questions, 2 points each) （ A） 1. Suppose U = 1, 2, ., 9, A = all multiples of 2, B = all multiples of 3, and C = 3, 4, 5, 6, 7. Then C - (B - A)= a) 4,5,6,7 b) 3,4,5,6 c) 4,6 d) 5,7 （ B） 2 Which of these implications is false? a) If 1 0, then 3 4. b) If 1 1 2 or 1 1 3, then 2 2 3 and 2 2 4. c) If 2 1 3, then 2 3 1. d) 1 1 3 if and only if 2 2 3. （ C） 3 Which of these propositions is not logically equivalent to the other three? a) (p q) (r q) b) (p r) q c) (pr) q d) The contrapositive of q (p r) （ B） 4. The best big-O function for n3 sin(n7). a) n7 b) n3 c) n5 d) n6 （ C） 5. How many different license plates are available if a license plate consists of 3 decimal digits(from 0 to 9) followed by 4 uppercase letters? a) P(10,3) P(26,4) b) C(10,3) C(26,4) c) 103 264 d) 3 10+4 26 （ D） 6. Suppose R1 and R2 be transitive on A. Which of the following is transitive? a) R1R 2 b) R1oR2 c) R2oR1 d) R1R 2 （ A） 7. If , then R is 01RM a) reflexive b) symmetric c) antisymmetric d) transitive. （A ） 8. Which of the following set is uncountable? a) The set of real numbers between 172 and 173. b) The set of integers c) The set of integers not divisible by 3. d) The union of two countable sets. 得 分 （A ） 9. Determine which of the following sequences are graphic,i.e. arise as the degree sequence of a simple graph G. a) 2,1,1,1,1 b) 3,3,2,2,1 c) 4,4,3,2,1 d) 4,4,3,3,3 （A ） 10. If all sets are finite, which of the following must be true? a) If a function is bijective, its domain and co-domain have the same cardinality. b) If a function is one-to-one, its domain and co-domain have the same cardinality. c) If a function is onto, its domain and co-domain have the same cardinality. d) If a function is neither one-to-one nor onto, its domain and co-domain do not have the same cardinality. II. True or False (10%, 10 questions, 1 point each) （F ） 1. The following sentence is a proposition: “Take two aspirin.” （F ） 2. A bipartite graph with an odd number of vertices that has a Hamilton circuit. （F ） 3. p (q r) is equivalent to (p q) r. （F ） 4. The proposition (p q) p) q is a tautology. （T ） 5. A B A (B A). （T ） 6. The set a is the power set of some set （F ） 7. Suppose B xx, then x B. （F ） 8. f N N where describes a function with the given domain and codomain.()fn （F ） 9. Suppose g A B and f B C, where f g is 1-1 and g is 1-1. Then f must be 1-1. （F ） 10. For all integers abcd, if a b and c d, then (ac) (b d). III. Fill in the Blanks (20%, 10 questions, 2 points each) 1. Find ( ). 1i ,. 2. Write the negation of the statement “Some bananas are yellow.” in good English: No bananas are yellow. 3. Suppose the variable x represents students and y represents courses, and T(x,y): student x is taking course y. Write the statement “Every student is taking at least one course.” using these predicates and any needed quantifiers:xy T(xy). 4. Find -84 61(2).ii 5. The twos complement of 12 is 0 1100 . 得 分 得 分 课程组长（签字） 系主任（签字） 学院 姓名 学号 选课/座号号 任课老师 密封线以内答题无效 第 3 页 共 6 页 6. An inverse of 5 modulo 12 is 5 . 7. If R=(12)(14)(23)(31)(42), the reflexive closure of R is (11)(12)(14)(22)(23)(31)(33)(42)(44). 8. Write a proposition equivalent to p q using only pq and the connective : (p q). 9. The negation of the statement xy (xy = 0) is xy (xy 0) . 10. The vertex-chromatic number for bipartite K77 is 2 . IV. Answer the Questions (30%,6 questions, 5 points each)： 1. Suppose f R R where f(x) x2. (a) If S x 1 x 6, find f(S). (b) If T 345, find f1(T). Ans: (a) 0123 (b) 612). 2. Use the definition of big-oh to prove that 13 23 n3 is O(n4). Ans: 13 23 n3 n3 n3 n3 n n3 n4. 3. Given that gcd(662414) 2, write 2 as a linear combination of 662 and 414. Ans: 662 (5) 414 8. 4. Give a recursive algorithm for computing na, where n is a positive integer and a is a real number. Ans: The following procedure computes na: procedure mult(a: real number, n: positive integer) if n 1 then mult(an) a else mult(an) a mult(an 1). 得 分 5. Represent the expression (x + xy) + (x/y) using a binary trees. 6. Determine whether these two graphs are isomorphic, and explain the reason. Ans: The graphs are isomorphic: label the graph clockwise from the top with 2,3,6,5,4,1. V. (6%) Prove that the distributive law A1 (A2 An) (A1 A2) (A1 An) is true for all n 3. Ans: The second form of mathematical induction is used. P(3) is true since it is the ordinary distributive law for intersection over union. P(3) P(n) P(n 1): A1 (A2 An 1) A1 (A2 An) An 1) A1 (A2 An) (A1 An 1) (A1 A2) (A1 An) (A1 An 1) (A1 A2) (A1 An 1). Grading rubric: -3 points for making wrong assumptions. 得 分 课程组长（签字） 系主任（签字） 学院 姓名 学号 选课/座号号 任课老师 密封线以内答题无效 第 5 页 共 6 页 -2 points for not being able to complete the proof. -1 to -3 points for illegal usage of inference rules. VI. (7%) Use Dijkstras algorithm to compute the shortest path from A to I, where edge labels indicate the distance (or cost) between vertices. For each iteration, write down the shortest path (i.e., its length and the vertices in it) from A to each vertex that has been found so far, and also indicate which vertices are currently in the set S. Vertices in S are shown in bold font. (1) A: 0; B: ; C: ; D: ; E: ; F: ; G: ; H: ; I: (2) A: 0; B: 3 (A); C: ; D: 7 (A); E: ; F: ; G: ; H: ; I: (3) A: 0; B: 3 (A); C: 7 (A, B); D: 7 (A); E: 12 (A, B); F: ; G: ; H: ; I: (4) A: 0; B: 3 (A); C: 7 (A, B); D: 7 (A); E: 12 (A, B); F: 15 (A, B, C); G: ; H: ; I: (5) A: 0; B: 3 (A); C: 7 (A, B); D: 7 (A); E: 12 (A, B); F: 15 (A, B, C); G: 8 (A, D); H: ; I: (6) A: 0; B: 3 (A); C: 7 (A, B); D: 7 (A); E: 12 (A, B); F: 15 (A, B, C); G: 8 (A, D); H: 10 (A, D, G); I: (7) A: 0; B: 3 (A); C: 7 (A, B); D: 7 (A); E: 11 (A, D, G, H); F: 15 (A, B, C); G: 8 (A, D); H: 10 (A, D, G); I: 16 (A, D, G, H) (8) A: 0; B: 3 (A); C: 7 (A, B); D: 7 (A); E: 11 (A, D, G, H); F: 13 (A, D, G, H, E); G: 8 (A, D); H: 10 (A, D, G); I: 16 (A, D, G, H) (9) A: 0; B: 3 (A); C: 7 (A, B); D: 7 (A); E: 11 (A, D, G, H); F: 13 (A, D, G, H, E); G: 8 (A, D); H: 10 (A, D, G); I: 14 (A, D, G, H, E, F) (10) A: 0; B: 3 (A); C: 7 (A, B); D: 7 (A); E: 11 (A, D, G, H); F: 13 (A, D, G, H, E); G: 8 (A, D); H: 10 (A, D, G); I: 14 (A, D, G, H, E, F) The shortest path passes through the vertices A, D, G, H, E, F, and I, and it covers a total distance of 14. Grad