Data Structure with Python (4331601) - Summer 2025 Solution

Question 1(a) [3 marks]

Differentiate between Linear and Non Linear Data Structure.

Answer:

Mnemonic: "Linear flows Like water, Non-linear Navigates Networks"

Question 1(b) [4 marks]

Explain different concepts of Object Oriented programming.

Answer:

Table of OOP Concepts:

• Encapsulation: Data hiding and bundling
• Inheritance: Code reusability through parent-child relationship
• Polymorphism: Method overriding and overloading
• Abstraction: Interface without implementation

Mnemonic: "Every Intelligent Programmer Abstracts"

Question 1(c) [7 marks]

Define Polymorphism. Write a python program for polymorphism through inheritance.

Answer:

Polymorphism means "many forms" - same method name behaving differently in different classes.

Code:

Python

• Polymorphism: Same interface, different implementation
• Runtime binding: Method called based on object type
• Code flexibility: Easy to extend with new classes

Mnemonic: "Polymorphism Provides Perfect Programming"

Question 1(c) OR [7 marks]

Define Abstraction. Write a python program to understand the concept of abstract class.

Answer:

Abstraction hides implementation details and shows only essential features.

Code:

Python

• Abstract class: Cannot be instantiated directly
• Abstract method: Must be implemented by child classes
• Interface definition: Provides template for subclasses

Mnemonic: "Abstraction Avoids Actual implementation"

Question 2(a) [3 marks]

Define Following terms: I. Best case II. Worst case III. Average case

Answer:

Mnemonic: "Best-Worst-Average = Performance Analysis"

Question 2(b) [4 marks]

Explain infix, postfix & prefix expressions.

Answer:

• Infix: Natural mathematical notation
• Prefix: Polish notation
• Postfix: Reverse Polish notation
• Stack usage: Postfix eliminates parentheses

Mnemonic: "In-Pre-Post = Position of operator"

Question 2(c) [7 marks]

Define circular queue. Explain INSERT and DELETE operations of circular queue with diagrams.

Answer:

Circular Queue: Linear data structure where last position connects to first position.

Diagram:

goat

INSERT Operation:

1. Check if queue is full
2. If not full, increment rear
3. If rear exceeds size, set rear = 0
4. Insert element at rear position

DELETE Operation:

1. Check if queue is empty
2. If not empty, remove element from front
3. Increment front
4. If front exceeds size, set front = 0

• Circular nature: Efficient memory utilization
• No shifting: Elements remain in place
• Front-rear pointers: Track queue boundaries

Mnemonic: "Circular Saves Space"

Question 2(a) OR [3 marks]

List out different Data Structure with examples.

Answer:

Mnemonic: "Arrays-Stacks-Queues = Linear, Trees-Graphs = Non-linear"

Question 2(b) OR [4 marks]

Discuss how the concept of circular queue is different from simple queue.

Answer:

• Memory efficiency: Circular reuses deleted spaces
• Pointer management: Modulo arithmetic for wraparound
• Performance: Better space utilization

Mnemonic: "Circular Conquers memory problems"

Question 2(c) OR [7 marks]

Define stack. Explain PUSH & POP operation with example. Write an algorithm for PUSH and POP operations of stack.

Answer:

Stack: LIFO (Last In First Out) data structure.

PUSH Algorithm:

1. Check if stack is full
2. If not full, increment top
3. Insert element at top position
4. Update top pointer

POP Algorithm:

1. Check if stack is empty
2. If not empty, store top element
3. Decrement top pointer
4. Return stored element

Example:

Stack: [10, 20, 30] ← top
PUSH 40: [10, 20, 30, 40] ← top
POP: returns 40, stack: [10, 20, 30] ← top

• LIFO principle: Last element added is first removed
• Top pointer: Tracks current stack position
• Overflow/Underflow: Check before operations

Mnemonic: "Stack Stores in Last-in-first-out"

Question 3(a) [3 marks]

Convert following infix expression to postfix: ( ( ( A - B ) * C ) + ( ( D - E ) / F ) )

Answer:

Step-by-step conversion:

Final Answer: AB-C*DE-F/+

Mnemonic: "Postfix Places operators after operands"

Question 3(b) [4 marks]

Write a short note on doubly linked list.

Answer:

Doubly Linked List: Linear data structure with bidirectional links.

Structure:

goat

Advantages:

• Bidirectional traversal: Forward and backward navigation
• Efficient deletion: No need for previous node reference
• Better insertion: Can insert before given node easily

Disadvantages:

• Extra memory: Additional pointer storage
• Complex operations: More pointer manipulations

Mnemonic: "Doubly Delivers Bidirectional Benefits"

Question 3(c) [7 marks]

Write a Python Program to delete first and last node from singly linked list.

Answer:

Code:

Python

• Delete first: Update head pointer
• Delete last: Traverse to second last node
• Edge cases: Empty list and single node

Mnemonic: "Delete Delivers by pointer updates"

Question 3(a) OR [3 marks]

List different applications of Queue.

Answer:

Queue Applications:

• FIFO nature: First come first served
• Real-time systems: Handle requests in order
• Resource sharing: Fair allocation

Mnemonic: "Queues Quietly handle ordered operations"

Question 3(b) OR [4 marks]

Explain different operations which we can perform on singly linked list.

Answer:

Singly Linked List Operations:

• Dynamic size: Grow/shrink during runtime
• Memory efficiency: Allocate as needed
• Sequential access: No random access

Mnemonic: "Insert-Delete-Traverse-Search-Count"

Question 3(c) OR [7 marks]

Write an algorithm to insert a new node at the end of doubly linked list.

Answer:

Algorithm for insertion at end:

1. Create new node with given data
2. Set new node's next = NULL
3. If list is empty:
   - Set head = new node
   - Set new node's prev = NULL
4. Else:
   - Traverse to last node
   - Set last node's next = new node
   - Set new node's prev = last node
5. Return success

Code:

Python

• Two-way linking: Update both next and prev pointers
• End insertion: Traverse to find last node
• Bidirectional connection: Maintain list integrity

Mnemonic: "Insert Intelligently with bidirectional links"

Question 4(a) [3 marks]

Write a python program for linear search.

Answer:

Code:

Python

• Sequential search: Check each element one by one
• Time complexity: O(n)
• Simple implementation: Easy to understand

Mnemonic: "Linear Looks through every element"

Question 4(b) [4 marks]

Write a short note on Circular linked list.

Answer:

Circular Linked List: Last node points back to first node forming a circle.

Diagram:

goat

Characteristics:

• No NULL pointers: Last node connects to first
• Continuous traversal: Can traverse infinitely
• Memory efficiency: Better cache performance
• Applications: Round-robin scheduling, multiplayer games

Advantages:

• Efficient insertion: At any position
• No wasted pointers: All nodes connected

Mnemonic: "Circular Connects everything in a loop"

Question 4(c) [7 marks]

Explain Quick sort algorithm with an example.

Answer:

Quick Sort: Divide and conquer sorting algorithm using pivot element.

Algorithm:

1. Choose pivot element
2. Partition array around pivot
3. Recursively sort left subarray
4. Recursively sort right subarray

Example: Sort [64, 34, 25, 12, 22, 11, 90]

Step 1: Pivot = 64

[34, 25, 12, 22, 11] 64 [90]

Step 2: Sort left partition [34, 25, 12, 22, 11] Pivot = 34

[25, 12, 22, 11] 34 []

Final sorted: [11, 12, 22, 25, 34, 64, 90]

• Divide and conquer: Break problem into smaller parts
• In-place sorting: Minimal extra memory
• Average complexity: O(n log n)

Mnemonic: "Quick Partitions then conquers"

Question 4(a) OR [3 marks]

Explain Binary search algorithm with an example.

Answer:

Binary Search: Search algorithm for sorted arrays using divide and conquer.

Algorithm:

1. Set left = 0, right = array length - 1
2. While left <= right:
   - Calculate mid = (left + right) / 2
   - If target = array[mid], return mid
   - If target < array[mid], right = mid - 1
   - If target > array[mid], left = mid + 1
3. Return -1 if not found

Example: Search 22 in [11, 12, 22, 25, 34, 64, 90]

Mnemonic: "Binary Bisects to find quickly"

Question 4(b) OR [4 marks]

Discuss different applications of linked list.

Answer:

Linked List Applications:

• Dynamic memory: Allocate as needed
• Efficient insertion/deletion: No shifting required
• Flexible structure: Adapt to changing requirements

Mnemonic: "Linked Lists Live in dynamic applications"

Question 4(c) OR [7 marks]

Write a python program for insertion sort with an example.

Answer:

Code:

Python

Step-by-step example:

Initial: [64, 34, 25, 12, 22, 11, 90]
Pass 1:  [34, 64, 25, 12, 22, 11, 90]
Pass 2:  [25, 34, 64, 12, 22, 11, 90]
Pass 3:  [12, 25, 34, 64, 22, 11, 90]
Pass 4:  [12, 22, 25, 34, 64, 11, 90]
Pass 5:  [11, 12, 22, 25, 34, 64, 90]
Pass 6:  [11, 12, 22, 25, 34, 64, 90]

• Card sorting analogy: Like arranging playing cards
• Stable sort: Maintains relative order of equal elements
• Online algorithm: Can sort list as it receives data

Mnemonic: "Insertion Inserts in right position"

Question 5(a) [3 marks]

Define following terms: I. Complete Binary tree II. In-degree III. Out-degree.

Answer:

Mnemonic: "Complete-In-Out = Tree terminology"

Question 5(b) [4 marks]

Explain bubble sort algorithm with an example.

Answer:

Bubble Sort: Compare adjacent elements and swap if in wrong order.

Algorithm:

1. For each pass (0 to n-1):
   2. For each element (0 to n-pass-1):
      3. If arr[j] > arr[j+1]:
         4. Swap arr[j] and arr[j+1]

Example: [64, 34, 25, 12]

• Bubble up: Largest element bubbles to end
• Multiple passes: Each pass places one element correctly
• Simple implementation: Easy to understand

Mnemonic: "Bubble Brings biggest to back"

Question 5(c) [7 marks]

Create a Binary Search Tree for the keys 15, 35, 12, 48, 5, 25, 58, 8 and write the Preorder, Inorder and Postorder traversal sequences.

Answer:

BST Construction:

goat

Traversal Sequences:

Traversal Rules:

• Preorder: Root → Left → Right
• Inorder: Left → Root → Right (gives sorted order)
• Postorder: Left → Right → Root

Mnemonic: "Pre-In-Post = Root position"

Question 5(a) OR [3 marks]

Define binary tree. Explain searching a node in binary tree.

Answer:

Binary Tree: Hierarchical data structure where each node has at most two children.

Search Algorithm:

1. Start from root
2. If target = current node, return found
3. If target < current node, go left
4. If target > current node, go right
5. Repeat until found or reach NULL

• Hierarchical structure: Parent-child relationship
• Binary property: Maximum two children per node
• Search efficiency: O(log n) for balanced trees

Mnemonic: "Binary Branches into two paths"

Question 5(b) OR [4 marks]

Give the trace to sort the given data using bubble sort method. Data are: 44, 72, 94, 28, 18, 442, 41

Answer:

Bubble Sort Trace:

Final sorted array: [18, 28, 41, 44, 72, 94, 442]

Mnemonic: "Bubble sort Bubbles largest to end each pass"

Question 5(c) OR [7 marks]

List applications of trees. Explain the technique for converting general tree into a Binary Search Tree with example.

Answer:

Tree Applications:

General Tree to BST Conversion:

Technique: First Child - Next Sibling Representation

Original General Tree:

    A
   /|\
  B C D
 /| |
E F G

Converted to Binary Tree:

goat

Steps:

1. First child: Becomes left child in binary tree
2. Next sibling: Becomes right child in binary tree
3. Recursive application: Apply to all nodes

• Systematic conversion: Preserves tree structure
• Binary representation: Uses only two pointers per node
• Space efficiency: Standard binary tree operations apply

Mnemonic: "First-child Left, Next-sibling Right"