Data Structure and Application (1333203) - Summer 2025 Solution

Question 1(a) [3 marks]

Define Big - O Notation, Big Omega Notation, Big Theta Notation.

Answer:

Table: Asymptotic Notations Comparison

• Big-O Notation: Describes maximum time/space complexity
• Big Omega: Describes minimum time/space complexity
• Big Theta: Describes exact time/space complexity

Mnemonic: "OWT - O for wOrst, Omega for Best, Theta for Tight"

Question 1(b) [4 marks]

Define Set. Write various operations that can be performed on Set.

Answer:

Definition: Set is a collection of unique elements with no duplicates.

Table: Set Operations

• Add/Insert: Adding new element
• Remove/Delete: Removing existing element
• Contains: Check if element exists

Mnemonic: "UIDS - Union, Intersection, Difference, Subset"

Question 1(c) [7 marks]

Write a Python class to represent a Cricketer. The class contains the name of the cricketer, team name and run as the data members. The member functions are as follows: to initialize the data members, to set run and display run.

Answer:

Python

• Constructor: Initializes name, team, and run
• set_run(): Updates run value
• display_run(): Shows player information

Mnemonic: "CSD - Constructor, Set, Display"

Question 1(c OR) [7 marks]

Design a student class for reading and displaying the student information, the getInfo() and displayInfo() methods will be used respectively. Where getInfo() will be a private method.

Answer:

Python

• Private method: Uses double underscore (__getInfo)
• Constructor: Automatically calls private method
• Public method: displayInfo() shows student data

Mnemonic: "PCP - Private, Constructor, Public"

Question 2(a) [3 marks]

Differentiate between Stack and Queue.

Answer:

Table: Stack vs Queue Comparison

• Stack: Like book pile - last added, first removed
• Queue: Like waiting line - first come, first served

Mnemonic: "SLIF QFIF - Stack LIFO, Queue FIFO"

Question 2(b) [4 marks]

Define recursion. Explain with example.

Answer:

Definition: Function calling itself with smaller problem until base condition.

Python

• Base case: Stopping condition
• Recursive case: Function calls itself
• Problem reduction: Each call handles smaller problem

Mnemonic: "BRP - Base, Recursive, Problem-reduction"

Question 2(c) [7 marks]

Consider the size of the stack as 5. Apply the following operation on stack and show status and top pointer after each operation. Push a,b,c pop

Answer:

Stack Operations Trace:

goat

• Push operations: Add elements from index 0 onwards
• Top pointer: Points to last inserted element
• Pop operation: Removes top element, decrements top pointer

Mnemonic: "PTD - Push Top Decrement"

Question 2(a OR) [3 marks]

List applications of Stack and Queue.

Answer:

Table: Applications of Stack and Queue

• Stack applications: Undo-redo, recursion, parsing
• Queue applications: Task scheduling, buffering, breadth-first search

Mnemonic: "Stack FUBE, Queue SPBH"

Question 2(b OR) [4 marks]

Convert following algebraic expression into postfix notation using Stack: i) (ab)(c^d(d+e)-f) ii) a-b/(c*d/e)

Answer:

i) (ab)(c^d(d+e)-f)

Result: abcdde+^f-

ii) a-b/(c*d/e)

Result: abcd*e/-

Mnemonic: "PEMDAS reversed for postfix"

Question 2(c OR) [7 marks]

Develop a program to implement a queue using a list that performs following operations: enqueue, dequeue.

Answer:

Python

• Enqueue: Add element at rear
• Dequeue: Remove element from front
• FIFO principle: First In, First Out

Mnemonic: "ERF - Enqueue Rear, Front"

Question 3(a) [3 marks]

List types of linked lists. Give graphical representation of each type.

Answer:

Table: Types of Linked Lists

goat

Mnemonic: "SDC - Singly, Doubly, Circular"

Question 3(b) [4 marks]

Write an algorithm to search a given node in a singly link list.

Answer:

Python

• Linear search: Traverse from head to tail
• Time complexity: O(n)
• Return: Position if found, -1 if not found

Mnemonic: "SCMR - Start, Compare, Move, Return"

Question 3(c) [7 marks]

Implement program to perform following operation on singly linked list: 1)Insert a node at the beginning of a singly linked list. 2)Delete a node from the beginning of a singly linked list.

Answer:

Python

• Insert: Create node, link to head, update head
• Delete: Store data, move head to next, return data

Mnemonic: "CLU - Create, Link, Update"

Question 3(a OR) [3 marks]

Differentiate between circular linked list and singly linked list.

Answer:

Table: Circular vs Singly Linked List

• Circular advantage: No NULL pointers, continuous traversal
• Singly advantage: Simple implementation, clear end point

Mnemonic: "CNTE - Circular No Termination End"

Question 3(b OR) [4 marks]

Explain three applications of linked list in brief.

Answer:

Table: Linked List Applications

• Music playlist: Add/remove songs dynamically
• Browser history: Navigate back/forward
• Image viewer: Previous/next image navigation

Mnemonic: "DIP - Dynamic, Implementation, Polynomial"

Question 3(c OR) [7 marks]

Implement a program to create and display circular linked lists.

Answer:

Python

• Creation: Link last node to head
• Display: Stop when reaching head again

Mnemonic: "CLH - Create, Link, Head"

Question 4(a) [3 marks]

Write a program for Selection Sort Method.

Answer:

Python

• Find minimum: In unsorted portion
• Swap: With first unsorted element
• Time complexity: O(n²)

Mnemonic: "FMS - Find, Minimum, Swap"

Question 4(b) [4 marks]

Apply Insertion sort to following data to arrange them in ascending order. 25 15 35 20 30 5 10

Answer:

Insertion Sort Steps:

Initial: [25, 15, 35, 20, 30, 5, 10]

Pass 1: [15, 25, 35, 20, 30, 5, 10]  (Insert 15)
Pass 2: [15, 25, 35, 20, 30, 5, 10]  (35 in place)
Pass 3: [15, 20, 25, 35, 30, 5, 10]  (Insert 20)
Pass 4: [15, 20, 25, 30, 35, 5, 10]  (Insert 30)
Pass 5: [5, 15, 20, 25, 30, 35, 10]  (Insert 5)
Pass 6: [5, 10, 15, 20, 25, 30, 35]  (Insert 10)

Final: [5, 10, 15, 20, 25, 30, 35]

• Method: Take element, find position in sorted part
• Comparisons: 15 total comparisons
• Shifts: Elements moved to make space

Mnemonic: "TFI - Take, Find, Insert"

Question 4(c) [7 marks]

Implement a python program to search a particular element from a list using Linear Search.

Answer:

Python

• Sequential search: Check each element one by one
• Time complexity: O(n) worst case
• Best case: O(1) if found at first position

Mnemonic: "CEO - Check Each One"

Question 4(a OR) [3 marks]

Write a program of Insertion Sort Method.

Answer:

Python

• Key element: Current element to be inserted
• Shift right: Larger elements move right
• Insert: Key at correct position

Mnemonic: "KSI - Key, Shift, Insert"

Question 4(b OR) [4 marks]

Apply Quick Sort to the following data and arrange them in the proper manner. 5 6 1 8 2 9 10 15 7 13

Answer:

Quick Sort Steps:

Initial: [5, 6, 1, 8, 2, 9, 10, 15, 7, 13]
Pivot: 5 (first element)

Partition 1: [1, 2] 5 [6, 8, 9, 10, 15, 7, 13]

Left subarray [1, 2]:
Pivot: 1 → [] 1 [2]
Result: [1, 2]

Right subarray [6, 8, 9, 10, 15, 7, 13]:
Pivot: 6 → [] 6 [8, 9, 10, 15, 7, 13]

Continue partitioning...

Final: [1, 2, 5, 6, 7, 8, 9, 10, 13, 15]

• Divide: Choose pivot, partition around it
• Conquer: Recursively sort subarrays
• Average time: O(n log n)

Mnemonic: "DCC - Divide, Conquer, Combine"

Question 4(c OR) [7 marks]

Implement Merge sort algorithm.

Answer:

Python

• Divide: Split array into halves
• Merge: Combine sorted subarrays
• Time complexity: O(n log n) always

Mnemonic: "DSM - Divide, Sort, Merge"

Question 5(a) [3 marks]

Write Short note on: Applications of Tree.

Answer:

Table: Tree Applications

• Decision trees: AI and machine learning
• Huffman coding: Data compression
• Game trees: Chess, tic-tac-toe

Mnemonic: "FED - File, Expression, Database"

Question 5(b) [4 marks]

Explain different Tree Traversal Methods.

Answer:

Table: Tree Traversal Methods

goat

• Inorder: Gives sorted sequence for BST
• Preorder: Used for copying tree
• Postorder: Used for deleting tree

Mnemonic: "LNR PNL LRN for In-Pre-Post"

Question 5(c) [7 marks]

Write a menu driven program to perform the following operation on Binary Search Tree: Create a BST.

Answer:

Python

• BST property: Left < Root < Right
• Insertion: Compare and go left/right
• Menu driven: User-friendly interface

Mnemonic: "CIM - Compare, Insert, Menu"

Question 5(a OR) [3 marks]

Define and give examples : Strict Binary Tree and Complete Binary Tree.

Answer:

Table: Binary Tree Types

goat

• Strict: No node with single child
• Complete: Optimal space utilization

Mnemonic: "SC - Strict Complete"

Question 5(b OR) [4 marks]

Explain basic terminology of Binary Tree : Level number, Degree, Indegree , Out-degree , Leaf Node.

Answer:

goat

Table: Binary Tree Terminology

Mnemonic: "LDIOL - Level, Degree, In-Out, Leaf"

Question 5(c OR) [7 marks]

Write a menu driven program to perform the following operation on Binary Search Tree: Insert an element in BST.

Answer:

Python

• Insert logic: Compare with current node, go left/right
• Recursive approach: Clean and efficient implementation
• Menu system: Interactive user interface

Mnemonic: "CRL - Compare, Recursive, Left/right"