WorksheetsDSA-Revised
Total questions: 20
Worksheet time: 13mins
What is the worst case time complexity of a linear search?
O(1)
O(n)
O(n^2)
O(logn)
What are the disadvantages of arrays?
a) Index value of an array can be negative
b) Elements are sequentially accessed
c) Data structure like queue or stack cannot be implemented
d) There are chances of wastage of memory space if elements inserted in an array are lesser than the allocated size
Consider an integer array int a[10]; in C. Which of the following expressions is equivalent to *(a + 3)?
a) &a[3]
b) a[3]
c) *a[3]
d) a + 3
Which of the following sorting algorithms has worst-case time complexity O(n²)?
a) Merge Sort
b) Quick Sort (randomized pivot)
c) Insertion Sort
Which asymptotic notation gives the tightest bound (both upper and lower) on an algorithm’s running time?
a) Big-O
b) Big-Ω
c) Big-Θ
d) Little-o
If an algorithm has running time T(n) = 3n² + 10n + 5, its time complexity in Big-Ω notation is:
a) O(n)
b) O(n log n)
c) O(n²)
d) O(n³)
void mystery(int n) {
int i = 1;
while (i < n) {
i = i * 2;
}
}
Time Complexity
a) O(1)
b) O(log n)
c) O(n)
d) O(n²)
What is the space complexity of storing a 2D array of size m × n?
a) O(m + n)
b) O(mn)
c) O(m² + n²)
d) O(1)
What is the space complexity of:
for (int i = 1; i < n; i = i * 2) { }
a) O(n)
b) O(log n)
c) O(n log n)
d) O(1)
What is the space complexity of the following function?
int fun(int n) {
int x = 0;
if (n <= 1) return 1;
return fun(n-1) + fun(n-1);
}
for if O(1)
for rest O(n)
for if O(1)
for rest O(logn)
for if O(1)
for rest O(n^2)
for if O(1)
for rest O(1)
Space Complexity
int sum = 0;
for (int i = n; i > 0; i = i / 2) {
for (int j = 0; j < i; j++) {
sum++;
}
}
O(n)
O(n^2)
O(1)
O(logn)
void mystery(int n) {
if (n <= 1) return;
mystery(n/2);
mystery(n/2);
}
Time Complexity
O(n)
O(logn)
O(n^2)
O(1)
Given the array:
[5, 2, 4, 6]
Show the array after two pass of Insertion Sort (treat the first element as sorted).
(a)
Time complexity of Counting Sort
Write in small letters
(a)
Given the array:
A = [20, 5, 18, 7, 15]
Show the array after the 1st pass and after the 2nd pass of Selection Sort
(a)
You want to sort the following two-digit decimal numbers in ascending order using Radix Sort (base 10) with 1 passes:
A = [39, 12, 25, 17, 43]
(a)
You have an array M[5][5] (0-based) of 2-byte integers.
If the address of M[2][4] is 2108 and the number of columns is 5, find the base address BA (address of M[0][0]).
(a)
A 2D array D[4][3] of 2-byte integers is stored in column-major order.
Base address is BA = 1000.
Find the address of D[2][1]
(a)
Which statement best describes an advantage of linked lists?
a) They always use less memory than arrays.
b) They provide O(1) access to the middle element.
c) They can efficiently grow and shrink during runtime.
d) They do not store elements in contiguous memory locations.
Which sorting algorithm is best for large datasets when the worst-case performance must remain good
Merge Sort,
Quick Sort,
Insertion Sort,
Bubble Sort)
