Data Structure with Python (4331601) - Summer 2024 Solution

Question 1(a) [3 marks]

#

Differentiate between array and list.

Answer:

Mnemonic: “Arrays are Fixed Friends, Lists are Loose Leaders”

Question 1(b) [4 marks]

#

Explain the concept of class and object with the help of python program.

Answer:

Class એ એક blueprint છે જે objects ના structure અને behavior define કરે છે. Object એ class નો instance છે.

class Student:
    def __init__(self, name, age):
        self.name = name
        self.age = age
    
    def display(self):
        print(f"Name: {self.name}, Age: {self.age}")

# Creating objects
s1 = Student("Ram", 20)
s2 = Student("Sita", 19)
s1.display()

• Class: Template બનાવે છે
• Object: Real instance બનાવે છે
• Constructor: Object initialize કરે છે

Mnemonic: “Class Blueprints Create Object Instances”

Question 1(c) [7 marks]

#

Define constructor. Discuss different types of constructors with suitable python program.

Answer:

Constructor એ special method છે જે object creation time પર automatically call થાય છે. Python માં __init__() method constructor છે.

class Demo:
    # Default Constructor
    def __init__(self):
        self.value = 0
    
    # Parameterized Constructor
    def __init__(self, x, y=10):
        self.x = x
        self.y = y

# Usage
d1 = Demo(5)      # x=5, y=10 (default)
d2 = Demo(3, 7)   # x=3, y=7

Types of Constructors:

Mnemonic: “Default Parameters Copy Objects”

Question 1(c) OR [7 marks]

#

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

Answer:

Polymorphism એ same interface વાપરીને different objects પર different operations perform કરવાની ability છે.

class Animal:
    def sound(self):
        pass

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

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

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

• Method Overriding: Child class માં same method name
• Dynamic Binding: Runtime પર method selection
• Code Reusability: Same interface, different implementation

Mnemonic: “Many Objects, One Interface”

Question 2(a) [3 marks]

#

Explain Python specific data structure List, Tuple and Dictionary.

Answer:

Mnemonic: “Lists Change, Tuples Stay, Dictionaries Map”

Question 2(b) [4 marks]

#

Explain application of stack.

Answer:

Stack Applications:

• Function Calls: Call stack management
• Expression Evaluation: Infix to postfix conversion
• Undo Operations: Text editors, browsers
• Parentheses Matching: Syntax checking

Mnemonic: “Functions Evaluate Undo Parentheses”

Question 2(c) [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) principle follow કરતું linear data structure છે.

PUSH Algorithm:

1. Check if stack is full
2. If full, print "Stack Overflow"
3. Else, increment top
4. Add element at top position

POP Algorithm:

1. Check if stack is empty
2. If empty, print "Stack Underflow"  
3. Else, remove element from top
4. Decrement top

Example:

stack = []
stack.append(10)  # PUSH
stack.append(20)  # PUSH
item = stack.pop()  # POP returns 20

Mnemonic: “Last In, First Out - Like Plates”

Question 2(a) OR [3 marks]

#

Define Following terms: I. Time Complexity II. Space Complexity III. Best case

Answer:

Mnemonic: “Time Space Best Performance”

Question 2(b) OR [4 marks]

#

Convert A – (B / C + (D % E * F) / G) H into postfix expression*

Answer:

Step-by-step conversion:

Infix: A – (B / C + (D % E * F) / G) * H

1. A B C / D E % F * G / + - H *

Stack operations:
- Operators: -, (, /, +, (, %, *, ), /, ), *
- Final: A B C / D E % F * G / + - H *

Postfix Result: A B C / D E % F * G / + - H *

Mnemonic: “Operands First, Operators Follow”

Question 2(c) OR [7 marks]

#

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

Answer:

Circular Queue એ queue નું modified version છે જ્યાં last position first position સાથે connected હોય છે.

INSERT Algorithm:

1. Check if queue is full
2. rear = (rear + 1) % size
3. queue[rear] = element
4. If first element, set front = 0

DELETE Algorithm:

1. Check if queue is empty
2. element = queue[front]
3. front = (front + 1) % size
4. Return element

• Advantage: Memory efficiency
• Application: CPU scheduling, buffering

Mnemonic: “Circle Back When Full”

Question 3(a) [3 marks]

#

Explain Implementation of Stack using List.

Answer:

Stack operations Python List વડે:

stack = []  # Empty stack
stack.append(10)  # PUSH
stack.append(20)  # PUSH
top = stack.pop()  # POP

• PUSH: append() method
• POP: pop() method
• TOP: stack[-1] for peek

Mnemonic: “Append Pushes, Pop Pulls”

Question 3(b) [4 marks]

#

Discuss different applications of linked list.

Answer:

Linked List Applications:

• Dynamic Memory: Size varies at runtime
• Insertion/Deletion: Efficient at any position
• Implementation: Stacks, queues, graphs
• Undo Functionality: Browser history, text editors

Mnemonic: “Dynamic Implementation Undo Memory”

Question 3(c) [7 marks]

#

Explain doubly linked list. Write an algorithm to delete a node from the beginning of doubly linked list

Answer:

Doubly Linked List માં દરેક node માં data, next pointer અને previous pointer હોય છે.

Delete from Beginning Algorithm:

1. If list is empty, return
2. If only one node:
   - head = NULL
3. Else:
   - temp = head
   - head = head.next
   - head.prev = NULL
   - delete temp

def delete_beginning(self):
    if self.head is None:
        return
    if self.head.next is None:
        self.head = None
    else:
        self.head = self.head.next
        self.head.prev = None

Mnemonic: “Two Way Navigation”

Question 3(a) OR [3 marks]

#

Convert this Infix expression into Postfix expression: A+B/C*D-E/F-G

Answer:

Step-by-step conversion:

Infix: A+B/C*D-E/F-G

Postfix: A B C / D * + E F / - G -

Operator precedence: *, / > +, -
Left to right associativity

Mnemonic: “Multiply Divide Before Add Subtract”

Question 3(b) OR [4 marks]

#

Explain Circular Linked List with its disadvantages.

Answer:

Circular Linked List માં last node નો next pointer first node ને point કરે છે.

Disadvantages:

• Infinite Loop Risk: Improper traversal
• Complex Implementation: Extra care needed
• Memory Overhead: Additional pointer management
• Debugging Difficulty: Circular references

Mnemonic: “Circles Can Cause Confusion”

Question 3(c) OR [7 marks]

#

Write a Python Program to perform Insert operation in doubly Linked List. Explain with neat diagrams.

Answer:

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

class DoublyLinkedList:
    def __init__(self):
        self.head = None
    
    def insert_beginning(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node

Insert Operations:

• Beginning: Update head pointer
• End: Traverse to last node
• Middle: Update prev/next pointers

Mnemonic: “Begin End Middle Insertions”

Question 4(a) [3 marks]

#

Write an algorithm for Merge sort.

Answer:

Merge Sort Algorithm:

1. If array size <= 1, return
2. Divide array into two halves
3. Recursively sort both halves  
4. Merge sorted halves

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

Mnemonic: “Divide Conquer Merge”

Question 4(b) [4 marks]

#

Differentiate between Singly Linked List and Doubly Linked List.

Answer:

Mnemonic: “Single Forward, Double Bidirectional”

Question 4(c) [7 marks]

#

Write an algorithm for selection sort. Give the trace to sort the given data using selection sort method. Data are: 13, 2, 6, 54, 18, 42, 11

Answer:

Selection Sort Algorithm:

1. For i = 0 to n-2:
   2. Find minimum in array[i...n-1]
   3. Swap minimum with array[i]

Trace for [13, 2, 6, 54, 18, 42, 11]:

Final Result: [2, 6, 11, 13, 18, 42, 54]

Mnemonic: “Select Minimum, Swap Position”

Question 4(a) OR [3 marks]

#

Write an algorithm for Insertion sort.

Answer:

Insertion Sort Algorithm:

1. For i = 1 to n-1:
   2. key = array[i]
   3. j = i-1
   4. While j >= 0 and array[j] > key:
      5. array[j+1] = array[j]
      6. j = j-1
   7. array[j+1] = key

Time Complexity: O(n²) Best Case: O(n) for sorted array

Mnemonic: “Insert In Right Position”

Question 4(b) OR [4 marks]

#

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

Answer:

Algorithm:

1. Create new_node with data
2. If list is empty:
   - head = new_node
   - new_node.next = new_node
3. Else:
   - temp = head
   - While temp.next != head:
     - temp = temp.next
   - temp.next = new_node
   - new_node.next = head

def insert_end(self, data):
    new_node = Node(data)
    if self.head is None:
        self.head = new_node
        new_node.next = new_node
    else:
        temp = self.head
        while temp.next != self.head:
            temp = temp.next
        temp.next = new_node
        new_node.next = self.head

Mnemonic: “Circle Back To Head”

Question 4(c) OR [7 marks]

#

Write an algorithm for bubble sort. Give the trace to sort the given data using bubble sort method. Data are: 37, 22, 64, 84, 58, 52, 11

Answer:

Bubble Sort Algorithm:

1. For i = 0 to n-2:
   2. For j = 0 to n-2-i:
      3. If array[j] > array[j+1]:
         4. Swap array[j] and array[j+1]

Trace for [37, 22, 64, 84, 58, 52, 11]:

Final Result: [11, 22, 37, 52, 58, 64, 84]

Mnemonic: “Bubble Up The Largest”

Question 5(a) [3 marks]

#

Explain Binary search tree and application of it.

Answer:

Binary Search Tree (BST) એ binary tree છે જ્યાં left subtree માં smaller values અને right subtree માં larger values હોય છે.

Properties:

• Left child < Parent < Right child
• Inorder traversal gives sorted sequence
• Search time: O(log n) average case

Applications:

Mnemonic: “Binary Search Trees Organize Data”

Question 5(b) [4 marks]

#

Write Python Program for Linear Search and explain it with an example

Answer:

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

# Example
numbers = [10, 25, 30, 45, 60]
result = linear_search(numbers, 30)
print(f"Element found at index: {result}")  # Output: 2

Working:

• Sequential check: Element by element
• Time Complexity: O(n)
• Space Complexity: O(1)
• Works on: Unsorted arrays

Mnemonic: “Linear Line By Line”

Question 5(c) [7 marks]

#

Create a Binary Search Tree for the keys 45, 35, 12, 58, 5, 55, 58, 80, 35, 42 and write the Preorder, Inorder and Postorder traversal sequences.

Answer:

BST Construction (duplicates ignored):

Insertion Order: 45(root), 35(left), 12(left of 35), 58(right), 5(left of 12), 55(left of 58), 80(right of 58), 42(right of 12)

Traversals:

Mnemonic: “Pre-Root First, In-Sorted, Post-Root Last”

Question 5(a) OR [3 marks]

#

Define following terms: I. Binary tree II. level number III. Leaf-node

Answer:

Mnemonic: “Binary Levels Lead To Leaves”

Question 5(b) OR [4 marks]

#

Differentiate between Linear Search and Binary search.

Answer:

Mnemonic: “Linear Line, Binary Bisect”

Question 5(c) OR [7 marks]

#

Write an algorithm for insertion and deletion a node in Binary search tree.

Answer:

Insertion Algorithm:

1. If root is NULL, create new node as root
2. If data < root.data, insert in left subtree
3. If data > root.data, insert in right subtree
4. If data == root.data, no insertion (duplicate)

Deletion Algorithm:

1. If node is leaf: Simply delete
2. If node has one child: Replace with child
3. If node has two children:
   - Find inorder successor
   - Replace data with successor's data
   - Delete successor

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

def delete(root, data):
    if root is None:
        return root
    if data < root.data:
        root.left = delete(root.left, data)
    elif data > root.data:
        root.right = delete(root.right, data)
    else:
        # Node to be deleted found
        if root.left is None:
            return root.right
        elif root.right is None:
            return root.left
        # Node with two children
        temp = find_min(root.right)
        root.data = temp.data
        root.right = delete(root.right, temp.data)
    return root

Cases:

• Leaf deletion: Direct removal
• One child: Replace with child
• Two children: Replace with successor

Mnemonic: “Insert Compare, Delete Replace”