Data Structure And Algorithm
Question No 1
Consider the following array of octal numbers
777
615
310
115
-133
415
566
Sort the above array using radix sort. Show the contents of each radix (bucket) in each
pass.
What is the maximum number of comparisons required to sort seven octal numbers?
To sort the given array using radix sort, we will use the LSD (Least Significant Digit) radix sort
algorithm. This algorithm sorts the numbers based on their digits, starting from the least
significant digit and moving towards the most significant digit.
Here is the step-by-step process of sorting the array using radix sort:
1. Convert the array elements to decimal numbers: To perform radix sort on octal numbers,
we need to first convert them to decimal numbers. This can be done by using the std::stoi
function from the <string> header.
2. Find the maximum number in the array: We need to find the maximum number in the
array to determine the number of digits in the largest number. This will help us determine
the number of passes required in the radix sort algorithm.
3. Perform the radix sort: We will iterate over each digit position in the numbers, starting
from the least significant digit (rightmost) to the most significant digit (leftmost). For each
digit position, we will create buckets for each possible digit value (0-7) and distribute the
numbers into these buckets based on the value of the current digit. After distributing the
numbers, we will collect them back from the buckets and update the array.
Now, let's go through each pass and show the contents of each radix (bucket) in each pass:
Pass 1: Sorting based on the least significant digit (rightmost digit)
Contents of each radix (bucket):
Radix 0:
Radix 1: 310
Radix 2:
Radix 3: 115
Radix 4: 415
Radix 5: 615
Radix 6: 566
Radix 7: 777
Array after pass 1:
310
115
415
615
566
777
Pass 2: Sorting based on the second least significant digit
Contents of each radix (bucket):
Radix 0: 310
Radix 1: 115
Radix 2:
Radix 3:
Radix 4: 415
Radix 5: 615
Radix 6: 566
Radix 7: 777
Array after pass 2:
310
115
415
615
566
777
Pass 3: Sorting based on the most significant digit
Contents of each radix (bucket):
Radix 0:
Radix 1: 115
Radix 2: 310
Radix 3:
Radix 4: 415
Radix 5:
Radix 6: 566
Radix 7: 615
Array after pass 3:
115
310
415
566
615
777
The final sorted array is:
115
310
415
566
615
777
Now, let's calculate the maximum number of comparisons required to sort the seven octal
numbers using radix sort.
In each pass, we compare the numbers based on the current digit being considered. In this
case, the maximum number of digits in the array is 3.
For each digit position, we compare all the numbers with each other. In this case, there are
7 numbers.
Therefore, the maximum number of comparisons required in each pass is 7*7 = 49
comparisons.
Since we have 3 passes in total, the maximum number of comparisons required to sort the
seven octal numbers using radix sort is 3*49 = 147 comparisons.
Question No 2
Convert the infix expression (A+B*C/D)^2/(2*A+B-D) into postfix using POLISH algorithm. Show
the contents of stack and the output variable P as you scan each character from the infix
expression.
Certainly! Let’s convert the given infix expression “(A+B*C/D)^2/(2*A+B-D)” into postfix
using the Polish algorithm.
To convert the infix expression to postfix, we’ll use a stack to store operators temporarily.
We’ll scan each character from the Infix expression and perform the necessary operations
based on the precedence of operators.
Here's the step-by-step process:
1. Initialize an empty stack and an empty output string variable, let’s call it “P”.
2. Start scanning each character from the infix expression from left to right.
3. If the scanned character is an operand (in this case, a variable), add it to the output
string “P”.
4. If the scanned character is an operator, we need to consider its precedence and
associativity.
a. If the stack is empty or contains a left parenthesis ‘(‘, push the operator onto
the stack.
b. If the scanned operator has higher precedence than the operator at the top of
the stack, push it onto the stack.
c. If the scanned operator has lower precedence than the operator at the top of
the stack, pop operators from the stack and add them to “P” until we find an
operator with lower precedence or an opening parenthesis ‘(‘. Then push the
scanned operator onto the stack.
d. If the scanned operator is a closing parenthesis ‘)’, pop operators from the
stack and add them to “P” until we find an opening parenthesis ‘(‘. Discard
both the opening and closing parenthesis.
5. Repeat steps 3 to 5 until all characters in the infix expression have been scanned.
6. Pop any remaining operators from the stack and add them to “P”.
Now, let’s apply this algorithm to convert the given infix expression into postfix:
Infix Expression: (A+B*C/D)^2/(2*A+B-D)
Stack: (empty)
P: (empty)
Scanning ‘(‘: Since it is an opening parenthesis, push it onto the stack.
Stack: (
P: (empty)
Scanning ‘A’: It is an operand, so add it to “P”.
Stack: (
P: A
Scanning ‘+’: Since the stack is not empty and the top of the stack is ‘(‘, push ‘+’ onto the
stack.
Stack: (+
P: A
Scanning ‘B’: It is an operand, so add it to “P”.
Stack: (+
P: AB
Scanning ‘*’: Since the top of the stack has higher precedence than ‘*’, push ‘*’ onto the
stack.
Stack: (*
P: AB
Scanning ‘C’: It is an operand, so add it to “P”.
Stack: (*
P: ABC
Scanning ‘/’: Since the top of the stack has the same precedence as ‘/’, push ‘/’ onto the
stack.
Stack: (/*
P: ABC
Scanning ‘D’: It is an operand, so add it to “P”.
Stack: (/*
P: ABCD
Scanning ‘)’: Pop the operators from the stack until we find ‘(‘, and discard both ‘(‘ and ‘)’.
Stack:
P: ABCD*/
Scanning ‘^’: Since the stack is empty, push ‘^’ onto the stack.
Stack: ^
P: ABCD*/
Scanning ‘2’: It is an operand, so add it to “P”.
Stack: ^
P: ABCD*/2
Scanning ‘/’: Since the top of the stack has the same precedence as ‘/’, push ‘/’ onto the
stack.
Stack: /^
P: ABCD*/2
Scanning ‘(‘: Push ‘(‘ onto the stack.
Stack: /^(
P: ABCD*/2
Scanning ‘2’: It is an operand, so add it to “P”.
Stack: /^(
P: ABCD*/22
Scanning ‘*’: Since the top of the stack has higher precedence than ‘*’, push ‘*’ onto the
stack.
Stack: /^(*
P: ABCD*/22
Scanning ‘A’: It is an operand, so add it to “P”.
Stack: /^(*
P: ABCD*/22A
Scanning ‘+’: Since the top of the stack has lower precedence than ‘+’, push ‘+’ onto the
stack.
Stack: /^(*+
P: ABCD*/22A
Scanning ‘B’: It is an operand, so add it to “P”.
Stack: /^(*+
P: ABCD*/22AB
Scanning ‘-‘: Since the top of the stack has the same precedence as ‘-‘, push ‘-‘ onto the
stack.
Stack: /^(*+-
P: ABCD*/22AB
Scanning ‘D’: It is an operand, so add it to “P”.
Stack: /^(*+-
P: ABCD*/22ABD
Scanning ‘)’: Pop the operators from the stack until we find ‘(‘, and discard both ‘(‘ and ‘)’.
Stack: /^
P: ABCD*/22ABD+-
Scanning ‘/’: Since the top of the stack has the same precedence as ‘/’, push ‘/’ onto the
stack.
Stack: /^/
Poops! It seems I made a mistake in the previous response. Let me correct it and continue
the explanation.
Scanning ‘/’: Since the top of the stack has the same precedence as ‘/’, push ‘/’ onto the
stack.
Stack: /^/
P: ABCD*/22ABD+-
Scanning ‘(‘: Push ‘(‘ onto the stack.
Stack: /^/(
P: ABCD*/22ABD+-
Scanning ‘2’: It is an operand, so add it to “P”.
Stack: /^/(
P: ABCD*/22ABD+-2
Scanning ‘*’: Since the top of the stack has higher precedence than ‘*’, push ‘*’ onto the
stack.
Stack: /^/*(
P: ABCD*/22ABD+-2
Scanning ‘A’: It is an operand, so add it to “P”.
Stack: /^/*(
P: ABCD*/22ABD+-2A
Scanning ‘+’: Since the top of the stack has lower precedence than ‘+’, push ‘+’ onto the
stack.
Stack: /^/*(
P: ABCD*/22ABD+-2A+
Scanning ‘B’: It is an operand, so add it to “P”.
Stack: /^/*(
P: ABCD*/22ABD+-2A+B
Scanning ‘-‘: Since the top of the stack has the same precedence as ‘-‘, push ‘-‘ onto the
stack.
Stack: /^/*(-
P: ABCD*/22ABD+-2A+B
Scanning ‘D’: It is an operand, so add it to “P”.
Stack: /^/*(-
P: ABCD*/22ABD+-2A+BD
Scanning ‘)’: Pop the operators from the stack until we find ‘(‘, and discard both ‘(‘ and ‘)’.
Stack: /^/
P: ABCD*/22ABD+-2A+B-
At this point, we have scanned all the characters from the infix expression. Now, we need to
pop any remaining operators from the stack and add them to “P”.
Stack: /^
P: ABCD*/22ABD+-2A+B-^
Finally, the postfix expression is “ABCD*/22ABD+-2A+B-^/”.
I hope this step-by-step explanation was helpful in understanding how to convert an infix
expression to postfix using the Polish algorithm. If you have any further questions, feel free
to ask!
Question No 3
Consider the following numbers
20
15
12
22
25
10
18
24
26
11
Construct a binary search tree from the above numbers. Also traverse the resultant tree using
post-order tree traversal algorithm and write down the order in which numbers (nodes) are
visited.
To construct a binary search tree, we start with the first number as the root of the tree. In
this case, the root will be 20.
Next, we compare the next number, 15, with the root. Since 15 is less than 20, it becomes
the left child of the root.
Moving on to the next number, 12, we compare it with the root. Since 12 is less than 20, we
move to the left child of the root. Since there is no left child of 15, we make 12 the left child
of 15.
Next, we compare 22 with the root. Since 22 is greater than 20, we move to the right child of
the root. Since there is no right child of 20, we make 22 the right child of 20.
Continuing this process, we compare 25 with the root. Since 25 is greater than 20, we move
to the right child of the root. Since there is a right child of 20 (22), we compare 25 with 22.
Since 25 is greater than 22, we move to the right child of 22. Since there is no right child of
22, we make 25 the right child of 22.
We repeat this process for the remaining numbers, 10, 18, 24, 26, and 11, and construct
the binary search tree accordingly.
The resulting binary search tree is as follows:
```
20
/ \
15 22
/ / \
12 18 25
/ \
10 26
11
```
To traverse the tree using post-order traversal, we visit the nodes in the following order: 11,
10, 12, 18, 15, 26, 25, 22, 20.
Question No 4
post-order tree traversal algorithm and write down the order in which numbers (nodes) are visited
Provide the adjacency matrix representation of the following graph Also write the order in which
nodes are visited if breadth-first-search algorithm is applied on the following graph starting with
vertex D
To represent the given graph as an adjacency matrix, we need to identify the nodes and the edges
connecting them. Let’s denote the nodes as A, B, C, D, E, and F, as provided.
By examining the graph, we can determine the following connections:
- Node A is connected to nodes B and C.
- Node B is connected to nodes A, D, and E.
- Node C is connected to nodes A and D.
- Node D is connected to nodes B and C.
- Node E is connected to node B.
- Node F is not directly connected to any other node.
Based on this information, we can construct the adjacency matrix:
```
ABCDEF
A 011000
B 100110
C 100100
D 011000
E 010000
F 000000
```
In the adjacency matrix, each row and column represents a node. The value at position (I, j) in the
matrix represents whether there is an edge between nodes I and j. In this case, a value of 1
indicates an edge, while 0 indicates no edge.
Now, let’s determine the order in which the nodes are visited using the breadth-first search (BFS)
algorithm, starting with vertex D.
The BFS algorithm starts by visiting the starting vertex, D, and then explores its adjacent nodes.
The order of visiting nodes is determined by their distance from the starting vertex.
In this case, the order in which nodes are visited using BFS starting with vertex D is:
D -> B -> A -> C -> E -> F
So the nodes are visited in the order: D, B, A, C, E, F.
Please note that this order may vary depending on the implementation details of the BFS
algorithm, but the overall pattern of visiting nodes based on their distance from the starting vertex
will remain the same.
Question No 1
Write a function to attach a singly linked list to the end of other singly
linked list.
Certainly! I can help you with that. To attach one singly linked list to the end
of another singly linked list, you will need to traverse the first list until you
reach its last node, and then update its "next" pointer to point to the head of
the second list.
Here's a sample implementation of the function:
```cpp
#include <iostream>
// Define the structure for a node in the linked list
struct Node {
int data;
Node* next;
};
// Function to attach one linked list to the end of another linked list
void attachLinkedList(Node* list1, Node* list2) {
if (list1 == nullptr) {
// If the first list is empty, simply assign the head of the second list to it
list1 = list2;
} else {
Node* current = list1;
// Traverse the first list until the last node
while (current->next != nullptr) {
current = current->next;
// Update the "next" pointer of the last node in the first list
current->next = list2;
// Function to print the elements of a linked list
void printLinkedList(Node* head) {
Node* current = head;
while (current != nullptr) {
std::cout << current->data << " ";
current = current->next;
}
std::cout << std::endl;
// Test the attachLinkedList function
int main() {
// Create the first linked list: 1 -> 2 -> 3
Node* head1 = new Node{1, nullptr};
Node* second1 = new Node{2, nullptr};
Node* third1 = new Node{3, nullptr};
head1->next = second1;
second1->next = third1;
// Create the second linked list: 4 -> 5 -> 6
Node* head2 = new Node{4, nullptr};
Node* second2 = new Node{5, nullptr};
Node* third2 = new Node{6, nullptr};
head2->next = second2;
second2->next = third2;
// Print the original linked lists
std::cout << "Original List 1: ";
printLinkedList(head1);
std::cout << "Original List 2: ";
printLinkedList(head2);
// Attach the second list to the end of the first list
attachLinkedList(head1, head2);
// Print the modified list
std::cout << "Modified List 1: ";
printLinkedList(head1);
// Free the memory
delete head1;
delete second1;
delete third1;
return 0;
```
In this example, we create two linked lists: List 1 (1 -> 2 -> 3) and List 2 (4 -
> 5 -> 6). Then, we attach List 2 to the end of List 1 using the
`attachLinkedList` function. Finally, we print the modified List 1 to verify
that the attachment was successful.
Note that this is just a sample implementation, and you can modify it
according to your specific needs or the structure of your linked lists.
Question No 2
Write a function to reverse the order o’ elements on stack S using
one
Sure! Here's an example of a function that can reverse the order of
elements on a stack using only one additional stack:
```cpp
#include <iostream>
#include <stack>
void reverseStack(std::stack<int>& S) {
std::stack<int> tempStack;
// Transfer elements from stack S to tempStack
while (!S.empty()) {
int element = S.top();
S.pop();
tempStack.push(element);
// Transfer elements from tempStack back to stack S (in reversed
order)
while (!tempStack.empty()) {
int element = tempStack.top();
tempStack.pop();
S.push(element);
int main() {
std::stack<int> myStack;
// Push elements onto the stack
myStack.push(1);
myStack.push(2);
myStack.push(3);
myStack.push(4);
myStack.push(5);
std::cout << "Original stack: ";
while (!myStack.empty()) {
std::cout << myStack.top() << " ";
myStack.pop();
std::cout << std::endl;
// Reverse the stack
reverseStack(myStack);
std::cout << "Reversed stack: ";
while (!myStack.empty()) {
std::cout << myStack.top() << " ";
myStack.pop();
std::cout << std::endl;
return 0;
```
In this example, we define a function called `reverseStack` that
takes a stack `S` as a parameter and reverses its order using one
additional stack (`tempStack`).
We transfer the elements from `S` to `tempStack` one by one,
effectively reversing their order. Then, we transfer the elements back
from `tempStack` to `S`, which now contains the elements in the
reversed order.
The `main` function demonstrates the usage of the `reverseStack`
function by creating a stack, pushing elements onto it, printing the
original stack, calling `reverseStack` to reverse the stack, and finally
printing the reversed stack.
Please note that the code assumes the stack contains integers
(`int`), but you can modify it to work with other types as needed.
Question No 3
Write a recursive function to find the factorial of a number.
For example, 41 =1*2*3*4=24
Certainly! Here's the recursive function to find the factorial of a
number:
```cpp
#include <iostream>
// Recursive function to find the factorial of a number
int factorial(int n) {
if (n == 0 || n == 1) {
return 1;
} else {
return n * factorial(n - 1);
int main() {
int num;
std::cout << "Enter a positive integer: ";
std::cin >> num;
// Find the factorial of the given number
int factorialResult = factorial(num);
std::cout << "The factorial of " << num << " is " << factorialResult <<
std::endl;
return 0;
```
In this recursive function, we check if the number `n` is either 0 or 1.
If it is, we return 1 since the factorial of 0 and 1 is 1.
If `n` is greater than 1, we make a recursive call to the `factorial`
function with `n-1` as the argument and multiply it with `n` to get the
factorial of `n`.
In the `main` function, we prompt the user to enter a positive integer,
find its factorial using the `factorial` function, and print the result.
Please note that this recursive function assumes that the input
number is a positive integer. You might want to add input validation to
handle non-positive integers or other invalid inputs, if necessary.
Question No 4
Write algorithms/function for sorting in descending order using
bubble sort;
BUBBLE (DATA, N), here DATA is an array with N elements.
Certainly! Here's an algorithm and a corresponding function for
sorting an array in descending order using the Bubble Sort algorithm:
Algorithm for Bubble Sort in Descending Order:
1. Start with the given array `DATA` and its length `N`.
2. Iterate `N-1` times for `i` from 0 to `N-2` (outer loop).
3. For each iteration of the outer loop, iterate `N-i-1` times for `j`
from 0 to `N-i-2` (inner loop).
4. Compare `DATA[j]` and `DATA[j+1]`.
- If `DATA[j]` is less than `DATA[j+1]`, swap the elements.
5. Repeat steps 3-4 until the inner loop completes for all iterations of
the outer loop.
6. After completing all iterations of the outer loop, the array will be
sorted in descending order.
Here's the corresponding function in C++ that implements the
Bubble Sort algorithm for sorting an array in descending order:
```cpp
#include <iostream>
void bubbleSortDescending(int data[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (data[j] < data[j + 1]) {
// Swap the elements
int temp = data[j];
data[j] = data[j + 1];
data[j + 1] = temp;
int main() {
int data[] = {5, 2, 8, 1, 4};
int n = sizeof(data) / sizeof(data[0]);
std::cout << "Original Array: ";
for (int i = 0; i < n; i++) {
std::cout << data[i] << " ";
std::cout << std::endl;
// Sort the array in descending order using Bubble Sort
bubbleSortDescending(data, n);
std::cout << "Sorted Array (Descending Order): ";
for (int i = 0; i < n; i++) {
std::cout << data[i] << " ";
}
std::cout << std::endl;
return 0;
```
In the `bubbleSortDescending` function, we use a nested loop to
iterate through the array and compare adjacent elements. If the
current element is less than the next element, we swap them. This
process is repeated until the array is sorted in descending order.
In the `main` function, we demonstrate the usage of the
`bubbleSortDescending` function by sorting an example array and
printing the original and sorted arrays.
Please note that this implementation assumes we are sorting an
array of integers. You can modify it to work with other data types or
make it more generic by using templates if needed.
