FiltersDone

Question type

Essay

Multiple Choice

Short Answer

True False

Matching

Exam 11: Trees

Show Answer

Share

---

All types

Filters

Study Flashcards

Question 21

Short Answer

Review LaterAdd Note

Review Later

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

Correct Answer

verified

Show Answer

Question 22

Short Answer

Review LaterAdd Note

Review Later

Suppose you have 5 coins, one of which is counterfeit (either heavier or lighter than the other four). You use a pan balance scale to find the bad coin and determine whether it is heavier or lighter. (a) Prove that 2 weighings are not enough to guarantee that you find the bad coin and determine whether it is heavier or lighter. (b) Draw a decision tree for weighing the coins to determine the bad coin (and whether it is heavier or lighter) in the minimum number of weighings.

Correct Answer

verified

Show Answer

Question 23

True/False

Review LaterAdd Note

mark the statement TRUE or FALSE. -In a binary tree with 16 vertices, there must be a path of length 4.

If T is a full binary tree with 101 vertices, its maximum height is .

Describe the difference between Prim's algorithm and Kruskal's algorithm for finding a spanning tree of minimum cost.

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

The best comparison-based sorting algorithms for a list of n items have complexity $O$ ( $\underline{\quad\quad}$ )

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

mark the statement TRUE or FALSE. -No tree has a Hamilton path.

refer to the tree at the right. -Find the postorder traversal.

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

Find the preorder traversal.

refer to this graph. -Using alphabetical ordering, find a spanning tree for this graph by using a breadth-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.

The algebraic expression is written in prefix notation. Write the expression in postfix notation.

mark the statement TRUE or FALSE. -If T is a tree with 17 vertices, then there is a simple path in T of length 17.

Every full 3-ary tree of height 2 has at least vertices and at most vertices.

Use Huffman coding to encode these symbols with given frequencies: $a : 0.35 , b : 0.4 , c : 0.2 , d : 0.05 \text {. What is }$ the average number of bits required to encode a character?

The bubble sort has complexity $O(\underline{\quad})$

Find a spanning tree for the graph K3,4 using a breadth-first search. (Assume that the vertices are labeled u1, u2, u3 in one set and v1, v2, v3, v4 in the other set, and that alphabetical ordering is used in the search, with numerical ordering on the subscripts used to break ties.)