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 છે.

Python

• 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 છે.

Python

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 છે.

Python

• 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

goat

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:

Python

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 હોય છે.

goat

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 વડે:

Python

• 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 હોય છે.

goat

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

Python

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 કરે છે.

goat

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:

Python

goat

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:

goat

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

Python

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:

Python

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):

goat

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:

goat

Mnemonic: "Binary Levels Lead To Leaves"

Question 5(b) OR [4 marks]

Differentiate between Linear Search and Binary search.

Answer:

goat

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

Python

Cases:

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

Mnemonic: "Insert Compare, Delete Replace"