电子科技大学2010 -2011学年第 2 学期期 末 考试 A卷
课程名称：_离散数学(双语) 考试形式： 闭卷 考试日期： 2011年 月 日 考试时长：120分钟 课程成绩构成：平时 10 %， 期中 10%， 实验 10%， 期末 70% 本试卷试题由__7__ _部分构成，共___6__页。
题号 得分 得 分 一 二 三 四 五 六 七 八 – 九 – 十 – 合计 I.
（A ） 1.
Multiple Choice (20%, 10 questions, 2 points each)
Suppose S = {1, 2, 3, 4, 5}. Find P(S). a) 32
（B ） 2
b) 5 c)
d)
Which of these implications is false?
a) If 1 + 1 = 3 then 2 + 2 = 5 b) If 1 + 1 = 2 then 2 + 2 = 5 c) If 1 + 1 = 2 then 2 + 2 = 4 d) If 1 + 1 = 3 then 2 + 2 = 4 The best big-O function for (x ? 2)log2(x2 ? 1) ? log2(x3 ? 1) is a) x(log2x)2 b) xlog2x. c)x2. d) (log2x)2.
How many bit strings of length 10 have exactly six 0s?
a) 210 b) C(10,6). c) 26 d) 36
（B ） 3. （B ） 4. （D ） 5.
?1?0If MR???0??0111?111??, then R is not 011??001? (a) reflexive (b) antisymmetric (c) transitive. (d) symmetric
（C ） 6.
Suppose f: R?R has the following property for all real numbers x and y: if x b) f is not necessarily 1-1 and not necessarily onto R. c) f must be 1-1 but is not necessarily onto R. d) f is onto R but is not necessarily 1-1. S is a collection of strings of symbols. It is recursively defined by 1) a and b belong to S; 2) if string X belongs to S , so does Xb. Which of the following does NOT belong to S? a) abbb b) bbb c) ba d) a Given the inductive definition: f(1)=2,f(2)=2 and f(n)=2f(n-1)+f(n-2) for n>2. f(5) is: a) 8 b) 34 c) 14 d) 36 Which one of these propositions is different from the other three? (For this problem, f and （C ） 7. （B ） 8. （C ） 9. （D ） 10. Which of these propositions is false (the domain is the set of real numbers)? a) ?x?y(x ≠= 0 ?x · y = 1) b) ?y?x(x + y = x) c) ?x?y[(x ≠= y) ? ?z(x < z < y ? y < z < x)] d) ?x?y?z(x < z < y) g are non-negative functions.) a) g(x) = ?(f(x)) b) ?c?k [(x > k) ? (f(x) ? c · g(x))] c) ?c?k [(x > k) ? (f(x) ? c · g(x))] d) ??c?k [(x > k) ? (f(x) > c · g(x))] 得 分 II. True or False (10%, 10 questions, 1 point each) （F ） 1. The following sentence is a proposition: “ x+ 4 > 9.” （T ） 2. （T ） 3. （T ） （T ） （F ） （T ） （F ） 4. 5. 6. 7. 8. There is no simple graph with 8 vertices, whose degrees are 0?1?2?3?4?5?6?7. (p ? q) ? (?p ? q) is equivalent to q. The proposition ((p ? ?q) ? q) ? ?p is a tautology. .A ? (B ? C) ? (A ? B) ? C. The set ????a?????a?? is the power set of some set Suppose B ? ?x??x??, then ? ? P(B). g ? N ? N where g(n) ? any integer ? n, describes a function with the given domain and codomain Suppose g ? A ? B and f ? B ? C, where f ? g is 1-1 and f is 1-1. g must be 1-1? （T ） 9. （F ） 10. For all integers a?b?c, if a ? (b ? c), then a ? b and a ? c 得 分 III. Fill in the Blanks (20%, 10 questions, 2 points each) Write a proposition equivalent to p ? q using only p?q?? and the connective: ?? ?p ? q. Write the negation of the statement “All integers ending in the digit 7 are odd.” in good English: Some integers ending in the digit 7 are not odd. Find 1. 2. 3. 4. Ui?1??[1?,1]. {1} 1iSuppose P(x,y) is a predicate and the universe for the variables x and y is {1,2,3}. Suppose P(1,3), P(2,1), P(2,2), P(2,3), P(2,3), P(3,1), P(3,2) are true, and P(x,y) is false otherwise. The truth value of statement ?x?yP(x?y) is True. Suppose the variable x represents students and y represents courses, and T(xy): student x is taking course y. Write the statement ?x?y T(x?y) in good English without using variables in your answers: Every student is taking at least one course. Find 5. 6. 7. 8. 9. ??ij. 25 j?1i?13jThe two's complement of 13 is 1 0011 . An inverse of 17 modulo 19 is 9 . If R ? ?(1?2)?(1?4)?(2?3)?(3?1)?(4?2)?, the symmetric closure of R is ?(1?2)?(1?3)?(1?4)?(2?1)?(2?3)?(2?4)?(3?1)?(3?2)?(4?1)?(4?2)?. 10. The smallest equivalence relation on ?1?2?3? that contains (1?2) and (2?3) is : ?(1?1)?(1?2)?(1?3)?(2?1)?(2?2)?(2?3)?(3?1)?(3?2)?(3?3)?. 得 分 IV. Answer the Questions (30%, 6 questions, 5 points each)： 1. Find a proposition using only p?q??, and the connective ? that has the given truth table. p q ? T T F T F F F T T F F F ?(p ? ?q). 2. Let f(x) ? ?x3?3?. Find f(S) if S is: (a) ??2??1?0?1?2?3?. (b) ?0?1?2?3?4?5?. Ans: (a) ??3??1?0?2?9?. (b) ?0?2?9?21?41?. 3. In the questions below suppose g ? A ? B and f ? B ? C where A ? B ? C ? ?1?2?3?4?, g ? ?(1?4)?(2?1)?(3?1)?(4?2)? and f ? ?(1?3)?(2?2)?(3?4)?(4?2)?. Find f ? g. Ans: ?(1?2)?(2?3)?(3?3)?(4?2)?. 4. A message has been encrypted using the function f (x) ? (x ? 5) mod 26. If the message in coded form is JCFHY, decode the message. Ans: EXACT. 5. Describe a recursive algorithm for computing 32n where n is a nonnegative integer. Ans: The following procedure computes 32n: procedure power(n: nonnegative integer) if n ? 0 then power(n) ? ? 3 else power(n) ? ? power(n ? 1) ? power(n ? 1). 6. Represent the expression x + ((x?y + x)/y) using a binary trees.
2_计算机学院_离散数学期末考试_2011年春季_试卷B1
