课程名称︰离散数学 课程性质︰选修 课程教师︰郭斯彦 开课学院：电资学院 开课系所︰电机系 考试日期（年月日）︰2010/06/21 考试时限（分钟）：120 是否需发放奖励金：是 （如未明确表示，则不予发放） 试题 : 1.Answer True of False for each of the following (a) C(n,n)=1 (b) There are 11! distinct orderings of the letters of the word MATHEMATICS (c) Rolling a total of 8 when three dice are rolled is more likely than rolling a total of 8 when two dice are rolled (d) The next larger permutation of 234651 is 235146 (e) |A∪B∪C∩| = |A| + |B| + |C| - |A∩B| - |A∩C| - |B∩C| (f) Recursive algorithm is always more efficient than its iterative counterpart (g) 1 + 10 +100 + ... + 10^1000 = 10^1001 - 1 2 5 (h) Σ Σ 1 = 1 i=1 j=1 (i) If the graph of relation contains no arrows at all, then the relation is symmetric (j) Zero is a multiple of 7 2.How many strings of decimal digits (0,1,2,...,9) of length 10 have a)Exactly three 0? b)At least three 0? c)Sum of all 10 digits equals to 3? 3.A relation R on a set A={1,2,...,10} is defined by a+b=10 where a belongs to set A and b belongs to set A and(a,b) belongs to set R . Plain answer without reasons will not get any points for part(b),(c),(d), and (e) (a) Find the relation R. (b) Is R symmetric? (c) Is R antisymmetric? (d) Is R irreflexive(not reflexive)? (e) Is R transitive? 4.Calculate the following (a) What is the probability that a five-card poker hand contains three queens ,one jack, and one 5. (b) When rolling three dice, what is the probability of getting the sum 6. (c) Use the Euclidean algorithms to find gcd(952,340) (d) A dodecahedral die has 12 faces that are numbered 1 through 12. What are the expected value and the variance of the number that comes up when a fair dodecahedral die is rolled? 5.(a)Give a recursive definition of the set of positive integers not divisible of 5 (b)Give the function that reverses a string(Hint:a string of length greater than 0 can be represented as xy where x is the first symbol of the string and y is the rest of the string. For example, for string abcd, we have x=a and y=bcd.) 6.Equivalence Relations: Are the following relations on the set of all people equivalence relations? If not, give a reason. (a) R={(a,b)| a and b are the same age} (b) R={(a,b)| a and b have the same parents} (c) R={(a,b)| a and b share a common parent} (d) R={(a,b)| a and b have met} (e) R={(a,b)| a and b speak a common language} 7.Prove that the sum of in-degree and out-degree of all nodes in a graph with directed edges is always even. 8.Use induction on n to prove the following: For any integer n>4 n^2<2^n 9.Modulo arithmetic: solve the following equation for x and y modulo the indicated modulus, or show that no solution exists. Show your work. (a) 7x≡1 (mod 15) (b) 10x+20≡ (mod 23) (c) the system of simultaneous equations 3x+2y≡0 (mod 7) and 2x+y≡4 (mod 7) --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.242.115