a) Differentiate between Linear and Non-Linear Data Structure
Linear Data Structure Non-Linear Data Structure
Elements are arranged hierarchically or
Elements are arranged sequentially
graph-like
Each element has a single predecessor and An element can have multiple
successor (except ends) predecessors/successors
Easy traversal Traversal is more complex
Examples: Array, Stack, Queue, Linked List Examples: Tree, Graph
b) Advantages and Disadvantages of Linked List over Array
Advantages of Linked List
Dynamic size (no fixed size limitation)
Efficient insertion and deletion (no shifting required)
Memory utilization is flexible
Disadvantages of Linked List
Extra memory required for pointers
No direct/random access (sequential access only)
More complex implementation compared to arrays
c) Pseudocode for Pushing an Element into a Stack
PUSH(stack, top, max, item)
BEGIN
IF top == max - 1 THEN
PRINT "Stack Overflow"
ELSE
top ← top + 1
stack[top] ← item
END IF
END
d) Pseudocode for Enqueue and Dequeue Operations (Queue)
Enqueue Operation
ENQUEUE(queue, rear, max, item)
BEGIN
IF rear == max - 1 THEN
PRINT "Queue Overflow"
ELSE
rear ← rear + 1
queue[rear] ← item
END IF
END
Dequeue Operation
DEQUEUE(queue, front, rear)
BEGIN
IF front > rear THEN
PRINT "Queue Underflow"
ELSE
item ← queue[front]
front ← front + 1
RETURN item
END IF
END
e) Complete Binary Tree (with Example)
A complete binary tree is a binary tree in which:
All levels are completely filled except possibly the last level.
Nodes in the last level are filled from left to right.
Example:
1
/ \
2 3
/\ /
4 56
This is a complete binary tree because all levels are filled left to right.
f) Graph – Definition and Types
Definition:
A graph is a non-linear data structure consisting of a set of vertices (nodes) and edges that
connect pairs of vertices.
Types of Graphs:
1. Undirected Graph
Edges have no direction.
Example: A — B
2. Directed Graph (Digraph)
Edges have direction.
Example: A → B
3. Weighted Graph
Edges have weights (costs).
Example: A —(5)— B
4. Cyclic Graph
Contains at least one cycle.
5. Acyclic Graph
Contains no cycles (e.g., Tree, DAG).
g) Sorting vs Searching & Internal vs External Sorting
Sorting vs Searching
Sorting Searching
Arrangement of data in a particular order Finding an element in a dataset
Changes data order Does not change data order
Example: Bubble Sort, Quick Sort Example: Linear Search, Binary Search
Internal vs External Sorting
Internal Sorting External Sorting
Data fits in main memory Data does not fit in main memory
Faster Slower due to disk access
Examples: Insertion Sort, Quick Sort Examples: Merge Sort, External Merge Sort
h) Need of Hashing & Hash Function
Need of Hashing
Provides fast data access
Reduces time complexity for search, insert, and delete operations
Used in symbol tables, databases, and indexing
Hash Function
A hash function is a function that maps a key to a specific index in a hash table.
Example:
h(k) = k mod m
where k is the key and m is the table size.
i) Address Calculation of 2D Array
Given:
Array A[4…7, –1…3]
Element size = 2 bytes
Base address = 100
Number of rows = 7 − 4 + 1 = 4
Number of columns = 3 − (−1) + 1 = 5
Row-Major Order
Formula:
Address = Base + w × [(i − lr) × n + (j − lc)]
= 100 + 2 × [(6 − 4) × 5 + (2 − (−1))]
= 100 + 2 × (10 + 3)
= 100 + 26
= 126
Address of A[6,2] = 126
Column-Major Order
Formula:
Address = Base + w × [(j − lc) × m + (i − lr)]
= 100 + 2 × [(2 − (−1)) × 4 + (6 − 4)]
= 100 + 2 × (12 + 2)
= 100 + 28
= 128
Address of A[6,2] = 128
j) Difference between B-Tree and B+-Tree
B-Tree B+-Tree
Data stored in both internal and leaf nodes Data stored only in leaf nodes
Leaf nodes not linked Leaf nodes are linked
Slower range queries Faster range queries
Used in file systems Used in databases and indexing
Below are 10-mark answers written along with the questions, in a clear exam-oriented
format.
a) Differentiate between Linear Search and Binary Search. Write the pseudocode for
implementing Binary Search. (10 Marks)
Linear Search vs Binary Search
Linear Search Binary Search
Searches elements sequentially Divides the search space into halves
Works on both sorted and unsorted data Works only on sorted data
Time complexity: O(n) Time complexity: O(log n)
Simple to implement More complex than linear search
Slower for large datasets Faster for large datasets
Pseudocode for Binary Search
BINARY_SEARCH(A, n, key)
BEGIN
low ← 0
high ← n − 1
WHILE low ≤ high DO
mid ← (low + high) / 2
IF A[mid] == key THEN
RETURN mid
ELSE IF key < A[mid] THEN
high ← mid − 1
ELSE
low ← mid + 1
END IF
END WHILE
RETURN −1 // Element not found
END
b) Give the prefix expression for (a + ((b * c − e) / f)) using Stack. (10 Marks)
Given Infix Expression
(a + ((b * c − e) / f))
Step 1: Convert Infix to Postfix
b * c → bc*
(b * c − e) → bc*e−
(b * c − e) / f → bc*e−f/
a + (...) → abc*e−f/+
Step 2: Convert Postfix to Prefix
Postfix: a b c * e − f / +
Prefix:
+a/−*bcef
Final Prefix Expression
+a/−*bcef
c) Circular Queue Operations (10 Marks)
Given:
Circular queue size = 5
Elements: 10, 20, 40
Front (F) = 2, Rear (R) = 4
Initial Queue State
Index: 0 1 2 3 4
Queue: - - 10 20 40
F = 2, R = 4
Insert 50
R = (4 + 1) % 5 = 0
Queue:
[50, -, 10, 20, 40]
F = 2, R = 0
Insert 60
R = (0 + 1) % 5 = 1
Queue:
[50, 60, 10, 20, 40]
F = 2, R = 1
Insert 30
Now,
(R + 1) % 5 = 2 = F
👉 Queue is FULL → Overflow occurs
Insertion of 30 is not possible.
Delete Two Elements
Delete 1st element
F = (2 + 1) % 5 = 3
Delete 2nd element
F = (3 + 1) % 5 = 4
Queue state:
[50, 60, -, -, 40]
F = 4, R = 1
Insert 70
R = (1 + 1) % 5 = 2
Insert 80
R = (2 + 1) % 5 = 3
Insert 90
R = (3 + 1) % 5 = 4
Final Queue State
[50, 60, 70, 80, 90]
F = 4, R = 4
✅ Summary of F and R Changes
Operation F R
Initial 2 4
Insert 50 2 0
Insert 60 2 1
Insert 30 Overflow —
Delete 2 elements 4 1
Insert 70 4 2
Insert 80 4 3
Insert 90 4 4