Module 1: Array

1 If a 2D array A[4][5] is stored in row-major order, with the base address BA = 2000 and each element
taking 2 bytes, what is the address of element A[2][3]?
A. 2000 + (2×5 + 3) × 2
B. 2000 + (3×5 + 2) × 2
C. 2000 + (2×4 + 3) × 2
D. 2000 + (5×2 + 4) × 2

2 Fun(A, n):
sum ← 0
for i ← 0 to n-1:
for j ← 0 to n-1:
if i == j:
sum ← sum + A[i][j]
return sum

What does this function compute?

A. Sum of all elements
B. Sum of upper triangle elements
C. Sum of main diagonal elements
D. Sum of lower triangle elements

3 Fun(A, n, m):
for i ← 0 to n-1:
for j ← i+1 to m-1:
temp ← A[i][j]
A[i][j] ← A[j][i]
A[j][i] ← temp

What is the purpose of this code?

A. It reverses each row
B. It transposes the square matrix
C. It rotates the matrix by 90°
D. It mirrors the matrix horizontally

4️ Fun(A, rows, cols):

max ← A[0][0]
for i ← 0 to rows-1:
for j ← 0 to cols-1:
if A[i][j] > max:
max ← A[i][j]
return max

What does the function return?

A. Index of maximum element
B. Maximum element value
C. Sum of all elements
D. Number of rows containing max
 A matrix
005
080
003
is represented as a list of triplets (row, column, value).
Which of the following correctly represents the sparse matrix?
A. [(0,2,5), (1,1,8), (2,2,3)]
B. [(2,0,5), (1,1,8), (3,3,3)]
C. [(1,3,5), (2,2,8), (3,3,3)]
D. [(0,0,5), (1,1,8), (2,2,3)]

Consider a doubly linked list with prev, data, and next fields.
If a new node is inserted before the first node, which pointer updates are necessary?
A. [Link] ← head; head ← newNode
B. [Link] ← head; [Link] ← newNode; head ← newNode
C. [Link] ← newNode; newNode ← head
D. [Link] ← newNode; head ← newNode

Which of the following applications best suits a linked list rather than an array?
A. When random access of elements is required frequently
B. When frequent insertions and deletions are required
C. When memory size is fixed
D. When elements are accessed by index

If a 2D array A[6][4] is stored in row-major order with base address 1000 and each element requires 4
bytes, find the address of A[3][2].
A. 1000 + (3×4 + 2)×4
B. 1000 + (2×6 + 3)×4
C. 1000 + (3×6 + 2)×4
D. 1000 + (4×3 + 2)×4

If the same array A[6][4] is stored in column-major order, what is the address of A[3][2]?
A. 1000 + (3×4 + 2)×4
B. 1000 + (2×6 + 3)×4
C. 1000 + (4×2 + 3)×4
D. 1000 + (6×2 + 3)×4
 Fun(A, n):
sum ← 0
for i ← 0 to n-1:
for j ← i to n-1:
sum ← sum + A[i][j]
return sum
What does this function compute?
A. Sum of main diagonal elements
B. Sum of lower triangle elements
C. Sum of upper triangle elements
D. Sum of all elements

1 Fun(A, n):
sum ← 0
for i ← 0 to n-1:
for j ← 0 to i:
sum ← sum + A[i][j]
return sum
This function returns:
A. Sum of upper triangle elements
B. Sum of lower triangle elements
C. Sum of diagonal elements
D. Total number of elements

1 For a square matrix A, which statement is TRUE for symmetric matrices?

A. A[i][j] = A[j][i]
B. A[i][j] = -A[j][i]
C. A[i][j] = A[i][i]
D. A[i][j] = 0

1 Fun(A, n, m):
count ← 0
for i ← 0 to n-1:
for j ← 0 to m-1:
if A[i][j] == 0:
count ← count + 1
return count
The function counts:
A. Total number of elements
B. Number of zeros in matrix
C. Sum of non-zero elements
D. Number of positive elements
1 A matrix of order 1000×1000 has only 5% non-zero entries. What is the best storage representation?
A. Normal 2D array
B. Sparse matrix representation
C. Linked representation
D. Graph adjacency list

1 Which of the following is TRUE about a sparse matrix?

A. Most of its elements are non-zero
B. Most of its elements are zero
C. It is always symmetric
D. It is always square

1 In a sparse matrix triplet representation, the first row typically stores:

A. Matrix name
B. Dimensions and total non-zero elements
C. Only non-zero values
D. Column indices

1 If a matrix has n non-zero elements, what is the space complexity of its triplet representation?
A. O(n²)
B. O(n)
C. O(3n)
D. O(n³)

1 In a singly linked list, which of the following is TRUE?

A. It can be traversed in both directions
B. It requires more memory per node than a doubly linked list
C. It can be traversed only in one direction
D. Each node has two pointers

1 In a circular linked list, the last node points to:

A. NULL
B. The first node
C. Any random node
D. Itself

2 Which of the following operations is more efficient in a linked list than in an array?
A. Random access
B. Insertion at the beginning
C. Accessing middle element
D. Binary search
2 In a doubly linked list, deleting the last node requires:
A. Traversal from head to last node
B. Direct access by index
C. Only tail pointer update
D. No pointer update

2 If head is NULL in a singly linked list, it means:

A. List is full
B. List is empty
C. List has one node
D. Memory overflow

2 To insert a node after a given node ptr in a singly linked list, which sequence is correct?
A. [Link] = [Link]; [Link] = new
B. [Link] = [Link]; [Link] = ptr
C. new = [Link]; ptr = new
D. [Link] = ptr; [Link] = new

2 In a circular singly linked list, deletion of the head node requires:

A. Traversing to the last node to update its next pointer
B. Simply setting head = [Link]
C. Deleting all nodes
D. Reversing the list

2 If each node in a doubly linked list has two pointers, what is the space overhead per node (assuming
4-byte addresses)?
A. 4 bytes
B. 8 bytes
C. 12 bytes
D. Depends on data type

2 Which of the following is an advantage of a circular linked list over a singly linked list?
A. Requires less memory
B. Can be traversed from any node
C. Supports random access
D. Faster element search

2 To reverse a singly linked list, which of the following is NOT needed?

A. Three pointers (prev, curr, next)
B. Temporary pointer variable
C. Extra node creation
D. Traversal of entire list
2 In a doubly circular linked list with one node, which of the following is true?
A. next = NULL, prev = NULL
B. next = prev = self
C. next = NULL, prev = self
D. prev = NULL, next = self

2 Which of the following linked list types is best suited for implementing a deque (double-ended
queue)?
A. Singly linked list
B. Doubly linked list
C. Circular singly linked list
D. Linear array

3 In linked list implementation of a stack, where should insertion and deletion take place?
A. Both at the head
B. Both at the tail
C. Insertion at head, deletion at tail
D. Insertion at tail, deletion at head

3 Which pointer adjustment is necessary when deleting the first node in a doubly linked list?
A. [Link] = NULL; head = [Link]
B. [Link] = [Link]
C. head = NULL
D. [Link] = NULL

3 To traverse a circular linked list, what is the correct termination condition?

A. while(ptr != NULL)
B. while(ptr->next != NULL)
C. while(ptr != head)
D. while(ptr->next != head)

3 Which data structure is most appropriate for representing polynomial addition efficiently?
A. Array
B. Queue
C. Linked list
D. Stack

3 To find the middle node of a singly linked list efficiently:

A. Use a counter and traverse twice
B. Use slow and fast pointers
C. Use recursion
D. Use stack
3 What will happen if the next pointer of the last node in a singly linked list is not set to NULL?
A. Memory leak
B. Infinite loop during traversal
C. Program crash
D. No effect

Module 2: Time and Space Complexity.

1. An algorithm recursively divides a problem of size n into three subproblems of size n/2, with a
constant combination cost. Which of the following best represents its time complexity?
A. O(n log n)
B. O(n^(log₂3))
C. O(n²)
D. O(3ⁿ)

2. Suppose you have to store a large number of student records with quick search and dynamic
insertion. Which data type and structure combination is most appropriate?
A. Primitive type with array
B. Non-primitive with linked list
C. Non-primitive with hash table
D. Primitive with stack
Correct Answer: Non-primitive with hash table

3. In a system, the growth of function f(n) = 5n log n + 20n is compared to g(n) = n². For large n,
which statement is true?
A. f(n) grows faster than g(n)
B. f(n) grows slower than g(n)
C. f(n) = Θ(g(n))
D. Both grow equally fast
Correct Answer: f(n) grows slower than g(n)

4. You design an algorithm that solves a problem in T(n) = 2T(n/2) + n/log n. What is its asymptotic
time complexity using Master’s theorem?
A. O(n log n)
B. O(n²)
C. O(n log log n)
D. O(n)
Correct Answer: O(n log n)
5. Which of the following best represents an Abstract Data Type (ADT)?
A. Integer data type
B. Stack with push/pop operations defined
C. Array with fixed size
D. Character variable
Correct Answer: Stack with push/pop operations defined

6. If a queue is implemented using two stacks, what will be the time complexity of dequeue()
operation in the worst case?
A. O(1)
B. O(log n)
C. O(n)
D. O(n²)
Correct Answer: O(n)

7. You must choose a data structure for a navigation app storing routes as graphs. Which structure
ensures efficient shortest path computation?
A. Tree
B. Linked list
C. Adjacency list
D. Stack
Correct Answer: Adjacency list

8. A recursive algorithm has recurrence T(n) = T(n–1) + T(n–2) + 1. What is its time complexity?
A. O(n)
B. O(2ⁿ)
C. O(n log n)
D. O(n²)
Correct Answer: O(2ⁿ)

9. You have two algorithms with time complexities O(n log n) and O(n²). For small input sizes (n <
100), which algorithm might perform better and why?
A. O(n²), due to smaller constant factor
B. O(n log n), always faster
C. O(n²), because of better recursion
D. O(n log n), due to better memory locality
Correct Answer: O(n²), due to smaller constant factor

10. If a function runs in Θ(n³) time and another in O(n² log n), which statement is correct?
A. Both have the same asymptotic growth
B. Θ(n³) grows slower
C. O(n² log n) grows slower
D. Cannot be compared
Correct Answer: O(n² log n) grows slower
 11. When analyzing algorithms, which statement correctly differentiates time complexity and space
complexity?
A. Time depends on variables, space on loops
B. Time measures memory, space measures CPU
C. Time measures execution steps, space measures memory usage
D. Both are identical
Correct Answer: Time measures execution steps, space measures memory usage

12. A divide and conquer algorithm solves a problem of size n by dividing it into 4 subproblems of
size n/2 and combining results in O(n²). What is its time complexity?
A. O(n²)
B. O(n³)
C. O(n² log n)
D. O(n⁴)
Correct Answer: O(n³)

13.

int a = 0, b = 0;
for (i = 0; i < N; i++) {
a = a + rand();
}
for (j = 0; j < M; j++) {
b = b + rand();
}
What is its time and space complexity?
A. O(N * M) time, O(1) space
B. O(N + M) time, O(N + M) space
C. O(N + M) time, O(1) space
D. O(N * M) time, O(N + M) space

14. Which data type would be ideal for representing a binary image where each pixel can be either ON
or OFF?
A. bool
B. int
C. char
D. short

15. Why are non-primitive data types considered more powerful than primitive ones?
A. They consume less memory
B. They can store multiple values together
C. They execute faster
D. They cannot be customized
16. Converting a primitive type into a non-primitive type (like int → Integer in Java) is called:
A. Overloading
B. Wrapping
C. Casting
D. Boxing

17. In which scenario is using a linked list more beneficial than an array?
A. When random access is frequent
B. When insertion/deletion is frequent
C. When memory is static
D. When data is constant

18. If elements must be processed in both forward and backward directions efficiently, which data
structure is most suitable?
A. Stack
B. Queue
C. Doubly linked list
D. Circular queue

19. You are asked to build a spell-checker. Which data structure provides efficient prefix search?
A. Stack
B. Trie
C. Queue
D. Heap

20. Which data structure is ideal for implementing an Undo/Redo feature?

A. Stack
B. Queue
C. Tree
D. Array

21. Which non-linear data structure is used in compiler syntax analysis?

A. Stack
B. Queue
C. Tree
D. Array
22. Which structure ensures all nodes have at most two children?
A. Graph
B. Tree
C. Linked List
D. Heap

23. What does an ADT hide from the user?

A. Implementation details
B. Operations
C. Data
D. Algorithms

24. Which is not an example of an ADT?

A. Stack
B. Queue
C. Integer
D. Graph

25. Why is defining ADT essential in software engineering?

A. Reduces abstraction
B. Increases complexity
C. Enables modular design
D. Decreases code reuse

26. Which operation in a stack ADT can lead to underflow?

A. Push
B. Pop
C. Peek
D. Insert

27. Algorithm A runs in 2n steps and Algorithm B in n² steps. For large n, which is faster?
A. A
B. B
C. Equal
D. Depends on constant factor
28. When analyzing an algorithm, which assumption ensures fair comparison?
A. Same input distribution
B. Same hardware
C. Same compiler
D. Same coding language

29. A sorting algorithm runs faster on nearly sorted data. Which property explains this?
A. Adaptive nature
B. Stable sorting
C. Divide and conquer
D. Randomization

30. Which metric determines the scalability of an algorithm?

A. Execution speed
B. Space usage
C. Growth of function
D. Input type

31. Which algorithmic approach recursively divides a problem and merges results?
A. Greedy
B. Dynamic programming
C. Divide and conquer
D. Backtracking

32. Which algorithm design paradigm ensures overlapping subproblems and optimal substructure?
A. Divide and conquer
B. Dynamic programming
C. Backtracking
D. Greedy

33. What does algorithm analysis primarily focus on?

A. Code structure
B. Logical errors
C. Resource usage
D. Syntax
34. For f(n)=n³ and g(n)=n²logn, what’s the correct relation?
A. f(n)=O(g(n))
B. f(n)=Ω(g(n))
C. f(n)=Θ(g(n))
D. f(n)=o(g(n))

35. If T(n)=O(nlogn), then which is always true?

A. T(n) < cn for some c
B. T(n)/n² → 0
C. T(n)/n → ∞
D. T(n)/logn → 0

36. Which function grows the fastest asymptotically?

A. n log n
B. n²
C. n³
D. 2ⁿ

37. Which growth function represents logarithmic complexity?

A. f(n)=n
B. f(n)=logn
C. f(n)=n²
D. f(n)=√n

38. Which function dominates for large n — log₂n or √n?

A. log₂n
B. √n
C. Both same
D. Depends on n

39. If an algorithm’s space complexity increases but time decreases, what has likely been used?
A. Parallelism
B. Recursion
C. Caching
D. Sorting
40. What is the best method to measure performance on real hardware?
A. Algorithm analysis
B. Profiling
C. Simulation
D. Debugging

41. Which contributes most to space complexity?

A. Constant variables
B. Recursion stack
C. Iterations
D. Loops

42. If an algorithm uses O(1) extra space, it is called:

A. Recursive
B. In-place
C. Static
D. Dynamic

43. Which asymptotic notation gives the tight bound of growth?

A. Big O
B. Big Theta
C. Big Omega
D. Little o

44. If f(n)=O(g(n)), what does it imply?

A. f grows faster
B. f grows slower or equal
C. f and g grow equally
D. f grows exponentially

45. For a function f(n)=3n²+2n+5, asymptotically it belongs to:

A. O(n)
B. O(log n)
C. O(n²)
D. O(n³)
46. If an algorithm’s time doubles when input size doubles, it is likely:
A. Linear
B. Logarithmic
C. Quadratic
D. Exponential

47. T(n)=T(n/2)+1 gives which time complexity?

A. O(log n)
B. O(n)
C. O(n log n)
D. O(n²)

48. T(n)=2T(n/2)+n gives:

A. O(n)
B. O(n log n)
C. O(n²)
D. O(log n)

49. T(n)=3T(n/2)+O(n²) by Master’s theorem is:

A. O(n²)
B. O(n² log n)
C. O(n³)
D. O(n log n)

50. Which recurrence represents binary search?

A. T(n)=T(n–1)+1
B. T(n)=T(n/2)+1
C. T(n)=2T(n/2)+n
D. T(n)=T(n/3)+n

51. Which recurrence corresponds to merge sort?

A. T(n)=2T(n/2)+n
B. T(n)=T(n–1)+1
C. T(n)=T(n/2)+1
D. T(n)=T(n/2)+n²
 52. If T(n)=T(n–1)+O(1), the algorithm is:
A. Logarithmic
B. Linear
C. Quadratic
D. Exponential

53. If f(n) = O(g(n)) and g(n) = O(h(n)), then:

A. f(n) = O(h(n))
B. h(n) = O(f(n))
C. f(n) = Ω(h(n))
D. No relation can be established between f(n) and h(n)

54. If a function f(n) grows faster than g(n), which of the following is correct?

A. f(n) = O(g(n))
B. f(n) = Θ(g(n))
C. f(n) = Ω(g(n))
D. g(n) = Ω(f(n))

55. Assertion (A): Iterative method always gives an exact asymptotic bound.
Reason (R): It expands the recurrence until reaching the base case.

A. Both A and R are true, and R is the correct explanation of A

B. Both A and R are true, but R is not the correct explanation of A
C. A is false, but R is true
D. A is true, but R is false