109年 - 109 國立嘉義大學_碩士班招生考試試題_資訊工程學系：離散數學#145661

1.Determine the minimum spanning tree for the below graph. (15%)

2. Prove that among 50,000,000 people there are two who were born at exactly the same day, hour, minute, and second. (15%)

3. Suppose that the probability that a 0 bit is generated is 0.8, that the probability that a 1 bit is generated is 0.2, and that bits are generated independently. What is the probability that exactly four 0 bits are generated when 5 bits are generated? (10%)

4. Describe an algorithm that interchanges the values of the variables x and y, using only assignments. (5%)

5. Find $\sum_{k=5}^{100} k$. (5%)

6. Prove that $\sqrt{50}$ is irrational. (10%)

7. What probability at least two students were born on the same day in a class of 5 students? (shown by % to the first decimal place, ##.#%) (10%)

 (1) anyone may sit in any of the seats? (3%)

(2) the first and last seats must be filled by women? (3%)

(3) men occupy the first 3 seats and women occupy the last three seats? (3%)

(4) all members of the same sex are seated in adjacent seats? (3%)

(5) men and women are seated alternately? (3%)

9. Prove that a B-tree of degree $k$ and height $h$ has at least $2 \cdot \left\lceil \frac{k}{2} \right\rceil^{h-1}$ leaves, for $h \geq 1$. (15%)