Recursion
What are the three main components of a recursive function?
Base case, work performed at each call, and recursive call.
What is the difference between passing a variable by value and passing it by reference?
Pass by value creates a copy; pass by reference refers to the original variable.
Which data structure follows LIFO: stack or queue?
Stack (Last In, First Out).
What is the time complexity of accessing an element in an array using a valid index?
O(1).
What should a recursive function that sums the values in a linked list return when head == nullptr?
0.
What should a recursive function that counts linked-list nodes return when the pointer reaches nullptr?
0. An empty remaining list contains zero nodes.
What three special member functions make up the Rule of 3?
Destructor, copy constructor, and copy assignment operator.
Which data structure serves the earliest arriving customer first, and what acronym describes its behavior?
Queue, FIFO (First In, First Out).
What is the time complexity of this loop?
for (int i = 0; i < n; i++) {
cout << i;
}
O(n), because it executes n times.
In the function printLinkedList(head), which statement recursively advances to the next node?
printLinkedList(head->next);
What value is returned by the following code?
int mystery(int n) {
if (n <= 1) return 2;
return 4 + mystery(n - 1);
}
mystery(4);
14
mystery(1)=2, mystery(2)=6, mystery(3)=10, mystery(4)=14.
Which operations must a class support for this code? Assume Widget supports the displayed constructor arguments.
Widget first(12);
Widget second(first);
second = first;
A constructor accepting 12, a copy constructor, and a copy assignment operator.
Construction and assignment are different operations.
A singly linked list has 80 nodes. You already have a pointer to the node immediately before the one to delete. What is the deletion complexity?
O(1), assuming a standard non-tail deletion and valid predecessor pointer. No traversal is needed.
What is the complexity?
for (int x : values) {
for (int y : values) {
cout << x + y;
}
}
Assume values has n elements.
O(n²). Each range-based loop visits n elements, so n × n operations.
A stack begins empty. Perform push(4), push(11), push(7), pop(), push(2), pop(). What remains, from top to bottom?
11, 4. Both 7 and 2 were removed.
Identify the base case, work, and recursive call:
int total(int n) {
if (n == 0) return 0;
return n * 2 + total(n - 1);
}
Base case: if (n == 0) return 0;
Work: n * 2;
Recursive call: total(n - 1).
What class operations are used here?
Counter x;
Counter y(9);
--y;
if (x != y) { }
Assume all operations are supported
Default constructor, non-default constructor, prefix decrement operator, and inequality comparison operator.
A queue starts empty. Perform enqueue(14), enqueue(6), enqueue(21), dequeue(), enqueue(8). What are its front and rear values?
Front = 6, Rear = 8. Remaining queue: 6 → 21 → 8.
What is the complexity?
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << j;
}
for (int k = 0; k < 17; k++) {
cout << k;
}
}
O(n²). Per outer iteration the work is O(n + 17), so total O(n² + 17n) = O(n²).
A program stores a fixed maximum of 60 readings and needs fast indexed access. Would a fixed array, vector, or linked list be the simplest choice? Explain.
A fixed array is a good choice because the maximum size is known and indexing is O(1). A vector could also work but dynamic growth is unnecessary.
Write a recursive helper that counts how many nodes contain a value greater than 10. The helper receives Node* ptr.
int countLarge(Node* ptr) {
// Base case
if (ptr == nullptr) {
return 0;
}
// Check if the current node's value is greater than 10
int add = 0;
if (ptr->data > 10) {
add = 1;
} else {
add = 0;
}
// Recursive call
return add + countLarge(ptr->next);
}
A program stores a growing collection of student scores and frequently accesses scores by index. Would you choose a vector or linked list? Explain.
Vector. It grows dynamically and supports O(1) indexed access, while linked-list indexing takes O(n).
A doubly linked list has a tail pointer. Why can it access a node a fixed three links before the tail in O(1), while a singly linked list generally requires O(n)?
The DLL can follow prev three times from tail. A typical SLL must traverse from head because it has no backward links.
Why is vector push_back O(1) amortized but O(n) in the worst case?
Most insertions append directly in O(1). When capacity is exhausted, reallocation and moving/copying existing elements take O(n). Across many insertions, average cost per insertion is O(1) amortized.
Complete the recursive logic for a helper that returns the first node containing an odd number, or nullptr if none exists. The function receives Node* ptr.
Node* firstOdd(Node* ptr) {
if (ptr == nullptr)
return nullptr;
if (ptr->data % 2 != 0)
return ptr;
return firstOdd(ptr->next); }