Exam 11: A: Trees

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

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

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

fill in the blanks. -The largest number of leaves in a binary tree of height 5 is ____.

Is the following code a prefix code: A: 11, B: 10, C: 0?

fill in the blanks. -If T is a tree, then its vertex-chromatic number is ____ and its region-chromatic number is ____.

refer to the tree -Find the inorder traversal.

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

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

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

fill in the blanks. -If T is a tree with 999 vertices, then T has ____ edges.

fill in the blanks. -Every full 3-ary tree of height 2 has at least ____ vertices and at most ____ vertices.

fill in the blanks. -There are ____ full binary trees with six vertices.

Is the code given by a : 0, m : 10, s : 110, t : 111 a prefix code?