Exam 11: Trees

Every 3-ary tree with 13 vertices has leaves.

If T is a full binary tree with 50 leaves, its minimum height is .

Use the merge sort to sort the list 3, 8, 12, 4, 1, 5, 9, 6 in increasing order.

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

Find a spanning tree for the graph K3,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.)

Prove that if T is a full m-ary tree with l leaves, then T has (ml − 1)/(m − 1) vertices.

Is the code given by $c : 00 , h : 10 , d : 1101 , e : 101 , z : 111 \text { a prefix code? }$

Every full binary tree with 45 vertices has internal vertices.

There are full 3-ary trees with 6 vertices.

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.

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.

Draw all nonisomorphic trees with 5 vertices.

There are non-isomorphic rooted trees with four vertices.

If T is a tree with 999 vertices, then T has edges.

A full 3-ary tree with 13 internal vertices has vertices.

Use the merge sort to sort the list 4,8,6,1,5,7,3,2 in increasing order.

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