课程名称︰离散数学(Discrete Mathematics) 课程性质︰必修(与工程数学-复变二者至少选一) 课程教师︰雷钦隆 开课学院：电机资讯学院 开课系所︰电机系 考试日期（年月日）︰2013/06/19 考试时限（分钟）：10:20~12:10 是否需发放奖励金： （如未明确表示，则不予发放） Yes 试题 : Discrete Mathematics 06/19/2013 1. (5 points) How many zeros are there at the end of 50! ? 2. (5 points) Solve the congruence 89x≡2 mod 232. 3. (8 points) Show that if n is an integer greater than 1, then n can be written as the product of primes. (Note: You have to clearly state the BASIS STEP, INDUCTIVE STEP, and the INDUCTIVE HYPOTHESIS) 4. Consider the following function: 2n if m=0 0 if m>=1 and n=0 A(m,n)= 2 if m>=1 and n=1 A(m-1,A(m,n-1)) if m>=1 and n>1 (a). (2 points) What is the value of A(1, 3)? (b). (3 points) What is the value of A(2, 3)? (c). (5 points) What is the value of A(3, 3)? 5. (4 points) Give a closed form formula for { sigma k=0 to n ((C n取k)*2^k) }. 6. (5 points) How many bit strings of length eight either start with a 1 bit or end with the two bits 00? 7. (5 points) How many cards must be selected from a standard deck of 52 cards to guarantee that at least three cards of the same suit are chosen? 8. (6 points) Thirteen people on a softball team show up for a game. (a). How many ways are there to assign the 10 positions by selecting players from the 13 people who show up? (b). Of the 13 people who show up, three are women. How many ways are there to choose 10 players to take the field if at least one of these players must be a woman? 9. (5 points) A shelf holds 12 books in a row. How many ways are there to choose five books so that no two adjacent books are chosen? 10. (5 points) What is the “Master Theorem”? (Note: Master Theorem is typically used to estimate the size of divide-and-conquer functions.) 11. (10 points) How many onto functions are there from a set with six elements to a set with three elements? 12. (20 points) (a). List all the binary relations on the set {0,1}. (b). List the reflexive relations on the set {0,1}. (c). List the symmetric relations on the set {0,1}. (d). Give a relations on the set {0,1}which is not transitive. (e). Give a relations on the set {0,1}which is not antisymmetric. 13. (12 points) In the questions below fill in the blanks. (a). K_n (complete graph) has ________ edges and _______ vertices. (b). W_n (wheel) has ________ edges and _______ vertices. (c). Q_n (hypercube) has ________ edges and _______ vertices. --

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