电子科技大学2010 -2011学年第 2 学期期末考试 A卷课程名称：_离散数学(双语) 考试形式：闭卷考试日期： 2011年月日考试时长：120分钟课程成绩构成：平时 10 %，期中 10%，实验 10%，期末 70%本试卷试题由__7__ _部分构成，共___6__页。

I.Multiple Choice(20%, 10 questions, 2 points each)（A ） 1. Suppose S = {1, 2, 3, 4, 5}. Find().P Sa) 32 b) 5 c) d)（B ） 2 Which of these implications is false?a) If 1 + 1 = 3 then 2 + 2 = 5 b) If 1 + 1 = 2 then 2 + 2 = 5c) If 1 + 1 = 2 then 2 + 2 = 4 d) If 1 + 1 = 3 then 2 + 2 = 4（B ） 3. The best big-O function for (x+ 2)log2(x2+ 1) + log2(x3+ 1) isa) x(log2x)2b) x log2x. c)x2. d) (log2x)2.（B） 4. How many bit strings of length 10 have exactly six 0s?a) 210 b) C(10,6). c) 26d) 36（D ） 5.If1111011100110001 R⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦M, then R is not(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<y then f(x)<f(y). Which of the following is true?a) f must be both 1-1 and onto R.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.（C ）7. 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（B）8. 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) 34c) 14 d) 36（C）9. Which one of these propositions is different from the other three? (For this problem, f andg 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))]（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 )II. True or False (10%, 10 questions, 1 point each)（F ） 1. The following sentence is a proposition: “ x+ 4 > 9.” （T ） 2. There is no simple graph with 8 vertices, whose degrees are 0,1,2,3,4,5,6,7. （T ） 3. (p → q ) ∧ (⌝p → q ) is equivalent to q .（T ） 4. The proposition ((p → ⌝q ) ∧ q ) → ⌝p is a tautology. （T ） 5. .A ⋃ (B ⋂ C ) ⊇ (A ⋃ B ) ⋂ C .（F ） 6. The set {∅,{a },{∅,a }} is the power set of some set （T ） 7. Suppose B = {x ,{x }}, then ∅ ∈ P (B ).（F ）8.g : N → N where g (n ) = any integer > n, describes a function with the given domain and codomain（T ） 9.Suppose g : A → B and f : B → C , where f g is 1-1 and f is 1-1. g must be 1-1?（F ） 10. For all integers a ,b ,c , if a | (b + c ), then a | b and a | cIII. Fill in the Blanks (20%, 10 questions, 2 points each)1. Write a proposition equivalent to p → q using only p ,q ,⌝ and the connective: ∨: ⌝p ∨ q .2. Write the negation of the stat ement “All integers ending in the digit 7 are odd.” in good English: Some integers ending in the digit 7 are not odd.3. Find1i +∞=[11,1i-]. {1}4.Suppose 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.5.Suppose the variable x represents students and y represents courses, and T (x y ): 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. 6. Find311.jj i ij ==∑∑ 257. The two's complement of 13 is 1 0011 .8. An inverse of 17 modulo 19 is 9 .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)：p ,q ,⌝, and the connective ∨ that has the given truth table.⌝(p ∨ ⌝q ).2. Let f (x ) = ⎣x 3/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 formis 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 ) : = 3else power (n ) : = power (n - 1) ⋅ power (n - 1).6. Represent the expression x + ((x ⋅y + x )/y ) using a binary trees.V. (6%) Prove that (q ∧ (p → ⌝q )) → ⌝p is a tautology using propositional equivalenceand the laws of logic.Ans: (())(())(()())()()()()q p q p q p q p q p q q pq p pq p p q p p q p p ∧→⌝→⌝⇐⇒∧⌝∨⌝→⌝⇐⇒∧⌝∨∧⌝→⌝⇐⇒∧⌝→⌝⇐⇒⌝∧⌝∨⌝⇐⇒⌝∨∨⌝⇐⇒⌝∨∨⌝Grading rubric: -3 points for making wrong assumptions.-2 points for not being able to complete the proof. -1 to -3 points for illegal usage of equivalence rules.VI. (7%)For an undisclosed reason, the German military often needs to transmit a massiveamount of integers through its communication channels. They use ASCII encoding for this transmission, so that each digit is encoded as an eight-bit string. Because all of their communication is intercepted by foreign intelligence, it is well known throughout the world得 分得 分that the frequencies of the digits that the Germans transmit are as follows:Help the German military by developing an optimal variable-length encoding fortheir communication. Use a Huffman coding tree for the development of theencoding, and then write down the resulting bit string for each digit.Grading rubric: -3 points for making a wrong Huffman coding tree-2 points for not being able to complete the encoding.-1 point for each incorrect encoding.得分VII.(7%) Use Dijkstra's Algorithm to find the shortest path length between the vertices a and z in this weighted graph.Ans: First iteration: distinguished vertices a; labels a:0, b:3, c:2, d,z:∞; second iteration: distinguished vertices a,c; labels a:0, b:3, c:2, d:8, z:∞; third iteration: distinguished vertices a,b,c, labels a:0, b:3, c:2, d:5, z:11; fourth iteration: distinguished vertices a,b,c,d, labels a:0, b:3, c:2, d:5, z:9. Since z now becomes a distinguished vertex, the length of a shortest path is 9.Grading rubric: -2 points for giving wrong result.-1 to -5 points for illegal usage of Dijkstra’s algorithm.。