Exam 11: A: Trees

fill in the blanks. -The best comparison-based sorting algorithms for a list of n items have complexity O( ____ ).

fill in the blanks. -C₇ has ____ spanning trees.

Use the bubble sort to sort the list 5, 2, 3, 1, 4 in increasing order.

Draw all nonisomorphic rooted trees with 4 vertices.

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

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

fill in the blanks. -The bubble sort has complexity O( ____ ).

If two trees have the same number of vertices and the same degrees, then the two trees are isomorphic.

If T is a tree with 50 vertices, the largest degree that any vertex can have is 49.

refer to the tree -Find the preorder traversal.

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.

fill in the blanks. -Write 3n − (k + 5) in prefix notation: ____.

The string $- \cdot 2 - x a + 4 y$ is prefix notation for an algebraic expression. Write the expression in postfix notation.

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.

The string $2\ 3\ a \cdot x + 4 \uparrow + 7 \uparrow$ is postfix notation for an algebraic expression. Write the expression in infix notation.

The algebraic expression $/ - \uparrow - a \cdot 7\ c\ 3\ 4 \cdot 3\ b$ is written in prefix notation. Write the expression in postfix notation.

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.

fill in the blanks. -The value of the arithmetic expression whose prefix representation is − 5 / · 6 2 − 5 3 is ____.

Find the value of $- \uparrow x \cdot 5 t / 4 - 7 c$ (in prefix notation) if $c = 5 , x = 2 , \text { and } t = 1$

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