Exam 11: Trees

refer to this graph. -Using alphabetical ordering, find a spanning tree for this graph by using a breadth-first search.

Every full 3-ary tree of height 2 has at least vertices and at most vertices.

Use Prim's algorithm to find a minimal spanning tree for this weighted graph. Use alphabetical order to break ties.

refer to the tree at the right. -Find the postorder traversal.

(a) Set up a binary tree for the following list, in the given order, using alphabetical ordering: STOP, LET, THERE, TAPE, NONE, YOU, ANT, NINE, OAT, NUT. (b) Explain step by step how you would search for the word TEST in your tree. (c) What is the height of the shortest binary search tree that can hold all 10 words? (d) Write the preorder traversal of the tree. (e) Write the postorder traversal of the tree. (f) Write the inorder traversal of the tree.

mark the statement TRUE or FALSE. -No tree has a Hamilton path.

Find a spanning tree for the graph K3,4 using a breadth-first search. (Assume that the vertices are labeled u1, u2, u3 in one set and v1, v2, v3, v4 in the other set, and that alphabetical ordering is used in the search, with numerical ordering on the subscripts used to break ties.)

mark the statement TRUE or FALSE. -In a binary tree with 16 vertices, there must be a path of length 4.

refer to this graph. -Using alphabetical ordering, find a spanning tree for this graph by using a depth-first search.

mark the statement TRUE or FALSE. -If T is a tree with 17 vertices, then there is a simple path in T of length 17.

refer to this graph. -Using reverse alphabetical ordering, find a spanning tree for the graph by using a breadth-first search.

If T is a full binary tree with 101 vertices, its maximum height is .

The bubble sort has complexity $O(\underline{\quad})$

Use Huffman coding to encode these symbols with given frequencies: $a : 0.35 , b : 0.4 , c : 0.2 , d : 0.05 \text {. What is }$ the average number of bits required to encode a character?

refer to this graph. -Using the ordering C, D, E, F, G, H, I, J, A, B, C, find a spanning tree for this graph by using a breadth-first search.

The best comparison-based sorting algorithms for a list of n items have complexity $O$ ( $\underline{\quad\quad}$ )

Describe the difference between Prim's algorithm and Kruskal's algorithm for finding a spanning tree of minimum cost.

Suppose you have 5 coins, one of which is counterfeit (either heavier or lighter than the other four). You use a pan balance scale to find the bad coin and determine whether it is heavier or lighter. (a) Prove that 2 weighings are not enough to guarantee that you find the bad coin and determine whether it is heavier or lighter. (b) Draw a decision tree for weighing the coins to determine the bad coin (and whether it is heavier or lighter) in the minimum number of weighings.

The algebraic expression is written in prefix notation. Write the expression in postfix notation.

Find the preorder traversal.