new
and delete
for simple objects and arrays.std::sort
function using a custom comparator.std::vector
std::list
std::stack
std::queue
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> #include <vector> int f(int x) { int r = 0; while (x) { x /= 2; ++r; } return r; } void g(int n, std::vector<int>& v) { for (int i = 0; i < n; ++i) { v.push_back(f(i)); } }
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() { std::vector<int> v; g(10, v); for (int x : v) { std::cout << x << " "; } std::cout << "\n"; 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?
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?
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; }
You have the following hash function:
$$ H(k) = k * 97 + 13 $$Given a hash table implemented using open addressing and linear probing on an integer array of size 10, 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.
Given the following postfix expression, what is the result of evaluating it?
$$ 100 \; 4 \; 5 \; 6 \; + \; * \; - \; 15 \; 3 \; / \;+ $$Indicate the infix expression corresponding to the previous question and build the corresponding expression tree.
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?
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 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; }