MCS-021 Solved Free Assignment 2024-25 Sem 3
Q1. Write a program in C to accepts two polynomials as input and prints the resultant polynomial due to the multiplication of input polynomials.
Ans:- Here is a C program that accepts two polynomials as input and prints the resultant polynomial after multiplying them.
C Program to Multiply Two Polynomials
```c
#include
#define MAX 100
// Structure to store a polynomial term
struct PolynomialTerm {
int coefficient;
int exponent;
};
// Function to read a polynomial
void readPolynomial(struct PolynomialTerm poly[], int *n) {
printf("Enter the number of terms in the polynomial: ");
scanf("%d", n);
for (int i = 0; i < *n; i++) {
printf("Enter coefficient and exponent of term %d: ", i + 1);
scanf("%d %d", &poly[i].coefficient, &poly[i].exponent);
}
}
// Function to multiply two polynomials
int multiplyPolynomials(struct PolynomialTerm poly1[], int n1, struct PolynomialTerm poly2[], int n2, struct PolynomialTerm result[]) {
int k = 0; // Index for result polynomial
// Multiply each term of the first polynomial with each term of the second polynomial
for (int i = 0; i < n1; i++) {
for (int j = 0; j < n2; j++) {
result[k].coefficient = poly1[i].coefficient * poly2[j].coefficient;
result[k].exponent = poly1[i].exponent + poly2[j].exponent;
k++;
}
}
return k; // Return the number of terms in the resultant polynomial
}
// Function to combine terms with the same exponent in the resultant polynomial
int combineLikeTerms(struct PolynomialTerm result[], int n) {
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (result[i].exponent == result[j].exponent) {
result[i].coefficient += result[j].coefficient;
// Shift the remaining terms
for (int k = j; k < n - 1; k++) {
result[k] = result[k + 1];
}
n--;
j--; // Re-check the current position after shifting
}
}
}
return n; // Return the new number of terms after combining
}
// Function to print a polynomial
void printPolynomial(struct PolynomialTerm poly[], int n) {
for (int i = 0; i < n; i++) {
printf("%d(x^%d)", poly[i].coefficient, poly[i].exponent);
if (i != n - 1) {
printf(" + ");
}
}
printf("\n");
}
int main() {
struct PolynomialTerm poly1[MAX], poly2[MAX], result[MAX];
int n1, n2, n3;
// Read first polynomial
printf("Enter the first polynomial:\n");
readPolynomial(poly1, &n1);
// Read second polynomial
printf("Enter the second polynomial:\n");
readPolynomial(poly2, &n2);
// Multiply the polynomials
n3 = multiplyPolynomials(poly1, n1, poly2, n2, result);
// Combine like terms in the resultant polynomial
n3 = combineLikeTerms(result, n3);
// Print the resultant polynomial
printf("Resultant polynomial after multiplication:\n");
printPolynomial(result, n3);
return 0;
}
```
Explanation:
1. **Structure `PolynomialTerm`:** This structure stores a term of the polynomial, which includes the coefficient and exponent.
2. **`readPolynomial()` Function:** Takes input for the number of terms in a polynomial and their coefficients and exponents.
3. **`multiplyPolynomials()` Function:** Multiplies two polynomials term by term and stores the result in the `result` array. Each term from the first polynomial is multiplied by each term from the second.
4. **`combineLikeTerms()` Function:**
Combines terms with the same exponent in the resultant polynomial.
5. **`printPolynomial()` Function:** Prints the polynomial in standard format.
6. **Main Program:** Reads two polynomials, multiplies them, and prints the resultant polynomial.
Example Output:
```
Enter the first polynomial:
Enter the number of terms in the polynomial: 2
Enter coefficient and exponent of term 1: 3 2
Enter coefficient and exponent of term 2: 5 1
Enter the second polynomial:
Enter the number of terms in the polynomial: 2
Enter coefficient and exponent of term 1: 4 1
Enter coefficient and exponent of term 2: 2 0
Resultant polynomial after multiplication:
12(x^3) + 6(x^2) + 20(x^2) + 10(x^1)
```
This program multiplies the two polynomials and displays the result.
Q2. Write a program in ‘C’ to create a single linked list and perform the following operations on it:
(i) Insert a new node at the beginning, in the middle or at the end of the linked list.
(ii) Delete a node from the linked list
(iii) Display the linked list in reverse order
(iv) Sort and display data of the linked list in ascending order.
(v) Count the number of items stored in a single linked list
Ans:- Here’s a C program to create a singly linked list and perform the following operations: insertion, deletion, displaying in reverse order, sorting, and counting nodes.
C Program for Singly Linked List
```c
#include
#include
// Structure of a node
struct Node {
int data;
struct Node* next;
};
// Function to create a new node
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (!newNode) {
printf("Memory error\n");
return NULL;
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// Function to insert a node at the beginning
void insertAtBeginning(struct Node** head, int data) {
struct Node* newNode = createNode(data);
if (newNode != NULL) {
newNode->next = *head;
*head = newNode;
}
}
// Function to insert a node at the end
void insertAtEnd(struct Node** head, int data) {
struct Node* newNode = createNode(data);
if (newNode != NULL) {
if (*head == NULL) {
*head = newNode;
} else {
struct Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
}
}
// Function to insert a node in the middle (after a specific position)
void insertAtMiddle(struct Node** head, int data, int position) {
if (position == 1) {
insertAtBeginning(head, data);
return;
}
struct Node* newNode = createNode(data);
if (newNode != NULL) {
struct Node* temp = *head;
for (int i = 1; i < position - 1 && temp != NULL; i++) {
temp = temp->next;
}
if (temp == NULL) {
printf("Position out of bounds.\n");
} else {
newNode->next = temp->next;
temp->next = newNode;
}
}
}
// Function to delete a node by value
void deleteNode(struct Node** head, int key) {
struct Node* temp = *head;
struct Node* prev = NULL;
// If the head node itself holds the key
if (temp != NULL && temp->data == key) {
*head = temp->next;
free(temp);
return;
}
// Search for the key
while (temp != NULL && temp->data != key) {
prev = temp;
temp = temp->next;
}
// If key was not found
if (temp == NULL) {
printf("Node with value %d not found.\n", key);
return;
}
// Unlink the node and free memory
prev->next = temp->next;
free(temp);
}
// Function to display the list in reverse order (recursively)
void displayReverse(struct Node* head) {
if (head == NULL)
return;
displayReverse(head->next);
printf("%d -> ", head->data);
}
// Function to sort the linked list in ascending order (Bubble Sort)
void sortList(struct Node** head) {
int swapped;
struct Node* ptr1;
struct Node* lptr = NULL;
if (*head == NULL)
return;
do {
swapped = 0;
ptr1 = *head;
while (ptr1->next != lptr) {
if (ptr1->data > ptr1->next->data) {
int temp = ptr1->data;
ptr1->data = ptr1->next->data;
ptr1->next->data = temp;
swapped = 1;
}
ptr1 = ptr1->next;
}
lptr = ptr1;
} while (swapped);
}
// Function to display the linked list
void displayList(struct Node* head) {
while (head != NULL) {
printf("%d -> ", head->data);
head = head->next;
}
printf("NULL\n");
}
// Function to count the number of nodes in the linked list
int countNodes(struct Node* head) {
int count = 0;
while (head != NULL) {
count++;
head = head->next;
}
return count;
}
// Main function
int main() {
struct Node* head = NULL;
int choice, data, position;
while (1) {
printf("\nMenu:\n");
printf("1. Insert at beginning\n");
printf("2. Insert at end\n");
printf("3. Insert at middle\n");
printf("4. Delete node\n");
printf("5. Display list in reverse order\n");
printf("6. Sort and display the list\n");
printf("7. Count the number of nodes\n");
printf("8. Display list\n");
printf("9. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter data to insert at the beginning: ");
scanf("%d", &data);
insertAtBeginning(&head, data);
break;
case 2:
printf("Enter data to insert at the end: ");
scanf("%d", &data);
insertAtEnd(&head, data);
break;
case 3:
printf("Enter data to insert in the middle: ");
scanf("%d", &data);
printf("Enter position to insert the node: ");
scanf("%d", &position);
insertAtMiddle(&head, data, position);
break;
case 4:
printf("Enter the value of the node to delete: ");
scanf("%d", &data);
deleteNode(&head, data);
break;
case 5:
printf("List in reverse order: ");
displayReverse(head);
printf("NULL\n");
break;
case 6:
sortList(&head);
printf("Sorted list: ");
displayList(head);
break;
case 7:
printf("Number of nodes: %d\n", countNodes(head));
break;
case 8:
displayList(head);
break;
case 9:
exit(0);
default:
printf("Invalid choice!\n");
}
}
return 0;
}
```
Explanation:
1. **Node Structure:** The `Node` structure has two fields: `data` (for storing the value) and `next` (for storing the pointer to the next node).
2. **Insertion Functions:**
- `insertAtBeginning`: Inserts a node at the beginning of the linked list.
- `insertAtEnd`: Inserts a node at the end of the linked list.
- `insertAtMiddle`: Inserts a node at a specific position in the list.
3. **Deletion Function:** `deleteNode` deletes a node by value.
4. **Display Functions:**
- `displayReverse`: Displays the linked list in reverse order using recursion.
- `displayList`: Displays the linked list from head to tail.
5. **Sorting Function:** `sortList` uses bubble sort to sort the list in ascending order.
6. **Counting Function:** `countNodes` counts the total number of nodes in the linked list.
7. **Main Menu:** Provides a menu-driven interface for the user to interact with the linked list.
Example Output:
```
Menu:
1. Insert at beginning
2. Insert at end
3. Insert at middle
4. Delete node
5. Display list in reverse order
6. Sort and display the list
7. Count the number of nodes
8. Display list
9. Exit
Enter your choice: 1
Enter data to insert at the beginning: 10
Menu:
...
```
Q3. Write a program in ‘C’ to create a doubly linked list to store integer values and perform the following operations on it:
(i) Insert a new node at the beginning, in the middle or at the end of the linked list.
(ii) Delete a node from the linked list
(iii) Sort and display data of the doubly linked list in ascending order.
(iv) Count the number of items stored in a single linked list
(v) Calculate the sum of all even integer numbers, stored in the doubly linked list
Ans:- Here is a C program that creates a doubly linked list to store integer values and allows you to perform various operations: inserting nodes at different positions, deleting nodes, sorting the list, counting the number of nodes, and calculating the sum of even integers.
C Program for Doubly Linked List
```c
#include
#include
// Structure of a node in the doubly linked list
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
// Function to create a new node
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (!newNode) {
printf("Memory error\n");
return NULL;
}
newNode->data = data;
newNode->next = NULL;
newNode->prev = NULL;
return newNode;
}
// Function to insert a node at the beginning
void insertAtBeginning(struct Node** head, int data) {
struct Node* newNode = createNode(data);
if (newNode != NULL) {
newNode->next = *head;
if (*head != NULL) {
(*head)->prev = newNode;
}
*head = newNode;
}
}
// Function to insert a node at the end
void insertAtEnd(struct Node** head, int data) {
struct Node* newNode = createNode(data);
if (newNode != NULL) {
if (*head == NULL) {
*head = newNode;
} else {
struct Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
newNode->prev = temp;
}
}
}
// Function to insert a node in the middle
void insertAtMiddle(struct Node** head, int data, int position) {
if (position == 1) {
insertAtBeginning(head, data);
return;
}
struct Node* newNode = createNode(data);
if (newNode != NULL) {
struct Node* temp = *head;
for (int i = 1; i < position - 1 && temp != NULL; i++) {
temp = temp->next;
}
if (temp == NULL) {
printf("Position out of bounds.\n");
free(newNode);
} else {
newNode->next = temp->next;
newNode->prev = temp;
if (temp->next != NULL) {
temp->next->prev = newNode;
}
temp->next = newNode;
}
}
}
// Function to delete a node by value
void deleteNode(struct Node** head, int key) {
struct Node* temp = *head;
// If the head node itself holds the key
if (temp != NULL && temp->data == key) {
*head = temp->next;
if (*head != NULL) {
(*head)->prev = NULL;
}
free(temp);
return;
}
// Search for the key
while (temp != NULL && temp->data != key) {
temp = temp->next;
}
// If key was not found
if (temp == NULL) {
printf("Node with value %d not found.\n", key);
return;
}
// Unlink the node
if (temp->next != NULL) {
temp->next->prev = temp->prev;
}
if (temp->prev != NULL) {
temp->prev->next = temp->next;
}
free(temp);
}
// Function to sort the doubly linked list in ascending order (Bubble Sort)
void sortList(struct Node** head) {
if (*head == NULL) return;
int swapped;
struct Node* ptr1;
struct Node* lptr = NULL;
do {
swapped = 0;
ptr1 = *head;
while (ptr1->next != lptr) {
if (ptr1->data > ptr1->next->data) {
// Swap data
int temp = ptr1->data;
ptr1->data = ptr1->next->data;
ptr1->next->data = temp;
swapped = 1;
}
ptr1 = ptr1->next;
}
lptr = ptr1;
} while (swapped);
}
// Function to display the list
void displayList(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
printf("%d <-> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
// Function to count the number of nodes in the doubly linked list
int countNodes(struct Node* head) {
int count = 0;
while (head != NULL) {
count++;
head = head->next;
}
return count;
}
// Function to calculate the sum of all even integers in the list
int sumOfEven(struct Node* head) {
int sum = 0;
while (head != NULL) {
if (head->data % 2 == 0) {
sum += head->data;
}
head = head->next;
}
return sum;
}
// Main function
int main() {
struct Node* head = NULL;
int choice, data, position;
while (1) {
printf("\nMenu:\n");
printf("1. Insert at beginning\n");
printf("2. Insert at end\n");
printf("3. Insert at middle\n");
printf("4. Delete node\n");
printf("5. Sort and display the list\n");
printf("6. Count the number of nodes\n");
printf("7. Calculate the sum of all even integers\n");
printf("8. Display list\n");
printf("9. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter data to insert at the beginning: ");
scanf("%d", &data);
insertAtBeginning(&head, data);
break;
case 2:
printf("Enter data to insert at the end: ");
scanf("%d", &data);
insertAtEnd(&head, data);
break;
case 3:
printf("Enter data to insert in the middle: ");
scanf("%d", &data);
printf("Enter position to insert the node: ");
scanf("%d", &position);
insertAtMiddle(&head, data, position);
break;
case 4:
printf("Enter the value of the node to delete: ");
scanf("%d", &data);
deleteNode(&head, data);
break;
case 5:
sortList(&head);
printf("Sorted list: ");
displayList(head);
break;
case 6:
printf("Number of nodes: %d\n", countNodes(head));
break;
case 7:
printf("Sum of all even integers: %d\n", sumOfEven(head));
break;
case 8:
displayList(head);
break;
case 9:
exit(0);
default:
printf("Invalid choice!\n");
}
}
return 0;
}
```
Explanation:
1. **Node Structure:** The `Node` structure has three fields: `data` (for storing the integer value), `next` (for storing the pointer to the next node), and `prev` (for storing the pointer to the previous node).
2. **Insertion Functions:**
- `insertAtBeginning`: Inserts a node at the beginning of the doubly linked list.
- `insertAtEnd`: Inserts a node at the end of the doubly linked list.
- `insertAtMiddle`: Inserts a node at a specific position in the list.
3. **Deletion Function:** `deleteNode` deletes a node by its value.
4. **Sorting Function:** `sortList` sorts the doubly linked list in ascending order using the bubble sort algorithm.
5. **Display Function:** `displayList` displays the doubly linked list from head to tail.
6. **Counting Function:** `countNodes` counts the total number of nodes in the doubly linked list.
7. **Sum Function:** `sumOfEven` calculates the sum of all even integers in the list.
8. **Main Menu:** Provides a menu-driven interface for user interaction with the doubly linked list.
Example Output:
```
Menu:
1. Insert at beginning
2. Insert at end
3. Insert at middle
4. Delete node
5. Sort and display the list
6. Count the number of nodes
7. Calculate the sum of all even integers
8. Display list
9. Exit
Enter your choice: 1
Enter data to insert at the beginning: 10
Menu:
...
```
You can continue to interact with the program by entering choices as prompted. This program provides a comprehensive implementation of a doubly linked list with various functionalities.
Q4. What is a Dequeue? Write algorithm to perform insert and delete operations in a Dequeue
Ans:- What is a Dequeue?
A **Dequeue** (Double-ended Queue) is a linear data structure that allows insertion and deletion of elements from both ends: the front and the rear. It can be viewed as a combination of both a queue and a stack, enabling elements to be added or removed from either end.
Characteristics of a Dequeue:
- It supports both FIFO (First In First Out) and LIFO (Last In First Out) operations.
- Elements can be added or removed from the front or the rear.
Operations on a Dequeue:
1. **Insert**: Add an element to either the front or the rear.
2. **Delete**: Remove an element from either the front or the rear.
3. **Get Front**: Retrieve the front element without removing it.
4. **Get Rear**: Retrieve the rear element without removing it.
Algorithm for Insert and Delete Operations in a Dequeue
1. Insert Operation
You can insert elements either at the front or the rear. Here’s how you can do it:
- **Insert at the Front**:
1. Check if the dequeue is full (if implemented using a fixed-size array).
2. Create a new node.
3. Set the new node's next pointer to the current front.
4. Update the previous front's previous pointer to the new node.
5. Update the front pointer to the new node.
6. If the dequeue was empty, also update the rear pointer to the new node.
- **Insert at the Rear**:
1. Check if the dequeue is full.
2. Create a new node.
3. Set the new node's previous pointer to the current rear.
4. Update the current rear's next pointer to the new node.
5. Update the rear pointer to the new node.
6. If the dequeue was empty, also update the front pointer to the new node.
2. Delete Operation
You can delete elements either from the front or the rear. Here’s how:
- **Delete from the Front**:
1. Check if the dequeue is empty.
2. Store the current front node.
3. Update the front pointer to the next node.
4. Update the new front's previous pointer to NULL.
5. Free the memory of the old front node.
6. If the dequeue is now empty, update the rear pointer to NULL.
- **Delete from the Rear**:
1. Check if the dequeue is empty.
2. Store the current rear node.
3. Update the rear pointer to the previous node.
4. Update the new rear's next pointer to NULL.
5. Free the memory of the old rear node.
6. If the dequeue is now empty, update the front pointer to NULL.
C Code Example
Here's an example implementation of a dequeue using a doubly linked list in C:
```c
#include
#include
// Structure for a deque node
struct DequeNode {
int data;
struct DequeNode* next;
struct DequeNode* prev;
};
// Structure for the deque
struct Deque {
struct DequeNode* front;
struct DequeNode* rear;
};
// Function to create a new node
struct DequeNode* createNode(int data) {
struct DequeNode* newNode = (struct DequeNode*)malloc(sizeof(struct DequeNode));
newNode->data = data;
newNode->next = NULL;
newNode->prev = NULL;
return newNode;
}
// Function to create a new deque
struct Deque* createDeque() {
struct Deque* dq = (struct Deque*)malloc(sizeof(struct Deque));
dq->front = NULL;
dq->rear = NULL;
return dq;
}
// Insert at the front
void insertFront(struct Deque* dq, int data) {
struct DequeNode* newNode = createNode(data);
if (dq->front == NULL) { // If the deque is empty
dq->front = newNode;
dq->rear = newNode;
} else {
newNode->next = dq->front;
dq->front->prev = newNode;
dq->front = newNode;
}
}
// Insert at the rear
void insertRear(struct Deque* dq, int data) {
struct DequeNode* newNode = createNode(data);
if (dq->rear == NULL) { // If the deque is empty
dq->front = newNode;
dq->rear = newNode;
} else {
newNode->prev = dq->rear;
dq->rear->next = newNode;
dq->rear = newNode;
}
}
// Delete from the front
void deleteFront(struct Deque* dq) {
if (dq->front == NULL) {
printf("Deque is empty, cannot delete from front.\n");
return;
}
struct DequeNode* temp = dq->front;
dq->front = dq->front->next;
if (dq->front != NULL) {
dq->front->prev = NULL;
} else { // Deque became empty
dq->rear = NULL;
}
free(temp);
}
// Delete from the rear
void deleteRear(struct Deque* dq) {
if (dq->rear == NULL) {
printf("Deque is empty, cannot delete from rear.\n");
return;
}
struct DequeNode* temp = dq->rear;
dq->rear = dq->rear->prev;
if (dq->rear != NULL) {
dq->rear->next = NULL;
} else { // Deque became empty
dq->front = NULL;
}
free(temp);
}
// Function to display the deque from front to rear
void displayDeque(struct Deque* dq) {
struct DequeNode* temp = dq->front;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
// Main function
int main() {
struct Deque* dq = createDeque();
insertRear(dq, 10);
insertRear(dq, 20);
insertFront(dq, 5);
printf("Deque after insertions: ");
displayDeque(dq);
deleteFront(dq);
printf("Deque after deleting from front: ");
displayDeque(dq);
deleteRear(dq);
printf("Deque after deleting from rear: ");
displayDeque(dq);
return 0;
}
```
Explanation of the Code:
- The code defines a **DequeNode** structure representing each node in the deque, containing data and pointers to the next and previous nodes.
- The **Deque** structure maintains pointers to both the front and rear of the deque.
- Functions are provided to insert nodes at the front or rear, delete nodes from the front or rear, and display the contents of the deque.
- The `main` function demonstrates inserting and deleting elements from the deque.
Example Output:
```
Deque after insertions: 5 10 20
Deque after deleting from front: 10 20
Deque after deleting from rear: 10
```
This implementation provides a basic understanding of how a dequeue can be implemented using a doubly linked list in C.
Q5. Draw the binary tree for which the traversal sequences are given as follows:
(i) Pre order: A B D E F C G H I J K
In order: B E D F A C I H K J G
(ii) Post order: I J H D K E C L M G F B A
In order: I H J D C K E A F L G M B
Ans:- To construct binary trees from the given traversal sequences, we can use the properties of tree traversals. The process typically involves using the pre-order or post-order sequence to determine the root nodes and then using the in-order sequence to determine the structure of the tree.
(i) Pre-order: A B D E F C G H I J K
In-order: B E D F A C I H K J G
**Steps to Construct the Tree:**
1. **Identify the Root**: The first element in the pre-order sequence is always the root. Here, the root is **A**.
2. **Split the In-order Sequence**: Locate the root in the in-order sequence to divide it into left and right subtrees.
- In-order: **B E D F** | **A** | **C I H K J G**
- Left Subtree (In-order): **B E D F**
- Right Subtree (In-order): **C I H K J G**
3. **Construct Left Subtree**:
- From the remaining pre-order sequence **B D E F**, the next root is **B**.
- In-order sequence for B: **B** | **E D F**
- **B** has no left child (since B is alone in the in-order), and its right subtree is **D E F**.
4. **Continue with the right subtree** for **D**:
- The next pre-order elements are **D E F**. Thus, root is **D**.
- Split again in in-order: **E** | **D** (root) | **F**.
5. **Construct Right Subtree of A**:
- Remaining pre-order is **C G H I J K**.
- Root is **C** and the in-order splits into left (none) and right subtree: **I H K J G**.
Following these steps, we build the complete tree:
Constructed Tree:
```
A
/ \
B C
\ \
D G
/ \ \
E F J
/ \
K H
/
I
```
(ii) Post-order: I J H D K E C L M G F B A
In-order: I H J D C K E A F L G M B
**Steps to Construct the Tree:**
1. **Identify the Root**: The last element in the post-order sequence is the root. Here, the root is **A**.
2. **Split the In-order Sequence**: Locate the root in the in-order sequence to divide it into left and right subtrees.
- In-order: **I H J D C K E** | **A** | **F L G M B**
- Left Subtree (In-order): **I H J D C K E**
- Right Subtree (In-order): **F L G M B**
3. **Construct Left Subtree**:
- From the post-order sequence **I J H D K E C**, the next root is **E**.
- In-order sequence: **I H J D C** | **E** | **A**.
4. **Continue with Left Subtree**:
- From remaining post-order, root is **C** (for **I H J D C**).
- Split it as **I H J D** (left subtree) and the root **C**.
5. **Build Remaining Subtrees**: Repeat for remaining elements to get the full structure.
Following these steps, we build the complete tree:
Constructed Tree:
```
A
/ \
E B
/ \
C F
/ \ \
D K G
/ \ \
I J L
\
M
```
Summary:
Both trees were constructed using pre-order and in-order or post-order and in-order traversal sequences. The split in in-order helps to identify the left and right children effectively, allowing for a proper reconstruction of the binary tree structure.
Q6. Write a program in ‘C’ to implement a binary search tree (BST). Traverse and display the binary search tree in the Inorder, Preorder and Post order form.
Ans:- Here’s a complete C program to implement a Binary Search Tree (BST) and traverse it in Inorder, Preorder, and Postorder forms.
C Program for Binary Search Tree (BST)
```c
#include
#include
// Structure for a BST node
struct Node {
int data;
struct Node* left;
struct Node* right;
};
// Function to create a new node
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// Function to insert a new node in the BST
struct Node* insert(struct Node* root, int data) {
if (root == NULL) {
return createNode(data);
}
if (data < root->data) {
root->left = insert(root->left, data);
} else if (data > root->data) {
root->right = insert(root->right, data);
}
return root;
}
// Function for Inorder traversal
void inorder(struct Node* root) {
if (root != NULL) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
// Function for Preorder traversal
void preorder(struct Node* root) {
if (root != NULL) {
printf("%d ", root->data);
preorder(root->left);
preorder(root->right);
}
}
// Function for Postorder traversal
void postorder(struct Node* root) {
if (root != NULL) {
postorder(root->left);
postorder(root->right);
printf("%d ", root->data);
}
}
// Main function
int main() {
struct Node* root = NULL;
int n, data;
printf("Enter number of elements to insert in the BST: ");
scanf("%d", &n);
printf("Enter the elements:\n");
for (int i = 0; i < n; i++) {
scanf("%d", &data);
root = insert(root, data);
}
printf("\nInorder Traversal: ");
inorder(root);
printf("\nPreorder Traversal: ");
preorder(root);
printf("\nPostorder Traversal: ");
postorder(root);
printf("\n");
return 0;
}
```
Explanation of the Code:
1. **Node Structure**: The `Node` structure contains three fields: `data`, `left`, and `right`.
2. **Creating a Node**: The `createNode` function allocates memory for a new node and initializes its data.
3. **Insertion**: The `insert` function adds a new node to the BST according to the properties of the BST:
- If the new data is less than the current node, it goes to the left.
- If the new data is greater, it goes to the right.
4. **Traversals**:
- **Inorder**: Visits the left subtree, the root, and then the right subtree (sorted order).
- **Preorder**: Visits the root first, then the left and right subtrees.
- **Postorder**: Visits the left and right subtrees first, and then the root.
5. **Main Function**: The user is prompted to enter the number of elements and the elements themselves. The program then inserts the elements into the BST and displays the three types of traversals.
Example Output:
```
Enter number of elements to insert in the BST: 5 Enter the elements:
40
20
60
10
30
Inorder Traversal: 10 20 30 40 60
Preorder Traversal: 40 20 10 30 60
Postorder Traversal: 10 30 20 60 40
```
This program provides a complete implementation of a Binary Search Tree in C, along with methods for inserting nodes and traversing the tree in various orders.
Q7. Define AVL tree. Create an AVL tree for the following list of data if the data are inserted in the order in an empty AVL tree.
12, 5, 15, 20, 35, 8, 2, 40, 14, 24, 27, 45, 50, 3, 4 Further delete 2, 4, 5 and 12 from the above AVL tree.
Ans:- AVL Tree Definition:
An AVL tree is a self-balancing binary search tree where the difference in heights between the left and right subtrees (the balance factor) is at most 1 for every node. The balance factor is defined as:
\[ \text{Balance Factor} = \text{Height of Left Subtree} - \text{Height of Right Subtree} \]
When the balance factor is not in the range of -1 to 1 after an insertion or deletion, the tree is rebalanced using rotations (single or double).
Step-by-Step Construction of the AVL Tree
**Insertion Sequence:** 12, 5, 15, 20, 35, 8, 2, 40, 14, 24, 27, 45, 50, 3, 4
1. **Insert 12:**
```
12
```
2. **Insert 5:**
```
12
/
5
```
3. **Insert 15:**
```
12
/ \
5 15
```
4. **Insert 20:**
```
12
/ \
5 15
\
20
```
*Balance Factor of 12 is -1, no rotations needed.*
5. **Insert 35:**
```
12
/ \
5 15
\
20
\
35
```
*Balance Factor of 15 is -2. Perform Left Rotation on 15.*
```
12
/ \
5 20
/ \
15 35
```
6. **Insert 8:**
```
12
/ \
5 20
\ / \
8 15 35
```
7. **Insert 2:**
```
12
/ \
5 20
/ \ / \
2 8 15 35
```
8. **Insert 40:**
```
12
/ \
5 20
/ \ / \
2 8 15 35
\
40
```
*Balance Factor of 20 is -1, no rotations needed.*
9. **Insert 14:**
```
12
/ \
5 20
/ \ / \
2 8 15 35
/ \
14 40
```
10. **Insert 24:**
```
12
/ \
5 20
/ \ / \
2 8 15 35
/ \
14 40
/
24
```
11. **Insert 27:**
```
12
/ \
5 20
/ \ / \
2 8 15 35
/ \
14 40
/
24
\
27
```
*Balance Factor of 35 is -2. Perform Left Rotation on 35.*
```
12
/ \
5 20
/ \ / \
2 8 15 27
/ \
24 40
```
12. **Insert 45:**
```
12
/ \
5 20
/ \ / \
2 8 15 27
/ \
24 40
\
45
```
13. **Insert 50:**
```
12
/ \
5 20
/ \ / \
2 8 15 27
/ \
24 40
\
45
\
50
```
*Balance Factor of 40 is -2. Perform Left Rotation on 40.*
```
12
/ \
5 20
/ \ / \
2 8 15 27
/ \
24 45
/ \
40 50
```
14. **Insert 3:**
```
12
/ \
5 20
/ \ / \
2 8 15 27
/ / \
3 24 45
/ \
40 50
```
15. **Insert 4:**
```
12
/ \
5 20
/ \ / \
2 8 15 27
/ \ / \
3 4 24 45
/ \
40 50
```
Deletion of Nodes
**Delete 2:**
1. Find node 2, which has a child (3).
2. Replace 2 with 3.
3. Rebalance if needed.
```
12
/ \
5 20
/ \ / \
3 8 15 27
/ / \
4 24 45
/ \
40 50
```
**Delete 4:**
1. Find node 4, which has no children.
2. Remove node 4.
3. Rebalance if needed.
```
12
/ \
5 20
/ \ / \
3 8 15 27
/ \
24 45
/ \
40 50
```
**Delete 5:**
1. Find node 5, which has children (3 and 8).
2. Replace 5 with the in-order successor (8).
3. Rebalance if needed.
```
12
/ \
8 20
/ / \
3 15 27
/ \
24 45
/ \
40 50
```
**Delete 12:**
1. Find node 12, which has children (8 and 20).
2. Replace 12 with the in-order successor (15).
3. Rebalance if needed.
```
15
/ \
8 20
/ / \
3 24 27
/ \
40 45
\
50
```
Final AVL Tree
After inserting all elements and performing the deletions, the final AVL tree structure looks like this:
```
15
/ \
8 20
/ / \
3 24 27
/ \
40 45
\
50
```
This tree maintains the AVL property, where the balance factor of each node is in the range of -1 to 1.
Q8. Define a B-tree and its properties. Create a B-tree of order-5, if the data items are inserted into an empty B-tree in the following sequence:12, 5, 15, 20, 60, 45, 35, 40, 25, 8, 7, 55, 50, 66, 65, 80
Further, delete the items 5, 12, 8, and 20 from the B-tree.
Ans:- B-Tree Definition:
A B-tree is a balanced tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time. It is commonly used in databases and filesystems. B-trees are characterized by their multi-way branching, meaning each node can have multiple children.
Properties of B-Trees:
1. **Order (m)**: The maximum number of children (m) for each node in the tree.
2. **Node Capacity**:
- Each internal node can have a maximum of \( m - 1 \) keys and \( m \) children.
- Each internal node must have at least \( \lceil m/2 \rceil - 1 \) keys (except for the root, which can have fewer).
3. **Sorted Keys**: Keys within a node are kept in sorted order.
4. **Leaf Nodes**: All leaf nodes are at the same level, ensuring the tree remains balanced.
5. **Searching**: The B-tree structure allows searching for keys in logarithmic time.
Creating a B-Tree of Order 5
**Insertion Sequence:** 12, 5, 15, 20, 60, 45, 35, 40, 25, 8, 7, 55, 50, 66, 65, 80
1. **Insert 12:**
```
[12]
```
2. **Insert 5:**
```
[5, 12]
```
3. **Insert 15:**
```
[5, 12, 15]
```
4. **Insert 20:**
```
[5, 12, 15, 20]
```
5. **Insert 60:** (Now exceeds order, so split the node)
```
[12]
/ \
[5] [15, 20, 60]
```
6. **Insert 45:**
```
[12]
/ \
[5] [15, 20, 45, 60]
```
7. **Insert 35:**
```
[12]
/ \
[5] [15, 20, 35, 45, 60]
```
8. **Insert 40:** (Now exceeds order, so split the right node)
```
[12, 35]
/ | \
[5] [15, 20] [40, 45, 60]
```
9. **Insert 25:**
```
[12, 35]
/ | \
[5] [15, 20, 25] [40, 45, 60]
```
10. **Insert 8:**
```
[12, 35]
/ | \
[5, 8] [15, 20, 25] [40, 45, 60]
```
11. **Insert 7:**
```
[12, 35]
/ | \
[5, 7, 8] [15, 20, 25] [40, 45, 60]
```
12. **Insert 55:**
```
[12, 35]
/ | \
[5, 7, 8] [15, 20, 25] [40, 45, 55, 60]
```
13. **Insert 50:**
```
[12, 35]
/ | \
[5, 7, 8] [15, 20, 25] [40, 45, 50, 55, 60]
```
14. **Insert 66:**
```
[12, 35]
/ | \
[5, 7, 8] [15, 20, 25] [40, 45, 50, 55, 60, 66]
```
15. **Insert 65:** (Now exceeds order, so split the right node)
```
[12, 35, 55]
/ | | \
[5, 7, 8] [15, 20, 25] [40, 45, 50] [60, 65, 66]
```
16. **Insert 80:**
```
[12, 35, 55]
/ | | \
[5, 7, 8] [15, 20, 25] [40, 45, 50] [60, 65, 66, 80]
```
Final B-Tree Structure After Insertion
```
[12, 35, 55]
/ | | \
[5, 7, 8] [15, 20, 25] [40, 45, 50] [60, 65, 66, 80]
```
Deleting Items: 5, 12, 8, and 20
1. **Delete 5:**
```
[12, 35, 55]
/ | | \
[7, 8] [15, 20, 25] [40, 45, 50] [60, 65, 66, 80]
```
2. **Delete 12:**
- Replace 12 with 15 (in-order successor).
```
[15, 35, 55]
/ | | \
[7, 8] [20, 25] [40, 45, 50] [60, 65, 66, 80]
```
3. **Delete 8:**
```
[15, 35, 55]
/ | | \
[7] [20, 25] [40, 45, 50] [60, 65, 66, 80]
```
4. **Delete 20:**
```
[15, 35, 55]
/ | | \
[7] [25] [40, 45, 50] [60, 65, 66, 80]
```
Final B-Tree Structure After Deletion
```
[15, 35, 55]
/ | | \
[7] [25] [40, 45, 50] [60, 65, 66, 80]
```
This structure maintains the properties of a B-tree, with all leaf nodes at the same level and the order of the tree properly adhered to.
Q9. Apply Dijkstra’s algorithm to find the shortest path from the vertex ‘S’ to all other vertices for the following graph:
To apply Dijkstra's algorithm, we need to follow a specific set of steps. Since you haven’t provided the graph, I’ll outline the process generally. If you can share the graph data (vertices and edges with weights), I can provide a specific example.
Steps for Dijkstra's Algorithm:
1. **Initialization**:
- Set the initial distance from the source vertex \( S \) to itself as 0 and to all other vertices as infinity.
- Mark all vertices as unvisited.
- Set the source vertex as the current vertex.
2. **Create a Priority Queue**:
- Use a priority queue to keep track of the vertices with their current distances.
3. **Process the Current Vertex**:
- For the current vertex, consider all its unvisited neighbors.
- For each neighbor, calculate the tentative distance from the source vertex to the neighbor through the current vertex.
- If the calculated distance is less than the currently known distance, update the shortest distance to that neighbor.
4. **Mark the Current Vertex as Visited**:
- Once all neighbors of the current vertex are processed, mark the current vertex as visited.
5. **Select the Next Current Vertex**:
- From the unvisited vertices, select the vertex with the smallest tentative distance and set it as the new current vertex.
6. **Repeat**:
- Repeat steps 3-5 until all vertices have been visited or the smallest tentative distance among the unvisited vertices is infinity (indicating that the remaining vertices are unreachable).
Example
Let's assume you have a graph as follows (you can adjust the graph with your own values):
```
(2)
A -------- B
| /|
(1)| / |(3)
| / |
|(4) / |(1)
| / |
C -------- D
(2)
```
Graph Representation:
- Vertices: A, B, C, D
- Edges with weights:
- A-B: 2
- A-C: 1
- B-D: 3
- C-D: 4
- C-B: 1
Steps for Dijkstra's Algorithm from Vertex S:
1. **Initialization**:
- Distance:
- A: 0 (source)
- B: ∞
- C: ∞
- D: ∞
- Visited: { }
2. **Current Vertex: A**:
- Neighbors: B and C
- Tentative distances:
- B: min(∞, 0 + 2) = 2
- C: min(∞, 0 + 1) = 1
- Update distances:
- A: 0, B: 2, C: 1, D: ∞
- Mark A as visited: Visited: {A}
3. **Select Next Vertex (C)**:
- Current distances: A: 0, B: 2, C: 1, D: ∞
- Neighbors of C: B and D
- Tentative distances:
- B: min(2, 1 + 1) = 2
- D: min(∞, 1 + 4) = 5
- Update distances:
- A: 0, B: 2, C: 1, D: 5
- Mark C as visited: Visited: {A, C}
4. **Select Next Vertex (B)**:
- Current distances: A: 0, B: 2, C: 1, D: 5
- Neighbors of B: D
- Tentative distances:
- D: min(5, 2 + 3) = 5
- No update required for D.
- Mark B as visited: Visited: {A, B, C}
5. **Select Next Vertex (D)**:
- All vertices are visited: Visited: {A, B, C, D}
Result:
The shortest distances from vertex A are:
- A to A: 0
- A to B: 2
- A to C: 1
- A to D: 5
Q10. Apply Prim’s Algorithm to find the minimum spanning tree for the following graph.
.jpeg)
Ans:- To apply Prim's Algorithm to find the Minimum Spanning Tree (MST) for a graph, we typically follow these steps:
1. **Select an arbitrary starting vertex**.
2. **Initialize an empty tree** to store the edges of the MST.
3. **Select the edge with the smallest weight** that connects a vertex in the MST to a vertex outside the MST.
4. **Add this edge and the new vertex** to the MST.
5. **Repeat steps 3-4** until all vertices are included in the MST.
Example Graph
Since you didn’t provide a specific graph, I will illustrate the process with a sample graph. Here’s a weighted undirected graph:
```
(2)
A-------B
| \ |
(3)| \(1) |
| \ |
C-------D
(4)
```
Graph Representation
- Vertices: A, B, C, D
- Edges with weights:
- A-B: 2
- A-C: 3
- A-D: 1
- B-D: 1
- C-D: 4
Steps for Prim's Algorithm
1. **Start from an arbitrary vertex** (let’s start with vertex A).
- MST: {}
- Selected vertices: {A}
2. **Select the minimum edge from A**:
- Possible edges: (A-B: 2), (A-C: 3), (A-D: 1)
- Select edge (A-D: 1).
- Update MST: { (A, D) }
- Selected vertices: {A, D}
3. **Select the next minimum edge connecting A or D to an unselected vertex**:
- Possible edges: (A-B: 2), (A-C: 3), (D-B: 1), (D-C: 4)
- Select edge (D-B: 1).
- Update MST: { (A, D), (D, B) }
- Selected vertices: {A, D, B}
4. **Select the next minimum edge connecting A, B, or D to an unselected vertex**:
- Possible edges: (A-C: 3), (B-D: 1), (D-C: 4)
- Select edge (A-B: 2).
- Update MST: { (A, D), (D, B), (A, B) }
- Selected vertices: {A, B, D, C}
5. **All vertices are now included in the MST**.
Final Minimum Spanning Tree
The Minimum Spanning Tree for the example graph consists of the edges:
- (A, D): 1
- (D, B): 1
- (A, B): 2
Resulting MST
The Minimum Spanning Tree contains the edges:
- A - D (Weight: 1)
- D - B (Weight: 1)
- A - C (Weight: 3)
Q11. Apply Insertion and Selection sorting algorithms to sort the following list of items. So, all theintermediate steps. Also, analyze their best, worst and average case time complexity.
12, 5, 2, 15, 25, 30, 45, 8, 17, 50, 3, 7
Ans:- Sure! Let's apply the Insertion Sort and Selection Sort algorithms to the list of items you provided:
**List**: 12, 5, 2, 15, 25, 30, 45, 8, 17, 50, 3, 7
Insertion Sort
**Insertion Sort** works by building a sorted section of the list one element at a time. The algorithm iterates through the list, taking one element and inserting it into the correct position in the already sorted part.
Steps of Insertion Sort:
**Initial List**: [12, 5, 2, 15, 25, 30, 45, 8, 17, 50, 3, 7]
1. **Step 1** (key = 5): [5, 12, 2, 15, 25, 30, 45, 8, 17, 50, 3, 7]
- Insert 5 before 12.
2. **Step 2** (key = 2): [2, 5, 12, 15, 25, 30, 45, 8, 17, 50, 3, 7]
- Insert 2 before 5.
3. **Step 3** (key = 15): [2, 5, 12, 15, 25, 30, 45, 8, 17, 50, 3, 7]
- 15 is already in the correct position.
4. **Step 4** (key = 25): [2, 5, 12, 15, 25, 30, 45, 8, 17, 50, 3, 7]
- 25 is already in the correct position.
5. **Step 5** (key = 30): [2, 5, 12, 15, 25, 30, 45, 8, 17, 50, 3, 7]
- 30 is already in the correct position.
6. **Step 6** (key = 45): [2, 5, 12, 15, 25, 30, 45, 8, 17, 50, 3, 7]
- 45 is already in the correct position.
7. **Step 7** (key = 8): [2, 5, 8, 12, 15, 25, 30, 45, 17, 50, 3, 7]
- Insert 8 before 12.
8. **Step 8** (key = 17): [2, 5, 8, 12, 15, 17, 25, 30, 45, 50, 3, 7]
- Insert 17 before 25.
9. **Step 9** (key = 50): [2, 5, 8, 12, 15, 17, 25, 30, 45, 50, 3, 7]
- 50 is already in the correct position.
10. **Step 10** (key = 3): [2, 3, 5, 8, 12, 15, 17, 25, 30, 45, 50, 7]
- Insert 3 before 5.
11. **Step 11** (key = 7): [2, 3, 5, 7, 8, 12, 15, 17, 25, 30, 45, 50]
- Insert 7 before 8.
**Final Sorted List**: [2, 3, 5, 7, 8, 12, 15, 17, 25, 30, 45, 50]
Selection Sort
**Selection Sort** works by repeatedly selecting the smallest (or largest) element from the unsorted part and moving it to the end of the sorted part.
Steps of Selection Sort:
**Initial List**: [12, 5, 2, 15, 25, 30, 45, 8, 17, 50, 3, 7]
1. **Step 1**: Find the minimum (2) and swap with the first element:
- Result: [2, 5, 12, 15, 25, 30, 45, 8, 17, 50, 3, 7]
2. **Step 2**: Find the minimum (3) and swap with the second element:
- Result: [2, 3, 12, 15, 25, 30, 45, 8, 17, 50, 5, 7]
3. **Step 3**: Find the minimum (5) and swap with the third element:
- Result: [2, 3, 5, 15, 25, 30, 45, 8, 17, 50, 12, 7]
4. **Step 4**: Find the minimum (7) and swap with the fourth element:
- Result: [2, 3, 5, 7, 25, 30, 45, 8, 17, 50, 12, 15]
5. **Step 5**: Find the minimum (8) and swap with the fifth element:
- Result: [2, 3, 5, 7, 8, 30, 45, 25, 17, 50, 12, 15]
6. **Step 6**: Find the minimum (12) and swap with the sixth element:
- Result: [2, 3, 5, 7, 8, 12, 45, 25, 17, 50, 30, 15]
7. **Step 7**: Find the minimum (15) and swap with the seventh element:
- Result: [2, 3, 5, 7, 8, 12, 15, 25, 17, 50, 30, 45]
8. **Step 8**: Find the minimum (17) and swap with the eighth element:
- Result: [2, 3, 5, 7, 8, 12, 15, 17, 25, 50, 30, 45]
9. **Step 9**: Find the minimum (25) and swap with the ninth element:
- Result: [2, 3, 5, 7, 8, 12, 15, 17, 25, 30, 50, 45]
10. **Step 10**: Finally, the last two elements are already in order:
- Result: [2, 3, 5, 7, 8, 12, 15, 17, 25, 30, 45, 50]
**Final Sorted List**: [2, 3, 5, 7, 8, 12, 15, 17, 25, 30, 45, 50]
Time Complexity Analysis
Insertion Sort
- **Best Case**: O(n) — This occurs when the array is already sorted, and each new element is greater than all previously sorted elements.
- **Average Case**: O(n²) — This occurs for random order inputs where comparisons and shifts are required for each element.
- **Worst Case**: O(n²) — This occurs when the array is sorted in reverse order, requiring maximum shifts.
Selection Sort
- **Best Case**: O(n²) — Even in the best case, Selection Sort always compares each element with every other element.
- **Average Case**: O(n²) — The same reasoning applies, as it will always go through the entire list.
- **Worst Case**: O(n²) — Selection Sort performs the same number of comparisons regardless of input, as it always looks for the minimum element in the unsorted part.
Summary
- **Insertion Sort**: Better for small or partially sorted arrays. It has a best case of O(n) and is adaptive.
- **Selection Sort**: Simpler but inefficient for large lists due to O(n²) time complexity in all cases. It does not adapt to the initial order of elements.
If you have any specific questions or need further examples, feel free to ask!
Q13. Write a program in ‘C’ language for 2-way merge sort.
Ans:- Here's a C program that implements the 2-way Merge Sort algorithm. Merge Sort is a divide-and-conquer algorithm that splits the input array into two halves, recursively sorts both halves, and then merges the sorted halves back together.
C Program for 2-Way Merge Sort
```c
#include
// Function to merge two halves
void merge(int arr[], int left, int mid, int right) {
int i, j, k;
int n1 = mid - left + 1; // Size of left subarray
int n2 = right - mid; // Size of right subarray
// Create temporary arrays
int L[n1], R[n2];
// Copy data to temporary arrays L[] and R[]
for (i = 0; i < n1; i++)
L[i] = arr[left + i];
for (j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
// Merge the temporary arrays back into arr[left..right]
i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = left; // Initial index of merged subarray
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// Copy the remaining elements of L[], if there are any
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// Copy the remaining elements of R[], if there are any
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
// Function to implement merge sort
void mergeSort(int arr[], int left, int right) {
if (left < right) {
// Find the middle point
int mid = left + (right - left) / 2;
// Sort first and second halves
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
// Merge the sorted halves
merge(arr, left, mid, right);
}
}
// Function to print the array
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
// Main function
int main() {
int arr[] = {12, 5, 2, 15, 25, 30, 45, 8, 17, 50, 3, 7};
int arrSize = sizeof(arr) / sizeof(arr[0]);
printf("Original array: \n");
printArray(arr, arrSize);
mergeSort(arr, 0, arrSize - 1);
printf("\nSorted array: \n");
printArray(arr, arrSize);
return 0;
}
```
Explanation of the Program
1. **Merge Function**:
- This function merges two halves of the array. It takes the original array and the indices of the left, middle, and right parts.
- It creates two temporary arrays to hold the left and right halves and merges them back into the original array.
2. **MergeSort Function**:
- This is the recursive function that divides the array into halves and calls itself for each half until the base case is reached (an array of size 1).
3. **PrintArray Function**:
- A utility function to print the array.
4. **Main Function**:
- Initializes the array to be sorted, prints the original array, calls the `mergeSort` function, and then prints the sorted array.
How to Compile and Run
1. Copy the code into a text file and save it as `merge_sort.c`.
2. Open a terminal (or command prompt) and navigate to the directory where you saved the file.
3. Compile the program using the following command:
```bash
gcc merge_sort.c -o merge_sort
```
4. Run the program:
```bash
./merge_sort
```
This will display the original unsorted array followed by the sorted array. If you have any further questions or need modifications, feel free to ask!
Q14. What is Splay tree? Explain the Zig zag and Zag zig rotations in Splay tree with the help of a suitable example.
Ans:- A **Splay Tree** is a type of self-adjusting binary search tree (BST) that moves frequently accessed elements closer to the root of the tree. This is achieved through a process called "splaying." When an element is accessed, it is brought to the root of the tree using a series of rotations, which can help optimize future access times for that element or its neighbors.
Key Operations of a Splay Tree
1. **Splaying**: The main operation that brings a node to the root using rotations.
2. **Rotations**: The basic operations used to restructure the tree. There are two types of rotations:
- **Zig Rotation**: Used when the accessed node is a child of the root.
- **Zig-Zag and Zag-Zig Rotations**:
L Used when the accessed node is a grandchild of the root, requiring two rotations.
Rotations in Splay Tree
1. Zig Rotation
This occurs when the accessed node is a child of the root (i.e., it is one level down).
- **Example**:
- Initial Tree:
```
20
/
10
```
- Accessing Node `10`:
- Perform a Zig rotation, which makes `10` the new root.
- After Zig Rotation:
```
10
\
20
```
2. Zig-Zag Rotation
This occurs when the accessed node is a right child of its parent, and the parent is a left child of its grandparent.
- **Example**:
- Initial Tree:
```
30
/
20
\
25
```
- Accessing Node `25`:
- First, perform a Zig rotation on `20`, which promotes `25` and makes `20` its left child.
- Then, perform another Zig rotation on `30` to bring `25` to the root.
- After Zig-Zag Rotation:
```
25
/ \
20 30
```
3. Zag-Zig Rotation
This is the opposite case of Zig-Zag. It occurs when the accessed node is a left child of its parent, and the parent is a right child of its grandparent.
- **Example**:
- Initial Tree:
```
40
\
50
/
45
```
- Accessing Node `45`:
- First, perform a Zag rotation on `50`, promoting `45` and making `50` its right child.
- Then, perform another Zag rotation on `40` to bring `45` to the root.
- After Zag-Zig Rotation:
```
45
/ \
40 50
```
Summary of Rotations
- **Zig Rotation**: Single rotation for bringing a child to the root.
- **Zig-Zag Rotation**: Double rotation for a right child of a left child.
- **Zag-Zig Rotation**: Double rotation for a left child of a right child.
Q15. What is Red-Black tree? Explain insertion and deletion operations in a Red-Black tree with the help of a suitable example.
Ans:- A **Red-Black Tree** is a balanced binary search tree that maintains specific properties to ensure that the tree remains approximately balanced during insertions and deletions. This helps guarantee O(log n) time complexity for search, insertion, and deletion operations.
Properties of Red-Black Trees
1. Each node is colored either red or black.
2. The root node is always black.
3. Red nodes cannot have red children (no two reds in a row).
4. Every path from a node to its descendant NULL nodes must have the same number of black nodes (this is known as the black height).
5. Every leaf (NIL) is black.
These properties help to maintain balance, ensuring that the longest path from the root to any leaf is no more than twice the length of the shortest path.
Insertion in a Red-Black Tree
The insertion process consists of two main steps:
1. Perform a standard BST insertion.
2. Fix any violations of the Red-Black properties.
Example of Insertion
Let’s insert the following values into a Red-Black tree: 10, 20, 30, 15.
**Step 1**: Insert 10.
- Tree after insertion:
```
10 (Black)
```
**Step 2**: Insert 20.
- Tree after insertion:
```
10 (Black)
\
20 (Red)
```
**Step 3**: Insert 30.
- This violates the property that a red node cannot have a red child (20 is red and has a red parent).
- Perform rotations and recoloring:
- Before Fix:
```
10 (Black)
\
20 (Red)
\
30 (Red)
```
- After Fix (rotate left around 10, color swap):
```
20 (Black)
/ \
10 30 (Red)
```
**Step 4**: Insert 15.
- Insert 15 as a red node under 20:
```
20 (Black)
/ \
10 30 (Red)
\
15 (Red)
```
- This insertion does not violate any properties, so no fixing is needed.
Final Tree after Insertions
```
20 (Black)
/ \
10 30 (Red)
\
15 (Red)
```
Deletion in a Red-Black Tree
The deletion process involves removing a node and then fixing any violations of the Red-Black properties.
The steps include:
1. Perform a standard BST deletion.
2. Fix any violations.
Example of Deletion
Continuing from the previous tree, let’s delete node 15.
**Step 1**: Remove 15.
- Tree after deletion:
```
20 (Black)
/ \
10 30 (Red)
```
- The node that replaced 15 (NIL) is black, and thus no violations occur.
**Step 2**: Delete node 10.
- This removes 10 and creates a violation since node 20 has only one red child (30) and no red parent.
- Before Fix:
```
20 (Black)
\
30 (Red)
```
- To fix this, we perform a rotation around 20 to promote 30:
```
30 (Black)
/
20 (Red)
```
- After fixing, we have:
```
30 (Black)
/
20 (Red)
```
Final Tree after Deletions
```
30 (Black)
/
20 (Red)
```
Summary of Operations
- **Insertion**: Always starts with a standard BST insertion, then fixes the tree by performing rotations and recoloring.
- **Deletion**: Similar to BST deletion, but it involves checking and fixing the tree to maintain Red-Black properties, which may include rotations and recoloring.
Q16. Explain Direct File and Indexed Sequential File Organization.
Ans:- File organization refers to the way data is stored in a file to allow efficient access and management. Two common types of file organization are **Direct File Organization** and **Indexed Sequential File Organization**.
1. Direct File Organization
**Direct file organization**, also known as random file organization, allows data to be accessed directly based on a specific key. This method uses a hashing function to determine the location of the record in the file.
Characteristics:
- **Access Method**: Records can be accessed in constant time (O(1)) if the key is known, since the hash function computes the address directly.
- **Storage**: Records are stored in a way that allows direct access, often using a hash table or a similar structure.
- **Insertion/Deletion**: Insertion and deletion can be more complex than sequential methods since they may lead to collisions (two keys hashing to the same location). Collision resolution techniques like chaining or open addressing are used.
- **Usage**: Ideal for applications that require frequent access to records based on a key and where the order of records is not important.
Example:
Suppose we have a file of student records where each student has a unique ID. Using a hashing function, we can compute the location of each student's record directly, allowing for quick retrieval.
2. Indexed Sequential File Organization
**Indexed sequential file organization** combines both sequential and direct access methods. This organization maintains a primary file (which is sorted sequentially) and an index that allows for faster searching.
Characteristics:
- **Access Method**: Records can be accessed sequentially or via an index, which significantly speeds up search operations.
- **Storage**: The file is divided into two parts:
- A sequential data file that holds the actual records.
- An index file that contains pointers to the records in the data file, typically organized in a way that allows for efficient searching (like binary search).
- **Insertion/Deletion**: Records can be inserted in sorted order, and the index can be updated accordingly. Deletions may require shifting records, but the overall structure can be maintained efficiently.
- **Usage**: Suitable for applications where both random access and sequential access are required, such as database systems.
Example:
Consider a file containing employee records sorted by employee ID. An index file might store the IDs with pointers to their corresponding records. If a user wants to access the record for employee ID 102, the system can quickly look it up in the index file to find the location in the data file, thus speeding up the search process.
Summary
- **Direct File Organization**:
- Uses a hashing technique for direct access.
- Provides fast retrieval times but can have complexity with insertions and deletions.
- Suitable for applications requiring frequent access to records based on a specific key.
- **Indexed Sequential File Organization**:
- Combines sequential and direct access.
- Maintains both a sorted data file and an index for efficient searching.
- Ideal for applications needing both random access and sequential processing.
Both file organizations serve different purposes and are chosen based on the specific needs of the application in terms of speed, access patterns, and complexity of operations. If you have further questions or need more details, feel free to ask!
No comments: