DSA · Question paper

CET-1 · 25 Aug 2025

Data Structures & Algorithms (C2310C5) · CET-I · 25 August 2025 · 30 marks · 10:30 am – 12:00 pm ITM (SLS) Baroda University · B.Tech CSE/CSN/IT/AI&DS · Semester III, Odd Semester 2025. Questions transcribed from the original paper. Solutions are written by CampusLoop; check them against your class notes.

Q1. Multiple choice questions [10]

1. Data structures are used to: a) Organize and store data efficiently · b) Control program flow · c) Perform compilation · d) None of the above

Answer: (a).

2. Which of the following operations has the best possible time complexity? a) O(log n) · b) O(n) · c) O(1) · d) O(n²)

Answer: (c) O(1) (constant time does not grow with n).

3. 35 teams qualified for the 2014 World Cup. If the names of the teams were arranged in sorted order (an array), how many times in the array would binary search have to examine to find the location of a particular team, in the worst case? a) At most 32 · b) At most 1 · c) At most 16 · d) At most 6

Answer: (d) At most 6. Binary search needs at most ⌈log₂(n+1)⌉ = ⌈log₂ 36⌉ = 6 comparisons (2⁵ = 32 < 35 ≤ 63 = 2⁶ − 1).

4. The two main measures for algorithm efficiency are: a) Memory and Time · b) Speed and Simplicity · c) Data and Storage · d) Complexity and Compilation

Answer: (a) space complexity and time complexity.

5. Which of the following is an example of a non-linear data structure? a) Array · b) Stack · c) Queue · d) Graph

Answer: (d) Graph.

6. Which of the following is a primitive data type? a) Array · b) Integer · c) Linked List · d) Stack

Answer: (b) Integer.

7. What is the advantage of a linked list over an array? a) Static data structure · b) Ease of insertion/deletion · c) Better memory utilization · d) Simple to revert

Answer: (b) Ease of insertion/deletion (no shifting of elements; also dynamic size).

8. Which ADT should be used for applications like file systems, decision trees, role-based access hierarchy? a) Graph · b) Tree · c) Linked List · d) Array

Answer: (b) Tree (hierarchical data).

9. Which concept is covered when ADTs are designed to be implemented in multiple ways? a) Abstraction · b) Reusability · c) Readability · d) Scalability

Answer: (a) Abstraction: the ADT says what operations do, not how, so it can be implemented with an array or a linked list.

10. In recursion, the function: a) Calls another function · b) Calls itself · c) Calls the main function · d) None of the above

Answer: (b) Calls itself.

Q2. Answer any TWO out of FOUR [10]

Q2.1 Short notes on linear and non-linear data structures (two examples each).

  • Linear: elements are arranged in a sequence; each element has at most one predecessor and one successor; traversed in a single run. Examples: array, stack, queue, linked list.
  • Non-linear: elements are arranged hierarchically or as a network; one element can connect to many; cannot be traversed in a single run. Examples: tree, graph (also heap).
LinearNon-linear
Single levelMultiple levels
Easy to implementMore complex
Memory may be wasted (arrays)Memory used as needed
Array, stack, queue, linked listTree, graph

Q2.2 Explain Big O, Big Omega and Big Theta with examples and graphs.

  • Big O (upper bound): f(n) = O(g(n)) if there exist c > 0 and n₀ such that 0 ≤ f(n) ≤ c·g(n) for all n ≥ n₀. Used for the worst case. Example: 3n + 2 = O(n) with c = 4, n₀ = 2.
  • Big Omega (lower bound): f(n) = Ω(g(n)) if 0 ≤ c·g(n) ≤ f(n) for all n ≥ n₀. Used for the best case. Example: 3n + 2 = Ω(n) with c = 3, n₀ = 1.
  • Big Theta (tight bound): f(n) = Θ(g(n)) if c₁·g(n) ≤ f(n) ≤ c₂·g(n) for all n ≥ n₀. Example: 3n + 2 = Θ(n) with c₁ = 3, c₂ = 4, n₀ = 2.

Graphs: for O, draw f(n) staying below c·g(n) after n₀; for Ω, f(n) stays above c·g(n); for Θ, f(n) is sandwiched between c₁·g(n) and c₂·g(n). Mark n₀ on the x-axis in each graph. See DSA Study Guide › Unit 1.

Q2.3 What is an Abstract Data Type (ADT)? How is it different from a data structure?

An ADT is a mathematical model of a data type defined only by its values and operations, without saying how they are implemented. Example: Stack ADT: push, pop, peek, isEmpty, with LIFO behaviour.

A data structure is a concrete implementation that stores data in memory: e.g. a stack implemented using an array or a linked list.

ADTData structure
Logical view: whatPhysical view: how
Implementation-independentImplementation-specific
Stack, Queue, List ADTArray, linked list

Q2.4 Time complexity of:

a) for (i = 0; i < n; i = i*2) { statement(s); } As written, i starts at 0, and 0 × 2 = 0, so the loop never terminates (infinite loop). If i started at 1, i takes values 1, 2, 4, … < n, i.e. about log₂ n iterations → O(log n). Mention both in the exam.

b) for (i = 0; i < n; i += 100) { statement(s); } Runs n/100 times → O(n) (constants are dropped).

c) Is f(n) = n² log n greater than f(n) = n (log n)¹⁰? Divide both by n log n: compare n with (log n)⁹. Any positive power of n grows faster than any power of log n, so yes, n² log n grows faster (n (log n)¹⁰ = O(n² log n)).

Q3. Answer any TWO out of FOUR [10]

Q3.1 What is recursion? Pseudocode for factorial using recursion.

Recursion is when a function solves a problem by calling itself on a smaller input, until it reaches a base case that is answered directly.

Function FACT(n)
1. [Base case]       If n = 0 or n = 1 then Return 1
2. [Recursive step]  Return n × FACT(n − 1)

Trace: FACT(4) = 4 × FACT(3) = 4 × 3 × FACT(2) = 4 × 3 × 2 × FACT(1) = 24. Time O(n), stack space O(n).

Q3.2 Time complexity of:

a)

for (int i = 1; i < n; i = i * 2)
    for (int j = 0; j < i; j++)
        sum++;

The outer loop runs for i = 1, 2, 4, …, < n (about log n times). The inner loop runs i times, so the total work is 1 + 2 + 4 + … + 2^k < 2n. Time complexity: O(n).

b)

int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);
}

T(n) = T(n−1) + T(n−2) + c → the call tree roughly doubles at each level: O(2ⁿ) (tight bound Θ(φⁿ), φ ≈ 1.618). Space: O(n) for the recursion stack.

Q3.3 Pseudocode for finding the largest element in an array.

Procedure LARGEST(A, N)
1. [Initialise]   MAX ← A[0]
2. [Scan]         Repeat for I = 1 to N − 1
                      If A[I] > MAX then MAX ← A[I]
3. [Finished]     Write MAX; Return

Time O(n), space O(1).

Q3.4 Compare iteration and recursion with example.

IterationRecursion
Repeats using loops (for/while)Function calls itself
Termination by loop conditionTermination by base case
No extra stack frames: O(1) spaceUses the call stack: O(depth) space
Usually fasterFunction-call overhead
Infinite loop if condition is wrongStack overflow if base case is missing
Code can be longer for tree-like problemsNatural for trees, Tower of Hanoi, divide & conquer

Example: factorial

int factIter(int n) { int f = 1; for (int i = 2; i <= n; i++) f *= i; return f; }
int factRec(int n)  { return (n <= 1) ? 1 : n * factRec(n - 1); }