NEW
Font size
WorksheetsDAA Sessional
Total questions: 30
Worksheet time: 15mins
If an array has n elements and you perform one right rotation of the first k elements, how many swaps are required using the EXCHANGE(p, q) function?
k − 1
k
k + 1
Depends on array contents
When computing prefix sums of an array (where prefixSum[i] represents Sum of elements from index 0 to i) , what is the time complexity if the algorithm is implemented iteratively?
O(log n)
O(n)
O(n log n)
O(1)
What is the time complexity of finding the second smallest element in an unsorted array of size n?
O(1)
O(log n)
O(n)
O(n²)
The worst-case of Quick Sort occurs when the pivot always becomes:
Middle element
Largest or smallest element
Random element
Median
What is the time complexity of Binary Search in a sorted array?
O(n)
O(n log n)
O(log n)
O(1)
Quick Sort exhibits worst-case behavior when:
The array is randomly arranged
The pivot divides array into equal halves
The partitioning produces subproblems of size n-1 and 0
The array has duplicate elements
In the best-case scenario, Quick Sort partition produces subproblems of size:
n and 0
At most n/2 each
n-1 and 1
n/3 and 2n/3
What is the time complexity of building a heap from an unsorted array of n elements?
O(n)
O(n log n)
O(log n)
O(n²)
What is the time complexity of inserting an element into a heap?
O(1)
O(log n)
O(n)
O(n log n)
In the Fractional Knapsack problem, items should be sorted based on:
Weight
Profit
Profit/Weight ratio
Weight/Profit ratio
Huffman coding assigns:
Fixed length codes to all characters
Variable length codes based on frequency
Random codes to characters
Alphabetically ordered codes
What is the time complexity of Prim's algorithm using a Min-Priority Queue?
O(V)
O(E)
O(E log V)
O(V²)
Kruskal's algorithm uses which data structure to detect cycles?
Stack
Queue
Disjoint Set (Union-Find)
Binary Tree
Dijkstra's algorithm works correctly only when:
Graph has cycles
All edge weights are non-negative
Graph is disconnected
All edge weights are equal
In Matrix Chain Multiplication, what does the M-table store?
Matrix dimensions
Minimum number of scalar multiplications
Order of matrix multiplication
Result of multiplication
What does the S-table store in Matrix Chain Multiplication?
Scalar multiplication count
Matrix sizes
Split position for optimal parenthesization
Final result
The time complexity of finding the Longest Common Subsequence (LCS) using dynamic programming is:
O(m + n)
O(m × n)
O(m² + n²)
O(2^n)
Floyd-Warshall algorithm finds:
Single source shortest path
All pairs shortest path
Minimum spanning tree
Maximum flow
The time complexity of Floyd-Warshall algorithm is:
O(V²)
O(V³)
O(V log V)
O(E log V)
Dynamic programming is applicable when a problem has:
Greedy choice property only
Optimal substructure only
Both optimal substructure and overlapping subproblems
Neither optimal substructure nor overlapping subproblems
In an undirected graph where each edge weighs 2 units, BFS can find:
Maximum path
Shortest path
Minimum spanning tree
Strongly connected components
The expected time complexity of Randomized Quick Sort is:
O(n)
O(n log n)
O(n²)
O(log n)
What is the main difference between Las Vegas and Monte Carlo algorithms?
Las Vegas always gives correct answer, Monte Carlo may not
Monte Carlo always gives correct answer, Las Vegas may not
Both always give correct answers
Neither gives correct answers
The cost model for incrementing a binary counter counts:
Total number of bits
Number of bits that need to be flipped
Number of zeros in the counter
Position of highest bit
The worst-case time complexity of Insertion Sort is:
O(n)
O(n log n)
O(n²)
O(log n)
A heap is always:
Complete binary tree
Balanced binary tree
Binary search tree
AVL tree
The time complexity of building a Huffman Tree with n symbols is:
O(n log n)
O(n²)
O(log n)
O(n)
The Longest Common Subsequence problem differs from substring problem because:
Elements must be consecutive
Order must be maintained but not continuity
Case sensitivity applies
None of the above
In a max-heap of n elements, the largest and smallest element positions are:
Root and leaf
Leaf and root
Both at root
Both at leaves
The amortized cost of incrementing a binary counter of k bits over n operations is:
O(1)
O(k)
O(log n)
O(n)
