課程名稱︰離散數學 課程性質︰選修 課程教師︰郭斯彥 開課學院：電資學院 開課系所︰電機系 考試日期（年月日）︰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