0), where is the entry with
the greatest value?
- A. data[0]
- B. data[n-1]
- C. data[n]
- D. data[2*n + 1]
- E. data[2*n + 2]
Select the true statement about the worst-case 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
out-of-place 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[(i-1)/2] < data[i])
- C. (i > 0) && (data[(i-1)/2] < data[i])
- D. (i > 0) || (data[(i-1)/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
out-of-place 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 out-of-place
node.
- C. The next step will swap the out-of-place node with its parent.
- D. The next step will swap the out-of-place node with its left child.
- E. The next step will swap the out-of-place 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 B-trees
|
Which statement is true for a B-tree?
- 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 non-leaf nodes have the exact same number of children.
Suppose that a non-leaf node in a B-tree has 41 entries. How many children
will this node have?
- A. 2
- B. 40
- C. 41
- D. 42
- e. 82
Suppose that a B-tree 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 B-tree 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.