Homework 7: Graphs (sections 4, 5, and 6) and Trees

1. (2 points) How many strongly connected components does the directed graph specified by the following adjacency matrix have?

Adj. Matrix: a -> (b), b -> (d), c -> (b), d -> (c), e -> (a, f, h), f -> (d, g), g -> (e), h -> (g)

a. 0

b. 1

c. 2

*d. 3

2. (2 points) Below is part of an undirected graph. Even though you can only see some of the vertices and edges, can you deduce whether the graph will have an Euler path or circuit?

Adj. Matrix: a -> (b, c, e), b -> (a, f, g), c -> (a, h), e -> (a, i, j)

a. It will have both an Euler path and an Euler circuit, as it is a tree.
b. It will not have an Euler circuit since it has a vertex of odd degree, but it might have an Euler path.

*c. It will not have an Euler path or an Euler circuit, since it has too many vertices with odd degree.

d. It will have both an Euler path but not an Euler circuit, since it has three vertices with odd degree.

3. (2 points) What is the prefix form for the following expression ((x + y) / 4) - (7 * (x - y))?
a. - + x y 4 / 7 * - x y
b. - + 4 x / y * 7 - x y
*c. - + x y / 4 * 7 - x y
d. - + x / y 4 * 7 x y -

4. (2 points) What is the postfix form for the following expression ((x + y) / 4) - (7 * (x - y))?
*a. x y + 4 / 7 x y - * -
b. x y + 4 / 7 - x y * -
c. - + x y * 4 7 - x y
d. - x y + 4 * 7 x y -

5. (2 points) What is the value of the postfix expression 8 3 2 * - 2 ^ 10 2 / + ?

a. 38
b. 20
c. 12
*d. 9

6. (2 points) If we have a complete binary tree with four levels (including the root), how many edges does it have?
*a. 14
b. 8
c. 15
d. 6

7. (2 points) If we have a binary tree with 7 levels (including the root), what is the least number of leaves we can have in level 7?
*a. 1
b. 32

c. 64
d. 128

8. (2 points) If a graph has no simple circuits, n vertices, and n - 1 edges, we know that it is:
*a. a tree
b. a complete graph
c. a binary tree
d. a complete tree

9. (2 points) Which of the following is a valid prefix coding scheme?
a. a = 01, b = 00, c = 001, d = 011, e = 111
b. a = 001, b = 000, c = 110, d = 01, e = 11
c. a = 001, b = 000, c = 101, d = 00, e = 11
*d. a = 001, b = 000, c = 101, d = 01, e = 11

10. (2 points) Consider the following Huffman code: a = 111, b = 110, d = 010, f = 10, g = 00, r = 011. What alphabetical string do the digits 1101110111011011100 represent?
a. barddab
*b. barfbag
c. arfbrag
d. badgarf