Descrete Math Multiple Choice

Note: Please see attachment for full details.

3.
A grammar that has no restrictions on production is called a:
A) phrase-structure grammar.
B) context-sensitive grammar.
C) context-free grammar.
D) regular grammar.

5.
A Karnaugh map for 6 variables will have __________ squares.
A) 16
B) 32
C) 64
D) 128

6.
A Turing machine exists with tape symbols 0, 1, and B, that takes a bit string as input and replaces all 0s with 1s; it does not change any of the 1s. Pick the Turing machine from the following:
A) (s0, 0, s0, 1, R), (s0, 1, s1, 1, R), (s1, 1, s1, 1, R), (s1, 1, s0, 1, R)
B) (s0, 0, s1, 1, R), (s1, 0, s0, 1, R)
C) (s0, 0, s0, 1, R), (s0, 1, s0, 1, R)
D) None of the above

8.
Bubble sort has worst case complexity of:
A) O(n log2 n)
B) O(n2)
C) O(n)
D) O(n!)

9.
Consider the following derivation tree:

What strings can be constructed using this derivation tree?
A) A large bunny hops wildly
B) A large bunny hops
C) A bunny hops wildly
D) A bunny hops
E) All of the above

10.
Every full binary tree with 61 vertices has __________ leaves.
A) 30
B) 31
C) 60
D) 61
E) none of the above

11.
How many different Boolean functions of degree 7 are there?
A) 27
B) 128
C) 228
D) 2128

12.
T is a tree with 999 vertices, therefore T has __________ edges.
A) 998
B) 999
C) 1000
D) none of the above

13.
The best comparison-based sorting algorithms for a list of n items have complexity of:
A) O(n log2 n)
B) O(n2)
C) O(n)
D) O(n!)

14.
The idempotent laws of Boolean algebra state that:
A) x + x = 2x
B) x * x = x2
C) x + x = x
D) x * x = 2x

15.
The identity, x + yz = (x + y)(x + z) is known as:
A) De Morgan's law.
B) distributive law.
C) associative law.
D) commutative law.

16.
The pairs of numbers define the input and output to and from each state. The machine starts in state s0. If the input value to s0 is a 0, then 1 is output and the machine transitions to state s1; if the input is a 1, then 0 is output and the machine transitions to state s3. If the machine is in state s1 and receives a 0 as input, it outputs a 1 and stays in state s1; if it receives a 1, it outputs a 1 and transitions to s2. The remainder of the machine diagram may be read in the same fashion.

The machine is started and receives the bit string 0000. What does it output?
A) 1111
B) 1000
C) 1010
D) 0000

17.
The pairs of numbers define the input and output to and from each state. The machine starts in state s0. If the input value to s0 is a 0, then 1 is output and the machine transitions to state s1; if the input is a 1, then 0 is output and the machine transitions to state s3. If the machine is in state s1 and receives a 0 as input, it outputs a 1 and stays in state s1; if it receives a 1, it outputs a 1 and transitions to s2. The remainder of the machine diagram may be read in the same fashion.

The machine is started and receives the bit string 101010. What does it output?
A) 010101
B) 011011
C) 001001
D) 000101

18.
The study of languages and grammars using discrete math focuses on:
A) syntactics.
B) semantics.
C) natural language.
D) none of the above.

19.
The sum-of-products expansion of F(x,y) = 1 is:
A)
B)
C)
D) none of the above

20.
The two outputs of a half adder are the sum, s and carry, c. What is the output for input values of 1 and 1?
A) s=1, c=1
B) s=1, c=0
C) s=0, c=1
D) s=0, c=0

21.
There are __________ non-isomorphic trees with 4 vertices.
A) 0
B) 1
C) 2
D) 3
E) 4

24.
What is the language recognized by the following nondeterministic finite-state machine?

A) { 0, 1 }
B) { 0, 00, 10, 01, 11 }
C) { 0, 00, 10 }
D) { 0, 10, 01 }

25.
What is the value of the following prefix notation arithmetic expression: - 5 / * 6 2 - 5 3
A) -1
B) 0
C) 1
D) none of the above