Deck 11: Trees

Question 1

Is the code

Answer 1

This is a prefix code since the code for A, 11, does not start the code for B or the code for C; the code for B, 10, does not start the code for A or the code for C; and the code for C, 0, does not start the code for A or the code for B.

Question 2

Use a depth-first search to find a spanning tree of the following graph. Start at the vertex a, and use alphabetical order.

Answer 2

The edges produced by a depth-first search are and {b, g}.

Question 3

Find a minimum spanning tree in the following weighted graph using Prim's algorithm.

Answer 3

Prim's algorithm adds the edges {d, e} of weight 1, {e, h} of weight 1, {e, f} of weight 2, {d, g} of weight 3, {g, a} of weight 2, {a, b} of weight 2, {b, c} of weight 3, and {c, i} of weight 3. The total weight of the minimum spanning tree is 17.

Question 4

Construct an expression tree for and write this expression is prefix form and postfix form.

Question 5

(a) Suppose that a full 3-ary tree has 100 internal vertices. How many leaves does it have? (b) Suppose that a full 4-ary tree has 100 leaves. How many internal vertices does it have?

Question 6

Form a binary search tree from the words of the sentence This test is not so difficult, using alphabetical order, inserting words in the order they appear in the sentence.

Question 7

Perform a preorder, inorder, and postorder traversal of the rooted tree below.

Question 8

Use Prim's algorithm to find a minimum spanning tree for the following weighted graph. Use alphabetical

Question 9

Which of the following graphs are trees ? Explain your answers.

Question 10

A tree has 99 edges. How many vertices does it have?

Question 11

Use backtracking to find a sum of integers in the set {18, 19, 23, 25, 31} that equals 44.

Question 12

How many nonisomorphic trees are there with four vertices? Draw them.

Question 13

Is the code A: 111, B: 101, C: 011, D: 010, E: 10, F: 1101 a prefix code?