Data Structure with Python (4331601) - Winter 2024 Solution

Question 1(a) [3 marks]

#

Explain set data structure in python?

Answer:

A set is an unordered collection of unique elements in Python. Sets are mutable but contain only immutable elements.

Key Properties:

Basic Operations:

# Create set
my_set = {1, 2, 3, 4}
# Add element
my_set.add(5)
# Remove element
my_set.remove(2)

Mnemonic: “Sets are Unique Unordered Collections”

Question 1(b) [4 marks]

#

Define Tuple in python? Explain operations of tuple data structure in python.

Answer:

A tuple is an ordered collection of items that is immutable (cannot be changed after creation).

Tuple Definition:

• Ordered: Elements have defined order
• Immutable: Cannot modify after creation
• Allow duplicates: Same values can appear multiple times
• Indexed: Access elements using index

Tuple Operations:

# Example operations
tup = (10, 20, 30, 40)
print(tup[1])      # Output: 20
print(tup[1:3])    # Output: (20, 30)

Mnemonic: “Tuples are Immutable Ordered Collections”

Question 1(c) [7 marks]

#

Explain Types of constructors in python? Write a python program to multiplication of two numbers using static method.

Answer:

Types of Constructors:

Static Method Program:

class Calculator:
    def __init__(self):
        pass
    
    @staticmethod
    def multiply(num1, num2):
        return num1 * num2

# Usage
result = Calculator.multiply(5, 3)
print(f"Multiplication: {result}")  # Output: 15

Key Points:

• Static methods: Don’t need object instance
• @staticmethod decorator: Defines static method
• No self parameter: Independent of class instance

Mnemonic: “Static methods Stand Separate from Self”

Question 1(c) OR [7 marks]

#

Define Data Encapsulation. List out different types of methods in python. Write a python program to multilevel inheritances.

Answer:

Data Encapsulation: Data encapsulation is the concept of bundling data and methods within a class and restricting direct access to some components.

Types of Methods:

Multilevel Inheritance Program:

class Animal:
    def __init__(self, name):
        self.name = name
    
    def speak(self):
        print(f"{self.name} makes sound")

class Mammal(Animal):
    def __init__(self, name, warm_blooded):
        super().__init__(name)
        self.warm_blooded = warm_blooded

class Dog(Mammal):
    def __init__(self, name, breed):
        super().__init__(name, True)
        self.breed = breed
    
    def bark(self):
        print(f"{self.name} barks")

# Usage
dog = Dog("Buddy", "Golden Retriever")
dog.speak()  # From Animal class
dog.bark()   # From Dog class

Mnemonic: “Encapsulation Hides Internal Details”

Question 2(a) [3 marks]

#

Differentiate between simple queue and circular queue.

Answer:

Queue Comparison:

Key Differences:

• Simple Queue: Front and rear move in one direction only
• Circular Queue: Rear connects back to front position
• Efficiency: Circular queue eliminates memory waste

Mnemonic: “Circular Queues Complete the Circle”

Question 2(b) [4 marks]

#

Explain polymorphism in python with example.

Answer:

Polymorphism means “many forms” - same method name behaves differently in different classes.

Types of Polymorphism:

Example:

class Animal:
    def make_sound(self):
        pass

class Dog(Animal):
    def make_sound(self):
        return "Woof!"

class Cat(Animal):
    def make_sound(self):
        return "Meow!"

# Polymorphic behavior
animals = [Dog(), Cat()]
for animal in animals:
    print(animal.make_sound())

Mnemonic: “Polymorphism Provides Multiple Personalities”

Question 2(c) [7 marks]

#

Define a).Infix b).postfix. Given equation to conversion from infix to postfix using stack. A+(B*C/D)

Answer:

Definitions:

Conversion Algorithm:

1. Scan infix expression left to right
2. If operand, add to output
3. If operator, compare precedence with stack top
4. Higher precedence → push to stack
5. Lower/equal precedence → pop and add to output

Step-by-step Conversion: A+(B*C/D)

Final Answer: ABC*D/+

Mnemonic: “Stack Stores Operators Strategically”

Question 2(a) OR [3 marks]

#

Explain disadvantages of Queue.

Answer:

Queue Disadvantages:

Key Issues:

• Linear Queue: Front spaces become unusable
• Insertion/Deletion: Only at specific ends
• Search Operations: Not efficient for searching

Mnemonic: “Queues Quietly Queue with Quirks”

Question 2(b) OR [4 marks]

#

Define Abstract class in python? Explain the declaration of abstract method in python?

Answer:

Abstract Class: A class that cannot be instantiated and contains one or more abstract methods that must be implemented by subclasses.

Abstract Method Declaration:

Example:

from abc import ABC, abstractmethod

class Shape(ABC):
    @abstractmethod
    def area(self):
        pass
    
    @abstractmethod
    def perimeter(self):
        pass

class Rectangle(Shape):
    def __init__(self, length, width):
        self.length = length
        self.width = width
    
    def area(self):
        return self.length * self.width
    
    def perimeter(self):
        return 2 * (self.length + self.width)

Mnemonic: “Abstract classes Are Blueprints Only”

Question 2(c) OR [7 marks]

#

Write an algorithm for Infix to postfix expression. Evaluate Postfix expression as: 5 6 2 + * 12 4 / -

Answer:

Infix to Postfix Algorithm:

1. Initialize empty stack and output string
2. Scan infix expression from left to right
3. If operand → add to output
4. If ‘(’ → push to stack
5. If ‘)’ → pop until ‘(’
6. If operator → pop higher/equal precedence operators
7. Push current operator to stack
8. Pop remaining operators

Postfix Evaluation: 5 6 2 + * 12 4 / -

Final Result: 37

Mnemonic: “Postfix Processing Pops Pairs Precisely”

Question 3(a) [3 marks]

#

Write an algorithm to traverse node in single linked list.

Answer:

Traversal Algorithm:

def traverse_linked_list(head):
    current = head
    while current is not None:
        print(current.data)
        current = current.next

Algorithm Steps:

Mnemonic: “Traverse Through Till The Tail”

Question 3(b) [4 marks]

#

Write an algorithm for Dequeue operation in queue using List.

Answer:

Dequeue Algorithm:

def dequeue(queue):
    if len(queue) == 0:
        print("Queue is empty")
        return None
    else:
        element = queue.pop(0)
        return element

Algorithm Steps:

Time Complexity: O(n) due to list shifting

Mnemonic: “Dequeue Deletes from Front Door”

Question 3(c) [7 marks]

#

Define double linked list. Enlist major operation of Linked List. Write an algorithm to insert a node at beginning in singly linked list.

Answer:

Double Linked List: A linear data structure where each node contains data and two pointers - one pointing to the next node and another to the previous node.

Major Linked List Operations:

Insert at Beginning Algorithm:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def insert_at_beginning(head, data):
    new_node = Node(data)
    new_node.next = head
    head = new_node
    return head

Algorithm Steps:

1. Create new node with given data
2. Set new node’s next to current head
3. Update head to point to new node
4. Return new head

Mnemonic: “Insert at Beginning Builds Better Lists”

Question 3(a) OR [3 marks]

#

Explain the applications of single linked list.

Answer:

Single Linked List Applications:

Key Benefits:

• Dynamic Size: Grows/shrinks during runtime
• Memory Efficiency: Allocates as needed
• Insertion/Deletion: Efficient at any position

Mnemonic: “Linked Lists Link Many Applications”

Question 3(b) OR [4 marks]

#

Write an algorithm for PUSH operation of stack using List.

Answer:

PUSH Algorithm:

def push(stack, element):
    stack.append(element)
    print(f"Pushed {element} to stack")

Algorithm Steps:

Detailed Algorithm:

1. Accept stack and element to push
2. Check if stack has capacity (for fixed size)
3. Add element to end of list using append()
4. List automatically handles memory allocation
5. Return success status

Time Complexity: O(1) - Constant time operation

Mnemonic: “PUSH Puts on Stack Summit”

Question 3(c) OR [7 marks]

#

Explain advantages of a linked list. Write an algorithm to delete node at last from single linked list.

Answer:

Linked List Advantages:

Delete Last Node Algorithm:

def delete_last_node(head):
    # Empty list
    if head is None:
        return None
    
    # Single node
    if head.next is None:
        return None
    
    # Multiple nodes
    current = head
    while current.next.next is not None:
        current = current.next
    
    current.next = None
    return head

Algorithm Steps:

1. Handle empty list case
2. Handle single node case
3. Traverse to second last node
4. Set second last node’s next to NULL
5. Return updated head

Mnemonic: “Linked Lists Lead to Logical Advantages”

Question 4(a) [3 marks]

#

Write an algorithm of Bubble sort.

Answer:

Bubble Sort Algorithm:

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

Algorithm Steps:

Time Complexity: O(n²)

Mnemonic: “Bubbles Rise to Surface Slowly”

Question 4(b) [4 marks]

#

Explain circular linked list with its advantages.

Answer:

Circular Linked List: A linked list where the last node points to the first node, forming a circular structure.

Characteristics:

Advantages:

• Memory Efficient: No NULL pointers
• Circular Traversal: Can loop continuously
• Queue Implementation: Efficient enqueue/dequeue
• Round Robin Scheduling: CPU time sharing
• Music Player: Continuous playlist looping

Mnemonic: “Circular Lists Create Continuous Connections”

Question 4(c) [7 marks]

#

Explain merge sort with suitable example.

Answer:

Merge Sort: A divide-and-conquer algorithm that divides array into halves, sorts them separately, and merges back.

Algorithm Phases:

Example: [38, 27, 43, 3, 9, 82, 10]

Time Complexity: O(n log n) Space Complexity: O(n)

Mnemonic: “Merge Sort Methodically Merges Segments”

Question 4(a) OR [3 marks]

#

Write an algorithm for selection sort.

Answer:

Selection Sort Algorithm:

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

Algorithm Steps:

Time Complexity: O(n²)

Mnemonic: “Selection Sort Selects Smallest Successfully”

Question 4(b) OR [4 marks]

#

Explain double linked list with its advantages.

Answer:

Double Linked List: A linked list where each node contains data and two pointers - next and previous.

Structure:

Advantages:

• Bidirectional Traversal: Forward and backward movement
• Easy Deletion: Can delete without knowing previous node
• Efficient Insertion: Insert at any position easily
• Better Navigation: Can move in both directions

Applications:

• Browser navigation (back/forward buttons)
• Music player (previous/next song)
• Undo/Redo operations

Mnemonic: “Double Links provide Dual Direction”

Question 4(c) OR [7 marks]

#

Explain insertion sort. Give trace of following numbers using insertion sort : 25, 15,30,9,99,20,26

Answer:

Insertion Sort: Builds sorted array one element at a time by inserting each element into its correct position.

Algorithm Concept:

• Sorted Portion: Left side of current element
• Unsorted Portion: Right side of current element
• Insert Strategy: Place current element in correct position in sorted portion

Trace of [25, 15, 30, 9, 99, 20, 26]:

Final Sorted Array: [9, 15, 20, 25, 26, 30, 99]

Time Complexity: O(n²) worst case, O(n) best case

Mnemonic: “Insertion Inserts Into Increasing Order”

Question 5(a) [3 marks]

#

Explain application of binary tree.

Answer:

Binary Tree Applications:

Key Benefits:

• Hierarchical Structure: Natural tree organization
• Efficient Operations: Search, insert, delete
• Recursive Processing: Easy to implement

Mnemonic: “Binary Trees Branch into Many Applications”

Question 5(b) [4 marks]

#

Write an algorithm for binary search using list.

Answer:

Binary Search Algorithm:

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1  # Element not found

Algorithm Steps:

Prerequisite: Array must be sorted Time Complexity: O(log n)

Mnemonic: “Binary Search Bisects to Find Faster”

Question 5(c) [7 marks]

#

Define Tree. Enlist Types of Tree. Write an algorithm to insert node in binary search tree using python.

Answer:

Tree Definition: A hierarchical data structure consisting of nodes connected by edges, with one root node and no cycles.

Types of Trees:

BST Insertion Algorithm:

class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def insert_bst(root, data):
    if root is None:
        return TreeNode(data)
    
    if data < root.data:
        root.left = insert_bst(root.left, data)
    elif data > root.data:
        root.right = insert_bst(root.right, data)
    
    return root

Algorithm Steps:

1. If tree empty, create root node
2. If data < root.data, insert in left subtree
3. If data > root.data, insert in right subtree
4. If data = root.data, ignore (no duplicates)
5. Return updated root

Mnemonic: “Trees Grow with Structured Organization”

Question 5(a) OR [3 marks]

#

Write an algorithm for in-order traversal of tree.

Answer:

In-order Traversal Algorithm:

def inorder_traversal(root):
    if root is not None:
        inorder_traversal(root.left)    # Left
        print(root.data)                # Root
        inorder_traversal(root.right)   # Right

Algorithm Steps:

Traversal Order: Left → Root → Right

Properties:

• BST Property: In-order gives sorted sequence
• Time Complexity: O(n)
• Space Complexity: O(h) where h is height

Example Tree Result:

Mnemonic: “In-order: Left, Root, Right”

Question 5(b) OR [4 marks]

#

Define search? Write an algorithm for Linear search using list.

Answer:

Search Definition: The process of finding a specific element or checking if an element exists in a data structure.

Linear Search Algorithm:

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i  # Return index if found
    return -1  # Return -1 if not found

Algorithm Characteristics:

Algorithm Steps:

1. Start from first element
2. Compare each element with target
3. If match found, return index
4. If end reached, return -1

Mnemonic: “Linear Search Looks through Lists Linearly”

Question 5(c) OR [7 marks]

#

Define: a) Path b). Leaf Node. Construct a binary search tree for following data items. 60, 40, 37,31,59,21,65,30

Answer:

Definitions:

BST Construction for: 60, 40, 37, 31, 59, 21, 65, 30

Step-by-step Construction:

Final BST Structure:

Leaf Nodes: 30, 59, 65

Mnemonic: “BST Building follows Binary Search Tree rules”