MAT 2051 Discrete Mathematics Unit 10 Quiz 5 

MAT 2051 Discrete Mathematics Unit 10 Quiz 5 

Question 1Given an unordered list of n numbers, what algorithm would you use to sort it, and what is the worst-case runtime of the algorithm?

Answers:

a. Tournament sort, O(n log n).

b. Tournament sort, O(n).

c. Prim’s Algorithm, O(n log n).

d. Prim’s Algorithm, O(n * n).

Question 2Given a graph with n vertices, what is the minimum number of edges needed such that the graph is connected?

Answers:

a. n.

b. n – 1.

c. n * n.

d. n log n.

Question 3Which is a minimal spanning tree of the following graph:

Graph A-E.[D]

Answers:

a. A-B-D-E-C.

b. A-D-E-C-B.

c. A-B-D.

d. There is no minimal spanning tree.

Question 4How many six-bit strings begin with 100?

Answers:

a. 4.

b. 8.

c. 32.

d. 16.

Question 5If you select 5 microprocessors from 100 microprocessors, where 30 of the 100 are defective, what is the probability that you select no defective processors?

Answers:

a. C(100, 10)/C(30, 5).

b. C(70, 5)/C(100, 5).

c. C(100, 5).

d. C(100, 5)/C(70, 5).