The exam will consist of short-answer questions, multiple choice questions, understanding written code, and writing your own code. The emphasis is on reading and writing code, particularly with recursive code and code which manipulates binary search trees.
The review below, in addition to the code you wrote for your labs, are all fair game for the exam. This is intended to be comprehensive; there will be no material on the exam which isn't touched by either the labs or this review.
If you're pushed for time, my personal recommendation is to spend the majority of your time studying the code you wrote for your labs. The best next thing to look at would be the materal below in the same order as it is presented. Overall, my philosophy with programming is that reading and writing code are the best ways to learn, and my questions tend to reflect this.
The questions below were not on the prior exam, though they were technically fair game. At least some of these are highly likely to be on this exam.
Consider the code below:
#include <iostream>
using namespace std;
class Des {
public:
Des(int x) { this->x = x; cout << x << endl; }
~Des() { cout << x << endl; }
private:
int x;
};
void test() {
Des d(1);
}
int main() {
Des* p = new Des(0);
test();
delete p;
return 0;
}
If the above code is compiled and run, what is the output?
Name and describe two operations which are typical of a stack ADT.
Name and describe two operations which are typical of a queue ADT.
Consider the following code:
#include <iostream>
using namespace std;
class Stack {
public:
Stack(); // creates a new, empty stack
void push(int item); // adds an item to the stack
int pop(); // removes an item from the stack
};
class Queue {
public:
Queue(); // creates a new, empty queue
void enqueue(int item); // adds an item to the end of the queue
int dequeue(); // removes an item from the front of the queue
};
int main() {
Stack s;
Queue q;
s.push(1);
s.push(2);
s.push(3);
q.enqueue(4);
q.enqueue(5);
q.enqueue(6);
for(int x = 0; x < 3; x++) {
cout << s.pop() << " " << q.dequeue() << endl;
}
}
If the program above is compiled and run, what is the output?
Name one reason why someone would prefer an equation in Big-O notation instead of terms like “efficient” or “fast”.
Consider the code below. What is its time complexity?
void foo(int* array, int length) {
int sum = 0;
for(int x = 0; x < length; x++) {
sum += array[x];
}
return sum;
}
Consider the code below. What is its time complexity?
void foo(int* array, int length) {
int sum = 0;
for(int x = 0; x < length; x++) {
for(int y = 0; y < length; y++) {
sum += array[x];
sum += array[y];
}
}
return sum;
}
Consider the code below. What is its time complexity?
// precondition: array is sorted
bool foo(int* array, int elem, int min, int max) {
if (min <= max) {
int mid = min + ((max - min) / 2);
if (elem < array[mid]) {
return foo(array, elem, min, mid - 1);
} else if (elem > array[mid]) {
return foo(array, elem, mid + 1, max);
} else {
return true;
}
} else {
return false;
}
}
Overall, you should be able to read and write recursive code. I have some examples in the questions below, but these are not comprehensive. Recursion is just as general as loops, so I cannot possibly give a comprehensive list of recursive programs, in much the same way that I cannot give a comprehensive list of programs that use loops.
What does it mean to be tail-recursive? Why is this important?
You should be able to take a tail-recursive algorthm and convert it to an iterative version. I will not ask about non-tail-recursive programs, since these need quite a bit of fairly tedious modification. As an example of this problem, consider the following tail-recursive program which would be fair game:
// precondition: length >= 1
int getMax(int* array, int length) {
return getMax(array + 1, length - 1, array[0]);
}
int getMax(int* array, int length, int curMax) {
if (length == 0) {
return curMax;
} else if (array[0] > curMax) {
return getMax(array + 1, length - 1, array[0]);
} else {
return getMax(array + 1, length - 1, curMax);
}
}
Be able to convert an iterative algorithm to a recursive version. In general, it should be possible to convert to a tail-recursive version, though you will not be required to do so if you don't want. I may, however, give bonus points for tail-recursive versions. As an example of this kind of problem, consider the iterative program below:
// Gets the second to last element of a linked list.
// Precondition: the provided list contains at least two elements
int getSecondToLast(Node* list) {
Node* prev2 = list;
Node* prev1 = prev2->getNext();
Node* current = prev1->getNext();
while (current != NULL) {
prev2 = prev1;
prev1 = current;
current = current->getNext();
}
return prev2->getInt();
}
In a recursive setting, what does it mean to “blow the stack”?
Name one reason why someone would choose recursion over iteration.
Name one reason why someone would choose iteration over recursion.
Provide definitions for the following terms, and be able to point them out in tree diagrams. For example, for a question regarding depth, you should be able to provide the depth of an arbitrary node in a tree.
What is the time complexity of addition / insertion / removal?
If we could guarantee that a binary search tree had a particular property, then we could guarantee a better time complexity for addition / insertion / removal. Name the property.
What data structure is needed for a breadth-first search?
What data structure is needed for a depth-first search?
Be able to provide the traversal order of a tree for the following (i.e., provide the order in which we'd process nodes):
Both heaps and binary search trees are types of binary trees. However, operations on both have very different time complexities. Why?
For the enqueue operation on a heap, where is the element initially
inserted? Why can't we always just leave the element in this position?