Exam 11: A: Trees

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

refer to the tree -Find the postorder traversal.

No tree has a Hamilton path.

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

(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.

fill in the blanks. -If T is a full binary tree with 101 vertices, its maximum height is ____.

Find the inorder traversal of the parsing tree for $( 8 x - y ) ^ { 5 } - 7 \sqrt { 4 z - 3 }$

fill in the blanks. -A full 3-ary tree with 13 internal vertices has ____ vertices.

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

Every tree is bipartite.

fill in the blanks. -There are ____ non-isomorphic rooted trees with four vertices.

Draw all nonisomorphic trees with 5 vertices.

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

Find a spanning tree for the graph K_3,4 using a depth-first search. (Assume that the vertices are labeled $u_{1}, u_{2}, u_{3}$ in one set and $v_{1}, v_{2}, v_{3}, v_{4}$ in the other set, and that alphabetical ordering is used in the search, with numerical ordering on the subscripts used to break ties.)

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 depth-first search.

Suppose T is a full m-ary tree with i internal vertices. Prove that T has 1 + (m − 1)i leaves.

fill in the blanks. -Every full binary tree with 61 vertices has ____ leaves.

Write the compound proposition $( \neg p ) \rightarrow ( q \vee ( r \wedge \neg s ) )$ in postfix notation.

There is a tree with degrees 3, 2, 2, 2, 1, 1, 1, 1, 1.

Suppose that the universal address set address of a vertex v in an ordered rooted tree is 3.2.5.1.5. Find (a) the level of v. (b) the minimum number of siblings of v. (c) the address of the parent of v. (d) the minimum number of vertices in the tree.