Array Lists & Linked List
What is the primary advantage of an Array List over a Linked List?
Faster random access of elements (O(1) vs O(n)).
What is the primary difference between a stack and a queue?
A stack follows LIFO, while a queue follows FIFO.
What is the base case in recursion?
The stopping condition that prevents infinite recursion.
What is the worst-case time complexity of searching in a BST?
O(n), if the tree is unbalanced.
What is the worst-case time complexity of searching in a sorted Array List?
O(log n) using binary search.
Why do Linked Lists use more memory per element than Array Lists?
They store extra pointers to the next (and possibly previous) nodes.
What is the time complexity of enqueue() in a queue implemented with a Linked List?
O(1), assuming a tail pointer is maintained.
What is the traversal order of an in-order tree traversal?
Left, Root, Right.
What is the height of a perfectly balanced AVL tree with 7 nodes?
2.
What is the amortized cost per insertion in an Array List that doubles in size?
O(1).
What is the time complexity of inserting an element at the front of an Array List?
O(n), because all elements must shift.
What operation must a circular buffer perform when it reaches capacity?
Overwrite old values or expand the buffer.
What does the following recursive function compute?
int mystery(int x, int y) {
if (y == 0) return 1;
return mystery(x, y - 1) * x;
}
Computes x^y (x raised to the power y).
What does an AVL tree do when an insertion causes an imbalance?
Performs rotations to restore balance.
What is the time complexity of searching for an element in a Linked List?
O(n).
Which operations have O(1) time complexity for both Array Lists and Linked Lists?
pushAtBack() and size().
If a Stack is implemented using the front of an Array List, which operation has the same complexity as in a Linked List?
push() (both O(1)).
How many nodes are in a full binary tree with height h?
2^(h+1) - 1.
What property must a BST satisfy?
Left subtree contains smaller elements, right subtree contains larger elements.
What are the three main components of a Makefile rule?
Target, dependencies, and command.
Given an empty Array List with an initial capacity of 4, how many resizes occur when adding 10 elements?
2 (resizes at 4 and 8).
What happens if you try to pop() from an empty stack?
A runtime error (stack underflow) occurs.
What traversal order should be used to delete a binary tree?
Post-order.
Given a BST with unique values, what is the worst-case time complexity of finding the maximum value?
O(h), where h is the tree height.
What is the difference between compilation and linking?
Compilation converts source code to object files, linking combines object files into an executable.