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 ([email protected]) 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()< } The output might be: 5 12 14 30 31 33 34 35 38 39
