Of course!

Here are the answers to your questions about the Fundamentals of Data Structures,
structured for your exam preparation.

1. Define data structures. Explain the classification of data structures

with examples.
A data structure is a particular way of organizing and storing data in a computer so that it can be
accessed and used efficiently. [cite_start]It defines the relationship between the data and the
operations that can be performed on that data.
[cite_start]Classification of Data Structures:
Data structures can be broadly classified into two main categories:
A. Primitive Data Structures: These are the basic data structures that are directly operated
upon by machine-level instructions.
●​ Examples: Integers, Floats, Characters, and Pointers.
B. Non-Primitive Data Structures: These are more complex data structures derived from
primitive data structures. They are used to store a collection of data. They are further divided
into:
i. Linear Data Structures: In linear data structures, the elements are arranged in a sequential
or linear order. Each element is connected to its previous and next element.
●​ Arrays: A collection of homogeneous elements stored in contiguous memory locations.
●​ [cite_start]Linked Lists: A collection of nodes where each node contains data and a
pointer to the next node.
●​ [cite_start]Stacks: A linear data structure that follows the Last-In, First-Out (LIFO)
principle.
●​ [cite_start]Queues: A linear data structure that follows the First-In, First-Out (FIFO)
principle.
ii. Non-Linear Data Structures: In non-linear data structures, the elements are not arranged in
a sequential order. The data items are connected in a hierarchical or network manner.
●​ Trees: A hierarchical structure where data is organized in parent-child relationships.
[cite_start]A binary tree is a common example.
●​ Graphs: A collection of vertices (nodes) and edges that connect these vertices.
[cite_start]A social network is a real-world example of a graph.

2. Explain circular queue with array representation. Write algorithms

for enqueue and dequeue operations.
[cite_start]A circular queue is a linear data structure that follows the FIFO (First-In, First-Out)
principle, but with a modification where the last position is connected back to the first position to
form a circle. This structure efficiently utilizes the space in an array by allowing elements to be
added to the end of the queue even if the array is full, provided there is empty space at the
beginning.
Array Representation: A circular queue is implemented using an array and two pointers: front
and rear.
●​ front: Points to the first element of the queue.
●​ rear: Points to the last element of the queue.
Initially, both front and rear are set to -1, indicating an empty queue.
Algorithms:
Let CQ be the circular queue, MAX be the size of the array, front and rear be the pointers, and
item be the element to be inserted.
Algorithm for Enqueue (Insertion): This operation adds an element to the rear of the queue.
1.​ Check for Overflow: If (front == 0 && rear == MAX-1) or (front == rear + 1), the queue is
full. Print "Overflow" and exit.
2.​ Handle First Element Insertion: If front == -1, it means the queue is empty. Set front = 0
and rear = 0.
3.​ Wrap-around Insertion: If rear == MAX-1 and front != 0, it means the rear has reached
the end of the array, but there is space at the beginning. Set rear = 0.
4.​ Normal Insertion: Otherwise, increment rear by 1: rear = rear + 1.
5.​ Insert Element: Set CQ[rear] = item.
Algorithm for Dequeue (Deletion): This operation removes an element from the front of the
queue.
1.​ Check for Underflow: If front == -1, the queue is empty. Print "Underflow" and exit.
2.​ Get the Element: Set item = CQ[front].
3.​ Handle Single Element Queue: If front == rear, it means there's only one element. Set
front = -1 and rear = -1.
4.​ Wrap-around Deletion: If front == MAX-1, it means the front is at the end of the array.
Set front = 0.
5.​ Normal Deletion: Otherwise, increment front by 1: front = front + 1.
6.​ Return item.

3. Compare stack and queue with respect to operations, order of

execution, and applications.
Feature Stack Queue
Operations Push: Adds an item to the top Enqueue: Adds an item to the
of the stack. [cite_start]<br> rear of the queue.
Pop: Removes an item from [cite_start]<br> Dequeue:
the top of the stack. Removes an item from the front
of the queue.
Order of Execution LIFO (Last-In, First-Out): The FIFO (First-In, First-Out): The
element that is inserted last is element that is inserted first is
the first one to be removed. the first one to be removed.
Applications - [cite_start]Function call - CPU and disk scheduling <br>
management (recursion) <br> - - Handling requests on a single
Expression conversion (Infix to shared resource (e.g., printer)
Postfix) [cite_start]<br> - <br> - Buffers in networking
Expression evaluation (Postfix <br> - Call center phone
evaluation) <br> - Undo/Redo systems
functionality in editors
4. What is recursion? Explain its working with an example of
calculating factorial using recursion.
[cite_start]Recursion is a programming technique where a function calls itself, either directly or
indirectly, to solve a problem. A recursive function must have a base case, which is a condition
that stops the recursion, and a recursive step, where the function calls itself with a modified
argument that moves it closer to the base case.
Working of Recursion: When a recursive function is called, its state (local variables and
parameters) is pushed onto the system's call stack. If the function calls itself again, a new state
is pushed onto the stack. When the base case is reached, the function returns a value, and its
state is popped from the stack. The execution then returns to the previous call, which continues
its computation until it also returns, and so on, until the initial call is completed.
Example: Factorial using Recursion
The factorial of a non-negative integer 'n' (denoted as n!) is the product of all positive integers
less than or equal to n. (e.g., 5! = 5 * 4 * 3 * 2 * 1 = 120).
A recursive function to calculate factorial can be defined as:
●​ Base Case: If n = 0 or n = 1, factorial(n) = 1.
●​ Recursive Step: If n > 1, factorial(n) = n * factorial(n-1).
How it works for factorial(4):
1.​ factorial(4) is called. Since 4 is not the base case, it calls 4 * factorial(3).
2.​ factorial(3) is called. It calls 3 * factorial(2).
3.​ factorial(2) is called. It calls 2 * factorial(1).
4.​ factorial(1) is called. This is the base case, so it returns 1.
5.​ The value 1 is returned to factorial(2), which computes 2 * 1 = 2 and returns 2.
6.​ The value 2 is returned to factorial(3), which computes 3 * 2 = 6 and returns 6.
7.​ The value 6 is returned to factorial(4), which computes 4 * 6 = 24 and returns 24.
The final result is 24.

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

structure? Give examples.
Abstract Data Type (ADT): [cite_start]An Abstract Data Type is a mathematical or logical
model of a data structure that specifies the type of data stored, the operations that can be
performed on that data, and the behavior of those operations, without specifying the
implementation details. It focuses on "what" the data structure does, not "how" it does it.
Difference between ADT and Data Structure:
Basis of Comparison Abstract Data Type (ADT) Data Structure
Concept [cite_start]A theoretical concept [cite_start]A concrete
that defines a set of values and implementation of an ADT that
a set of operations (a logical provides a way of organizing
description). and storing data.
Focus Focuses on the "what" Focuses on the "how"
(behavior, operations). It hides (implementation). It is the
the implementation details. actual representation of the
data.
Level of Abstraction High-level (Interface). Low-level (Implementation).
Example The List ADT specifies that we An Array or a Linked List are
can store a collection of items data structures that can be
and perform operations like used to implement the List ADT.
add(), remove(), get(), size().
In simpler terms, an ADT is like a blueprint or an interface, while a data structure is the actual
building constructed from that blueprint.