- 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 77 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.
- What feature of heaps allows them to be efficiently implemented using a
partially filled array?
A. Heaps are binary search trees.
B. Heaps are binary trees.
C. Heaps are full binary trees.
D. Heaps contain only integer data.
E. None of these.
- 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[n/2]
B. data[n-1]
C. data[n]
D. data[2*n + 1]
E. None of these.
- Select the true statement about the worst-case time for operations on heaps.
A. Neither 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.
E. None of these.
- 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].priority.
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].priority < data[i].priority)
C. (i > 0) && (data[(i-1)/2].priority > data[i].priority)
D. (i > 0) || (data[(i-1)/2].priority <= data[i].priority)
E. None of these.
- 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 swap the out-of-place node with its parent.
C. The next step will swap the out-of-place node with its left child.
D. The next step will swap the out-of-place node with its right child.
E. None of these.
- Which formula is the best approximation for the depth of a heap with n nodes?
A. log2 n
B. log10 n
C. n
D. n2
E. None of these.
- 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. None of these.
- 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 total number of entries in all the nodes of the tree.
E. None of these.
Chapter 12
Here is an array with exactly 15 elements: 1 2 3
4 5 6 7 8 9
10 11 12 13 14
15. Suppose that we are doing a serial search for an element.
- Circle any elements that will be found by examining two or fewer numbers
from the array.
Here is an array with exactly 15 elements: 1 2 3
4 5 6 7 8 9
10 11 12 13 14
15
- Suppose that we are doing a binary search for an element. Circle any elements
that will be found by examining two or fewer numbers from the array.
- Draw a hash table with open addressing and a size of 9. Use the hash function
"k % 9". Insert the keys: 5, 29, 20, 0, 27 and 18 into your table (in that
order).
- Suppose you are building an open address hash table with double hashing.
The hash table capacity is n, so that the valid hash table indexes range from
0 to n-1. Fill in the blanks:
- In order to ensure that every array position is examined, the value
returned by the second hash function must be ________________________
with respect to n.
- One way to ensure this good behavior is to make n be _______________,
- and have the return value of the second hash function range from _________
to _________ (including the end points)
- You are writing code for the remove member function of a chained hash table.
Fill in the blanks in this pseudocode with the two missing statements. You
may use pseudocode yourself, or write actual C++ code:
void Table::remove(int key)
{
Node * cursor;
size_t i;
1. i = hash(key);
2. Make cursor point to the node that contains an item with the given key
(or set it to NULL if there is no such node).
3. if (cursor != NULL)
{
3a. _____________________________________________________________
3b. _____________________________________________________________
}
}
- Draw a hash table with chaining and a size of 9. Use the hash function "k
% 9" to insert the keys 5, 29, 20, 0, and 18 into your table.
- Suppose that I have the following RecordType definition for a record in
a hash table:
struct RecordType
{
int key;
... other stuff may also appear here
...
};
The hash table uses open addressing with linear probing. The table size is a
global constant called CAPACITY. Locations of the table that have NEVER been
used will contain the key -1. Locations of the table that were once used but
are now vacant will contain the key -2. All valid keys will be non-negative,
and the hash function is as follows:
size_t hash(int key)
{
return (key % CAPACITY);
}
- What is the worst-case time for serial search finding a single item in an
array?
A. Constant time
B. Logarithmic time
C. Linear time
D. Quadratic time
E. None of these.
- What is the worst-case time for binary search finding a single item in an
array?
A. Constant time
B. Logarithmic time
C. Linear time
D. Quadratic time
E. None of these.
- What additional requirement is placed on an array, so that binary search
may be used to locate an entry?
A. The array elements must form a heap.
B. The array must have at least 2 entries.
C. The array must not be sorted.
D. The array's size must be a power of two.
E. None of these.
- What is the best definition of a collision in a hash table?
A. Two entries are identical except for their keys.
B. Two entries with different data have the exact same key.
C. Two entries with different keys have the same exact hash value.
D. Two entries with the exact same key have different hash values.
E. None of these.
- In an open-address hash table there is a difference between those spots
which have never been used and those spots which have previously been used
but no longer contain an item. Which function has a better implementation
because of this difference?
A. insert
B. is_present
C. remove
D. Two or more of the above functions
E. None of these.
- What kind of initialization needs to be done for an open-address hash table?
A. None.
B. The key at each array location must be initialized.
C. The head pointer of each chain must be set to NULL.
D. Both B and C must be carried out.
E. None of these.
- What kind of initialization needs to be done for a chained hash table?
A. None.
B. The key at each array location must be initialized.
C. The head pointer of each chain must be set to NULL.
D. Both B and C must be carried out.
E. None of these.
- A chained hash table has an array size of 512. What is the maximum number
of entries that can be placed in the table?
A. 256
B. 512
C. 1024
D. There is no maximum.
E. None of these.
- Suppose you place m items in a hash table with an array size of s. What
is the correct formula for the load factor?
A. 1/2 * (1 + 1/(1 - s / m))
B. s - m
C. m / s
D. m * s
E. None of these.
Chapter 13
Here is an array of ten integers: 5 3 8 9
1 7 0 2 6 4
- Draw this array after the FIRST iteration of the large loop in a selection
sort (sorting from smallest to largest).
Here is an array of ten integers: 5 3 8 9 1
7 0 2 6 4
- Draw this array after the FIRST iteration of the large loop in an insertion
sort (sorting from smallest to largest). This iteration has shifted at least
one item in the array!
Suppose that you are writing a program that has the usual selectionsort
function available:
void selectionsort(int data[ ], size_t n);
- Your program also has an integer array called x, with 10 elements. Write
two function calls: The first call uses selectionsort to sort all of x; the
second call uses selectionsort to sort x[3]..x[9].
- Describe a case where quicksort will result in quadratic behavior.
Here is an array which has just been partitioned by the first step of quicksort
3, 0, 2, 4, 5, 8, 7, 6, 9
- Which of these elements could be the pivot? (There may be more than one
possibility!)
Here is an array of ten integers: 5 3 8 9 1
7 0 2 6 4. Suppose we partition this array using
quicksort's partition function and using 5 for the pivot.
- Draw the resulting array after the partition finishes.
Here is an array of ten integers: 5 3 8 9 1
7 0 2 6 4
- Draw this array after the TWO recursive calls of merge sort are completed,
and before the final merge step has occurred.
- Fill in the following table for the times to sort an array of n items. Use
only big-O notation, and do not have any extraneous constants in your expressions.
|
Average Case |
Worst Case |
Binary Search of a sorted array |
|
|
Insertion sort |
|
|
Merge sort |
|
|
Quick sort without "median of three" pivot selection |
|
|
Selection sort |
|
|
Heap sort |
|
|
Suppose that you are writing a program that has these two functions available:
int compare_ints(const void * p1, const void * p2);
// Precondition: p1 and p2 are really pointers to integers.
// Postcondition: The return value is:
// (a) negative if *p1 < *p2
// (b) zero if *p1 == *p2
// (c) positive if *p1 > *p2
void qsort(
void * base,
size_t n,
size_t bytes,
int compar(const void *, const void *)
);
// Same specification as the standard library qsort function.
- Your program also has an integer array called x, with 10 elements. Write
two function calls: The first call uses qsort to sort all of x; the second
call uses qsort to sort x[3]..x[9].
- In a selectionsort of n elements, how many times is the swap function called
in the complete execution of the algorithm?
A. 1
B. n - 1
C. n log n
D. n²
E. None of these.
- Selectionsort and quicksort both fall into the same category of sorting
algorithms. What is this category?
A. O(n log n) sorts
B. Divide-and-conquer sorts
C. Interchange sorts
D. Average time is quadratic.
E. None of these.
- Suppose that a selectionsort of 100 items has completed 42 iterations of
the main loop. How many items are now guaranteed to be in their final spot
(never to be moved again)?
A. 5
B. 42
C. 226
D. 1764
E. None of these.
- Suppose we are sorting an array of ten integers using a some quadratic sorting
algorithm. After four iterations of the algorithm's main loop, the array elements
are ordered as shown here:
1 2 3 4 5 0 6 7 8 9
Which statement is correct? (Note: Our selectionsort picks largest items first.)
A. The algorithm might be either selectionsort or insertionsort.
B. The algorithm might be selectionsort, but could not be insertionsort.
C. The algorithm might be insertionsort, but could not be selectionsort.
D. The algorithm is neither selectionsort nor insertionsort.
E. None of these.
- Suppose we are sorting an array of eight integers using a some quadratic
sorting algorithm. After four iterations of the algorithm's main loop, the
array elements are ordered as shown here:
2 4 5 7 8 1 3 6
Which statement is correct? (Note: Our selectionsort picks largest items
first.)
A. The algorithm might be either selectionsort or insertionsort.
B. The algorithm might be selectionsort, but it is not insertionsort.
C. The algorithm is not selectionsort, but it might be insertionsort.
D. The algorithm is neither selectionsort nor insertionsort.
E. None of these.
- When is insertionsort a good choice for sorting an array?
A. Each component of the array requires a large amount of memory.
B. Each component of the array requires a small amount of memory.
C. The hard drive is slow.
D. The processor speed is fast.
E. None of these.
- What is the worst-case time for mergesort to sort an array of n elements?
A. O(log n)
B. O(n)
C. O(n log n)
D. O(n²)
E. None of these.
- What is the worst-case time for quicksort to sort an array of n elements?
A. O(log n)
B. O(n)
C. O(n log n)
D. O(n²)
E. None of these.
- Mergesort makes two recursive calls. Which statement is true after these
recursive calls finish, but before the merge step?
A. The array elements form a heap.
B. Elements in the second half of the array are less than or equal to elements
in the first half of the array.
C. Elements in the first half of the array are less than or equal to elements
in the second half of the array.
D. The algorithm is complete.
E. None of these.
- What is the worst-case time for heapsort to sort an array of n elements?
A. O(log n)
B. O(n)
C. O(n log n)
D. O(n²)
E. None of these.
Chapter 14
- Throughout this section A is a class and B is a new class derived from A.
Also, we have these variables
A a;
B b;
B b1;
B b2;
- What C++ syntax is used to declare that a class B is derived from class
A?
A. class A derives B { ... };
B. class B from A { ... };
C. class B : class A { ... };
D. class B subclass of A { ... };
E. None of these.
- If a class B is derived from A, then which of the following terms describes
A?
A. ancestor class.
B. base class.
C. parent class.
D. All of the above.
E. None of these.
- Consider the assignment statement a=b; (with the variable declarations at
the top of this section). Which answer is true?
A. The assignment statement is illegal.
B. The assignment statement activates the A assignment operator.
C. The assignment statement activates the B assignment operator.
D. The assignment statement activates both A and B assignment operators.
E. None of these.
- Consider the assignment statement b=a; (with the variable declarations at
the top of this section). Which answer is true?
A. The assignment statement is illegal.
B. The assignment statement activates the A assignment operator.
C. The assignment statement activates the B assignment operator.
D. The assignment statement activates both A and B assignment operators.
E. None of these.
- What is the term used to describe the situation when a derived class provides
a function already provided in the base class?
A. Inheriting.
B. Overriding.
C. Overloading.
D. Instantiating.
E. None of these.
- Consider the declarations at the top of this section. Suppose there are
two functions: f has an argument of type A and g has an argument of type B.
Which statement is correct?
A. Both f(b) and g(b) are legal function calls.
B. f(b) is legal, but g(b) is not legal.
C. f(b) is not legal, but g(b) is legal.
D. Neither f(b) nor g(b) is a legal function function call.
E. None of these.
- Consider the declarations at the top of this section. Suppose there are
two functions: f has an argument of type A and g has an argument of type B.
Which statement is correct?
A. Both f(a) and g(a) are legal function calls.
B. f(a) is legal, but g(a) is not legal.
C. f(a) is not legal, but g(a) is legal.
D. Neither f(a) nor g(a) is a legal function function call.
E. None of these.
- Suppose you were going to quickly implement a Stack class. What class would
be the best base class?
A. Bag.
B. List.
C. Queue.
D. Table.
E. None of these.
- Suppose you were going to quickly implement a Stack class as a derived class.
Why would it be likely that the base class would be a private base class?
A. You would not want to have all of the base classes private member
functions be private member functions of the stack.
B. You would not want to have all of the base classes private member functions
be public member functions of the stack.
C. You would not want to have all of the base classes public member functions
be private member functions of the stack.
D. You would not want to have all of the base classes public member functions
be public member functions of the stack.
E. None of these.
- Complete the implementation of the following function. There is no need
to check the precondition, but your code must be as efficient as possible.
bool key_occurs(const RecordType data[ ], int search_key)
// Precondition: data[0]...data[CAPACITY-1] is an open address hash table
// as described above.
// Postcondition: If search_key occurs as a key of a record in the table,
// then the function returns true; otherwise the function returns false.