10 Trees (EX)

Chapter 10
Trees
10.1 Introduction to Trees
1. Which of these graphs are trees?

2.
a) Which vertex is the root?
b) Which vertices are internal?
c) Which vertices are leaves?
d) Which vertices are children of j?
e) Which vertex is the parent of h?
f) Which vertices are siblings of o?
g) Which vertices are ancestors of m?
h) Which vertices are descendants of b?
i) Is the rooted tree a full m - ary tree for some positive integer m?
j) What is the level of each vertex of this rooted tree?
k) Draw the subtree of this tree that is rooted at
a) a. b) c. c) e.
3. a) How many edges does a tree with 10,000 vertices have?

b) How many vertices does a full 5-ary tree with 100 internal
vertices have?
c) How many edges does a full binary tree with 1000 internal
vertices have?
d) How many leaves does a full 3-ary tree with 100 vertices
have?
4. Construct a complete binary tree of height 4 and a complete 3-

ary tree of height 3.
10.2 Applications of Trees
5. Build a binary search tree for the words banana, peach, apple,
pear, coconut, mango, and papaya using alphabetical order.
6. How many comparisons are needed to locate or to add each of
these words in the search tree for Exercise 5, starting fresh each
time?
a) pear
b) banana
c) kumquat
d) orange
7. a) How many weighings of a balance scale are needed to find
a counterfeit coin among four coins if the counterfeit coin may be
either heavier or lighter than the others?
b) How many weighings of a balance scale are needed to find a
counterfeit coin among 12 coins if the counterfeit coin is lighter
than the others?
8. Find the least number of comparisons needed to sort four
elements and devise an algorithm that sorts these elements
using this number of comparisons.
9. Which of these codes are prefix codes?
a) a: 11, e: 00, t: 10, s: 01
b) a: 0, e: 1, t: 01, s: 001
c) a: 101, e: 11, t: 001, s: 011, n: 010
d) a: 010, e: 11, t: 011, s: 1011, n: 1001, i: 10101

10. Construct the binary tree with prefix codes representing these
coding schemes.
a) a: 11, e: 0, t: 101, s: 100
b) a: 1, e: 01, t: 001, s: 0001, n: 00001
c) a: 1010, e: 0, t: 11, s: 1011, n: 1001, i: 10001
11. What are the codes for a, e, i, k, o, p, and u if the coding
scheme is represented by this tree?
12. Given the coding scheme a: 001, b: 0001, e: 1, r: 0000, s: 0100,
t: 011, x: 01010, find the word represented by
a) 01110100011.
b) 0001110000.
c) 01100101010.
13. Use Huffman coding to encode these symbols with given
frequencies: a: 0.20, b: 0.10, c: 0.15, d: 0.25, e: 0.30. What is the
average number of bits required to encode a character?
14. Use Huffman coding to encode these symbols with given
frequencies: A: 0.10, B: 0.25, C: 0.05, D: 0.15, E: 0.30, F: 0.07,
G: 0.08. What is the average number of bits required to encode a
symbol?
10.3 Tree Traversal
15. Construct the universal address system for the given
ordered rooted tree. Then use this to order its vertices using
the lexicographic order of their labels
10.3 Tree Traversal
16. In which order are the vertices of the ordered rooted tree visited
using:
a) A preorder traversal?
b) An inorder traversal?
c) A postorder traversal?
10.3 Tree Traversal
17. a) Represent the expression ((x + 2) ↑ 3) ∗ (y −(3 + x)) − 5
using a binary tree.
Write this expression in
b) prefix notation.
c) postfix notation.
d) infix notation.
10.3 Tree Traversal
18. a) Represent the expression ¬(p ∧ q) ↔ (¬p ∨ ¬q) using a
binary tree.
Write this expression in
b) prefix notation.
c) postfix notation.
d) infix notation.
10.3 Tree Traversal
19. Draw the ordered rooted tree corresponding to each of
these arithmetic expressions written in prefix notation. Then
write each expression using infix notation.
a) + ∗ + − 5 3 2 1 4 b) ∗ / 9 3 + ∗ 2 4 − 7 6
10.3 Tree Traversal
20. What is the value of each of these prefix expressions?
a) − ∗ 2 / 8 4 3 b) ↑ − ∗ 3 3 ∗ 4 2 5
10.3 Tree Traversal
21. What is the value of each of these postfix expressions?
a) 5 2 1 − − 3 1 4 ++ ∗ b) 9 3 / 5 + 7 2 − ∗
10.4 Spanning trees
22. How many edges must be removed from a connected
graph with n vertices and m edges to produce a spanning tree?
10.4 Spanning trees
23. Find a spanning tree for the graph shown by removing edges
in simple circuits.
10.4 Spanning trees
24. Find a spanning tree for each of these graphs.
a) K5 b) K 4,4 c) K1,6 d ) Q3 e) C5 f ) W5
10.4 Spanning trees
25. Draw all the spanning trees of the given simple graphs.
10.4 Spanning trees
26. Use depth-first search and breadth-first search to produce
a spanning tree for the given simple graph. Choose a as the root
of this spanning tree and assume that the vertices are ordered
alphabetically.
10.4 Spanning trees
27. Use depth-first search and breadth-first search to find a
spanning tree of each of these graphs.
a) W6 starting at the vertex of degree 6
b) K 5
c) K 3,4 , starting at a vertex of degree 3
d) Q3
10.5 Minimum Spanning Trees
28. The roads represented by this graph are all unpaved. The
lengths of the roads between pairs of towns are represented
by edge weights. Which roads should be paved so that there
is a path of paved
roads between each
pair of towns so that
a minimum road
length is paved?
(Note: These towns
are in Nevada.)
10.5 Minimum Spanning Trees
29. Use Prim’s algorithm and Kruskal’s algorithm to find a minimum
spanning tree for the given weighted graph.

10 Trees (EX)

Uploaded by

Copyright:

Available Formats

10 Trees (EX)

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

10 Trees (EX)

Uploaded by

Copyright:

Available Formats

Chapter 10

1. Which of these graphs are trees?

3. a) How many edges does a tree with 10,000 vertices have?

4. Construct a complete binary tree of height 4 and a complete 3-

a) a: 11, e: 00, t: 10, s: 01

c) a: 101, e: 11, t: 001, s: 011, n: 010

d) a: 010, e: 11, t: 011, s: 1011, n: 1001, i: 10101

You might also like