Suppose x is the value at the front of a std::queue after the following operations: push(5), push(10), push(9), pop(), push(1), push(1), pop(), push(6), pop(), pop(). What operation sequences make the value at the top of a std::stack equal x?
What is the time complexity of the following code (Suppose m>0 and n>1)?
int func (int m, int n){
int i=0; while (i < m){
i++;
}
for (int i; i < n-1; i++){
for (int j=i+1; j < n; j++) return i*j;
}
}
What are the articulation points (i.e., cutting vertices) in the graph below?
Graph: see image.
Which data structures store and retrieve elements by keys?
Given the binary max-heap below, what will the tree structure look like after a new element, 18, is inserted into it?
Binary max-heap: see image.
Which of the following is TRUE about template, std::iterator, reference, and pointer?
A. We can define more than one template variable for a class or a function.
B. Suppose iter is an std::iterator variable, then we can use iter++; or (*iter)+=1; to move to the next element within a container.
C. A reference variable is an alias for an already existing variable. It can be used in the same way as how you use a pointer to the variable.
D. All of template, std::iterator, reference, and pointer store the memory address of things.
Suppose you are using Dijkstra's algorithm to find the shortest path from A to E, and until now, the algorithm has only visited three nodes, A, C, D, sequentially. What is the current shortest distance from A to E as calculated by the algorithm at this time?
Graph: see image.
The visiting orders of a Preorder traversal and an Inorder traversal of a tree are shown below:
Pre-order: A B D H E C F I G J K
In-order: D H B E A I F C J G K
So what is the visiting order a Postorder traversal of the same tree?
What is the worst-case complexity of removing an element from a binary heap? Suppose n is the number of elements in the heap. You may consider either a max-heap or a min-heap; that will not affect the result.
Which of the following is/are NOT true about adjacency_matrix and adjacency_list?
A. Suppose a graph has n vertices. The size of the adjacency_matrix is fixed to n2; the size of the adajcency_list depends on the number of edges in the graph.
B. Suppose a graph has m edges (no self-loops) and is undirected. The number of trues or 1s in the adjacency_matrix would be 2m.
C. Suppose a graph contains the maximum number of edges it could possibly have. The adajcency_list may take more memory space than the adajcency_matrix used to represent the graph.
D. Given a vertex in a directed graph, the degree of this vertex may not equal the sum of the in_degree and out_degree of the vertex.
What is the time complexity of inserting a new element before the fourth element in a singly linked list? Suppose the length of the linked list is n, which is bigger than 4.
Suppose P != NP. Which of the following statement about an NP-hard problem is/are TRUE (More than one answer may be selected)?
A. The problem might be P.
B. The problem might be NP.
C. The problem might be NP-Complete.
D. The problem is one of the hardest problems in NP.
Given the directed graph below, how many vertices are there in the largest strongly connected component (SCC) in the graph?
Graph: see image.
Suppose you use the simple division hash function, h(k)=k%n and quadratic probing to insert a sequence of elements: 4,5,8,10, one by one to an array (Suppose the length of array: n=6). What would be the array position (or index) to store 10?
Which of the following is/are NOT the result of topological sorting on the graph below (More than one answer may be selected)?
Graph: see image.
A. A, B, F, D, E, H, G, C
B. B, C, F, D, E, A, H, G
C. F, H, E, B, D, A, C, G
D. B, F, D, E, H, A, G, C
Considering a collection of elements { 3, 7, 6, 2, 9, 4 }, what insertion order of these elements would produce a Binary Search Tree (BST) that has the biggest height?
Please give at least four insertion orders that meet the above requirement (word limit: 100).
Can you briefly describe what the function below does in plain English (word limit: 100)?
std::queue< int > q; q.push(0);
q.push(1);
for (int i = 0; i < n; i++) { int a = q.front(); q.pop();
int b = q.front(); q.pop();
q.push(b);
q.push(a + b);
}
std::cout << a << std::endl;
}
Suppose we wish to store 80 non-negative ints in a two-dimensional array (i.e., a square matrix like int A[10][10]). Can you design a mechanism to insert these ints into the array so that we can check if an int exists in this two-dimensional array efficiently? This mechanism should perform better than the exhaustive approach (i.e., iterating over the whole matrix), which has the time complexity of O(n2).
Please briefly describe your method in plain English, pseudo-code, or C++ code (word limit: 200).
Suppose we have a square matrix: int matrix[n][n], where n>0. Can you briefly describe what the code below does (word limit: 100)? You may draw a figure to illustrate your idea if you want.
for (int x = n-1; x > -1; x--) {
for (int y = n-1; y > -1; y--) { if (x < n-1 && y < n-1) {
matrix[x][y] += std::min(matrix[x+1][y], matrix[x][y+1]);
} else if (x < n-1) {
matrix[x][y] += matrix[x+1][y];
} else if (y < n-1) {
matrix[x][y] += matrix[x][y+1];
}
}
}
std::cout << matrix[0][0] << std::endl;
Suppose we have a set of numbers {1,8,5,2,6,3,9}, and we wish to find a subset of these numbers so that the sum of these numbers is as close to 20 as possible yet still no greater than 20.
For example,
Below shows an algorithm to find such a subset. Can you tell what strategy the code takes? Does this code guarantee to get the optimal result? (word limit: 100)
std::vector< int > v = {1, 8, 5, 2, 6, 3, 9};
std::sort(v.begin(), v.end()); int sum = 0, sum_limit = 20;
for (int i = 0; i < v.size(); i++) { if (sum + v[i] <= sum_limit) {
sum += v[i];
}
}
std::cout << sum << std::endl;
Can you describe an algorithm that can obtain an optimal subset of the numbers for Question 20? The optimal subset should achieve the largest sum (no greater than 20).
You can explain in plain English, pseudo-code, or C++ code (word limit: 200).