Question Bank for DSA UNIT I

​ Data Structures Overview: Concept of data, Data object, Data structure, Concept of
Primitive, and non-primitive, linear and Nonlinear, static and dynamic, persistent and
ephemeral data structures. Abstract Data Types (ADTs), Arrays, multidimensional
arrays, pointers, dynamic memory allocation.

​ Iteration and Recursion: Recursive algorithms, solving problems with recursion.

​ Linked Structures: Linked lists singly and doubly, circular linked lists, introduction to
generalized linked lists, Applications of linked lists (dynamic memory allocation,
polynomial representation)

​ Asymptotic notations: Big-O, Big-Theta, Big-Omega notations, Frequency count,

Time, and space complexity.

​ Case Study: Representing a polynomial using a linked list (LL) and performing
operations - addition, subtraction, and multiplication on given 2 polynomials.

Sr No Question Mark Bloo

s m’s
6/5/4/ taxon
2 omy
Data Structures Overview: Concept of data, Data object, Data structure, Concept of
Primitive, and non-primitive, linear and Nonlinear, static and dynamic, persistent and
ephemeral data structures. Abstract Data Types (ADTs), Arrays, multidimensional arrays,
pointers, dynamic memory allocation.

1. Define and differentiate between data, data object, and data 4 2

structure with suitable examples.

2. Explain how organizing data into data structures improves the 4 2

efficiency of programs.

3. What are primitive and non-primitive data structures? Give at 4 2

least two examples of each.

4. Differentiate between linear and non-linear data structures. 5 2

Illustrate with diagrams and examples.

5. Explain static and dynamic data structures with suitable 4 2

examples. Highlight key differences.

6. Why are dynamic data structures preferred in certain 5 3

applications? Give at least two scenarios.

7. Define persistent and ephemeral data structures. Give one 4 2

real-life example of each.

8. What is an Abstract Data Type? Explain with examples of at least 5 2

two ADTs.

9. Write an algorithm to insert an element at a specific position in a 6 3

1D array. Analyze the time complexity. (handle the case collision
assuming that sufficient locations are available in the array)

10. Discuss the limitations of arrays. How are they overcome by 5 3

other structures?

11. What is a 2D array? Explain memory storage 5 2

12. Write a C++ program to dynamically allocate memory for an 6 3

integer array and release it.

13. Explain the concept of pointers with a diagram. How are they 5 2
useful in data structures?
14
Compare persistent and ephemeral data structures with ( 5).
example
15
What do you mean by data structure ? Explain linear and (5)
Nonlinear with example.

16
Define ADT? Write an ADT for integer. (5)

17
(5)
Draw the memory map and annotate the address and
subscript to each element of array of following types ?

Char c[10][10]; Float f[10][10];

18
How address is calculated in arrays? For a given A[10] elements (5)
of integer type explain address calculation if base address is
1000

19
Compare row major and column major wrt to array

20
Define ADT? Write an ADT for Array (5)

Iteration and Recursion: Recursive algorithms, solving problems with recursion.

1 Explain the difference between iteration and recursion. Provide 5 2
one example of a problem best solved using recursion and justify
why recursion is preferred.
2 Write a recursive algorithm to find the greatest common divisor 6 3
(GCD) of two numbers m and n.
a) Explain the base case and recursive case. (2 marks)
b) Trace the recursion for GCD(48, 18) step by step. (4 marks)
3 6 3
The factorial of a number n (denoted as n!) is defined as:

n!=n×(n−1)×(n−2)×…×1,with 0!=1
(a) Write an algorithm to compute the factorial of a number using
a recursive approach.​
(b) Write the same algorithm using an iterative approach
(loop-based).​
(c) Compare the recursive and iterative solutions in terms of
efficiency and memory usage.
4 6 3
For input 1234, the output should be 1+2+3+4 = 10​
(a) Write a recursive algorithm to calculate the sum of digits of a
number.​
(b) Write the same algorithm using iteration.​
(c) Which approach is easier to understand and why?

5 Write a CPP pseudocode algorithm for String Reversal using a 6 3

recursive and iterative way.
 Compare both solutions in terms of space usage
Asymptotic notations: Big-O, Big-Theta, Big-Omega notations, Frequency count, Time,
and space complexity.

1 Define Big-O, Big-Theta, and Big-Omega notations. Explain with 5 2

examples how each notation represents the time complexity of
an algorithm
2 Write an algorithm to find the smallest element in an array of 6 3
integers and analyze its time complexity using frequency count.
3 What is Time complexity of an algorithm? Explain its importance 4 2
with suitable example.
4 Obtain the frequency count for the following code 3 3
for (int i = 0; i < m; i++) {
for (int j = 0; j < p; j++) {
for (int k = 0; k < n; k++) {
C[i][j] += A[i][k] * B[k][j];
}
}
}

5 Obtain the frequency count for the following code 3 3

int temp = num;

do {
sum += temp % 10;
temp /= 10;
} while (temp > 0);

6 Obtain the frequency count for the following code 3 3

original = num;
do {
int digit = num % 10;
rev = rev * 10 + digit;
num /= 10;
} while (num > 0);

7
1. Calculate Space and time complexity of following code
snippet (4)

int a = 0, b = 0;

for (i = 0; i < N; i++) {

​ a = a + rand();
 }

for (j = 0; j < M; j++) {

​ b = b + rand();

8
Why Big O is used instead of other notations.(2)

9
If complexity is O( n!), What does it mean.(2)

10
Why asymptomatic notation are used to compare algorithms.(3)

11
What is Frequency count ? How it is used for calculating
complexity?

12
What is big O notation, list all algorithms with O(n) notation.
Write how you calculate complexity. (5)

Linked Structures: Linked lists singly and doubly, circular linked lists, introduction to
generalized linked lists, Applications of linked lists (dynamic memory allocation,
polynomial representation)

1 Dataset of patient is stored in linked organization, search patient’s 5M 3

name in the given list. List can be traversed to and fro.
2 Design Binary search algorithm using Iterative and non-iterative 5M 3
manner.
3 Write a C++ Pseudocode to insert a node in linked list in 5M 4
ascending order
4 Write an algorithm to copy one linked list in to another list 3M 4
5 Write an algorithm to concatenate one linked list in to another list 4M 4
6 Write a C++ Pseudocode to delete a node from doubly linked 5M 3
list.
7 Write a C++ Pseudocode to search a node in doubly linked list. 5M 3

8 Write a C++ Pseudocode to delete a node from singly linked list. 5M 3

9 Write a C++ Pseudocode to insert a node in doubly linked list. 5M 3
10 Write a C++ Pseudocode to find a node in singly linked list. 5M 3
11 What do you mean by CLL? Mention display Pseudocode of 5M 3
CLL?
12 Represent given list using (p, q, (r, s, (t, u, v), w ),x, y) GLL
13 Polynomial representation using Linked List

8X3
14 Represent polynomial expression using linked List
15
Write a C++ function to perform following operations

1. To find a node in singly linked list.

2. To delete a node from singly linked list.