[Link].

COMPUTER SCIENCE AND

ENGINEERING
PAPER SET: set_2 PAPER TYPE: Question Paper

TIME: 3 HOURS SEMESTER/YEAR: II SUBJECT CODE: 41205

SUBJECT: DATA STRUCTURES AND ALGORITHMS MAX MARKS: 100

Answer Key

[Link] Answer All the Questions Unit

Part A (10x2 = 20 Marks)
1 Compare primitive data types with data structures. U1
Answer:
Primitive Data Types Data Structures
Basic data types (int, float, Collection of data elements
char)
Store single value Store multiple values
Built-in User-defined
Simple operations Complex operations
2 Define time complexity. Illustrate with an example from sorting algorithms. U1
Answer:
Time complexity is the measure of time taken by an algorithm as a function of
input size n.
Example:
 Linear Search → O(n)
 Binary Search → O(log n)
3 Define singly linked list and illustrate its structure with a diagram. U2
Answer:
A singly linked list is a collection of nodes where each node contains data and a
pointer to the next node.
HEAD → [10] → [20] → [30] → NULL
4 Define circular linked list and mention its use in real-time applications. U2
Answer:
A circular linked list is a linked list where the last node points to the first node.
Application:
 Round-robin scheduling
 Circular buffer
5 Identify the operations of a stack and classify them based on their functionality. U3
Answer:

Operations:
 Push → Insert
  Pop → Delete
 Peek → View top
Classification:
 Based on LIFO principle
 Static (array) / Dynamic (linked list)

6 Convert the following infix expression into postfix form and justify the result U3
(A + B) ∗ (C − D) / E + F
Answer:
Postfix:
AB+CD-*E/F+
7 Define queue ADT. What are its basic operations? U4
Answer:
A queue ADT follows FIFO principle.
Operations:
 Enqueue
 Dequeue
 Peek
8 Define dequeue. Mention its types. U4
Answer:
A deque (double-ended queue) allows insertion and deletion at both ends.
Types:
 Input-restricted deque
 Output-restricted deque
9 What is a binary tree? Differentiate it with a complete binary tree. U5
Answer:
Binary Tree vs Complete Binary Tree
Binary Tree Complete Binary Tree
Each node has ≤ 2 All levels filled except last
children
General structure Strict left-to-right filling
May have gaps No gaps allowed
10 Define expression tree and explain its significance in computation. U5
Answer:
An expression tree is a binary tree where:
 Internal nodes → operators
 Leaf nodes → operands
Significance:
 Expression evaluation
 Compiler design
[Link] Part B (5x16 = 80 Marks) Unit
Q11 Demonstrate Quick Sort by tracing its execution using a suitable example. U1
Answer:

1. Definition (2 Marks)
Quick Sort is a divide-and-conquer sorting algorithm that:

 Selects a pivot element

 Partitions the array into two parts:
o Elements less than pivot
o Elements greater than pivot
 Recursively sorts subarrays

2. Algorithm (4 Marks)
QUICKSORT(A, low, high)
1. if low < high:
2. p = PARTITION(A, low, high)
3. QUICKSORT(A, low, p-1)
4. QUICKSORT(A, p+1, high)

PARTITION(A, low, high)

1. pivot = A[high]
2. i = low - 1
3. for j = low to high-1:
4. if A[j] < pivot:
5. i++
6. swap A[i], A[j]
7. swap A[i+1], A[high]
8. return i+1

3. Example (1 Mark)

Sort the array:

[10, 7, 8, 9, 1, 5]

4. Step-by-Step Trace (7 Marks)

✔ Step 1: Pivot = 5
[10, 7, 8, 9, 1, 5]
→ [1, 5, 8, 9, 10, 7]

Pivot index = 1

✔ Step 2: Left Subarray [1] → already sorted

✔ Step 3: Right Subarray [8, 9, 10, 7]

 Pivot = 7

[8, 9, 10, 7]
→ [7, 9, 10, 8]

✔ Step 4: Right Subarray [9, 10, 8]

Pivot = 8

[9, 10, 8]
→ [8, 10, 9]

✔ Step 5: Right Subarray [10, 9]

Pivot = 9

[10, 9]
→ [9, 10]

5. Final Sorted Array (1 Mark)

[1, 5, 7, 8, 9, 10]

6. Time Complexity (2 Mark)

Case Complexity
Best O(n log n)
Averag O(n log n)
e
Worst O(n²)
(OR)
Q11 Explain one-dimensional and two-dimensional arrays with memory representation, U1
operations, and examples.
Answer:

1. One-Dimensional Array (1D Array) (3 Marks)

✔ Definition
A one-dimensional array is a collection of elements of the same data type
stored in contiguous memory locations and accessed using a single index.

✔ Example
int A[5] = {10, 20, 30, 40, 50};

2. Memory Representation of 1D Array (3 Marks)

Address Calculation Formula:

Example:
If base = 1000 and size = 4 bytes
A[2] = 1000 + (2 × 4) = 1008

3. Operations on 1D Array (2 Marks)

 Traversal → Visit all elements
 Insertion → Add element at position
 Deletion → Remove element
 Searching → Find element

4. Two-Dimensional Array (2D Array) (3 Marks)

✔ Definition
A two-dimensional array is a collection of elements arranged in rows and
columns, accessed using two indices.

✔ Example
int A[2][3] = {
{1, 2, 3},
{4, 5, 6}
};

5. Memory Representation of 2D Array (3 Marks)

 6. Operations on 2D Array (1 Mark)
 Traversal (row-wise / column-wise)
 Insertion / update
 Searching

7. Differences (2 Mark)
1D Array 2D Array
Single index Two indices
Linear Matrix structure
structure
Simple access Row & column access
Q12 Illustrate the working of a doubly linked list with node structure and memory U2
representation.
Answer:

1. Definition (2 Marks)
A doubly linked list (DLL) is a linear data structure in which each node
contains:

 Data
 Pointer to previous node (prev)
 Pointer to next node (next)

Allows traversal in both forward and backward directions

2. Node Structure (2 Marks)

struct Node {
int data;
struct Node* prev;
struct Node* next;
};

3. Representation (Diagram) (3 Marks)

Example:
NULL ← [10 | • | •] ⇄ [20 | • | •] ⇄ [30 | • | •] → NULL

4. Memory Representation (2 Marks)

 Nodes are stored in non-contiguous memory locations
 Each node contains:
o prev → address of previous node
o next → address of next node

Enables bidirectional navigation

5. Working of Doubly Linked List (5 Marks)

(a) Traversal
Forward Traversal:

temp = head
while temp != NULL:
print temp->data
temp = temp->next
Backward Traversal:

temp = last node

while temp != NULL:
print temp->data
temp = temp->prev

(b) Insertion at Beginning

1. Create new node
2. new->next = head
3. new->prev = NULL
4. if head != NULL:
head->prev = new
5. head = new

(c) Insertion at End

1. Traverse to last node
2. last->next = new
3. new->prev = last
4. new->next = NULL

(d) Deletion
1. Locate node to delete
2. prev->next = next node
3. next->prev = prev node
4. free(node)
 6. Advantages (1 Mark)
 Bidirectional traversal
 Easy insertion and deletion
 No need to traverse from beginning always

7. Disadvantages (2 Mark)
 Extra memory for prev pointer
 More complex implementation

(OR)
Q12 Describe linked list operations including traversal, insertion at different positions, and U2
deletion. Write algorithms and analyze efficiency.

Answer:

1. Linked List (Brief) (1–2 Marks)

A linked list is a collection of nodes where each node contains:

 Data
 Pointer to next node

Stored in non-contiguous memory

2. Traversal (3 Marks)
Visiting all nodes sequentially

TRAVERSE(head)
1. temp = head
2. while temp != NULL
3. print temp->data
4. temp = temp->next
✔ Time Complexity: O(n)

3. Insertion Operations (6 Marks)

(a) Insertion at Beginning

1. Create new node
2. new->next = head
3. head = new
✔ Time Complexity: O(1)

(b) Insertion at End

1. Create new node
2. temp = head
3. while temp->next != NULL
4. temp = temp->next
5. temp->next = new
✔ Time Complexity: O(n)

(c) Insertion at Position

1. Traverse to (pos-1)
2. new->next = temp->next
3. temp->next = new
✔ Time Complexity: O(n)

4. Deletion Operations (5 Marks)

(a) Deletion at Beginning

1. temp = head
2. head = head->next
3. free(temp)
✔ Time Complexity: O(1)

(b) Deletion at End

1. Traverse to second last node
2. temp = last node
3. prev->next = NULL
4. free(temp)
✔ Time Complexity: O(n)

(c) Deletion at Position

1. Traverse to (pos-1)
2. temp = node to delete
3. prev->next = temp->next
4. free(temp)
✔ Time Complexity: O(n)

5. Efficiency Analysis (3 Marks)

Operation Time Complexity
Traversal O(n)
Insert (Beginning) O(1)
Insert (End) O(n)
Insert (Position) O(n)
Delete O(1)
(Beginning)
Delete (End) O(n)
Delete (Position) O(n)

6. Advantages (1 Mark)
  Dynamic size
 Efficient insertion/deletion

7. Disadvantages (1 Mark)
 No random access
 Extra memory for pointer

Q13 Explain recursion using the implicit stack mechanism. Illustrate the execution of a U3
recursive factorial function using stack trace, and discuss multiple stack concepts with
applications.
Answer:

1. Recursion & Implicit Stack (3 Marks)

Recursion is a technique where a function calls itself to solve a problem.

During recursion, the system uses an implicit stack (function call stack) to:

 Store function parameters

 Maintain local variables
 Store return addresses

✔Each function call creates a stack frame

✔ Follows LIFO (Last In First Out) order

2. Function Call Stack (2 Marks)

 Each recursive call is pushed onto the stack
 When base condition is reached → function returns
 Calls are popped in reverse order

3. Example: Factorial Function (4 Marks)

✔ Definition

int fact(int n) {
if(n == 1)
return 1;
return n * fact(n-1);
}

4. Stack Trace (Execution) (4 Marks)

Evaluate fact(4)

Function Calls (Push)

Top
-----
 fact(1)
fact(2)
fact(3)
fact(4)

Returning (Pop)
fact(1) = 1
fact(2) = 2 × 1 = 2
fact(3) = 3 × 2 = 6
fact(4) = 4 × 6 = 24

5. Multiple Stack Concept (2 Marks)

Multiple stacks refer to using more than one stack in memory.

Types:
 Two stacks in one array
 Multiple independent stacks

6. Applications of Multiple Stacks (3 Marks)

 Expression evaluation
 Undo/Redo operations
 Backtracking algorithms
 Function call management

7. Advantages of Recursion (1 Mark)

 Simplifies complex problems
 Cleaner and readable code

8. Disadvantages (1 Mark)
 Extra memory usage (stack overhead)
 Risk of stack overflow

(OR)
Q13 Explain stack ADT with suitable representation. Discuss its implementation using U3
array and linked list, and write algorithms for PUSH and POP operations. Analyze the
time complexity.
Answer:

1. Stack ADT (Definition) (2 Marks)

A Stack ADT is a linear data structure that follows the LIFO (Last In First Out)
principle.

Basic operations:

 PUSH → Insert element

  POP → Remove element
 PEEK → View top element

2. Representation of Stack (2 Marks)

Stack can be represented using:

 Array (Static implementation)

 Linked List (Dynamic implementation)

3. Array Implementation (Static) (5 Marks)

Representation
Stack:
[10]
[20]
[30] ← Top
👉 Uses:

 top pointer
 Array A[]

Algorithm: PUSH (Array)

PUSH(A, top, n, value)
1. if top == n-1 → Overflow
2. top = top + 1
3. A[top] = value

Algorithm: POP (Array)

POP(A, top)
1. if top == -1 → Underflow
2. value = A[top]
3. top = top - 1
4. return value

Limitations
 Fixed size
 Overflow possible

4. Linked List Implementation (Dynamic) (5 Marks)

Representation
Top → [30] → [20] → [10] → NULL

Uses pointer top

Algorithm: PUSH (Linked List)

1. Create new node
2. new->data = value
 3. new->next = top
4. top = new

Algorithm: POP (Linked List)

1. if top == NULL → Underflow
2. temp = top
3. top = top->next
4. free(temp)

Advantages
 Dynamic size
 No overflow (until memory full)

5. Time Complexity Analysis (3 Marks)

Operation Array Linked List
PUSH O(1) O(1)
POP O(1) O(1)
PEEK O(1) O(1)

6. Comparison (Optional Extra) (1 Mark)

Feature Array Linked List
Size Fixed Dynamic
Memory Contiguous Non-contiguous
Overflow Possible Rare
Q14 Discuss circular queue and its implementation using array. Provide algorithms for U4
operations, explain conditions for full and empty, and analyze its advantages.
Answer:

1. Definition (2 Marks)
A circular queue is a linear data structure in which:

 The last position is connected back to the first position

 It forms a circular structure
 Follows FIFO (First In First Out)

Overcomes limitation of linear queue (false overflow)

2. Representation (2 Marks)
Uses:

 Array A[n]
 front → first element
 rear → last element

3. Conditions (3 Marks)
✔ Empty Condition
front == -1
✔Full Condition
(front == (rear + 1) % n)

4. Operations (Algorithms) (6 Marks)

(a) ENQUEUE (Insertion)

ENQUEUE(A, front, rear, n, value)
1. if (front == (rear + 1) % n) → Overflow
2. if front == -1:
front = rear = 0
else:
rear = (rear + 1) % n
3. A[rear] = value

(b) DEQUEUE (Deletion)

DEQUEUE(A, front, rear, n)
1. if front == -1 → Underflow
2. value = A[front]
3. if front == rear:
front = rear = -1
else:
front = (front + 1) % n
4. return value

(c) Display / Traversal

 i = front
while True:
print A[i]
if i == rear: break
i = (i + 1) % n
5. Advantages (2 Marks)
 Efficient memory utilization
 Eliminates false overflow
 Faster operations using circular indexing
 Suitable for real-time systems

6. Disadvantages (1 Mark)
 Implementation is slightly complex
 Difficult to differentiate full vs empty (handled using condition)

7. Time Complexity (2 Mark)

Operation Complexity
ENQUEUE O(1)
DEQUEUE O(1)
(OR)
Q14 Explain priority queue in detail with suitable example. Describe its representation U4
methods, operations, and applications such as CPU scheduling.
Answer:

1. Definition (2 Marks)
A priority queue is a data structure where each element is assigned a priority,
and elements are processed based on priority order rather than FIFO.

Higher priority element is served first

If priorities are equal → FIFO is followed

2. Example (2 Marks)
Consider processes:

Process Priority
P1 3
P2 1
P3 2
✔ Execution order: P2 → P3 → P1 (lower number = higher priority)

3. Representation Methods (4 Marks)

(a) Array / List Representation

  Elements stored in array
 Can be:
o Unsorted → insertion fast
o Sorted → deletion fast

(b) Heap Representation (Binary Heap)

 Implemented using binary heap

 Types:
o Min Heap → smallest element at root
o Max Heap → largest element at root

✔ Most efficient implementation

4. Operations (Algorithms) (4 Marks)

(a) INSERT (Enqueue)

Add element based on priority

1. Insert element at proper position

2. Maintain priority order
 (b) DELETE (Dequeue)
Remove highest priority element

1. Remove element with highest priority

2. Rearrange remaining elements

(c) PEEK
Return element with highest priority

5. Time Complexity (2 Marks)

Operation Array Heap
Insert O(n) / O(1) O(log n)
Delete O(n) / O(1) O(log n)
Peek O(1) O(1)

6. Applications (3 Marks)
 CPU Scheduling (process with highest priority executes first)
 Dijkstra’s Algorithm (shortest path)
 Huffman Coding
 Network packet scheduling

7. Advantages (1 Mark)
 Efficient priority-based processing
 Flexible data handling

Q15 Construct a binary tree from the given traversals (Inorder: D B E A F C, Postorder: D E U5
B F C A) and draw the resulting tree. Find the preorder traversal, determine the height
of the tree, and identify the leaf and internal nodes.
Answer:

Given Traversals
 Inorder: D B E A F C
 Postorder: D E B F C A

1. Construct Binary Tree (Step-by-Step)

✔ Step 1: Identify Root
Last element of Postorder = A (Root)

✔ Step 2: Split Inorder using A

Inorder: D B E | A | F C

 Left subtree → D B E
  Right subtree → F C

✔ Step 3: Left Subtree (Postorder: D E B)

Root = B

Split:

 Left → D
 Right → E

✔ Step 4: Right Subtree (Postorder: F C)

Root = C

Split:

 Left → F
 Right → NULL

Final Binary Tree

Structure:

A
/\
B C
/\ /
D EF
2. Preorder Traversal (2 Marks)
Root, Left, Right

✔ A, B, D, E, C, F
 3. Height of Tree (2 Marks)
Longest path:
A→B→D

✔ Height = 2 (edges)
✔ Height = 3 (levels)

4. Leaf Nodes (2 Marks)

Nodes with no children:

✔ D, E, F

5. Internal Nodes (3 Marks)

Nodes with at least one child:

✔ A, B, C

(OR)
Q15 Construct an expression tree for the given postfix expression and perform expression U5
manipulation.

Answer:

1. Identify the Expression (2 Marks)

From the tree:

 Root → +
 Left subtree → (a + b*c)
 Right subtree → (d * (e + f))

✔ Infix Expression:

2. Postfix Expression (3 Marks)

Left, Right, Root
✔ Left subtree → a b c * +
✔ Right subtree → d e f + *

Final:

abc*+def+*+

3. Prefix Expression (3 Marks)

Root, Left, Right

✔ Final:

++a*bc*d+ef
4. Expression Tree Construction Logic (4 Marks)
From postfix:

 Read left → right

 Operand → push
 Operator → pop 2 operands, form subtree

✔ Stack-based construction ensures correct structure

5. Traversals Summary (2 Marks)

Traversal Expression
Inorder (a + bc) + (d(e+f))
Preorder + + a * b c * d + e f
Postorder abc*+def+*+
6. Applications (3 Marks)
 Expression evaluation
 Compiler design
 Syntax tree representation