new
and delete
for simple objects and arrays.std::list
std::forward_list
std::vector
std::array
std::stack
std::queue
std::sort
function using a custom comparator.std::set
std::map
std::unordered_set
std::unordered_map
NOTE: Once the exam starts you are not allowed to share any items with anyone else.
Pen, pencil, eraser, pencil sharpener.
Simple scientific calculator. You are not allowed to use a cell phone, programmable calculator, tablet, computer, or any other electronic device.
Personal cheat sheet with the following characteristics:

You have three algorithms: A, B, and C. Algorithm A has a performance of \(O(N!)\). Algorithm B has a performance of \(O(N^3)\). Algorithm C has a performance of \(O(2^N)\). Which algorithm has the best performance? Which one has the worst?
You have the following C++ code:
#include <iostream> int f(int n) { int r = 1; for (int i = 0; i < n; ++i) { r *= 2; } return r; } void g(int n) { int r = f(n); for (int i = 0; i < r; ++i) { std::cout << i << " "; } std::cout << "\n"; }
What is the time complexity of function g
? Explain your answer.
Assume that the following code completes the program that started with the code from the previous question. What gets printed to the standard output when running the program?
int main() { g(5); return 0; }
When trying to find a certain item inside a linked list, which search algorithm should be used and what is its time complexity?
Assume you have the following C++ struct
declaration:
struct Node { int value; Node* next; };
Using this structure it is possible to create a singly linked list using dynamic memory. For example:
Write a reverse
function that inverts a linked list by changing the links between nodes. No new nodes should be created. The value
field of the nodes should not be modified. For the list shown above, the resulting inverted list should be as follows:
The signature of the reverse
function should be:
void reverse(Node*& list)
What gets printed to the standard output when running the following C++ code?
#include <iostream> #include <queue> #include <stack> int main() { std::stack<int> s; std::queue<int> q; q.push(4); q.push(8); q.push(15); q.push(16); q.push(23); q.push(42); while (not q.empty()) { int x = q.front(); q.pop(); if (x % 2 == 0) { s.push(x); } } while (not s.empty()) { int x = s.top(); s.pop(); std::cout << x << " "; } std::cout << "\n"; return 0; }
Given the following postfix expression:
$$ 3 \; 5 \; 6 \; + \; * \; 10 \; 7 \;  \;  \; 3 \; / $$What gets printed to the standard output when running the following C++ code?
#include <algorithm> #include <iostream> #include <vector> bool comparator(int a, int b) { return std::abs(a) <= std::abs(b); } int main() { std::vector<int> v {35, 12, 43, 50, 77, 76, 8, 69}; std::sort(v.begin(), v.end(), comparator); for (int x : v) { std::cout << x << " "; } std::cout << "\n"; return 0; }
This sorting algorithm uses the fairly obvious fact that, if an array is not sorted, it must contain two adjacent elements that are out of order. The algorithm repeatedly passes through the array, swapping items that are out of order, until it can't find any more swaps. What’s the name of this algorithm?
You have the following hash function:
$$ H(k) = k * 97 + 5 $$Given a hash table implemented using open addressing and linear probing on an integer array of size 15, indicate the final state of that table after inserting the following numbers using the hash function above:
$$ 54, 45, 92, 22, 15, 90 $$In order to solve the Tower of Hanoi puzzle with ten disks, at least how many moves do you need?
Build a binary search tree by inserting the following values:
$$ 34, 15, 25, 40, 60, 51, 9, 31, 87, 71, 24 $$Traverse the resulting tree in inorder, preorder, postorder, and levelorder.
You are given a binary tree with the following traversals:
With this information rebuild the corresponding binary tree.
You have a perfect binary tree with 511 nodes. What is the height of this tree?
Draw four different binary trees of height \(H=2\) that are also:
You have the following struct
declaration that represents a binary tree node.
struct Node { Node* left; Node* right; };
Write in C++ or pseudocode a recursive function called node_count
that returns the total number of nodes contained in a given tree. The function’s signature is as follows:
int node_count(Node* p)
What’s the output of the following C++ program?
#include <iostream> #include <map> #include <vector> int main() { std::map<int, std::vector<int>> m; for (int n = 1; n <= 10; ++n) { std::vector<int> v; for (int i = 1; i <= n; ++i) { if (n % i == 0) { v.push_back(i); } } m[n] = v; } for (auto p : m) { std::cout << p.first << ": "; for (int x : p.second) { std::cout << x << " "; } std::cout << "\n"; } return 0; }