課程名稱︰離散數學(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