Data Structure And Application (1333203) - Summer 2024 Solution

Question 1(a) [3 marks]

#

Define linear data structure and give its examples.

Answer: A linear data structure is a collection of elements arranged in sequential order where each element has exactly one predecessor and one successor (except first and last elements).

Table: Linear Data Structures Examples

Mnemonic: “ALSQ are in a Line”

Question 1(b) [4 marks]

#

Define time and space complexity.

Answer: Time and space complexity measure algorithm efficiency in terms of execution time and memory usage as input size grows.

Table: Complexity Comparison

Mnemonic: “TS: Time-Speed and Space-Storage”

Question 1(c) [7 marks]

#

Explain the concept of class and object with example.

Answer: Classes and objects are fundamental OOP concepts where classes are blueprints for creating objects with attributes and behaviors.

Diagram: Class and Object Relationship

classDiagram
    class Student {
        +name: string
        +rollNo: int
        +marks: float
        +displayInfo()
    }
    Student <|-- StudentObject: Creates

Code Example:

class Student:
    def __init__(self, name, rollNo, marks):
        self.name = name
        self.rollNo = rollNo
        self.marks = marks
    
    def displayInfo(self):
        print(f"Name: {self.name}, Roll No: {self.rollNo}, Marks: {self.marks}")

# Creating object
student1 = Student("Raj", 101, 85.5)
student1.displayInfo()

• Class: Blueprint defining attributes (name, rollNo, marks) and methods (displayInfo)
• Object: Instance (student1) created from the class with specific values

Mnemonic: “CAR - Class defines Attributes and Routines”

Question 1(c) OR [7 marks]

#

Explain instance method, class method and static method with example.

Answer: Python supports three method types: instance, class, and static methods, each serving different purposes.

Table: Comparison of Method Types

Code Example:

class Student:
    school = "ABC School"  # class variable
    
    def __init__(self, name):
        self.name = name  # instance variable
    
    def instance_method(self):  # instance method
        return f"Hi {self.name} from {self.school}"
    
    @classmethod
    def class_method(cls):  # class method
        return f"School is {cls.school}"
    
    @staticmethod
    def static_method():  # static method
        return "This is a utility function"

Mnemonic: “ICS: Instance-Self, Class-Cls, Static-Solo”

Question 2(a) [3 marks]

#

Explain concept of recursive function.

Answer: A recursive function is a function that calls itself during its execution to solve smaller instances of the same problem.

Diagram: Recursive Function Execution

graph TD
    A[factorial(3)] --> B[factorial(2)]
    B --> C[factorial(1)]
    C --> D[Return 1]
    D --> E[Return 1*2=2]
    E --> F[Return 2*3=6]

Mnemonic: “BASE and RECURSE - Base case stops, Recursion repeats”

Question 2(b) [4 marks]

#

Define stack and queue.

Answer: Stack and queue are linear data structures with different access patterns for data insertion and removal.

Table: Stack vs Queue

Mnemonic: “SLIFF vs QFIFF - Stack-LIFO vs Queue-FIFO”

Question 2(c) [7 marks]

#

Explain basic operations on stack.

Answer: Stack operations follow LIFO (Last In First Out) principle with the following basic operations:

Table: Stack Operations

Diagram: Stack Operations

Code Example:

class Stack:
    def __init__(self):
        self.items = []
    
    def push(self, item):
        self.items.append(item)
    
    def pop(self):
        if not self.isEmpty():
            return self.items.pop()
    
    def peek(self):
        if not self.isEmpty():
            return self.items[-1]
    
    def isEmpty(self):
        return len(self.items) == 0

Mnemonic: “PIPES - Push In, Pop Exit, See top”

Question 2(a) OR [3 marks]

#

Define singly linked list.

Answer: A singly linked list is a linear data structure with a collection of nodes where each node contains data and a reference to the next node.

Diagram: Singly Linked List

Mnemonic: “DNL - Data and Next Link”

Question 2(b) OR [4 marks]

#

Explain Enqueue and Dequeue operations on Queue.

Answer: Enqueue and Dequeue are the primary operations for adding and removing elements in a queue data structure.

Table: Queue Operations

Diagram: Queue Operations

Mnemonic: “ERfDFr - Enqueue at Rear, Dequeue from Front”

Question 2(c) OR [7 marks]

#

Convert expression A+B/C+D to postfix and evaluate postfix expression using stack assuming some values for A, B, C and D.

Answer: Converting and evaluating the expression “A+B/C+D” using stack:

Step 1: Convert to Postfix

Table: Infix to Postfix Conversion

Final Postfix: A B C / + D +

Step 2: Evaluate with values A=5, B=10, C=2, D=3

Table: Postfix Evaluation

Result: 13

Mnemonic: “PC-SE - Push operands, Calculate when operators, Stack holds Everything”

Question 3(a) [3 marks]

#

Enlist applications of Linked List.

Answer: Linked lists are versatile data structures with many practical applications.

Table: Applications of Linked List

Mnemonic: “DSUHM - Dynamic allocation, Stacks & queues, Undo, Hash tables, Music players”

Question 3(b) [4 marks]

#

Explain creation of singly linked list in python.

Answer: Creating a singly linked list in Python involves defining a Node class and implementing basic operations.

Code Example:

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

class LinkedList:
    def __init__(self):
        self.head = None
    
    def append(self, data):
        new_node = Node(data)
        # If empty list, set new node as head
        if self.head is None:
            self.head = new_node
            return
        # Traverse to the end and add node
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node

Diagram: Creating a Linked List

flowchart LR
    A["Create Node"] --> B["Set head if empty"]
    A --> C["Otherwise traverse to end"]
    C --> D["Attach new node at end"]

Mnemonic: “CHEN - Create nodes, Head first, End attachment, Next pointers”

Question 3(c) [7 marks]

#

Write a code to insert a new node at the beginning and end of singly linked list.

Answer: Adding nodes at the beginning and end of a singly linked list requires different approaches.

Code Example:

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

class LinkedList:
    def __init__(self):
        self.head = None
    
    # Insert at beginning (prepend)
    def insert_at_beginning(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
    
    # Insert at end (append)
    def insert_at_end(self, data):
        new_node = Node(data)
        # If empty list
        if self.head is None:
            self.head = new_node
            return
        
        # Traverse to last node
        current = self.head
        while current.next:
            current = current.next
        
        # Attach new node
        current.next = new_node

Diagram: Insertion Operations

Mnemonic: “BEN - Beginning is Easy and Next-based, End Needs traversal”

Question 3(a) OR [3 marks]

#

Write a code to count the number of nodes in singly linked list.

Answer: Counting nodes requires traversing the entire linked list from head to tail.

Code Example:

def count_nodes(self):
    count = 0
    current = self.head
    
    # Traverse the list and count nodes
    while current:
        count += 1
        current = current.next
    
    return count

Diagram: Counting Nodes

flowchart LR
    A[Initialize count=0] --> B[Start from head]
    B --> C[Traverse each node]
    C --> D[Increment count]
    D --> E[Move to next node]
    E --> C
    C -- All nodes visited --> F[Return count]

Mnemonic: “CIT - Count Incrementally while Traversing”

Question 3(b) OR [4 marks]

#

Match appropriate options from column A and B

Answer: The matching between different linked list types and their characteristics:

Table: Matching Linked List Types with Characteristics

Diagram: Different Linked List Types

Mnemonic: “SDCN - Single-Direction, Double-Direction, Circular-Connection, Node-Component”

Question 3(c) OR [7 marks]

#

Explain deletion of first and last node in singly linked list.

Answer: Deleting nodes from a singly linked list varies in complexity based on the position (first vs. last).

Table: Deletion Comparison

Code Example:

def delete_first(self):
    # Check if list is empty
    if self.head is None:
        return
    
    # Update head to second node
    self.head = self.head.next

def delete_last(self):
    # Check if list is empty
    if self.head is None:
        return
    
    # If only one node
    if self.head.next is None:
        self.head = None
        return
    
    # Traverse to second last node
    current = self.head
    while current.next.next:
        current = current.next
    
    # Remove last node
    current.next = None

Diagram: Deletion Operations

Mnemonic: “FELO - First is Easy, Last needs One-before-last”

Question 4(a) [3 marks]

#

Explain concept of doubly linked list.

Answer: A doubly linked list is a bidirectional linear data structure with nodes containing data, previous, and next references.

Diagram: Doubly Linked List

Mnemonic: “PDN - Previous, Data, Next”

Question 4(b) [4 marks]

#

Explain concept of linear search.

Answer: Linear search is a simple sequential search algorithm that checks each element one by one until finding the target.

Table: Linear Search Characteristics

Diagram: Linear Search Process

flowchart LR
    A[Start] --> B[Check First Element]
    B -- Match --> C[Return Position]
    B -- No Match --> D[Move to Next Element]
    D --> E{Reached End?}
    E -- No --> B
    E -- Yes --> F[Not Found]

Mnemonic: “SCENT - Search Consecutively Each element until Target”

Question 4(c) [7 marks]

#

Write a code to implement binary search algorithm.

Answer: Binary search is an efficient algorithm for finding elements in a sorted array by repeatedly dividing the search interval in half.

Code Example:

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        
        # Check if target is present at mid
        if arr[mid] == target:
            return mid
        
        # If target is greater, ignore left half
        elif arr[mid] < target:
            left = mid + 1
        
        # If target is smaller, ignore right half
        else:
            right = mid - 1
    
    # Target not found
    return -1

Diagram: Binary Search Process

Mnemonic: “MCLR - Middle Compare, Left or Right adjust”

Question 4(a) OR [3 marks]

#

Explain concept of selection sort algorithm.

Answer: Selection sort is a simple comparison-based sorting algorithm that divides the array into sorted and unsorted regions.

Table: Selection Sort Characteristics

Mnemonic: “FSMR - Find Smallest, Move to Right position, Repeat”

Question 4(b) OR [4 marks]

#

Explain bubble sort method.

Answer: Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they’re in the wrong order.

Table: Bubble Sort Characteristics

Diagram: Bubble Sort Process

Mnemonic: “CABS - Compare Adjacent, Bubble-up Swapping”

Question 4(c) OR [7 marks]

#

Explain the working of quick sort method with example.

Answer: Quick sort is an efficient divide-and-conquer sorting algorithm that works by selecting a pivot element and partitioning the array.

Table: Quick Sort Steps

Example with Array [7, 2, 1, 6, 8, 5, 3, 4]:

Pivot: 4
After partition: [2, 1, 3] 4 [7, 6, 8, 5]
                 Left      P  Right

Recursively sort left: [1] 2 [3] → [1, 2, 3]
Recursively sort right: [5] 7 [6, 8] → [5, 6, 7, 8]

Final sorted array: [1, 2, 3, 4, 5, 6, 7, 8]

Diagram: Quick Sort Partitioning

flowchart TD
    A[Array: 7,2,1,6,8,5,3,4] --> B[Choose Pivot: 4]
    B --> C[Partition]
    C --> D[Left: 2,1,3]
    C --> E[Pivot: 4]
    C --> F[Right: 7,6,8,5]
    D --> G[Recursively Sort Left]
    F --> H[Recursively Sort Right]
    G --> I[Sorted Left: 1,2,3]
    H --> J[Sorted Right: 5,6,7,8]
    I --> K[Final: 1,2,3,4,5,6,7,8]
    E --> K
    J --> K

Mnemonic: “PPR - Pivot, Partition, Recursive divide”

Question 5(a) [3 marks]

#

Explain binary tree.

Answer: A binary tree is a hierarchical data structure where each node has at most two children referred to as left and right child.

Diagram: Binary Tree

Table: Binary Tree Properties

Mnemonic: “RLTM - Root, Left, Two, Maximum”

Question 5(b) [4 marks]

#

Define the terms root, path, parent and children with reference to tree.

Answer: Trees have specific terminology to describe relationships between nodes in the hierarchy.

Table: Tree Terminology

Diagram: Tree Terminology

Mnemonic: “RPPC - Root at Top, Path connects, Parent above, Children below”

Question 5(c) [7 marks]

#

Apply preorder and postorder traversal for given below tree.

Answer: Preorder and postorder are depth-first tree traversal methods with different node visiting sequences.

Given Tree:

Table: Tree Traversal Comparison

Code Example:

def preorder(root):
    if root:
        print(root.data, end=", ")  # Visit root
        preorder(root.left)         # Visit left subtree
        preorder(root.right)        # Visit right subtree

def postorder(root):
    if root:
        postorder(root.left)        # Visit left subtree
        postorder(root.right)       # Visit right subtree
        print(root.data, end=", ")  # Visit root

Mnemonic: “PRE-NLR, POST-LRN - Preorder (Node-Left-Right), Postorder (Left-Right-Node)”

Question 5(a) OR [3 marks]

#

Enlist applications of binary tree.

Answer: Binary trees have numerous practical applications in various fields of computer science.

Table: Binary Tree Applications

Mnemonic: “BEHPD - BST, Expression, Huffman, Priority queue, Decision tree”

Question 5(b) OR [4 marks]

#

Explain insertion of a node in binary search tree.

Answer: Insertion in a Binary Search Tree (BST) follows the BST property: left child < parent < right child.

Table: Insertion Steps in BST

Diagram: BST Insertion

flowchart TD
    A[Start at Root] --> B{New Value < Current?}
    B -- Yes --> C[Move to Left Child]
    B -- No --> D[Move to Right Child]
    C --> E{Left Child Exists?}
    D --> F{Right Child Exists?}
    E -- Yes --> B
    E -- No --> G[Insert as Left Child]
    F -- Yes --> B
    F -- No --> H[Insert as Right Child]

Mnemonic: “LSRG - Less-go-left, Same-or-greater-go-right”

Question 5(c) OR [7 marks]

#

Draw Binary search tree for 8, 4, 12, 2, 6, 10, 14, 1, 3, 5 and write In-order traversal for the tree.

Answer: Binary Search Tree (BST) is constructed by inserting nodes while maintaining the BST property.

Binary Search Tree for the given elements:

Table: BST Construction Process

In-order Traversal:

An in-order traversal visits nodes in the order: left subtree, current node, right subtree.

For the given BST, the in-order traversal is: 1, 2, 3, 4, 5, 6, 8, 10, 12, 14

Code Example:

def inorder_traversal(root):
    if root:
        inorder_traversal(root.left)    # Visit left subtree
        print(root.data, end=", ")      # Visit current node
        inorder_traversal(root.right)   # Visit right subtree

Mnemonic: “LNR - Left, Node, Right makes sorted order in BST”