552
Graphs and Trees
Section 6.3
1. The root of a decision tree for the binary search
algorithm acting on a sorted list of 11 items would
represent the comparison of the target element with
the sixth list item.
2. Searching for any target element x in a list of n elements requires at least 1 + :log n; comparisons.
3. A binary tree search is done with a target element
of 14 on a binary search tree whose root has the
value 10; the right subtree will be searched next.
4. A binary search tree is unique for any given set of
data.
5. A decision tree for sorting n elements must have a
depth of at least n!
Section 6.4
1. The ASCII encoding scheme requires 8 bits to store
each character.
2. In a prefix code, each code word is the prefix of
another code word.
3. In a Huffman code, characters that occur most frequently have the most 0s in their binary string representation.
4. The maximum number of bits for any encoded
character using a Huffman code will be the depth
of the Huffman tree.
5. To be able to decode an encoded file, a frequency
count from the original file must be stored along
with the encoded file.
O n t h e C O m p u t e r
For Exercises 1–4, write a computer program that produces the desired output from the given input.
1. Input: Adjacency list for a graph
Output: Adjacency matrix for the graph
2. Input: Adjacency matrix for a graph
Output: Adjacency list for the graph
3. Input: Adjacency list for a graph and the name of a
node n in the graph
Output: Adjacency list for the graph with node n
and its associated arcs removed
4. Input: List of n characters and their (integer) frequencies
Output: Huffman code for the characters
(Hint: Maintain a sorted linked list of records that represent the roots of binary trees. Initially there will be n
such records, each with no children; at the end, there
will be one such record, the root of the Huffman tree.)
5. Write a program that allows the user to enter a list
of integers and constructs a binary search tree with
those integers as nodes. The user can then enter one
integer at a time, and the program will do a binary
tree search and indicate whether the given integer
is in the list.
6. Write a program that allows the user to enter a list
of integers and then constructs a binary search tree
with those integers as nodes. The user can then enter the type of traversal desired (inorder, preorder,
or postorder), and the program will write out the
nodes in the appropriate order.
7. Write a program that carries out the first three steps
in Table 6.1. That is, beginning with a text file, the
program should produce a frequency count file, then
nal file. Write a second program that uses the encoded file and the code table, and recreates the original
file.
Graphs and Trees
Section 6.3
1. The root of a decision tree for the binary search
algorithm acting on a sorted list of 11 items would
represent the comparison of the target element with
the sixth list item.
2. Searching for any target element x in a list of n elements requires at least 1 + :log n; comparisons.
3. A binary tree search is done with a target element
of 14 on a binary search tree whose root has the
value 10; the right subtree will be searched next.
4. A binary search tree is unique for any given set of
data.
5. A decision tree for sorting n elements must have a
depth of at least n!
Section 6.4
1. The ASCII encoding scheme requires 8 bits to store
each character.
2. In a prefix code, each code word is the prefix of
another code word.
3. In a Huffman code, characters that occur most frequently have the most 0s in their binary string representation.
4. The maximum number of bits for any encoded
character using a Huffman code will be the depth
of the Huffman tree.
5. To be able to decode an encoded file, a frequency
count from the original file must be stored along
with the encoded file.
O n t h e C O m p u t e r
For Exercises 1–4, write a computer program that produces the desired output from the given input.
1. Input: Adjacency list for a graph
Output: Adjacency matrix for the graph
2. Input: Adjacency matrix for a graph
Output: Adjacency list for the graph
3. Input: Adjacency list for a graph and the name of a
node n in the graph
Output: Adjacency list for the graph with node n
and its associated arcs removed
4. Input: List of n characters and their (integer) frequencies
Output: Huffman code for the characters
(Hint: Maintain a sorted linked list of records that represent the roots of binary trees. Initially there will be n
such records, each with no children; at the end, there
will be one such record, the root of the Huffman tree.)
5. Write a program that allows the user to enter a list
of integers and constructs a binary search tree with
those integers as nodes. The user can then enter one
integer at a time, and the program will do a binary
tree search and indicate whether the given integer
is in the list.
6. Write a program that allows the user to enter a list
of integers and then constructs a binary search tree
with those integers as nodes. The user can then enter the type of traversal desired (inorder, preorder,
or postorder), and the program will write out the
nodes in the appropriate order.
7. Write a program that carries out the first three steps
in Table 6.1. That is, beginning with a text file, the
program should produce a frequency count file, then
nal file. Write a second program that uses the encoded file and the code table, and recreates the original
file.