Exam 11: Trees

Is the code given by $a : 0 , m : 10 , s : 110 , t : 111 \quad \text { a prefix code? }$

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

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.

mark the statement TRUE or FALSE. -If two trees have the same number of vertices and the same degrees, then the two trees are isomorphic.

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.

There are full binary trees with six vertices.

mark the statement TRUE or FALSE. -If T is a rooted binary tree of height 5, then T has at most 25 leaves.

Use Huffman coding to encode these symbols with given frequencies: a: 0.15, b: 0.35, c: 0.23, d: 0.22, e: 0.04, f: 0.01 . What is the average number of bits required to encode a character?

The value of the arithmetic expression whose prefix representation is $- 5 / .62 - 53 \text { is }$$\underline{\quad\quad}$

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

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

Every full binary tree with 50 leaves has vertices.

The largest number of leaves in a binary tree of height 5 is .

If each edge of $Q _ { 4 } \text { has weight } 1 \text {, then the cost of any spanning tree of minimum cost is }$$\underline{\quad\quad}$

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

Write the compound proposition $( \neg p ) \rightarrow ( q \vee ( r \wedge \neg s ) ) \text { in prefix notation. }$

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

The string $p r q \rightarrow \neg q \Delta p \rightarrow \wedge$ is postfix notation for a logic expression; however, there is a misprint. The triangle should be one of these three: $r _ { , } , \vee , \text { Or } \neg$ Determine which of these three it must be and explain your reasoning.

Draw a parsing tree for $( a - ( 3 + 2 b ) ) / \left( c ^ { 2 } + d \right)$

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