Q.1 Which of the following best describes amortized analysis?
Average case cost per operation over a sequence of operations
Worst case cost of a single operation
Best case cost of a single operation
The memory used by a data structure
Explanation - Amortized analysis calculates the average cost per operation over a worst-case sequence of operations, rather than the cost of an individual operation.
Correct answer is: Average case cost per operation over a sequence of operations
Q.2 What is the amortized cost of incrementing a binary counter n times?
O(1)
O(n)
O(log n)
O(n log n)
Explanation - Although individual increments may take up to O(log n) due to multiple bit flips, the amortized cost over n increments is O(1) per increment.
Correct answer is: O(1)
Q.3 Which method of amortized analysis uses a potential function to account for future costs?
Aggregate method
Accounting method
Potential method
Recursive method
Explanation - The potential method assigns a potential to the data structure representing pre-paid work, allowing future operations to use this stored potential.
Correct answer is: Potential method
Q.4 In the accounting method of amortized analysis, what does overcharging an operation do?
It increases worst-case cost
It stores extra cost to pay for future operations
It reduces memory usage
It decreases the actual cost
Explanation - The accounting method assigns more cost than actual to some operations, storing the excess as credit for more expensive future operations.
Correct answer is: It stores extra cost to pay for future operations
Q.5 Which advanced data structure is designed to support fast dynamic connectivity queries?
Disjoint Set Union (Union-Find)
Binary Search Tree
Hash Table
Queue
Explanation - Union-Find is used to efficiently determine whether elements belong to the same set and supports union operations with nearly constant amortized time.
Correct answer is: Disjoint Set Union (Union-Find)
Q.6 What is the amortized time complexity of Union-Find with path compression and union by rank?
O(log n)
O(1)
O(α(n))
O(n)
Explanation - With path compression and union by rank, each operation runs in nearly constant time, specifically O(α(n)), where α(n) is the inverse Ackermann function.
Correct answer is: O(α(n))
Q.7 A Fibonacci heap supports decrease-key operation in what amortized time?
O(1)
O(log n)
O(n)
O(n log n)
Explanation - Fibonacci heaps allow decrease-key in O(1) amortized time, which is useful in algorithms like Dijkstra's shortest path.
Correct answer is: O(1)
Q.8 Which data structure is most suitable for implementing a priority queue with very fast merge operations?
Binary heap
Fibonacci heap
Array
Linked list
Explanation - Fibonacci heaps allow merging of two heaps in O(1) amortized time, unlike binary heaps which require O(n).
Correct answer is: Fibonacci heap
Q.9 What does the term 'lazy deletion' mean in advanced data structures?
Deleting elements immediately
Marking elements as deleted but removing them later
Avoiding deletion altogether
Replacing elements with zero
Explanation - Lazy deletion defers physical removal, allowing amortized efficiency for operations where deletion is frequent.
Correct answer is: Marking elements as deleted but removing them later
Q.10 In splay trees, what is the amortized time for a basic operation like search, insert, or delete?
O(log n)
O(1)
O(n)
O(n log n)
Explanation - Splay trees have O(log n) amortized time for search, insert, and delete due to splaying operations that balance the tree over sequences of operations.
Correct answer is: O(log n)
Q.11 Which operation in a dynamic array can be expensive but has low amortized cost?
Insertion at the end
Deletion from the beginning
Searching
Sorting
Explanation - When the array is full, resizing doubles its size, which is expensive once, but amortized cost per insertion remains O(1).
Correct answer is: Insertion at the end
Q.12 What property does a skew heap maintain?
Heap property without strict balancing
Complete binary tree property
Balanced binary search property
Red-black property
Explanation - Skew heaps are self-adjusting heaps that maintain the heap order but do not enforce strict balance, giving good amortized performance.
Correct answer is: Heap property without strict balancing
Q.13 In the aggregate method of amortized analysis, what is done?
Sum total cost of n operations and divide by n
Compute worst-case cost of a single operation
Estimate average case cost using probability
Use a potential function for future operations
Explanation - The aggregate method calculates the total cost for a sequence and averages it to get the amortized cost per operation.
Correct answer is: Sum total cost of n operations and divide by n
Q.14 What is the worst-case time for inserting an element in a standard binary heap?
O(1)
O(log n)
O(n)
O(n log n)
Explanation - Insertion in a binary heap may require bubbling up the element, which takes O(log n) in the worst case.
Correct answer is: O(log n)
Q.15 Which advanced data structure is often used to implement priority queues in Dijkstra's algorithm for sparse graphs?
Binary heap
Fibonacci heap
Red-black tree
AVL tree
Explanation - Fibonacci heaps are suitable for sparse graphs due to their O(1) amortized decrease-key operation, which is frequent in Dijkstra's algorithm.
Correct answer is: Fibonacci heap
Q.16 What is the key idea behind path compression in Union-Find?
Flattening the tree structure to reduce future search time
Balancing the tree strictly
Using linked lists instead of trees
Sorting elements in each set
Explanation - Path compression makes nodes point directly to the root during find operations, reducing the depth and speeding up future finds.
Correct answer is: Flattening the tree structure to reduce future search time
Q.17 In amortized analysis, which statement is true?
Amortized cost always equals worst-case cost
Amortized cost equals average cost per operation over a sequence
Amortized cost equals best-case cost
Amortized cost is only used for recursive algorithms
Explanation - Amortized analysis averages the cost of operations over a sequence, giving insight into long-term performance, not individual worst cases.
Correct answer is: Amortized cost equals average cost per operation over a sequence
Q.18 Which advanced data structure allows constant-time concatenation of two sequences?
Fibonacci heap
Splay tree
Deque implemented with linked lists
Binomial heap
Explanation - Splay trees allow concatenation and split operations in O(log n) amortized time, making them efficient for sequence manipulation.
Correct answer is: Splay tree
Q.19 Which of the following is true for binomial heaps?
They are collections of binomial trees
They are always complete binary trees
They do not support merge operations efficiently
They do not maintain the heap property
Explanation - Binomial heaps consist of a set of binomial trees of different orders, which allows efficient merging in O(log n) time.
Correct answer is: They are collections of binomial trees
Q.20 What is the amortized cost of inserting n elements into an empty dynamic array?
O(n log n)
O(n)
O(log n)
O(n^2)
Explanation - Each insertion is O(1) amortized, so inserting n elements totals O(n) despite occasional costly resizing operations.
Correct answer is: O(n)
Q.21 Which data structure is self-adjusting and does not require explicit balancing?
Splay tree
AVL tree
Red-black tree
Binary heap
Explanation - Splay trees adjust themselves during access operations, bringing frequently accessed elements closer to the root without explicit balancing rules.
Correct answer is: Splay tree
Q.22 What is the amortized cost of delete-min operation in Fibonacci heaps?
O(1)
O(log n)
O(n)
O(n log n)
Explanation - While insertion and decrease-key are O(1), delete-min requires consolidating trees, which takes O(log n) amortized time.
Correct answer is: O(log n)
Q.23 Which of the following best describes a skew heap?
Self-adjusting heap with no structural constraints
Heap with balanced binary tree
Heap with Fibonacci trees
Array-based binary heap
Explanation - Skew heaps maintain the heap order but self-adjust via merging operations, achieving good amortized performance without strict balance.
Correct answer is: Self-adjusting heap with no structural constraints
Q.24 Which technique is commonly used to analyze dynamic array resizing?
Amortized analysis
Best-case analysis
Divide and conquer
Graph traversal
Explanation - Amortized analysis calculates the average insertion cost over multiple operations, accounting for occasional costly resizes efficiently.
Correct answer is: Amortized analysis