NYU – Tandon School of Engineering
Brooklyn, NY 11201
CS Bridge
3rd Exam – 14 November 2019
Prof. Katz
• Duration: 2 hours
• This is a closed book exam, no calculators are allowed
• You are permitted two sheets of scrap paper
• YOU MAY USE A COMPILER SUCH AS: Visual Studio, XCode or CLion
• Comments are not required
• Anyone found cheating on this exam will receive a zero for the exam.
• Anyone who is found writing after time has been called will receive a zero for this exam.
• Make sure that at the conclusion of the exam you ATTACH and SUBMIT your file,
Submit your exam, email to me () and logout of New Classes before
disconnecting from ProctorU!
1. (3 pts) What would be the appropriate function header/prototype for the overloaded
addition operator defined as a non-member of a class Exam.
a. Exam* operator+(Exam e1, Exam e2);
b. Exam Exam::operator+(Exam e1, Exam e2);
c. Exam operator+(Exam e1, Exam e2);
d. Exam operator+(const Exam e1, const Exam e2);
2. (3 pts) Given two classes, Base and Derived where Derived derives from Base
(obviously), and given a Base class pointer which is pointing to a Derived class object,
which of the following are invalid:
a. Calling a function defined only in the Derived class
b. Calling a non-virtual function defined in the Base class
c. Calling a virtual function defined in the Base class
d. Assigning a Derived pointer to a Base pointer (Base* bptr=derivedPointer;)
3. (3 pts) The worst-case time complexity of a “findMin” function on a Balanced Binary
Search Tree would be:
a. Theta(log N)
b. Theta(N)
c. Theta(N log N)
d. Theta(N2)
e. Cannot be determined
4. (6 pts) Convert the math expression 1-2+3*4-5 to post fix form.
5. (5 pts) Evaluate the post fix expression (assume C++ rules for handling integer operations
such as division) “8 4 / 1 – 2 *” to a value.
6. (15 pts) Given a binary search tree of ints, in which each node contains a size parameter
indicating the number of nodes in the tree (a leaf node has a size of 1), explain, in
English, not code, how you would find the “Nth” element of the tree, where N is a given
number which would indicate the order of the elements. For example, if N were 2, we
would be searching the tree for the second element if the tree were being processed with
an in-order traversal. Your solution should be as efficient as possible.
7. (15 pts) Given a pointer to the first node of a binary search tree (BSTNode*), provide a
function (or functions) which will delete the entire tree. For reference, the BSTNode
class begins as follows:
class BSTNode{
public:
BSTNode* parent, *left, *right;
int height;
int data;
...
}
8. (20 pts) Someone has given us a file (Computers.txt; it is guaranteed to exist) with a list
of names of servers on our network, the cities that they are in and their purpose. Each
line is guaranteed to contain all three elements, separated by spaces (no other white space
exists in this file; city names and purposes don’t contain spaces). Please read the data
and compile a list of all web and mail servers and print them to the screen. Also print the
cities that contain either Web or Mail servers.
For example, if the file contains:
ServerA NY Mail
ServerB NY Mail
ServerC NY Web
ServerD LA Mail
ServerE LA Web
ServerF LA File
ServerG CHI File
The output would be:
Mail servers: ServerA ServerB ServerD
Web servers: ServerC ServerE
Servers exist in: NY LA
9. (10 pts) Quicksort is the “preferred” sorting algorithm for most default sorting functions.
Explain, in English, why you believe it is that though Mergesort has a more predictable
runtime, quicksort is still the preferred algorithm.
10. (20 pts) In class, we learned about a normal FIFO Queue. However, another type of
queue exists known as a PriorityQueue. In a PriorityQueue, the dequeue operation does
not remove the oldest item in the queue, instead, it removes the lowest valued item in the
queue regardless of where is lies in the queue. While more efficient solutions exist, we
would like you to create a PriorityQueue class which derives from the Queue class given
below and overrides the dequeue function in order to implement the PriorityQueue
concept.
class Queue {
list data;
public:
void enqueue(int newItem) { data.push_back(newItem); }
int dequeue();
int top() const { return *data.begin(); }
bool isEmpty()const { return data.size() == 0; }
int size() const { return data.size(); }
void clear() { data.clear(); }
};
int Queue::dequeue() {
int retval = top();
data.pop_front();
return retval;
}
For example, Given this main:
int main() {
srand(time(NULL));
PriorityQueue pq;
for (int i = 0; i < 10; i++)
pq.enqueue(rand()%100);
while (!pq.isEmpty())
cout << pq.dequeue()<