Data Structure and Application (1333203) - Winter 2024 Solution

Solution guide for Data Structure and Application (1333203) Winter 2024 exam

December 7, 2024

study-material solutions data-structure 1333203 2024 winter

Question 1(a) [3 marks]

Write names of linear data structures.

Answer:

Linear Data Structures
1. Array
2. Stack
3. Queue
4. Linked List

Mnemonic: "All Students Queue Lazily"

Question 1(b) [4 marks]

Define Time and space complexity.

Answer:

Complexity Type	Definition	Notation
Time Complexity	Measures how execution time increases as input size grows	O(n), O(1), O(log n)
Space Complexity	Measures how memory usage increases as input size grows	O(n), O(1), O(log n)

Diagram:

goat

Mnemonic: "Time Steps, Space Stores"

Question 1(c) [7 marks]

Explain concept of class & object with example.

Answer:

Diagram:

Concept	Definition	Example
Class	Blueprint or template for creating objects	Student class with properties (rollNo, name) and methods (setData, displayData)
Object	Instance of a class with specific values	student1 (rollNo=101, name="Raj")

Code Example:

Python

Mnemonic: "Class Creates, Objects Operate"

Question 1(c) OR [7 marks]

Develop a class for managing student records with instance methods for adding and removing students from a class.

Answer:

Diagram:

Code:

Python

Mnemonic: "Add Accumulates, Remove Reduces"

Question 2(a) [3 marks]

Explain the importance of constructor in class.

Answer:

Constructor Importance
1. Initializes object's data members
2. Automatically called when object is created
3. Can have different versions (default, parameterized, copy)

Mnemonic: "Initialization Always Creates"

Question 2(b) [4 marks]

Explain different operations on stack.

Answer:

Operation	Description	Example
Push	Adds element to top	push(5)
Pop	Removes element from top	x = pop()
Peek/Top	Views top element without removing	x = peek()
isEmpty	Checks if stack is empty	if(isEmpty())

Diagram:

goat

Mnemonic: "Push Pop Peek Properly"

Question 2(c) [7 marks]

Describe evaluation algorithm of postfix expression A B C + * D /

Answer:

Diagram:

goat

Step	Symbol	Action	Stack
1	A	Push onto stack	A
2	B	Push onto stack	A,B
3	C	Push onto stack	A,B,C
4	+	Pop B,C; Push B+C	A,B+C
5	*	Pop A,B+C; Push A*(B+C)	A*(B+C)
6	D	Push onto stack	A*(B+C),D
7	/	Pop A(B+C),D; Push A(B+C)/D	A*(B+C)/D

Mnemonic: "Read, Push, Pop, Calculate"

Question 2(a) OR [3 marks]

Write difference between stack and queue.

Answer:

Feature	Stack	Queue
Principle	LIFO (Last In First Out)	FIFO (First In First Out)
Operations	Push/Pop	Enqueue/Dequeue
Access Points	Single end (top)	Two ends (front, rear)

Mnemonic: "Stack LIFO, Queue FIFO"

Question 2(b) OR [4 marks]

Explain concept of circular queue.

Answer:

Diagram:

Feature	Description
Structure	Linear data structure with connected ends
Advantage	Efficiently uses memory by reusing empty spaces
Operations	Enqueue, Dequeue with modulo arithmetic

Mnemonic: "Circular Connects Front to Rear"

Question 2(c) OR [7 marks]

Describe the procedure for inserting a new node after and before a given node in a singly linked list.

Answer:

Diagram:

goat

Insertion	Steps
After Node X	1. Create new node N 2. Set N's next to X's next 3. Set X's next to N
Before Node X	1. Create new node N 2. Find node A pointing to X 3. Set N's next to X 4. Set A's next to N

Mnemonic: "After: Set Next Links, Before: Find Previous First"

Question 3(a) [3 marks]

Explain traversing a linked list.

Answer:

Diagram:

goat

Step	Action
1	Initialize pointer to head
2	Access data at current node
3	Move pointer to next node
4	Repeat until NULL

Mnemonic: "Start, Access, Move, Repeat"

Question 3(b) [4 marks]

Explain expression conversion from infix to postfix.

Answer:

Diagram:

goat

Step	Action	Stack	Output
1	Scan from left to right
2	If operand, add to output		A
3	If operator, push if higher precedence	+	A
4	Pop lower precedence operators	+	A B
5	Push current operator	*	A B
6	Continue until expression ends	*	A B C
7	Pop remaining operators		A B C * +

Mnemonic: "Operators Push Pop, Operands Output Directly"

Question 3(c) [7 marks]

Write a program to delete a node at the beginning and end of singly linked list.

Answer:

Diagram:

goat

Code:

Python

Mnemonic: "Delete First: Shift Head, Delete Last: Find Second-Last"

Question 3(a) OR [3 marks]

Explain searching an element in linked list.

Answer:

Diagram:

goat

Step	Description
1	Start from head node
2	Compare current node's data with key
3	If match found, return true
4	Else, move to next node and repeat

Mnemonic: "Start, Compare, Move, Repeat"

Question 3(b) OR [4 marks]

Explain concepts of circular linked lists.

Answer:

Diagram:

Feature	Description
Structure	Last node points to first node
Advantage	No NULL pointers, efficient for circular operations
Traversal	Need extra condition to prevent infinite loop

Mnemonic: "Last Links to First"

Question 3(c) OR [7 marks]

Explain algorithm to search a particular element from list using Binary Search.

Answer:

Diagram:

Code:

Python

Mnemonic: "Middle, Compare, Eliminate Half"

Question 4(a) [3 marks]

Write applications of linked list.

Answer:

Applications of Linked List
1. Implementation of stacks and queues
2. Dynamic memory allocation
3. Image viewer (next/previous images)

Mnemonic: "Store Data Dynamically"

Question 4(b) [4 marks]

Differentiate between singly linked list and doubly linked list.

Answer:

Feature	Singly Linked List	Doubly Linked List
Node Structure	One pointer (next)	Two pointers (next, prev)
Traversal	Forward only	Both directions
Memory	Less memory	More memory
Operations	Simple, less code	Complex, more flexible

Diagram:

goat

Mnemonic: "Single Direction, Double Direction"

Question 4(c) [7 marks]

Write a program to sort numbers in ascending order using selection sort algorithm.

Answer:

Diagram:

goat

Code:

Python

Mnemonic: "Find Minimum, Swap Position"

Question 4(a) OR [3 marks]

Explain bubble sort algorithm.

Answer:

Diagram:

Key Points
Compare adjacent elements
Swap if they are in wrong order
Largest element bubbles to end in each pass

Mnemonic: "Bubble Bigger Elements Upward"

Question 4(b) OR [4 marks]

Differentiate Linear & Binary search.

Answer:

Feature	Linear Search	Binary Search
Working Principle	Sequential checking	Divide and conquer
Time Complexity	O(n)	O(log n)
Data Arrangement	Unsorted or sorted	Must be sorted
Best For	Small datasets	Large datasets

Mnemonic: "Linear Looks at All, Binary Breaks in Half"

Question 4(c) OR [7 marks]

Explain Quick sort & Merge sort algorithm.

Answer:

Quick Sort:

Merge Sort:

Algorithm	Principle	Average Time	Space Complexity
Quick Sort	Partitioning around pivot	O(n log n)	O(log n)
Merge Sort	Divide, conquer, combine	O(n log n)	O(n)

Mnemonic: "Quick Partitions, Merge Divides"

Question 5(a) [3 marks]

Define a complete binary tree.

Answer:

Diagram:

goat

Property	Description
All levels filled	Except possibly the last level
Last level filled from left	Nodes added from left to right

Mnemonic: "Fill Left to Right, Level by Level"

Question 5(b) [4 marks]

Explain inorder traversal of a binary tree.

Answer:

Diagram:

goat

Step	Action
1	Traverse left subtree
2	Visit root node
3	Traverse right subtree

Code:

Python

Mnemonic: "Left, Root, Right"

Question 5(c) [7 marks]

Write a program to inserting a node into a binary search tree.

Answer:

Diagram:

Code:

Python

Mnemonic: "Compare, Move, Insert"

Question 5(a) OR [3 marks]

State the fundamental characteristic of a binary search tree.

Answer:

Characteristics of Binary Search Tree
1. Left child nodes < Parent node
2. Right child nodes > Parent node
3. No duplicate values allowed

Mnemonic: "Left Less, Right More"

Question 5(b) OR [4 marks]

Explain postorder traversal of a binary tree.

Answer:

Diagram:

goat

Step	Action
1	Traverse left subtree
2	Traverse right subtree
3	Visit root node

Code:

Python

Mnemonic: "Left, Right, Root"

Question 5(c) OR [7 marks]

Write a program to delete a node from a binary search tree.

Answer:

Diagram:

Code:

Python

Mnemonic: "Find, Replace, Reconnect"