UNDER CONSTRUCTION
Computer Science 153
Introduction to Data Structures
Question Pool for Final Exam
Up to 25% of the questions on the Final Exam will come from exams 1, 2
and 3
One-third of the exam will involve writing the
C++ member functions listed at the end of the pool
Chapter 11
1. 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.
2. Give two different reasons to explain why the following binary tree
is not a heap:
91
/ \
77 46
/ \ \
68 81 11
3. Draw a new heap that is created by inserting 82 into the following heap:
910
/ \
77 66
/ \ / \
68 1 3 11
4. Draw a new heap that is created by removing 77 from the following heap:
910
/ \
77 66
/ \ / \
68 1 3 11
5. Suppose that you are performing a reheapification downward. Write a
precise condition that describes the situation that causes the reheapification
to stop.
6. Suppose that you are performing a reheapification upward. Write a
precise condition that describes the situation that causes the reheapification
to stop.
7. 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.
8. 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.
9. 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.
10. 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.
11. 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.
12. 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.
13. 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.
14. 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
1. 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.
2. 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.
3. Implement the body of the following function using a binary search
of the array. You do not need to check the precondition. All your local
variables must be size_t variables.
bool has_42(const int data[ ], size_t n)
// Precondition: The elements data[0]...data[n-1] are sorted from smallest
// to largest. The value of n might be zero (indicating an empty array).
// Postcondition: A true return value indicates that the number 42 appears in
// data[0]...data[n-1]. A false return value indicates that 42 doesn't appear.
4. 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).
5. 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).
6. 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. _____________________________________________________________
}
}
7. 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.
8. 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);
}
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.
9. Suppose that an open-address hash table has a capacity of 811 and it
contains 81 elements. What is the table's load factor? (An approximation
is fine.)
10. I plan to put 1000 items in a hash table, and I want the average
number of accesses in a successful search to be about 2.0.
A. About how big should the array be if I use open addressing with
linear probing? NOTE: For a load factor of A, the average number of accesses
is generally ½(1+1/(1-A)).
B. About how big should the array be if I use chained hashing? NOTE:
For a load factor of A, the average number of accesses is generally (1+A/2).
11. 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.
12. 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.
13. 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.
14. 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.
15. 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.
16. 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.
17. 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.
18. 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.
19. 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
1. 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).
2. 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!
3. 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].
4. Describe a case where quicksort will result in quadratic behavior.
5. 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!)
6. 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.
7. 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.
8. 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 |
|
|
Quick sort with "median of three" pivot selection |
|
|
Selection sort |
|
|
Heap sort |
|
|
9. 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].
10. 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.
11. 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.
12. 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.
13. 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.
14. 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.
15. 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.
16. 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.
17. 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.
18. 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.
19. 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
Describe one purpose of a member initialization list for a derived
class.
Describe the difference between a public base class and a private base
class.
Suppose that a derived class has a private base class. How is it possible
to to make some of the inherited members become public?
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.
You will be given all of the following class definitions on the exam.
Be prepared to write any of the member functions defined within the classes.
In the case of class Stack, write the requested member function without
using inheritance.
struct Node
{ Node * Next;
Node * Prev;
int Data;
}; |
class Stack
{public:
Stack();
~Stack();
void Push(int);
int Pop();
int Peek();
bool Empty();
bool Full();
private:
Node * Top;
}; |
class List //Forward-Backward List
{public:
List();
~List();
InsertHead(int);
InsertTail(int);
int RemoveHead(); //and return the value of
int RemoveTail(); //and
return the value of
int GetCurrent(); //return the value pointed
to by Current
bool Find(int); //if successful, leave
Current pointing to the
// Node found
private:
Node * Head;
Node * Tail;
Node * Current;
}; |
class BST //Binary Search Tree
{
public:
BST();
~BST();
void Insert(BNode *);
bool Find(BNode *);
private:
BNode * Root;
}; |
struct BNode // An abstract Node
{
virtual bool operator<(const BNode &)=0;
virtual bool operator==(const BNode &)=0;
BNode * LC;
BNode * RC;
}; |
struct MyData : public BNode
{
virtual bool operator<(const BNode & arg);
virtual bool operator==(const BNode & arg);
int Data;
}; |