[Link] is Data Structure? What are the different types of data structure? Explain.

4 Write an algorithm to insert a node at the front/beginning of a single linked list. Set head = null the index of the next node. This method is mainly used when pointers are not available or when linked list needs to be
A data structure is a systematic way of storing and organizing data in a computer so that it can be used efficiently. When In a singly linked list, inserting a new node at the front means that the new node becomes the first node of the list. For this Stop stored in a fixed-size structure.
we write any program, the data cannot be kept in a random manner. It must be arranged in a proper structure so that operation, we need to create a new node, store the data in it, and make its next pointer point to the current head of the list. Step 4: Set temp = head For example, suppose we have:
operations like searching, inserting, deleting, updating, and sorting can be performed quickly. A good data structure After that, the head pointer should be updated to point to the new node. This algorithm is simple and takes constant time Step 5: Repeat while [Link] is not null DATA array: stores the data of each node
improves the speed of the program, saves memory, and makes the overall program efficient. Data structures help in because it does not require traversal of the list. Set temp = [Link] NEXT array: stores the index of the next node
managing large amounts of data in an organized form. Algorithm: Insert at Front of Singly Linked List Step 6: Set [Link] = null The NEXT array works like the next pointer in a normal linked list. If NEXT[i] = j, it means node at index i points to node
Data structures are mainly divided into two types: Step 1: Start Step 7: Free temp at index j. If NEXT[i] = -1, it means the node is the last node. An additional variable called START or HEAD is used to
a. Primitive Data Structures Step 2: Create a new node Step 8: Stop store the index of the first node.
These are the basic or fundamental data types that are directly supported by the programming language. These include Step 3: Store the value to be inserted in the data part of the new node This algorithm ensures the last node is removed properly and the list remains connected. This representation is useful in environments where dynamic memory allocation is not available. However, it has
integer, float, character, and boolean. These are simple structures and are used to build more complex data structures. Step 4: Set [Link] = head limitations because the size of the list is fixed by the array size and cannot grow beyond that. Still, it gives a clear way of
b. Non-Primitive Data Structures Step 5: Set head = newnode 8. Write an algorithm to delete a node from the end of a single linked list. implementing linked lists using simple array structures.
These are complex data structures made using primitive types. They can store multiple values and can grow or shrink as Step 6: Stop To delete the last node of a singly linked list, we need to traverse the list until we reach the second last node. The last node
required. These are further divided into: This algorithm works even if the list is empty. If head is null, the new node simply becomes the first node of the list. is identified when its next pointer is null. Once the second last node is found, we set its next pointer to null and free the last 11. Explain the dynamic representation of a linked list in memory.
1. Linear Data Structures node. If there is only one node, then deleting it will make the head null. Dynamic representation means that the linked list nodes are stored in memory using dynamic memory allocation. This is
In linear structures, all elements are stored in a sequential order. Each element has a next element except the last 5. Write an algorithm to insert a node at the end of a doubly linked list. Algorithm: Delete from End of Singly Linked List the standard way of representing linked lists in real programs. In this method, each node is created only when needed and
one. Examples: In a doubly linked list, each node contains data, a pointer to the next node, and a pointer to the previous node. To insert a Step 1: Start memory is allocated from the heap using functions like malloc in C. Each node contains two fields: the data field to store
Array: Stores similar type of data in continuous memory locations. node at the end, we need to traverse from the head to the last node. Then the next pointer of the last node will point to the Step 2: If head is null the value and the pointer field to store the address of the next node.
Linked List: Stores data in nodes which are connected through pointers. new node and the previous pointer of the new node will point to the last node. The new node becomes the last node of the Display "List is empty" Nodes do not have to be stored in continuous memory locations. They can be stored anywhere in memory, and they are
Stack: Follows last in first out order. list. Stop connected through pointers. The linked list starts with a special pointer called head, which stores the address of the first
Queue: Follows first in first out order. Algorithm: Insert at End of Doubly Linked List Step 3: If [Link] is null node. If the head is null, the list is empty. To add a new node, memory is allocated and the pointer links are adjusted. To
2. Non-Linear Data Structures Step 1: Start Free head delete a node, its memory is released back to the system.
In non-linear structures, the data is not arranged in a straight line. The elements are connected in a branching or Step 2: Create a new node Set head = null This representation is flexible because the list can grow or shrink at runtime. It uses memory efficiently because only the
hierarchical pattern. Examples: Step 3: Store the value to be inserted in the data part of the new node Stop required memory is allocated. It also avoids the fixed size limitation of arrays. Therefore, dynamic representation is the
Tree: Represents data in a hierarchical form with root and children. Step 4: Set [Link] = null Step 4: Set temp = head preferred method in most data structure implementations.
Graph: Represents data in the form of nodes and edges where complex relations can be shown. Step 5: If head is null, then Step 5: Repeat while [Link] is not null
Thus, data structures provide a logical way to organize data so that programs run faster and memory is used properly. Set [Link] = null Set temp = [Link] 12. What is a circular linked list? Explain with an example.
Set head = newnode Step 6: Free [Link] A circular linked list is a variation of the linked list in which the last node does not point to null. Instead, the last node
2. What is a linked list? What are the types of linked list? Stop Step 7: Set [Link] = null points back to the first node, forming a circular structure. Because of this circular connection, traversal can continue
A linked list is a dynamic data structure in which data is stored in the form of nodes. Each node contains two parts: the first Step 6: Set temp = head Step 8: Stop endlessly unless stopped manually. It allows movement from any node and provides a continuous looping effect.
part stores the actual data, and the second part stores the address of the next node. The nodes are connected using pointers, Step 7: Repeat while [Link] is not null This algorithm deletes the last node by safely reaching the second last node.
which form a chain-like structure. Linked lists do not require continuous memory allocation like arrays. Memory is Set temp = [Link] points to the head. This type of list is useful in applications where repeated cycling is requir ed, such as round-robin
allocated only when required, which reduces wastage. Insertion and deletion of elements in a linked list are easy because Step 8: Set [Link] = newnode 9. Write an algorithm to delete a node from a specified location in a linked list. scheduling or managing circular queues.
we only need to change the pointers, and no shifting of elements is needed. Step 9: Set [Link] = temp Deleting a node from a specific location means removing a node whose position is given by the user. For example, deleting Example:
Types of linked lists: Step 10: Stop the 3rd node or 5th node. For this, we need to traverse the list until the node just before the target position. Then we change Suppose we have a list containing three nodes with values 10, 20, and 30.
a. Singly Linked List This algorithm ensures the new node is linked correctly in both forward and backward directions. its next pointer to skip the node to be deleted. If the position is 1, we simply delete the first node by moving the head Node1 (data=10) points to Node2
In this list, each node contains data and the address of the next node. Traversal is possible only in one direction, that is from pointer ahead. Node2 (data=20) points to Node3
the first node to the last. The last node contains a null pointer. 6. Write an algorithm to traverse a single linked list. Algorithm: Delete Node from Specific Location in Singly Linked List Node3 (data=30) points back to Node1
b. Doubly Linked List Traversal in a singly linked list means visiting each node one by one from the first node to the last. We use a temporary Step 1: Start There is
Each node contains three parts: data, address of the previous node, and address of the next node. This allows traversal in pointer that starts at the head. Then it moves through the list using the next pointer of each node until it reaches null. Step 2: Input the position pos forming a complete cycle.
both forward and backward directions. It requires more memory because of the extra pointer. Traversal is important for displaying data or performing any search operation. Step 3: If head is null A circular linked list provides continuous traversal and is useful wherever looping data structures are required.
c. Circular Linked List Algorithm: Traverse a Singly Linked List Display "List is empty"
In this list, the last node does not point to null. Instead, it points back to the first node, making the list circular. Traversal Step 1: Start Stop 13. Define a double linked list.
can start from any node and continues in a loop. Step 2: If head is null Step 4: If pos == 1 A doubly linked list is a type of linked list in which each node contains three parts: the data part, a pointer to the next node,
d. Doubly Circular Linked List Display "List is empty" Set temp = head and a pointer to the previous node. This means every node is connected in both forward and backward directions. The list
This is a combination of circular and doubly linked lists. Each node has links for both previous and next nodes, and the last Stop Set head = [Link] starts with a head pointer which points to the first node and may end with a tail pointer pointing to the last node. In a
node connects back to the first node. Step 3: Set temp = head Free temp doubly linked list, traversal can be done from left to right as well as from right to left, which is one of its main advantages.
Linked lists are flexible, memory-efficient, and suitable for dynamic data handling in many applications. Step 4: Repeat while temp is not null Stop Because each node has two pointers, insertion and deletion operations become easier, especially when we need to move in
Display [Link] Step 5: Set temp = head both directions. However, a doubly linked list requires more memory than a singly linked list because every node stores an
3. Explain the representation of a single linked list. Set temp = [Link] Step 6: Repeat i = 1 to pos-2 extra pointer. Still, it is very useful in applications where backward traversal is required, such as navigation systems or
A single linked list is represented by nodes that are connected using pointers. Each node has two main parts. The first part Step 5: Stop If [Link] is null undo-redo operations.
stores the data element, and the second part stores the address of the next node. These nodes are distributed anywhere in This algorithm visits each node exactly once and stops when the end of the list is reached. Display "Invalid position" Structure of a Doubly Linked List Node
memory, but they remain connected through pointers. The starting point of the list is stored in a special pointer called the Stop Each node looks like:
head. The head pointer always points to the first node of the list. If the head is null, it means the list is empty. 7. Write an algorithm to delete a node from the end of a doubly linked list. Set temp = [Link] [ prev | data | next ]
The structure of a node in a singly linked list contains: In a doubly linked list, each node has two links: one for the next node and one for the previous node. To delete a node from Step 7: Set ptr = [Link] of previous node
data: stores the actual information the end, we traverse the list till the last node. Step 8: Set [Link] = [Link]
next: stores the address of the next node and free the last node. If the list has only one node, then deleting it will make the head null. Step 9: Free ptr
When we insert or delete elements, we only modify the pointers. This makes linked lists easier to update compared to Algorithm: Delete from End of Doubly Linked List Step 10: Stop 14. Write an algorithm to add an element at the beginning of a double linked list.
arrays. The last node of the list contains a null pointer which indicates the end of the list. Step 1: Start This algorithm cleans the node from any location while keeping the list properly linked. To insert a new node at the beginning of a doubly linked list, we need to create a new node, store the data in it, and then
Traversal in a single linked list starts from the head. From the head, we follow each next pointer until we reach a null Step 2: If head is null link
pointer. Since singly linked lists allow movement only in one direction, operations depend completely on proper pointer Display "List is empty" 10. Explain the array representation of a linked list in memory. empty, the previous pointer of the old head should point to the new node. Finally, we update the head pointer to point to the
management. Stop In the array representation of a linked list, we use two separate arrays to represent the data part and the pointer part of each newly inserted node.
Thus, the representation of a single linked list is based on storing nodes at different memory locations and connecting them Step 3: If [Link] is null node. Since a linked list normally uses dynamic nodes with pointers, representing it in an array requires us to store the links
through pointers to form a chain. Free head in the form of index numbers instead of memory addresses. One array stores the actual data values and another array stores

Algorithm: Insert at Beginning of Doubly Linked List Example of underflow: Overflow- Overflow condition happens when we try to push an element into a stack that is already full. Since the array has Step 7: While the stack is not empty and the operator at the top of the stack has higher or equal priority, pop it and add it to
Step 1: Start If head = null and we call delete operation, we get: a fixed maximum size, once the top pointer reaches the last index of the array, no new element can be inserted. If we still the postfix expression. After that push the scanned operator.
Step 2: Create a new node "List is empty. Underflow condition." try to push a value, the operation fails and the condition is called stack overflow. It usually means the stack has run out of Step 8: After scanning the entire expression, pop all remaining operators from the stack and add them to the postfix
Step 3: Store the value in [Link] Underflow is important to check because linked lists work with pointers. If the list is empty and still we try to access memory space. expression.
Step 4: Set [Link] = null [Link] or move pointers, it may cause program errors. Therefore, every delete operation must first check if head is null Underflow- Underflow condition happens when we try to pop an element from a stack that is already empty. In a stack, Step 9: The final postfix string obtained is the required postfix expression.
Step 5: Set [Link] = head to avoid underflow. deletion is possible only when there is at least one element present. If the top pointer is already at -1 (which indicates an
Step 6: If head is not null empty stack) and we still attempt to perform a pop operation, the operation cannot be completed. This situation is called 2.8. Convert the following infix expressions into equivalent prefix and postfix expressions:
Set [Link] = newnode 2.1. What is a stack? Explain PUSH & POP operations on stack. stack underflow. It means there is no element available to remove. (A+B)/(D-(E+G)*H)
Step 7: Set head = newnode A stack is a linear data structure that follows the LIFO (Last In, First Out) principle. In simple words, overflow means the stack is completely filled and no more items can be added, and underflow means the Infix Expression: (A + B) / (D - (E + G) * H)
Step 8: Stop This means the element that is inserted last will be removed first. stack is empty and no items can be removed. Prefix conversion step by step
This algorithm works for both empty and non-empty lists. A stack has only one end called the TOP, where all insertions and deletions take place. (A + B) becomes + A B
Common examples of stack usage: 2.5 Create a stack and perform the following operations: (E + G) becomes + E G
15. Write an algorithm to count the number of nodes in a linked list. Undo/Redo operations (i) Push A (E + G) * H becomes * + E G H
Algorithm: Count Nodes in Singly Linked List (ii) Push B D - [(E + G) * H] becomes - D * + E G H
Step 1: Start Function call management in memory (iii) Pop (A + B) / [above] becomes / + A B - D * + E G H
Step 2: If head is null Expression evaluation (iv) Push C Prefix expression:
Display "List is empty" PUSH Operation (Insert): (v) Push D /+ A B -D *+ E GH
Set count = 0 PUSH means inserting a new element on the top of the stack. Let the stack be empty initially. Let top = -1. Postfix conversion step by step
Stop Before inserting, we check whether the stack is full or not. Operation 1: Push A (A + B) becomes A B +
Step 3: Set temp = head If the stack is full, it is called Overflow condition. Stack: A (E + G) becomes E G +
Step 4: Set count = 0 If not full, the TOP is increased by 1 and the new element is inserted. Top = 0 (E + G) * H becomes E G + H *
Step 5: Repeat while temp is not null POP Operation (Delete): Operation 2: Push B D - [(E + G) * H] becomes D E G + H * -
Increase count by 1 POP means removing an element from the top of the stack. Stack: A, B (A + B) / [above] becomes A B + D E G + H * - /
Set temp = [Link] Before deleting, we check whether the stack is empty or not. Top = 1 Postfix expression:
Step 6: Display count If the stack is empty, it is called Underflow condition. Operation 3: Pop AB+D EG +H *- /
Step 7: Stop If not empty, the element at TOP is removed and TOP is decreased by 1. Element removed: B
This algorithm ensures that every node is counted exactly once. Stack: A 2.9. Translate the following infix expression into prefix and postfix expressions:
2.2. Write an algorithm to insert an element into a stack. (PUSH Operation) Top = 0 (i) A + (B * D / E) * (F + G / H) - K
16. Explain the linked list representation of a polynomial with example. Algorithm: PUSH(stack, element) Operation 4: Push C Breakdown:
A polynomial is an expression that contains terms made up of coefficients and powers of variables. For example: Step 1: If TOP = MAX 1, then Stack: A, C Inside first bracket: B * D / E
5x³ + 2x² + 7x + 4 Top = 1 B * D becomes B D *
In mathematical operations, we often need to store and process polynomials. A linked list is a very good way to represent a Step 2: TOP = TOP + 1 Operation 5: Push D (B * D) / E becomes B D * E /
polynomial because each term can be stored as a separate node. Step 3: STACK[TOP] = element Stack: A, C, D Second bracket: F + G / H
In a linked list representation of a polynomial, each node contains three parts: Top = 2 G / H becomes G H /
1. Coefficient: the number before the variable Step 5: End Final stack from bottom to top: A, C, D F + (G / H) becomes F G H / +
2. Exponent: the power of the variable Now full expression:
3. Next pointer: the address of the next term 2.3. Explain different operations on stack data structure. 2.6 Explain Polish notations. A + [B D * E /] * [F G H / +] - K
Each node represents one term of the polynomial, and all nodes are linked in decreasing or increasing order of exponent. A stack supports several important operations. These operations are: Polish notations are special ways of writing arithmetic expressions so that there is no need to use brackets. These notations Prefix expression:
Using this structure, we can easily perform operations like polynomial addition, subtraction, evaluation, and multiplication. 1. PUSH help reduce confusion and make expression evaluation easier for computers because the order of operations becomes clear
Example: Represent the polynomial Used to insert a new element into the stack. from the position of operators and operands.
The element is always inserted at the top.
o A*/ *B DE F+GH / K
5x³ + 2x² + 7x + 4 There are mainly two types of Polish notations: prefix notation and postfix notation. Postfix expression:
We create four nodes as follows: If the stack is full, Overflow occurs. Prefix notation is also known as Polish notation. In prefix notation, the operator comes before the operands. For example, ABD*E/FGH/+*+K -
Node1: coeff = 5, expo = 3 2. POP the infix expression A + B is written as + A B in prefix. Parentheses are not required because the order is fixed by writing
Node2: coeff = 2, expo = 2 Used to delete the element from the top of the stack. the operator first. Prefix expressions are useful in expression evaluation and compiler design because they can be easily (ii) (A + B) * C * (D * E) / F
Node3: coeff = 7, expo = 1 If the stack is empty, Underflow occurs. calculated from right to left. Step 1: (A + B) becomes A B +
Node4: coeff = 4, expo = 0 3. PEEK / TOP Postfix notation is also known as Reverse Polish Notation (RPN). In postfix notation, the operator comes after the Step 2: (D * E) becomes D E *
The next pointer of each node points to the next term: This operation returns the value of the topmost element without removing it. operands. For example, A + B becomes A B + in postfix. Postfix expressions can be evaluated easily using a stack. The Full expression:
It helps to check the current element at top. scanning is generally done from left to right, and whenever an operand is found it is pushed onto the stack, and when an (A+B) * C * (D*E) / F
Here, the last node contains a next pointer as null, indicating the end of the polynomial. 4. isEmpty operator is found, the required number of operands are popped and the operator is applied. Prefix expression:
This form of representation is better than arrays because we do not waste memory and can add or remove terms easily. This operation checks whether the stack is empty. Infix notation is the usual way we write expressions in mathematics, where the operator is between the operands, like A + / **+ ABCD E *F
Also, operations like combining like terms and adding new polynomial terms become simple because pointers can be It returns TRUE if TOP = -1, otherwise FALSE. B. But infix needs parentheses to show priority, while prefix and postfix do not. Postfix expression:
updated quickly. 5. isFull In summary, Polish notations provide a clear and bracket-free way of writing expressions, and they are very useful in A B + C * D E * * F /.
This operation checks whether the stack is full. computer algorithms for expression evaluation.
17. Explain the underflow condition in a linked list. It returns TRUE if TOP = MAX 1, else FALSE.
2.10. Write an algorithm to evaluate a postfix expression.
Underflow means trying to perform an operation on a linked list when the list is already empty. In simple words, underflow 6. Display 7. Write an algorithm for translating an infix expression into postfix notation. Algorithm: Evaluate Postfix Expression
occurs when you try to delete a node but there is no node present in the list to delete. This is an error condition because the This operation prints all elements of the stack starting from TOP to bottom. Algorithm: Infix to Postfix Conversion Step 1: Create an empty stack.
operation cannot be completed. These operations help in managing data in a LIFO order and are widely used in programming, compilers, and memory Step 1: Create an empty stack for operators. Step 2: Scan the postfix expression from left to right.
In a linked list, the head pointer stores the address of the first node. If head is null, it means the list is empty. Any delete management. Step 2: Scan the infix expression from left to right. Step 3: If the scanned symbol is an operand, push it onto the stack.
operation, such as: Step 3: If the scanned character is an operand, add it directly to the postfix expression. Step 4: If the scanned symbol is an operator, then pop the top two elements from the stack.
delete from beginning 2.4 What are the overflow and underflow conditions of a stack in array representation? Step 4: If the scanned character is an opening bracket (, push it onto the stack. Step 5: Apply the operator on the two popped values in the correct order (second popped operand operator first popped
delete from end In array representation, a stack is implemented using a fixed-size array. This means the size of the stack cannot grow Step 5: If the scanned character is a closing bracket ), pop operators from the stack and add them to the postfix expression operand).
delete from specific position beyond the limit of the array. Two important exceptional conditions occur during stack operations: overflow and until an opening bracket is removed. Step 6: Push the result back onto the stack.
cannot be performed if the head is null. If we try to delete in this situation, underflow happens. underflow. Step 6: If the scanned character is an operator, check its priority and associativity.
Step 7: Repeat steps until the entire postfix expression is scanned. 2. Partition the array so that all elements smaller than pivot go to left and all greater go to right. Order of deletion will be: 1. Assume the first element is already sorted.
Step 8: The final value remaining in the stack is the evaluated result of the postfix expression. 3. Recursively apply Quick Sort to the left part. First remove 10 (priority 3) 2. Take the next element and compare it with elements in the sorted part.
4. Recursively apply Quick Sort to the right part. Then remove 20 (priority 2) 3. Shift all larger elements one position ahead.
5. Continue until all subarrays are sorted. Then remove 5 (priority 1) 4. Insert the current element into the correct position.
Example: Sort the array [8, 3, 1, 7, 9] Array representation: 5. Repeat the process for all elements.
Choose pivot = 8 Elements are stored along with their priorities. Example: Example:
2.11. What is recursion? Left side: 3, 1, 7 Index: 0 1 2 Array: 5, 3, 8, 4
Recursion is a programming technique in which a function calls itself repeatedly until a base condition is reached. In Right side: 9 Element: 10 20 5 8, 4
recursion, a problem is divided into smaller subproblems of the same type. Each recursive call solves a smaller part until Now sort left side [3, 1, 7] Priority: 3 2 1
the simplest version of the problem is solved. Choose pivot = 3 During deletion, search the array for the highest priority element. Final sorted list: 3, 4, 5, 8
A recursive function always has two important parts: Left: 1
1. A base case, which stops the recursion. Right: 7 3.5. Give a diagrammatic representation of a dequeue. 3.9. Write an algorithm for the insertion sort method.
2. A recursive case, which calls the function again with a smaller or simpler input. Now these subarrays are sorted. Example diagram of a deque: Algorithm: Insertion Sort
Recursion is used in problems like factorial, Fibonacci series, Tower of Hanoi, tree traversal, sorting, and many Right side [9] is already sorted. Step 1: Start
mathematical computations. Final sorted array: 1, 3, 7, 8, 9 Or as a box structure:
Quick Sort is faster than many sorting algorithms because it reduces the average time complexity to O(n log n). | Front | Step 3: Set key = A[i]
2.12. Write a recursive algorithm to find the factorial of a given number. | 20 | 15 | 40 | 10 |
Algorithm: Recursive Factorial 3.1. What is a queue? Write an algorithm to insert an element into a queue. | Rear | Step 5: While j >= 0 and A[j] > key
Step 1: Start A queue is a linear data structure that follows the FIFO method, which means First In First Out. The element inserted first It indicates that insertions and deletions can occur from both ends. A[j + 1] = A[j]
Step 2: If n = 0 or n = 1, return 1 is removed first. In a queue, insertion is done from the rear end and deletion is done from the front end. It is used in Here are the long, simple-language, exam-ready answers. Headings are in bold as you allowed. Everything else is simple
Step 3: Otherwise return n * factorial(n - 1) scheduling, CPU task management, printers, and many real-life applications like waiting lines. font. Step 6: Insert key at A[j + 1]
Step 4: End Algorithm to insert an element into a queue (Enqueue): Step 7: Continue until the list is sorted
Example: Step 1: Check if rear = MAX 1. If yes, queue is full, insertion not possible. 3.6. What is sorting? Explain selection sort method with suitable example. Step 8: End
factorial(5) Step 2: If queue is empty (front = -1 and rear = -1), set front = 0 and rear = 0. Sorting is the process of arranging data in a particular order, either in ascending (small to large) or descending (large to
= 5 * factorial(4) Step 3: Otherwise, increase rear by 1 (rear = rear + 1). small) order. Sorting helps in fast searching, easy data management, and improves processing efficiency. 3.10. What is merging? Explain Merge Sort with a suitable example.
= 5 * 4 * factorial(3) Step 4: Insert the new element at position queue[rear]. Selection sort is one of the simplest sorting methods. It works by repeatedly finding the smallest element from the unsorted Merging is the process of combining two sorted lists into one single sorted list. Merge sort is a sorting algorithm based on
= 5 * 4 * 3 * factorial(2) Step 5: End. part of the list and placing it at the beginning. In each pass, the algorithm selects the minimum value and swaps it with the the divide-and-conquer technique. It breaks the array into two smaller halves, sorts each half, and then merges them to form
= 5 * 4 * 3 * 2 * factorial(1) first unsorted position. the final sorted list.
= 120 3.2. What is a circular queue? Write an algorithm to insert an element in a circular queue. Steps of Selection Sort: Steps in Merge Sort:
A circular queue is an improved version of a simple queue where the last position is connected back to the first position 1. Start from the first element. 1. Divide the array into two halves.
2.13. Explain the Tower of Hanoi problem and write the moves to solve it for three disks. forming a circle. This structure solves the problem of unused space in normal queues. When the rear reaches the end of the 2. Find the smallest element in the entire list. 2. Recursively apply merge sort to each half.
Tower of Hanoi is a classic problem in recursion. It contains three pegs named A, B, and C. All disks start on peg A in array, it wraps around to the first index if space is available. 3. Swap it with the first element. 3. Merge the two sorted halves to get the final sorted array.
increasing size from top to bottom. The objective is to move all disks from peg A to peg C using peg B as a helper, Algorithm to insert an element in a circular queue: 4. Now move to the second position and repeat the process for the remaining list. Example: Sort 8, 3, 1, 6
following three rules: Step 1: Check if the queue is full. Condition: (rear + 1) % MAX = front 5. Continue this until the whole list is sorted. Divide into two halves: [8, 3] and [1, 6]
1. Only one disk can be moved at a time. If true, queue is full. Example: Given array: 5, 2, 8, 4 Sort each: [3, 8] and [1, 6]
2. A larger disk cannot be placed on top of a smaller disk. Step 2: If the queue is empty (front = -1 and rear = -1), set front = 0 and rear = 0. Merge: [1, 3, 6, 8]
3. Use the helper peg to temporarily hold disks. Step 3: Otherwise, set rear = (rear + 1) % MAX 4, 8, 5 Merge sort always divides, sorts each part, and then merges properly.
Moves for 3 disks from A to C: Step 4: Insert the new element at queue[rear].
Move 1: Move disk 1 from A to C Step 5: End. Final sorted list: 2, 4, 5, 8 3.11. Discuss the complexity of the merge sort method.
Move 2: Move disk 2 from A to B Time Complexity:
Move 3: Move disk 1 from C to B 3.3. What is a double-ended queue (Deque)? Explain with suitable example. 3.7. Sort the following data using selection sort: Merge sort always divides the list into two halves and performs merging.
Move 4: Move disk 3 from A to C A double-ended queue, also called deque, is a linear data structure where insertion and deletion can be performed from both 7, 6, 1, 4, 3, 9, 2 It takes:
Move 5: Move disk 1 from B to A ends: the front and the rear. Unlike a normal queue, which allows insertion only at rear and deletion only from front, a Step-by-step selection sort: O(n log n) time in best case
Move 6: Move disk 2 from B to C deque provides more flexibility. Initial array: O(n log n) time in average case
Move 7: Move disk 1 from A to C Types of deque: 7, 6, 1, 4, 3, 9, 2 O(n log n) time in worst case
Total moves required = 2^n 1 = 7 moves. 1. Input restricted deque deletion from both ends, insertion only at one end. with 7 So merge sort is very efficient and stable.
2. Output restricted deque insertion from both ends, deletion only at one end. 1, 6, 7, 4, 3, 9, 2 Space Complexity:
2.14. Write a recursive procedure for the Tower of Hanoi problem. Example: Pass 2: From 6 Merge sort requires additional space to store the merged result. Hence its space complexity is O(n).
Procedure TowerOfHanoi(n, source, auxiliary, destination): Take a deque: [ ] 1, 2, 7, 4, 3, 9, 2 Merge sort is preferred in cases when stable sorting and consistent performance are required.
If n = 1: Pass 3: From 7
Print move disk from source to destination Insert from fr 1, 2, 3, 4, 7, 9, 6 3.12 . Explain Big-O Notation.
Return Pass 4: From 4 Big-O notation is a way to describe the time complexity or performance of an algorithm in terms of the size of input
Else: 1, 2, 3, 4, 7, 9, 6 (usually n). It shows how the runtime or space requirement grows as the input size increases. Big-O focuses on the worst-
TowerOfHanoi(n - 1, source, destination, auxiliary) Thus, operations are allowed from both sides. Pass 5: From 7 case scenario and ignores constants and lower-order terms.
Print move disk from source to destination 1, 2, 3, 4, 6, 9, 7 Common Big-O notations:
TowerOfHanoi(n - 1, auxiliary, source, destination) 3.4. What is a priority queue? Explain with suitable example and its array representation. Pass 6: From 9 1. O(1) Constant time: Execution time does not change with input size. Example: Accessing an array element.
A priority queue is a special type of queue where every element has a priority. Instead of FIFO order, the element with the 1, 2, 3, 4, 6, 7, 9 2. O(n) Linear time: Time grows linearly with input size. Example: Traversing a list of n elements.
2.15. Explain the Quick Sort algorithm using an example. highest priority is removed first. If two elements have the same priority, then FIFO order is followed. Final sorted list: 3. O(n²) Quadratic time: Time grows proportional to the square of input. Example: Bubble sort or selection sort.
Quick Sort is a divide-and-conquer sorting algorithm. It works by selecting one element as the pivot and partitioning the Uses: job scheduling, CPU scheduling, emergency systems, printer queue with priority documents. 1, 2, 3, 4, 6, 7, 9 4. O(log n) Logarithmic time: Time grows logarithmically. Example: Binary search.
array so that smaller elements move to the left of the pivot and larger elements move to the right. After partitioning, the Example: 3.8. Explain Insertion sort method with a suitable example. 5. O(n log n) Linearithmic time: Time grows proportionally to n log n. Example: Merge sort, Quick sort.
pivot reaches its correct sorted position. Then the same process is applied recursively to the left and right subarrays. Suppose three elements with priorities: Insertion sort is a simple, intuitive sorting method. It works like sorting playing cards in your hand. In each step, one Big-O helps to compare algorithms and select the most efficient one for large input sizes.
Steps of Quick Sort: (10, priority 3), (5, priority 1), (20, priority 2) element from the unsorted portion is taken and inserted into its correct position in the sorted portion.
1. Choose a pivot element from the array (first, last, or middle element). Steps: 3.13 What is a hash function? Explain hashing methods with example.

A hash function is a function that converts a key into an index in a hash table where the corresponding value will be stored. o Parent of node 1. It must be a complete binary tree. ABCD
Hashing is used for fast data retrieval in constant time. Array representation is simple but wastes space if the tree is not complete. This means all levels of the tree are completely filled, except possibly the last level, and the nodes in the last
Example: Suppose we have keys 10, 22, 31, 4, 15. Using hash function h(key) = key % 10 level are filled from left to right. D0 1 0 0
We get the table indexes: 4.3. What is traversing? Write an algorithm for preorder traversal of Binary tree. 2. It must satisfy the heap property. 2. Adjacency List:
Traversing means visiting all nodes of a tree in a specific order. Traversal is used to display or process data in the tree. There are two types of heaps based on this property: o Each vertex stores a list of connected vertices.
Hashing methods: Preorder Traversal: Visit nodes in order: a. Max Heap: o Memory efficient for sparse graphs.
1. Direct Addressing: Use the key itself as an index (works when keys are small and limited). Algorithm: PreorderTraversal(node) In a max heap, the value of each parent node is greater than or equal to the value of its children. o Example:
2. Division Method: Use h(key) = key % table_size. Most common method. Step 1: Start The largest element is always stored at the root of the tree.
3. Multiplication Method: Multiply key with a constant, take fractional part, then multiply by table size. Step 2: If node is null, return b. Min Heap:
4. Mid-square Method: Square the key and take middle digits as index. Step 3: Visit node (print [Link]) In a min heap, the value of each parent node is less than or equal to the value of its children.
Hashing allows fast insertion, deletion, and search in a hash table. Step 4: PreorderTraversal([Link]) The smallest element is stored at the root.
Step 5: PreorderTraversal([Link]) Heaps are mainly used in priority queues, heap sort algorithm, and for selecting highest/lowest elements quickly.
3.14 What is collision? Explain collision resolution techniques in brief. Step 6: End Example of a Max Heap Adjacency matrix is easy for checking edge existence, while adjacency list is better for memory efficiency.
A collision occurs in hashing when two keys produce the same index in the hash table. Since only one element can Example: Preorder of BST above: 50, 30, 20, 40, 70, 60, 80 Let the elements be: 50, 30, 20, 15, 10, 8, 16
occupy a table slot, a method is needed to resolve collisions. The max heap will look like this: 4.11 What is traversing? Explain BFS traversing on graphs with suitable example.
Collision resolution techniques: 4.4. Write an algorithm for inorder traversal of a binary tree. 50 Traversing a graph means visiting all vertices and edges in a systematic way. Traversal is used to search, analyze, or
1. Chaining: Inorder Traversal: Visit nodes in order: / \ process the graph.
Store all elements that hash to the same index in a linked list. In BST, inorder traversal gives elements in sorted order. 30 20 Breadth First Search (BFS):
Algorithm: InorderTraversal(node) / \ / \ BFS visits all vertices of a graph level by level, starting from a selected source vertex.
2. Open Addressing: Step 1: Start 15 10 8 16 BFS uses a queue to keep track of vertices to visit.
If a collision occurs, find another free slot in the table using a probing method: Step 2: If node is null, return Explanation: Steps of BFS:
o Linear probing: Move sequentially to the next slot until free space is found. Step 3: InorderTraversal([Link]) 50 is the largest, so it becomes the root. 1. Start from the source vertex, mark it visited and enqueue it.
o Quadratic probing: Move using a quadratic function, e.g., (i²) steps ahead. Step 4: Visit node (print [Link]) 30 and 20 are the next largest values, so they become children of 50. 2. While the queue is not empty:
o Double hashing: Use a second hash function to find the next slot. Step 5: InorderTraversal([Link]) 15, 10, 8, 16 fill the next levels while maintaining the complete tree structure and max-heap property.
Example of a Min Heap
o Dequeue a vertex and visit it.
Collision resolution ensures that every key can be stored and retrieved efficiently even when collisions happen. Step 6: End
Let elements be: 5, 12, 20, 30, 25, 40 o Enqueue all its unvisited adjacent vertices and mark them as visited.
Example: Inorder of BST above: 20, 30, 40, 50, 60, 70, 80 Example: Graph with vertices A, B, C, D, E and edges A-B, A-C, B-D, C-E
4.1. What is a tree? Explain the concept of Binary Search Tree with suitable example. Min heap looks like:
5 BFS starting from A:
A tree is a non-linear data structure that consists of nodes connected by edges. It starts with a special node called root 4.5. Write an algorithm for postorder traversal of a binary tree.
Postorder Traversal: Visit nodes in order: / \ Start: Queue = [A], Visited = {A}
and each node may have child nodes. Nodes with no children are called leaf nodes. Trees are used to represent hierarchical
data like file systems, organizational charts, etc. It is used when deleting the tree or calculating space occupied by subtrees. 12 20
A Binary Search Tree (BST) is a type of binary tree in which: Algorithm: PostorderTraversal(node) / \ /
Step 1: Start 30 25 40
1. Each node has at most two children (left and right).
2. The left child contains values less than the parent node. Step 2: If node is null, return Root contains the smallest value 5, and every parent node has a smaller value than its children.
3. The right child contains values greater than the parent node. Step 3: PostorderTraversal([Link])
4. There are no duplicate nodes. Step 4: PostorderTraversal([Link]) 4.9. What is a graph? Explain the following: (1) Graph (2) Multigraphs (3) Weighted graph.
Example: Insert 50, 30, 70, 20, 40, 60, 80 into BST Step 5: Visit node (print [Link]) A graph is a collection of vertices (nodes) and edges (connections) between them. Graphs are used to model networks, BFS order: A, B, C, D, E
50 Step 6: End social connections, transportation systems, etc.
/ \ Example: Postorder of BST above: 20, 40, 30, 60, 80, 70, 50 1. Graph: 4.12 Explain Depth First Search (DFS) algorithm for graph.
30 70 A simple graph consists of vertices connected by edges with no loops or multiple edges between the same pair Depth First Search (DFS):
/ \ / \ 4.7. Given a list of numbers, construct a binary search tree: 14, 10, 17, 12, 8, 11, 20, 12, 18, 25. of vertices. DFS explores a graph by going as deep as possible along each branch before backtracking.
20 40 60 80 Steps to construct BST: Example: Vertices {A, B, C}, Edges {(A,B), (B,C)}
BST allows fast searching, insertion, and deletion because each comparison reduces the search space by half. 1. 2. Multigraphs: DFS uses a stack (can be implemented recursively) to keep track of vertices.
2. A graph that allows multiple edges between the same pair of vertices. Steps of DFS:
3. Example: Vertices {A, B}, multiple edges connecting A and B. 1. Start from a selected vertex, mark it as visited and push it onto stack (or call recursively).
4.2. Explain the representation of binary trees in memory.
4. 3. Weighted Graph: 2. Visit an adjacent unvisited vertex and repeat step 1.
Binary trees can be represented in memory using two methods:
5. A graph in which each edge is assigned a weight or cost representing distance, time, or any value. 3. If a vertex has no unvisited adjacent vertices, backtrack to previous vertex.
1. Linked Representation:
6. Example: Vertices {A, B, C} with edges and weights: (A-B, 5), (B-C, 2), (A-C, 8) 4. Continue until all vertices are visited.
Each node contains:
7. Weighted graphs are useful in shortest path problems, network routing, and cost optimization. Example: Graph with vertices A, B, C, D, E and edges A-B, A-C, B-D, C-E
o Data DFS starting from A:
o Pointer to left child 8.
o Pointer to right child 9. 4.10. Give the memory representation of a graph as an array/adjacency matrix.
Nodes are dynamically allocated. The root node pointer is used to access the tree. 10. A graph can be represented in memory in two common ways:
Example node structure in C-style: Constructed BST diagram: 1. Adjacency Matrix:
struct Node { 14 o It is a 2D array of size V × V, where V is the number of vertices.
int data; / \ o If there is an edge between vertex i and vertex j, then matrix[i][j] = 1 (or weight of edge for weighted
Node* left; 10 17 graph), otherwise 0. ark visited
Node* right; / \ \ o Suitable for dense graphs where number of edges is large.
}; 8 12 20 Example: Graph with vertices A, B, C, D and edges A-B, A-C, B-D DFS order: A, B, D, C, E
/ / \
2. Array Representation: AB CD DFS is useful in pathfinding, cycle detection, and topological sorting.
Suitable for complete binary trees. 11 18 25.
A0 1 1 0
o Root is stored at index 1 (or 0).
o B 1 0 0 1
4.8 What is a heap tree? Explain with example.
o A heap tree is a special type of binary tree that follows two important rules: C 1 0 0 0