Q1. Explain Array data structure with operations and example.
(5 Marks)
Answer:
An array is a linear data structure that stores a collection of elements of the
same data type in contiguous memory locations. Each element in an array is
identified by an index, which allows fast access to any element directly.
Characteristics of Array:
Fixed or dynamic size
Stores homogeneous data
Direct access using index
Stored in contiguous memory
Basic Operations on Array:
Traversal – Visiting each element
Insertion – Adding an element at a specific position
Deletion – Removing an element
Searching – Finding an element
Updation – Modifying an element
Python Example:
arr = [10, 20, 30, 40]
# Traversal
for i in arr:
print(i)
# Insertion
[Link](2, 25)
# Deletion
[Link](20)
# Searching
print(30 in arr)
Advantages: Fast access, easy implementation
Disadvantages: Insertion and deletion are costly due to shifting
Q2. Explain Singly Linked List in detail with example. (5 Marks)
Answer:
A singly linked list is a dynamic linear data structure where elements are
stored in nodes. Each node contains two parts:
Data
Address of the next node
Unlike arrays, linked lists do not store elements in contiguous memory
locations.
Structure of Node:
| Data | Next |
Working:
The first node is called head
The last node points to NULL
Traversal is done only in forward direction
Python Example:
class Node:
def __init__(self, data):
[Link] = data
[Link] = None
n1 = Node(10)
n2 = Node(20)
n3 = Node(30)
[Link] = n2
[Link] = n3
temp = n1
while temp:
print([Link], end=" -> ")
temp = [Link]
Advantages: Dynamic size, efficient insertion
Disadvantages: Extra memory for pointers, no random access
Q.)Explain Doubly Linked List in Detail with Example (5 Marks)
Answer:
A doubly linked list is a linear data structure in which each node contains
three parts:
A pointer to the previous node
The data part
A pointer to the next node
Unlike a singly linked list, a doubly linked list allows traversal in both
forward and backward directions. This makes certain operations such as deletion
and reverse traversal easier and more efficient.
Structure of a Node:
| Prev | Data | Next |
The first node’s prev pointer is set to NULL
The last node’s next pointer is set to NULL
Nodes are connected in both directions
Working of Doubly Linked List:
Each node knows the address of both its previous and next nodes
Traversal can be done from head to tail and tail to head
Deletion does not require traversal to find the previous node
Python Example:
class Node:
def __init__(self, data):
[Link] = None
[Link] = data
[Link] = None
# Creating nodes
n1 = Node(10)
n2 = Node(20)
n3 = Node(30)
# Linking nodes
[Link] = n2
[Link] = n1
[Link] = n3
[Link] = n2
# Forward traversal
temp = n1
while temp:
print([Link], end=" <-> ")
temp = [Link]
Advantages of Doubly Linked List:
Traversal possible in both directions
Easier deletion of a specific node
Efficient insertion and deletion
Disadvantages of Doubly Linked List:
Requires extra memory for previous pointer
More complex implementation compared to singly linked list
Q8. Explain Circular Queue in detail. (5 Marks)
Answer:
A circular queue is an improved version of linear queue where the last position
is connected back to the first position, forming a circle. This helps in
efficient utilization of memory.
Advantages:
No memory wastage
Better performance
Efficient for scheduling
Circular queues are widely used in operating systems.
Q9. Explain Priority Queue with example. (5 Marks)
Answer:
A priority queue is a special type of queue where each element has a priority.
Elements with higher priority are removed first, regardless of insertion order.
Real-Life Example:
Emergency patients in hospital
Python Example:
import heapq
pq = []
[Link](pq, 3)
[Link](pq, 1)
[Link](pq, 2)
print([Link](pq))
Q9. Explain Priority Queue with example. (5 Marks)
Answer:
A priority queue is a special type of queue where each element has a priority.
Elements with higher priority are removed first, regardless of insertion order.
Real-Life Example:
Emergency patients in hospital
Python Example:
import heapq
pq = []
[Link](pq, 3)
[Link](pq, 1)
[Link](pq, 2)
print([Link](pq))
Compare Stack and Queue (5 Marks)
Answer:
Stack and Queue are both linear data structures used to store and manage data in
a sequential manner, but they differ in the way elements are inserted and
removed. The main difference between stack and queue lies in the order of
processing of elements.
A stack follows the LIFO (Last In First Out) principle. This means the element
that is inserted last is removed first. In a stack, both insertion (push) and
deletion (pop) operations take place at the same end, called the top of the
stack. Because of this property, stacks are widely used in situations where
reversing data or backtracking is required.
On the other hand, a queue follows the FIFO (First In First Out) principle. This
means the element that is inserted first is removed first. In a queue, insertion
(enqueue) is performed at the rear, while deletion (dequeue) is performed from
the front. Due to this behavior, queues are commonly used in scheduling and
resource management applications.
Python Example:
Stack Example:
stack = []
[Link](10)
[Link](20)
[Link]()
print(stack)
Queue Example:
from collections import deque
q = deque()
[Link](10)
[Link](20)
[Link]()
print(q)
Q. Explain recursion and its working mechanism. (5 Marks)
Answer:
Recursion is a programming technique where a function calls itself to solve a
problem by breaking it into smaller subproblems.
Components:
Base condition
Recursive call
Example:
def factorial(n):
if n == 0:
return 1
return n * factorial(n-1)
Each recursive call is stored in the call stack.
[Link] Stack and Its Operations in Detail with Examples (5 Marks)
Answer:
A stack is a linear data structure that follows the LIFO (Last In First Out)
principle. This means that the element which is inserted last is the first one
to be removed. In a stack, both insertion and deletion operations are performed
at one end only, known as the top of the stack.
Stacks are widely used in computer science for managing function calls,
expression evaluation, and undo/redo operations because of their last-come-
first-serve behavior.
Basic Terminology:
Top: Points to the most recent element in the stack
Push: Operation to insert an element into the stack
Pop: Operation to remove an element from the stack
Stack Operations:
1. Push Operation
The push operation inserts an element at the top of the stack. Before inserting,
overflow condition is checked to ensure the stack is not full.
stack = []
[Link](10)
[Link](20)
[Link](30)
print(stack)
2. Pop Operation
The pop operation removes the top element from the stack. Underflow condition
occurs if we try to pop from an empty stack.
[Link]()
print(stack)
3. Peek (Top) Operation
The peek operation returns the top element without removing it.
print(stack[-1])
4. IsEmpty Operation
This operation checks whether the stack is empty or not.
if not stack:
print("Stack is empty")
Advantages of Stack:
Simple implementation
Efficient memory usage
Useful in recursion and backtracking
Applications of Stack:
Function calls (call stack)
Expression evaluation
Undo and redo operations
Q.n improved version of the simple queue where the last position is connected
back to the first position, forming a circular structure. This allows better
utilization of memory by reusing empty spaces.
Example:
class CircularQueue:
def __init__(self, size):
[Link] = [None]*size
[Link] = [Link] = -1
Advantage: Efficient memory usage
Application: CPU scheduling (Round Robin)
3. Priority Queue
A priority queue is a special type of queue in which each element is assigned a
priority. Elements with higher priority are removed first, regardless of the
order of insertion.
Real-Life Example:
Emergency patients treated first in hospitals.
Python Example:
import heapq
pq = []
[Link](pq, 2)
[Link](pq, 1)
[Link](pq, 3)
print([Link](pq))