Data Structure and Application (1333203) - Winter 2023 Solution
Solution guide for Data Structure and Application (1333203) Winter 2023 exam
Question 1(a) [3 marks]
Define linked list. List different types of linked list.
Answer:
| Definition | Types of Linked List |
|---|---|
| A linked list is a linear data structure where elements are stored in nodes, and each node points to the next node in the sequence | 1. Singly Linked List 2. Doubly Linked List 3. Circular Linked List 4. Circular Doubly Linked List |
Diagram:
goat
Mnemonic: "Single, Double, Circle, Double-Circle"
Question 1(b) [4 marks]
Explain Linear and Non Linear Data structure in Python with examples.
Answer:
| Data Structure | Description | Python Examples |
|---|---|---|
| Linear | Elements arranged in sequential order where each element has exactly one predecessor and successor (except first and last) | Lists: [1, 2, 3] Tuples: (1, 2, 3) Strings: "abc" Queue: queue.Queue() |
| Non-Linear | Elements not arranged sequentially; an element can connect to multiple elements | Dictionary: {"a": 1, "b": 2} Set: {1, 2, 3} Tree: Custom implementation Graph: Custom implementation |
Diagram:
Mnemonic: "Linear Listens In Sequence, Non-linear Navigates Various Paths"
Question 1(c) [7 marks]
Explain class, attributes, object and class method in python with suitable example.
Answer:
Diagram:
| Term | Description |
|---|---|
| Class | Blueprint for creating objects with shared attributes and methods |
| Attributes | Variables that store data inside a class |
| Object | Instance of a class with specific attribute values |
| Class Method | Functions defined within a class that can access and modify class states |
Code:
Python
Mnemonic: "Class Creates, Attributes Store, Objects Use, Methods Operate"
Question 1(c) OR [7 marks]
Define Data Encapsulation & Polymorphism. Develop a Python code to explain Polymorphism.
Answer:
| Concept | Definition |
|---|---|
| Data Encapsulation | Bundling data and methods into a single unit (class) and restricting direct access to some components |
| Polymorphism | Ability of different classes to provide their own implementation of methods with the same name |
Diagram:
Code:
Python
Mnemonic: "Encapsulate to Protect, Polymorphism for Flexibility"
Question 2(a) [3 marks]
Differentiate 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 | Elements can only be added/removed from one end (top) | Elements are added at rear end and removed from front end |
Diagram:
goat
Mnemonic: "Stack Piles Up, Queue Lines Up"
Question 2(b) [4 marks]
Write an algorithm for PUSH and POP operation of stack in python.
Answer:
PUSH Algorithm:
goat
POP Algorithm:
goat
Code:
Python
Mnemonic: "Push to Top, Pop from Top"
Question 2(c) [7 marks]
Convert following equation from infix to postfix using Stack. A * (B + C) - D / (E + F)
Answer:
Diagram:
goat
| Step | Symbol | Stack | Output |
|---|---|---|---|
| 1 | A | A | |
| 2 | * | * | A |
| 3 | ( | * ( | A |
| 4 | B | * ( | A B |
| 5 | + | * ( + | A B |
| 6 | C | * ( + | A B C |
| 7 | ) | * | A B C + |
| 8 | - | - | A B C + * |
| 9 | D | - | A B C + * D |
| 10 | / | - / | A B C + * D |
| 11 | ( | - / ( | A B C + * D |
| 12 | E | - / ( | A B C + * D E |
| 13 | + | - / ( + | A B C + * D E |
| 14 | F | - / ( + | A B C + * D E F |
| 15 | ) | - / | A B C + * D E F + |
| 16 | end | A B C + * D E F + / - |
Answer: A B C + * D E F + / -
Mnemonic: "Operators Stack, Operands Print"
Question 2(a) OR [3 marks]
Differentiate between simple Queue and circular Queue.
Answer:
| Feature | Simple Queue | Circular Queue |
|---|---|---|
| Structure | Linear data structure | Linear data structure with connected ends |
| Memory | Inefficient memory usage due to unused space after dequeue | Efficient memory usage by reusing empty spaces |
| Implementation | Front always at index 0, rear increases | Front and rear move in circular fashion using modulo |
Diagram:
Mnemonic: "Simple Wastes, Circular Reuses"
Question 2(b) OR [4 marks]
Explain concept of recursive function with suitable example.
Answer:
| Key Aspects | Description |
|---|---|
| Definition | A function that calls itself to solve a smaller instance of the same problem |
| Base Case | The condition where the function stops calling itself |
| Recursive Case | The condition where the function calls itself with a simpler version of the problem |
Diagram:
Code:
Python
Mnemonic: "Base Breaks, Recursion Returns"
Question 2(c) OR [7 marks]
Develop a python code to implement Enqueue and Dequeue operation in Queue.
Answer:
Diagram:
goat
Code:
Python
Mnemonic: "Enqueue at End, Dequeue from Start"
Question 3(a) [3 marks]
Give Difference between Singly linked list and Circular linked list.
Answer:
| Feature | Singly Linked List | Circular Linked List |
|---|---|---|
| Last Node | Points to NULL | Points back to the first node |
| Traversal | Has a definite end | Can be traversed continuously |
| Memory | Each node needs one pointer | Each node needs one pointer |
Diagram:
goat
Mnemonic: "Singly Stops, Circular Cycles"
Question 3(b) [4 marks]
Explain concept of Doubly linked list.
Answer:
Diagram:
goat
| Feature | Description |
|---|---|
| Node Structure | Each node contains data and two pointers (previous and next) |
| Navigation | Can traverse in both forward and backward directions |
| Operations | Insertion and deletion can be performed from both ends |
| Memory Usage | Requires more memory than singly linked list due to extra pointer |
Code:
Python
Mnemonic: "Double Pointers, Double Directions"
Question 3(c) [7 marks]
Write an algorithm for following operation on singly linked list: 1. To insert a node at the beginning of the list. 2. To insert the node at the end of the list.
Answer:
Insert at Beginning:
Insert at End:
Code:
Python
Mnemonic: "Begin: New Leads Old, End: Old Leads New"
Question 3(a) OR [3 marks]
List different operations performed on singly linked list.
Answer:
| Operations on Singly Linked List |
|---|
| 1. Insertion (at beginning, middle, end) |
| 2. Deletion (from beginning, middle, end) |
| 3. Traversal (visiting each node) |
| 4. Searching (finding a specific node) |
| 5. Updating (modifying node data) |
Diagram:
Mnemonic: "Insert Delete Traverse Search Update"
Question 3(b) OR [4 marks]
Explain concept of Circular linked list.
Answer:
Diagram:
goat
| Feature | Description |
|---|---|
| Structure | Last node points to the first node instead of NULL |
| Advantage | Allows continuous traversal through all nodes |
| Applications | Round robin scheduling, circular buffer implementation |
| Operations | Insertion and deletion similar to singly linked list with special handling for the last node |
Code:
Python
Mnemonic: "Last Links to First"
Question 3(c) OR [7 marks]
List application of linked list. Write an algorithm to count the number of nodes in singly linked list.
Answer:
| Applications of Linked List |
|---|
| 1. Implementation of stacks and queues |
| 2. Dynamic memory allocation |
| 3. Undo functionality in applications |
| 4. Hash tables (chaining) |
| 5. Adjacency lists for graphs |
Algorithm to Count Nodes:
Code:
Python
Mnemonic: "Count While Moving"
Question 4(a) [3 marks]
Compare Linear search with Binary search.
Answer:
| Feature | Linear Search | Binary Search |
|---|---|---|
| Data Arrangement | Works on both sorted and unsorted data | Works only on sorted data |
| Time Complexity | O(n) | O(log n) |
| Implementation | Simpler | More complex |
| Best For | Small datasets or unsorted data | Large sorted datasets |
Diagram:
goat
Mnemonic: "Linear Looks at All, Binary Breaks in Half"
Question 4(b) [4 marks]
Write an algorithm for selection sort method.
Answer:
Diagram:
goat
Algorithm:
Code Outline:
Python
Mnemonic: "Find Minimum, Swap Position"
Question 4(c) [7 marks]
Develop a python code to sort following list in ascending order using Bubble sort method. list1=[5,4,3,2,1,0]
Answer:
Diagram:
goat
Code:
Python
Mnemonic: "Bubble Biggest Upward"
Question 4(a) OR [3 marks]
Define sorting. List different sorting methods.
Answer:
| Definition | Sorting Methods |
|---|---|
| Sorting is the process of arranging data in a specified order (ascending or descending) | 1. Bubble Sort 2. Selection Sort 3. Insertion Sort 4. Merge Sort 5. Quick Sort 6. Heap Sort 7. Radix Sort |
Diagram:
Mnemonic: "Better Sort Improves Many Query Results"
Question 4(b) OR [4 marks]
Write an algorithm for Insertion sort method.
Answer:
Diagram:
goat
Algorithm:
Code Outline:
Python
Mnemonic: "Take Card, Insert In Order"
Question 4(c) OR [7 marks]
Develop a python code to sort following list in ascending order using selection sort method. list1=[6,3,25,8,-1,55,0]
Answer:
Diagram:
goat
Code:
Python
Mnemonic: "Select Smallest, Shift to Start"
Question 5(a) [3 marks]
Define following terms regarding Tree data structure: 1. Forest 2. Root node 3. Leaf node
Answer:
| Term | Definition |
|---|---|
| Forest | Collection of disjoint trees (multiple trees without connections between them) |
| Root Node | Topmost node of a tree with no parent, from which all other nodes are descended |
| Leaf Node | Node with no children (terminal node at the bottom of the tree) |
Diagram:
goat
Mnemonic: "Forest has Many Roots, Roots Lead All, Leaves End All"
Question 5(b) [4 marks]
Draw Binary search tree for 78,58,82,15,66,80,99 and write In-order traversal for the tree.
Answer:
Binary Search Tree:
goat
In-order Traversal:
| Step | Visit Order |
|---|---|
| 1 | Visit left subtree of 78 |
| 2 | Visit left subtree of 58 |
| 3 | Visit 15 |
| 4 | Visit 58 |
| 5 | Visit 66 |
| 6 | Visit 78 |
| 7 | Visit left subtree of 82 |
| 8 | Visit 80 |
| 9 | Visit 82 |
| 10 | Visit 99 |
In-order Traversal Result: 15, 58, 66, 78, 80, 82, 99
Mnemonic: "Left, Root, Right"
Question 5(c) [7 marks]
Write an algorithm for following operation: 1. Insertion of Node in Binary Tree 2. Deletion of Node in Binary Tree
Answer:
Insertion Algorithm:
Deletion Algorithm:
Code:
Python
Mnemonic: "Insert at Empty, Delete by Swap and Remove"
Question 5(a) OR [3 marks]
Define following terms regarding Tree data structure: 1. In-degree 2. Out-degree 3. Depth
Answer:
| Term | Definition |
|---|---|
| In-degree | Number of edges coming into a node (always 1 for each node except root node in a tree) |
| Out-degree | Number of edges going out from a node (number of children) |
| Depth | Length of the path from root to the node (number of edges in path) |
Diagram:
goat
| Node | In-degree | Out-degree |
|---|---|---|
| A | 0 | 2 |
| B | 1 | 2 |
| C | 1 | 1 |
| D | 1 | 0 |
| E | 1 | 0 |
| F | 1 | 0 |
Mnemonic: "In Counts Parents, Out Counts Children, Depth Counts Edges from Root"
Question 5(b) OR [4 marks]
Write Preorder and postorder traversal of following Binary tree.
Binary Tree:
goat
Answer:
| Traversal | Order | Result |
|---|---|---|
| Preorder | Root, Left, Right | 100, 20, 10, 30, 200, 150, 300 |
| Postorder | Left, Right, Root | 10, 30, 20, 150, 300, 200, 100 |
Preorder Visualization:
Postorder Visualization:
Mnemonic:
- Preorder: "Root First, Then Children"
- Postorder: "Children First, Then Root"
Question 5(c) OR [7 marks]
Develop a program to implement construction of Binary Search Tree.
Answer:
Diagram:
Code:
Python
Example Output:
Inorder traversal: 20 30 40 50 60 70 80
Preorder traversal: 50 30 20 40 70 60 80
Postorder traversal: 20 40 30 60 80 70 50
Mnemonic: "Insert Smaller Left, Larger Right"