Sample Data Structures Questions
Chapter 11
Trees Projects
Data Structures and Other Objects Using C++
by
Michael Main
and
Walter Savitch
Second Edition ISBN 0201702975, Softcover, 816 pages, 2000
The Purpose of These Questions
These are typical exam questions from Chapter 11 of the textbook. These
exact questions might not be on your exam, but if you research and find
the right answers to these questions, that should be good preparation
for a real exam. (It's also possible that some of this material was
not covered in your class.) At the moment there are
14 short answer questions
and
12 multiple choice questions
in this file.
Short Answers
Short Answers Section 11.1 Heaps


Suppose that we want to create a heap where each node contains
information of some data type
called Item (which has a default constructor and a correct value semantics).
What additional factor is required for the Item data type?

A heap is a binary tree where the entries can be compared using the usual
six comparison operations (that form a total
order semantics). Write the two rules that the binary tree must follow
in order for the structure to actually be a heap.

Give two different reasons to explain why the following binary tree is not
a heap:
91
/ \
77 46
/ \ \
68 81 11

Draw a new heap that is created by inserting 82 into the following heap:
910
/ \
77 66
/ \ / \
68 1 3 11

Draw a new heap that is created by removing one item from the following heap:
910
/ \
77 66
/ \ / \
68 1 3 11

Suppose that you are performing a reheapification downward. Write a precise
condition that describes the situation that causes the reheapification
to stop.

Suppose that you are performing a reheapification upward. Write a precise
condition that describes the situation that causes the reheapification
to stop.
Short Answers Section 11.2 BTrees


Suppose that a nonleaf node in a Btree contains 42 entries. How many children
does the node have?

Draw an example of a Btree with four nodes and seven integer entries. The value
of MINIMUM is 1 for this tree.

Draw a new Btree that is created by inserting 82 into the following Btree.
For this example, the minimum number of items in each node is 1. Note that
the rightmost leaf starts with two entries, 71 and 93.
56
/ \
7 66
/ \ / \
2 8 63 71 and 93

Draw a new Btree that is created by deleting 63 from the following Btree.
For this example, the minimum number of items in each node is 1. Note that
the rightmost leaf starts with two entries, 71 and 93.
56
/ \
7 66
/ \ / \
2 8 63 71 and 93

Suppose that a Btree is declared so that MAXIMUM (the maximum
number of items in a node) is 84. What is the value of MINIMUM (the minimum
number of items in a nonroot node)?

Suppose that a Btree is declared so that MAXIMUM (the maximum
number of items in a node) is 84. Write one clear sentence to describe why
each node's data array is set up to hold up to 85 items (one more than
MAXIMUM).
Short Answers Section 11.3 Trees, Logs, and Time Analysis


Suppose that a and b are two positive integers and n is some nonnegative
number. Write an equation to show the relationship between
log base a of n and log base b of n. Give a derivation to show that the
relationship is valid.
Multiple Choice
Multiple Choice Section 11.1 Heaps


What feature of heaps allows them to be efficiently implemented using
a partially filled array?
 A. Heaps are binary search trees.
 B. Heaps are complete binary trees.
 C. Heaps are full binary trees.
 D. Heaps contain only integer data.

If a heap is implemented using a partially filled array called data, and the
array
contains n elements (n > 0), where is the entry with
the greatest value?
 A. data[0]
 B. data[n1]
 C. data[n]
 D. data[2*n + 1]
 E. data[2*n + 2]

Select the true statement about the worstcase time for operations on heaps.
 A. Niether insertion nor removal is better than linear.
 B. Insertion is better than linear, but removal is not.
 C. Removal is better than linear, but insertion is not.
 D. Both insertion and removal are better than linear.

Suppose that we have implemented a priority queue by storing the items in
a heap (using an array for the heap items). We are now
executing a reheapification upward and the
outofplace node is at data[i] with priority given by data[i].
Which of the following boolean expressions is TRUE to indicate that
the reheapification IS NOT YET DONE.
 A. (i > 0)
 B. (data[(i1)/2] < data[i])
 C. (i > 0) && (data[(i1)/2] < data[i])
 D. (i > 0)  (data[(i1)/2] < data[i])

Suppose that we have implemented a priority queue by storing the items in
a heap. We are now
executing a reheapification downward and the
outofplace node has priority of 42. The node's parent has a priority
of 72, the left child has priority
52 and the node's right child has priority 62.
Which statement best describes the status of the reheapification.
 A. The reheapification is done.
 B. The next step will interchange the two children of the outofplace
node.
 C. The next step will swap the outofplace node with its parent.
 D. The next step will swap the outofplace node with its left child.
 E. The next step will swap the outofplace node with its right child.

Which formula is the best approximation for the depth of a heap with
n nodes?
 A. log (base 2) of n
 B> The number of digits in n (base 10)
 C. The square root of n
 D. n
 E. The square of n
Multiple Choice Section 11.3 Btrees


Which statement is true for a Btree?
 A. All entries of a node are greater than or equal to the entries
in the node's children.
 B. All leaves are at the exact same depth.
 C. All nodes contain the exact same number of entres.
 D. All nonleaf nodes have the exact same number of children.

Suppose that a nonleaf node in a Btree has 41 entries. How many children
will this node have?
 A. 2
 B. 40
 C. 41
 D. 42
 e. 82

Suppose that a Btree has MAXIMUM of 10 and that a node already
contains the integers 1 through 10. If a new value, 11, is added to this
node, the node will split into two pieces. What values will be in these two
pieces?
 A. The first piece will have only 1 and the
second piece will have the rest of the numbers.
 B. The first piece will have 1 through 5 and
the second piece will have 6 through 11.
 C. The first piece will have 1 through 5 and
the second piece will have 7 through 11.
 D. The first piece will have 1 through 6 and
the second piece will have 7 through 11.
 E. The first piece will have 1 through 10 and
the second piece will have only 11.

Suppose that X is a Btree leaf containing 41 entries and having
at least one sibling. Which statement is true?
 A.
Any sibling of X is also a leaf.
 B.
Any sibling of X contains at least 41 entries.
 C.
The parent of X has exactly 42 entries.
 D.
X has at least 41 siblings.
Multiple Choice Section 11.3 Trees, Logs, and Time Analysis


Suppose you run a O(log n) algorithm with an input size of 1000 and
the algorithm requires 110 operations. When you double the input size to
2000, the algorithm now requires 120 operations. What is your best guess
for the number of operations required when you again double the input
size to 4000?
 A. 130
 B. 140
 C. 150
 D. 160
 E. 170

Tree algorithms typically run in time O(d) . What is d?
 A. The depth of the tree.
 B. The number of divisions at each level.
 C. The number of entries in each node.
 D. The number of nodes in the tree.
 E. The total number of entries in all the nodes of the tree.
Data Structures and Other Objects Using C++
Michael Main
(main@colorado.edu)
and
Walter Savitch
(wsavitch@ucsd.edu)
Thank you for visiting
http://www.cs.colorado.edu/~main/questions/chap11q.html
Copyright © 2000
AddisonWesley Computer and Engineering Publishing Group