DS Midsem Prep
This is a live document. Expect changes frequently. I am parsing through PYQs during free time. You can expect it to conclude in a week's time.
- Given the following function in C:
void func() {
int i = 1, j;
while(i <= n) {
for(j = 1; j * j <= n; j++)
printf("Data Structure...\n");
++i;
}
}
Determine the time complexity of the function.
Answer
Time Complexity Analysis:
Outer
while
loop:- The loop runs from
i = 1
toi = n
, so it iteratesn
times.
- The loop runs from
Inner
for
loop:- The loop runs from
j = 1
toj * j <= n
, which implies thatj
runs approximately up to \(\sqrt{n}\).
- The loop runs from
Therefore, the inner loop runs approximately \(\sqrt{n}\) times for each iteration of the outer loop.
Total Time Complexity:
- Since the outer loop runs
n
times and for each iteration of the outer loop, the inner loop runs \(\sqrt{n}\) times, the total time complexity is:
- Since the outer loop runs
$$\text{Time Complexity} = O(n \times \sqrt{n}) = O(n^{3/2})$$
- Consider a 2-D array
arr[6][7]
(with 6 rows and 7 columns). Each element of the array requires 4 bytes of memory space. If the array is stored in row-major order with a base address of 1001, what will be the address of the array elementarr[5][3]
?
Answer
To calculate the address of a specific element in a 2D array stored in row-major order, we use the following formula:
$$\text{Address} = \text{Base Address} + \text{Element Size} \times \left[\text{Number of Columns} \times i + j\right]$$
Where:
Base Address = 1001
Element Size = 4 bytes
Number of Columns = 7
i
andj
are the row and column indices, respectively.
For the element arr[5][3]
:
i = 5
j = 3
Substitute the values into the formula, the address of the array element arr[5][3]
is 1153.
- If the node of a doubly linked list is declared in C as:
struct node {
int data;
struct node *prev;
struct node *next;
};
and ptr
is a pointer pointing to one of the internal nodes of a doubly linked list, then write the required statements to delete the node to which ptr
is pointing without using any other pointer variable.
Answer
To delete the node pointed to by ptr
in a doubly linked list without using any other pointer variable, you can use the following statements:
ptr->prev->next = ptr->next;
ptr->next->prev = ptr->prev;
free(ptr);
Explanation:
ptr->prev->next = ptr->next;
- This statement updates the
next
pointer of the previous node to point to the next node, effectively bypassing the node pointed to byptr
.
- This statement updates the
ptr->next->prev = ptr->prev;
- This statement updates the
prev
pointer of the next node to point to the previous node, completing the bypass.
- This statement updates the
free(ptr);
- Finally, the
ptr
node is freed from memory.
- Finally, the
These operations effectively remove the node from the doubly linked list and free the memory occupied by it without requiring any additional pointer variables.
- How can a singly linked list be used to represent the following polynomial?
$$P(x) = 2xy^2z^3 + 3x^2yz - 4xy^3z + 5x^2y^2 + 7xy^2z^5 + 11$$
Answer
To represent the polynomial using a singly linked list, each node of the list will represent a term in the polynomial. The structure of the node will contain:
The coefficient of the term.
The powers of the variables (x), (y), and (z).
A pointer to the next node.
Here is how you can define the structure in C:
struct Node {
int coefficient;
int power_x;
int power_y;
int power_z;
struct Node* next;
};
Each node will store the coefficient and powers corresponding to one term of the polynomial. The linked list will be created with each node representing a term in the polynomial in descending order of the degree (or any other specific order).
For example:
The first node might represent (2xy^2z^3) with
coefficient = 2
,power_x = 1
,power_y = 2
, andpower_z = 3
.The second node might represent (3x^2yz) with
coefficient = 3
,power_x = 2
,power_y = 1
, andpower_z = 1
.And so on for the rest of the terms.
- A stack is implemented using an array declared in C:
st[N]
and an integer variablepos
. The pseudo code for thepush()
andpop()
operations of the stack are as follows:
push(x) {
st[pos] = x;
pos = pos - 1;
}
pop() {
pos = pos + 1;
return(st[pos]);
}
Find the initialization of the integer variable pos
for an empty stack with a maximum capacity of N
elements for the above implementation.
Answer
The stack is implemented using an array st[N]
, and pos
is used to track the position of the stack's top element.
Initialization of
pos
:Since the
push()
operation first assignsx
tost[pos]
and then decrementspos
, it suggests thatpos
starts at the topmost position of the stack.After a
push
,pos
is decremented, and after apop
,pos
is incremented.
For an empty stack:
- The stack should be considered empty when
pos
is just below the first index of the array (which would bepos = N - 1
if using a 0-based index for a maximum capacity ofN
elements).
Thus, pos
should be initialized to N - 1
for an empty stack.
Create a two-dimensional array of size M×N dynamically containing English alphabets (capital letters) except ‘X’. Write a C program to delete ALL the vowels present in the matrix. Once any vowel is found in a row and deleted, the elements will be shifted from the same row as well as the next rows to fill the deleted element. The empty space at the end will be replaced by the alphabet ‘X’.
Example:
For the deletion of the first vowel (
U
):Before:
A S D U C J P R I J K L M N T W O Y Q S F D B L
After:
A S D C J P R I J K L M N T W O Y Q S F D B L X
For the deletion of the second vowel (
I
):Before:
A S D C J P R I J K L M N T W O Y Q S F D B L X
After:
A S D C J P R J K L M N T W O Y Q S F D B L X X
Answer
Since 2D arrays in C are stored in row-major order, we can directly use a pointer to the start of the 2D array and manipulate it as if it were a 1D array. This allows us to treat the matrix as a single contiguous block of memory.
Direct Pointer Usage: Instead of copying the matrix data, directly assign a pointer to the beginning of the 2D array (
&example[0][0]
). This pointer will be used to traverse and manipulate the matrix.Vowel Detection and Shifting:
Traverse the matrix using the pointer.
When a vowel is detected, shift all subsequent elements to the left to fill the gap.
Replacement with 'X':
- After all vowels have been deleted, fill the remaining positions at the end of the array with 'X'.
Use of Original Array: The operations modify the original array (
example
), and the changes are reflected in the same array.
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// Function to check if a character is a vowel
bool isVowel(char c) {
return c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U';
}
// Function to delete vowels from the matrix and shift elements
void deleteVowels(char* matrix, int size) {
int writeIndex = 0; // Pointer to track the next write position
// Traverse through the matrix as a linear 1D array
for (int readIndex = 0; readIndex < size; readIndex++) {
if (!isVowel(matrix[readIndex])) {
matrix[writeIndex++] = matrix[readIndex]; // Copy non-vowel characters
}
}
// Fill the remaining positions with 'X'
for (int i = writeIndex; i < size; i++) {
matrix[i] = 'X';
}
}
int main() {
int M = 4, N = 6; // Dimensions of the matrix
int size = M * N; // Total number of elements in the matrix
// Example matrix (declared as a 2D array)
char example[4][6] = {
{'A', 'S', 'D', 'U', 'C', 'J'},
{'P', 'R', 'I', 'J', 'K', 'L'},
{'M', 'N', 'T', 'W', 'O', 'Y'},
{'Q', 'S', 'F', 'D', 'B', 'L'}
};
// Use a pointer to the start of the example matrix
char* matrix = &example[0][0];
// Print the initial matrix
printf("Initial Matrix:\n");
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
printf("%c ", example[i][j]); // Using the original array 'example' to print
}
printf("\n");
}
// Delete vowels and shift elements
deleteVowels(matrix, size);
// Print the modified matrix
printf("\nModified Matrix:\n");
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
printf("%c ", example[i][j]); // Changes are reflected in the original 'example' array
}
printf("\n");
}
return 0;
}
Explanation
Direct Pointer Usage: The pointer
matrix
is initialized to point to the start of the 2D arrayexample
(char* matrix = &example[0][0];
). This allows the program to treat the 2D array as a linear block of memory and perform operations as if it were a 1D array.Efficient Vowel Deletion and Element Shifting:
- The
deleteVowels
function processes the array using the pointer (matrix
). It identifies vowels and shifts non-vowel elements to the left in the array, directly modifying the original 2D array.
- The
Reflecting Changes in the Original Array: The printing of the matrix before and after the operation is done using the
example
array. This demonstrates that the operations performed through the pointermatrix
are directly modifying the original 2D arrayexample
.Memory Efficiency: By directly manipulating the original array without copying, the program is efficient in both time and space, ensuring all operations are done in-place.
- The table below is a representation of a doubly linked list where the nodes are declared in C as:
struct node {
int data;
struct node *prev;
struct node *next;
};
The nodes are connected as per the data shown in the table. Draw the linked list. Also, write C-like statements to replace the values of Node-III and Node-IV by adding the value of Node-I to these node values and replace the value of Node-II by subtracting the value of Node-I from it. Consider the base pointer ptr
, which holds the address of Node-I. Do not use any other pointer variable.
Node | Data | Prev Address | Next Address | Node Address |
I | 10 | 2001 | 3001 | 1001 |
II | 15 | NULL | NULL | 2001 |
III | -5 | NULL | 4001 | 3001 |
IV | 25 | NULL | NULL | 4001 |
Answer
Drawing the Linked List:
Node-II (2001) <- Node-I (1001) -> Node-III (3001) -> Node-IV (4001)
C-like Statements:
Assuming ptr
is pointing to Node-I:
// Replace Node-III data with Node-III data + Node-I data
ptr->next->data = ptr->next->data + ptr->data;
// Replace Node-IV data with Node-IV data + Node-I data
ptr->next->next->data = ptr->next->next->data + ptr->data;
// Replace Node-II data with Node-II data - Node-I data
ptr->prev->data = ptr->prev->data - ptr->data;
- The following data are stored in a singly linked list in the order shown below:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10
Write a pseudo code or C-function to delete all odd numbers from the list.
Answer
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
// Function to delete all odd numbers from the list
void deleteOdds(struct Node** head) {
struct Node* temp = *head;
struct Node* prev = NULL;
while (temp != NULL) {
if (temp->data % 2 != 0) {
if (prev == NULL) {
// Head node is odd
*head = temp->next;
free(temp);
temp = *head;
} else {
// Middle or last node is odd
prev->next = temp->next;
free(temp);
temp = prev->next;
}
} else {
prev = temp;
temp = temp->next;
}
}
}
// Function to print the list
void printList(struct Node* node) {
while (node != NULL) {
printf("%d -> ", node->data);
node = node->next;
}
printf("NULL\n");
}
// Main function for testing
int main() {
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
head->data = 1;
head->next = (struct Node*)malloc(sizeof(struct Node));
head->next->data = 2;
head->next->next = (struct Node*)malloc(sizeof(struct Node));
head->next->next->data = 3;
head->next->next->next = (struct Node*)malloc(sizeof(struct Node));
head->next->next->next->data = 4;
head->next->next->next->next = (struct Node*)malloc(sizeof(struct Node));
head->next->next->next->next->data = 5;
head->next->next->next->next->next = NULL;
printf("Original List:\n");
printList(head);
deleteOdds(&head);
printf("List after deleting odd numbers:\n");
printList(head);
return 0;
}
- Explain a sparse matrix and its representations. Write a pseudo code or C-function to display the triplet of a transpose of a sparse matrix with a suitable example.
Answer
Let's use a struct
to represent the triplet form of a sparse matrix. Each triplet will store the row index, column index, and value of a non-zero element. The sparse matrix will be an array of these triplet structures.
To represent a sparse matrix using structs in C:
Define a struct to hold each non-zero element's row index, column index, and value.
Use an array of this struct to represent the entire sparse matrix.
#include <stdio.h>
#include <stdlib.h>
// Define a struct for the triplet representation
struct Triplet {
int row;
int col;
int value;
};
// Function to display the triplet representation
void displayTriplets(struct Triplet* spMatrix, int nonZeroCount) {
printf("Row Column Value\n");
for (int i = 0; i < nonZeroCount; i++) {
printf("%d %d %d\n", spMatrix[i].row, spMatrix[i].col, spMatrix[i].value);
}
}
// Function to compute and display the transpose of the sparse matrix in triplet form
void transposeSparseMatrix(struct Triplet* spMatrix, int nonZeroCount) {
struct Triplet* transposeMatrix = (struct Triplet*)malloc(nonZeroCount * sizeof(struct Triplet));
for (int i = 0; i < nonZeroCount; i++) {
transposeMatrix[i].row = spMatrix[i].col;
transposeMatrix[i].col = spMatrix[i].row;
transposeMatrix[i].value = spMatrix[i].value;
}
printf("\nTranspose in Triplet Form:\n");
displayTriplets(transposeMatrix, nonZeroCount);
free(transposeMatrix);
}
int main() {
// Initialize the sparse matrix with non-zero elements
struct Triplet spMatrix[] = {
{0, 2, 3},
{1, 0, 4},
{2, 1, 5},
{2, 3, 7}
};
int nonZeroCount = sizeof(spMatrix) / sizeof(spMatrix[0]);
printf("Original Matrix in Triplet Form:\n");
displayTriplets(spMatrix, nonZeroCount);
// Compute and display the transpose
transposeSparseMatrix(spMatrix, nonZeroCount);
return 0;
}
Output
Original Matrix in Triplet Form:
Row Column Value
0 2 3
1 0 4
2 1 5
2 3 7
Transpose in Triplet Form:
Row Column Value
2 0 3
0 1 4
1 2 5
3 2 7
Explanation:
Struct Definition (
Triplet
):- Defines a structure to store the row index, column index, and value of each non-zero element in the sparse matrix.
Array of Structs (
spMatrix
):- Represents the sparse matrix as an array of
Triplet
structs, where each struct contains the row, column, and value of a non-zero element.
- Represents the sparse matrix as an array of
Function
displayTriplets()
:- Takes the array of triplets and the count of non-zero elements and prints the triplet form of the matrix.
Function
transposeSparseMatrix()
:Computes the transpose of the sparse matrix by swapping the row and column indices for each triplet.
Uses dynamic memory allocation to create an array for the transpose matrix and frees the memory after use.
Main Function (
main()
):- Initializes the sparse matrix in triplet form, displays it, computes the transpose, and then displays the transpose matrix.
Write an algorithm, pseudo code, or C-function to convert an expression in infix notation to its equivalent prefix expression. Convert the infix expression:
(A+B)+C-(D-E)^F
to prefix equivalent mentioning each step of the algorithm.
Answer
Infix Expression
(A+B)+C-(D-E)^F
Steps to Convert Infix to Prefix
Reverse the Infix Expression:
Reverse the expression.
Swap '(' with ')' and vice versa.
Reversed Infix:
F^(E-D)-C+(B+A)
Convert the Reversed Infix to Postfix:
Initialize an empty stack for operators and an empty output list.
Read the reversed infix expression from left to right.
Process each character using the stack rules:
Step-by-Step Process:
F
: Operand → Add to output: Postfix:F
^
: Operator → Push to stack: Stack:^
(
: Right parenthesis after reversing (treated as left) → Push to stack: Stack:^ (
E
: Operand → Add to output: Postfix:FE
-
: Operator → Push to stack: Stack:^ ( -
D
: Operand → Add to output: Postfix:FED
)
: Left parenthesis after reversing (treated as right) → Pop from stack to output until '(' is found. Postfix:FED-
Stack:^
-
: Operator → Compare precedence with^
, pop^
and push-
: Postfix:FED-^
Stack:-
C
: Operand → Add to output: Postfix:FED-^C
+
: Operator → Push to stack: Stack:- +
(
: Right parenthesis after reversing (treated as left) → Push to stack: Stack:- + (
B
: Operand → Add to output: Postfix:FED-^CB
+
: Operator → Push to stack: Stack:- + ( +
A
: Operand → Add to output: Postfix:FED-^CBA
)
: Left parenthesis after reversing (treated as right) → Pop from stack to output until(
is found. Postfix:FED-^CBA+
Stack:- +
Pop remaining operators from stack to output:
Postfix:FED-^CBA+-
Reverse the Postfix Expression to Get Prefix:
Reversed Postfix:
-+ABC^-DEF
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define MAX 100
typedef struct {
char items[MAX];
int top;
} Stack;
// Initialize the stack
void initialize(Stack* stack) {
stack->top = -1;
}
// Check if the stack is empty
int isEmpty(Stack* stack) {
return stack->top == -1;
}
// Push element onto the stack
void push(Stack* stack, char c) {
if (stack->top == MAX - 1) return;
stack->items[++(stack->top)] = c;
}
// Pop element from the stack
char pop(Stack* stack) {
if (isEmpty(stack)) return '\0';
return stack->items[(stack->top)--];
}
// Peek at the top element of the stack
char peek(Stack* stack) {
if (isEmpty(stack)) return '\0';
return stack->items[stack->top];
}
// Determine precedence of operators
int precedence(char op) {
if (op == '+' || op == '-') return 1;
if (op == '*' || op == '/') return 2;
if (op == '^') return 3;
return 0;
}
// Check if character is an operator
int isOperator(char c) {
return c == '+' || c == '-' || c == '*' || c == '/' || c == '^';
}
// Function to reverse a string
void reverseString(char* str) {
int length = strlen(str);
for (int i = 0; i < length / 2; i++) {
char temp = str[i];
str[i] = str[length - i - 1];
str[length - i - 1] = temp;
}
}
// Convert infix expression to prefix
void infixToPrefix(char* infix) {
Stack s;
initialize(&s);
int length = strlen(infix);
char postfix[MAX];
int k = 0;
// Reverse the infix expression
reverseString(infix);
// Swap '(' with ')' and vice versa
for (int i = 0; i < length; i++) {
if (infix[i] == '(') {
infix[i] = ')';
} else if (infix[i] == ')') {
infix[i] = '(';
}
}
// Process the reversed infix expression to get postfix
for (int i = 0; i < length; i++) {
char c = infix[i];
if (isalnum(c)) {
postfix[k++] = c;
} else if (c == '(') {
push(&s, c);
} else if (c == ')') {
while (peek(&s) != '(') {
postfix[k++] = pop(&s);
}
pop(&s); // Remove '(' from the stack
} else if (isOperator(c)) {
while (!isEmpty(&s) && precedence(peek(&s)) >= precedence(c)) {
postfix[k++] = pop(&s);
}
push(&s, c);
}
}
while (!isEmpty(&s)) {
postfix[k++] = pop(&s);
}
postfix[k] = '\0';
// Reverse the postfix expression to get the prefix expression
reverseString(postfix);
printf("Prefix Expression: %s\n", postfix);
}
int main() {
char infix[MAX] = "(A+B)+C-(D-E)^F";
infixToPrefix(infix);
return 0;
}
Explanation:
Stack Operations: Basic stack operations (push, pop, peek) are used to manage the operators.
Reverse the Infix Expression: The expression is reversed, and parentheses are swapped to ensure the correct processing order.
Convert Reversed Infix to Postfix: The reversed expression is processed as a postfix conversion, respecting operator precedence and associativity.
Reverse the Postfix to Get Prefix: Finally, reverse the postfix result to get the prefix expression.
Output
Prefix Expression: -+ABC^-DEF
Create a function that searches for an integer
num
in a doubly linked list and displays the content (info/data) of its left node and right node. In case of unavailability, the content should be displayed as-1
.Answer
cCopy code#include <stdio.h> #include <stdlib.h> // Define the structure for a doubly linked list node struct Node { int data; struct Node* prev; struct Node* next; }; // Function to search for a number and display adjacent node data void searchAndDisplay(struct Node* head, int num) { struct Node* temp = head; while (temp != NULL) { if (temp->data == num) { int leftData = (temp->prev != NULL) ? temp->prev->data : -1; int rightData = (temp->next != NULL) ? temp->next->data : -1; printf("Left Node Data: %d\n", leftData); printf("Right Node Data: %d\n", rightData); return; } temp = temp->next; } printf("Number not found. Left Node Data: -1, Right Node Data: -1\n"); } // Helper function to create a new node struct Node* createNode(int data) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = data; newNode->prev = NULL; newNode->next = NULL; return newNode; } // Example usage int main() { // Creating a doubly linked list for demonstration struct Node* head = createNode(10); head->next = createNode(20); head->next->prev = head; head->next->next = createNode(30); head->next->next->prev = head->next; head->next->next->next = createNode(40); head->next->next->next->prev = head->next->next; int num = 20; searchAndDisplay(head, num); return 0; }
Evaluate the following postfix expression where
a=10, b=2, c=3, d=5, e=4
:a b / c - d e * + a c * -
Answer
To evaluate the postfix expression, follow these steps:Substitute the values:
10 2 / 3 - 5 4 * + 10 3 * -
Process using a stack:
Push 10, 2
/
operator:10 / 2 = 5
Push 3
-
operator:5 - 3 = 2
Push 5, 4
*
operator:5 * 4 = 20
+
operator:2 + 20 = 22
Push 10, 3
*
operator:10 * 3 = 30
-
operator:22 - 30 = -8
Result: -8
The seven elements A, B, C, D, E, F, and G are pushed onto a stack in reverse order, i.e., starting from G. The stack is popped five times, and each element is inserted into a queue. Two elements are deleted from the queue and pushed back onto the stack. Finally, one element is popped from the stack. Stepwise show the content of both stack and queue.
Answer
Initial Stack (after pushing G to A in reverse):
Stack: G, F, E, D, C, B, APop 5 elements and insert them into the queue:
Stack: G, F
Queue: A, B, C, D, EDelete 2 elements from the queue and push onto the stack:
Stack: G, F, A, B
Queue: C, D, EPop 1 element from the stack:
Stack: G, F, A
Queue: C, D, E
Write a function that concatenates two circular linked lists into one circular linked list.
Answer#include <stdio.h> #include <stdlib.h> // Define the structure for a circular linked list node struct Node { int data; struct Node* next; }; // Function to concatenate two circular linked lists void concatenate(struct Node** head1, struct Node** head2) { if (*head1 == NULL) { *head1 = *head2; return; } if (*head2 == NULL) { return; } struct Node* temp1 = *head1; while (temp1->next != *head1) { temp1 = temp1->next; } struct Node* temp2 = *head2; while (temp2->next != *head2) { temp2 = temp2->next; } temp1->next = *head2; temp2->next = *head1; } // Helper function to create a new node struct Node* createNode(int data) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = data; newNode->next = newNode; // Points to itself to form a circular list return newNode; } // Example usage int main() { // Creating two circular linked lists for demonstration struct Node* head1 = createNode(1); head1->next = createNode(2); head1->next->next = createNode(3); head1->next->next->next = head1; // Making it circular struct Node* head2 = createNode(4); head2->next = createNode(5); head2->next->next = head2; // Making it circular concatenate(&head1, &head2); // Printing the concatenated circular linked list struct Node* temp = head1; do { printf("%d ", temp->data); temp = temp->next; } while (temp != head1); printf("\n"); return 0; }
Write insertion and deletion functions to implement an output-restricted double-ended queue (deque).
Answer
An output-restricted double-ended queue (deque) is a type of double-ended queue where insertion operations can be performed at both the front and rear ends, but deletion operations are restricted to only one end (usually the front).This kind of deque allows for more flexible insertion while still maintaining the constraint of a traditional queue with respect to deletion. This structure is useful in scenarios where elements need to be added from both ends but only removed from one end, such as in certain scheduling or buffering algorithms.
cCopy code#include <stdio.h> #include <stdlib.h> #define MAX 100 // Define the structure for an output-restricted deque struct Deque { int arr[MAX]; int front, rear; }; // Function to initialize deque void initDeque(struct Deque* deque) { deque->front = -1; deque->rear = -1; } // Function to insert at the front of the deque void insertFront(struct Deque* deque, int item) { if ((deque->front == 0 && deque->rear == MAX - 1) || (deque->front == deque->rear + 1)) { printf("Deque is full\n"); return; } if (deque->front == -1) { deque->front = 0; deque->rear = 0; } else if (deque->front == 0) { deque->front = MAX - 1; } else { deque->front = deque->front - 1; } deque->arr[deque->front] = item; } // Function to insert at the rear of the deque void insertRear(struct Deque* deque, int item) { if ((deque->front == 0 && deque->rear == MAX - 1) || (deque->front == deque->rear + 1)) { printf("Deque is full\n"); return; } if (deque->front == -1) { deque->front = 0; deque->rear = 0; } else if (deque->rear == MAX - 1) { deque->rear = 0; } else { deque->rear = deque->rear + 1; } deque->arr[deque->rear] = item; } // Function to delete from the front of the deque int deleteFront(struct Deque* deque) { if (deque->front == -1) { printf("Deque is empty\n"); return -1; } int item = deque->arr[deque->front]; if (deque->front == deque->rear) { deque->front = -1; deque->rear = -1; } else if (deque->front == MAX - 1) { deque->front = 0; } else { deque->front = deque->front + 1; } return item; } // Example usage int main() { struct Deque deque; initDeque(&deque); // Inserting elements into the deque insertRear(&deque, 10); insertRear(&deque, 20); insertFront(&deque, 5); insertRear(&deque, 30); // Deleting elements from the front printf("Deleted from front: %d\n", deleteFront(&deque)); printf("Deleted from front: %d\n", deleteFront(&deque)); printf("Deleted from front: %d\n", deleteFront(&deque)); // Attempt to delete from an empty deque printf("Deleted from front: %d\n", deleteFront(&deque)); return 0; }
Explanation of the Code
Initialization (
initDeque
): Initializes the deque by setting bothfront
andrear
pointers to-1
, indicating that the deque is empty.Insertion at the Front (
insertFront
): Adds an element to the front of the deque. It adjusts thefront
pointer accordingly and handles cases where the deque is either full or empty.Insertion at the Rear (
insertRear
): Adds an element to the rear of the deque. Similar toinsertFront
, it adjusts therear
pointer and checks for full or empty conditions.Deletion from the Front (
deleteFront
): Removes an element from the front of the deque and returns it. If the deque becomes empty after the deletion, bothfront
andrear
pointers are reset to-1
.Output-Restricted Nature: The deletion operation is restricted to only the front of the deque, which is the defining characteristic of an output-restricted deque.
Given two singly linked lists, write the code to merge their nodes to make one list, taking nodes alternately between the two lists. If either list runs out, all the nodes should be taken from the other list.
Answer:
cCopy code#include <stdio.h> #include <stdlib.h> // Define the structure for a singly linked list node struct Node { int data; struct Node* next; }; // Function to merge two lists alternately struct Node* mergeAlternately(struct Node* list1, struct Node* list2) { if (!list1) return list2; if (!list2) return list1; struct Node* head = list1; struct Node* temp1 = list1->next; struct Node* temp2 = list2; struct Node* current = head; int toggle = 0; // To switch between lists while (temp1 && temp2) { if (toggle == 0) { current->next = temp2; temp2 = temp2->next; toggle = 1; } else { current->next = temp1; temp1 = temp1->next; toggle = 0; } current = current->next; } // Append the remaining nodes of either list current->next = (temp1) ? temp1 : temp2; return head; } // Helper function to create a new node struct Node* createNode(int data) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = data; newNode->next = NULL; return newNode; } // Helper function to print the list void printList(struct Node* head) { while (head) { printf("%d -> ", head->data); head = head->next; } printf("NULL\n"); } // Example usage int main() { // Creating two lists for demonstration struct Node* list1 = createNode(1); list1->next = createNode(2); list1->next->next = createNode(3); struct Node* list2 = createNode(7); list2->next = createNode(13); list2->next->next = createNode(1); struct Node* mergedList = mergeAlternately(list1, list2); printList(mergedList); return 0; }
Represent the following sparse matrix in the triplet form using the data structure array and linked list. Write the C-code or pseudo-code to add two sparse matrices using any of the representations.
Sparse Matrix:
Answer
Triplet Representation
The triplet form of a sparse matrix stores only the non-zero elements along with their row and column indices. This can be represented using an array or a linked list.
Triplet Array Representation: Each non-zero element is stored as a triplet (row, column, value).
For the given matrix, the triplet representation would be:
Adding Two Sparse Matrices
Assume we have two matrices
A
andB
in triplet form. The addition involves merging these two lists by adding values with the same row and column indices.// Node structure for linked list representation struct Node { int row, col, value; struct Node* next; }; // Function to add two sparse matrices struct Node* addSparseMatrices(struct Node* head1, struct Node* head2) { struct Node* head3 = NULL; struct Node* temp1 = head1; struct Node* temp2 = head2; struct Node* temp3 = NULL; while (temp1 != NULL && temp2 != NULL) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->next = NULL; if (temp1->row < temp2->row || (temp1->row == temp2->row && temp1->col < temp2->col)) { newNode->row = temp1->row; newNode->col = temp1->col; newNode->value = temp1->value; temp1 = temp1->next; } else if (temp2->row < temp1->row || (temp1->row == temp2->row && temp2->col < temp1->col)) { newNode->row = temp2->row; newNode->col = temp2->col; newNode->value = temp2->value; temp2 = temp2->next; } else { newNode->row = temp1->row; newNode->col = temp1->col; newNode->value = temp1->value + temp2->value; temp1 = temp1->next; temp2 = temp2->next; } if (head3 == NULL) { head3 = newNode; temp3 = head3; } else { temp3->next = newNode; temp3 = temp3->next; } } while (temp1 != NULL) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->row = temp1->row; newNode->col = temp1->col; newNode->value = temp1->value; newNode->next = NULL; temp3->next = newNode; temp3 = temp3->next; temp1 = temp1->next; } while (temp2 != NULL) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->row = temp2->row; newNode->col = temp2->col; newNode->value = temp2->value; newNode->next = NULL; temp3->next = newNode; temp3 = temp3->next; temp2 = temp2->next; } return head3; }
Write a program to insert
n
records (nodes) of student profiles in a double linked list such that the records or nodes will be present in ascending order of the student's CGPA. The student profile consists of roll number (int), name (string), and CGPA (float).
Answer#include <stdio.h> #include <stdlib.h> #include <string.h> // Structure to hold student profile struct Student { int rollNumber; char name[50]; float cgpa; struct Student* prev; struct Student* next; }; // Function to create a new node struct Student* createStudent(int rollNumber, char* name, float cgpa) { struct Student* newStudent = (struct Student*)malloc(sizeof(struct Student)); newStudent->rollNumber = rollNumber; strcpy(newStudent->name, name); newStudent->cgpa = cgpa; newStudent->prev = newStudent->next = NULL; return newStudent; } // Function to insert student in sorted order by CGPA void insertStudent(struct Student** head, int rollNumber, char* name, float cgpa) { struct Student* newStudent = createStudent(rollNumber, name, cgpa); if (*head == NULL) { *head = newStudent; return; } struct Student* current = *head; while (current != NULL && current->cgpa < cgpa) { current = current->next; } if (current == NULL) { // Insert at the end struct Student* temp = *head; while (temp->next != NULL) { temp = temp->next; } temp->next = newStudent; newStudent->prev = temp; } else { // Insert before the current node newStudent->next = current; newStudent->prev = current->prev; if (current->prev != NULL) { current->prev->next = newStudent; } else { *head = newStudent; // Update head if inserted at the beginning } current->prev = newStudent; } } // Function to display the list void displayList(struct Student* head) { while (head != NULL) { printf("Roll Number: %d, Name: %s, CGPA: %.2f\n", head->rollNumber, head->name, head->cgpa); head = head->next; } } // Example usage int main() { struct Student* head = NULL; insertStudent(&head, 101, "Alice", 8.5); insertStudent(&head, 102, "Bob", 7.8); insertStudent(&head, 103, "Charlie", 9.1); insertStudent(&head, 104, "David", 8.0); printf("Students in ascending order of CGPA:\n"); displayList(head); return 0; }
Write a C-code or pseudo-code that will create a new linked list by removing alternative nodes from the given linear linked list. Display the resultant two linked lists (old and new).
Input Example:
2 -> 5 -> 3 -> 7 -> 8
Output:Old List: 5 -> 7
New List: 2 -> 3 -> 8
Answer
#include <stdio.h> #include <stdlib.h> // Define the structure for a linked list 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)); newNode->data = data; newNode->next = NULL; return newNode; } // Function to split the list into two lists by removing alternate nodes void splitAlternateNodes(struct Node* head, struct Node** newList) { struct Node* current = head; *newList = head; // Initialize new list with the head while (current != NULL && current->next != NULL) { struct Node* temp = current->next; current->next = temp->next; current = current->next; temp->next = NULL; // Isolate the removed node } } // Function to print a linked list void printList(struct Node* head) { while (head != NULL) { printf("%d -> ", head->data); head = head->next; } printf("NULL\n"); } // Example usage int main() { // Creating a linked list for demonstration struct Node* head = createNode(2); head->next = createNode(5); head->next->next = createNode(3); head->next->next->next = createNode(7); head->next->next->next->next = createNode(8); printf("Original List:\n"); printList(head); struct Node* newList = NULL; splitAlternateNodes(head, &newList); printf("Old List after removal of alternate nodes:\n"); printList(head); printf("New List with removed nodes:\n"); printList(newList); return 0; }
- What is the time complexity of the function
func()
?
- What is the time complexity of the function
void func(int arr[], int n) {
int i, j = 0;
for (i = 0; i < n; i++) {
while (j < n && arr[i] < arr[j]) {
j++;
}
}
}
Answer
The time complexity is O(n). This is because the outer loop runs n
times, and the inner loop's total number of executions across all iterations of the outer loop is also at most n
.
- A matrix
M[1...n, 1...n]
is initialized as:M[i][j] = i - j
for alli, j
,1 ≤ i ≤ n; 1 ≤ j ≤ n
. Write a code for initializingM
and find the sum of all the elements of the matrixM
. If the value ofn
is 100, then what is the sum of all the elements of the matrixM
?
Answer
#include <stdio.h>
int main() {
int n = 100;
int M[100][100];
int sum = 0;
// Initialize the matrix and compute the sum
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
M[i][j] = i - j;
sum += M[i][j];
}
}
printf("Sum of all elements in the matrix M: %d\n", sum);
return 0;
}
For n = 100
, the sum is 0.
Let a doubly linked list consist of 20 elements. If a pointer called
ptr
is pointing to the 5th node of the list, then write a code to swap the 5th and 6th nodes of the list without using any additional pointer variable and without changing theptr
's position.Define data structure and Abstract Data Type. Implement PUSH and POP operations of STACK ADT.
Answer
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
typedef struct Stack {
int arr[MAX];
int top;
} Stack;
// Initialize stack
void initialize(Stack* stack) {
stack->top = -1;
}
// Check if stack is empty
int isEmpty(Stack* stack) {
return stack->top == -1;
}
// Check if stack is full
int isFull(Stack* stack) {
return stack->top == MAX - 1;
}
// Push operation
void push(Stack* stack, int value) {
if (isFull(stack)) {
printf("Stack Overflow\n");
return;
}
stack->arr[++stack->top] = value;
}
// Pop operation
int pop(Stack* stack) {
if (isEmpty(stack)) {
printf("Stack Underflow\n");
return -1;
}
return stack->arr[stack->top--];
}
// Example usage
int main() {
Stack stack;
initialize(&stack);
push(&stack, 10);
push(&stack, 20);
printf("Popped: %d\n", pop(&stack));
printf("Popped: %d\n", pop(&stack));
return 0;
}
- What does the following function do for the linked list:
10 -> 20 -> 30 -> 40 -> 50
?
void func(struct Node* start) {
if (start == NULL) return;
func(start->next);
printf("%d ", start->data);
func(start->next);
}
25. Design a suitable data structure to efficiently represent a sparse matrix? Write an algorithm to add the original sparse matrix with the transpose of the same matrix.
Answer
To efficiently represent a sparse matrix using the triplet form, we can design a data structure that uses an array of struct Triplet
. Each Triplet
will store the row index, column index, and value of a non-zero element. To add the original sparse matrix with its transpose, we will use this data structure to perform matrix operations.
Define a
struct
to hold each non-zero element's row index, column index, and value.Use an array of this struct to represent the entire sparse matrix.
#include <stdio.h>
#include <stdlib.h>
// Define a struct for the triplet representation
struct Triplet {
int row;
int col;
int value;
};
// Function to display the triplet representation
void displayTriplets(struct Triplet* spMatrix, int nonZeroCount) {
printf("Row Column Value\n");
for (int i = 0; i < nonZeroCount; i++) {
printf("%d %d %d\n", spMatrix[i].row, spMatrix[i].col, spMatrix[i].value);
}
}
// Function to transpose a sparse matrix
void transposeSparseMatrix(struct Triplet* spMatrix, struct Triplet* transposeMatrix, int nonZeroCount) {
for (int i = 0; i < nonZeroCount; i++) {
transposeMatrix[i].row = spMatrix[i].col;
transposeMatrix[i].col = spMatrix[i].row;
transposeMatrix[i].value = spMatrix[i].value;
}
}
// Function to add two sparse matrices
void addSparseMatrices(struct Triplet* spMatrix, struct Triplet* transposeMatrix, struct Triplet* resultMatrix, int nonZeroCount, int* resultCount) {
int i = 0, j = 0, k = 0;
while (i < nonZeroCount && j < nonZeroCount) {
if (spMatrix[i].row < transposeMatrix[j].row ||
(spMatrix[i].row == transposeMatrix[j].row && spMatrix[i].col < transposeMatrix[j].col)) {
resultMatrix[k++] = spMatrix[i++];
} else if (transposeMatrix[j].row < spMatrix[i].row ||
(transposeMatrix[j].row == spMatrix[i].row && transposeMatrix[j].col < spMatrix[i].col)) {
resultMatrix[k++] = transposeMatrix[j++];
} else {
resultMatrix[k].row = spMatrix[i].row;
resultMatrix[k].col = spMatrix[i].col;
resultMatrix[k].value = spMatrix[i].value + transposeMatrix[j].value;
i++; j++; k++;
}
}
// Add remaining elements
while (i < nonZeroCount) {
resultMatrix[k++] = spMatrix[i++];
}
while (j < nonZeroCount) {
resultMatrix[k++] = transposeMatrix[j++];
}
*resultCount = k; // Update the count of non-zero elements in the result
}
int main() {
// Example sparse matrix in triplet form
struct Triplet spMatrix[] = {
{0, 2, 3},
{1, 0, 4},
{2, 1, 5},
{2, 3, 7}
};
int nonZeroCount = sizeof(spMatrix) / sizeof(spMatrix[0]);
printf("Original Matrix in Triplet Form:\n");
displayTriplets(spMatrix, nonZeroCount);
// Array to store the transpose matrix
struct Triplet transposeMatrix[nonZeroCount];
transposeSparseMatrix(spMatrix, transposeMatrix, nonZeroCount);
printf("\nTranspose Matrix in Triplet Form:\n");
displayTriplets(transposeMatrix, nonZeroCount);
// Array to store the result of addition
struct Triplet resultMatrix[2 * nonZeroCount]; // In worst case, result can have at most 2 * nonZeroCount elements
int resultCount = 0;
// Add the original matrix and its transpose
addSparseMatrices(spMatrix, transposeMatrix, resultMatrix, nonZeroCount, &resultCount);
printf("\nResultant Matrix after Adding Original and Transpose:\n");
displayTriplets(resultMatrix, resultCount);
return 0;
}
Explanation:
Struct Definition (
Triplet
):- Defines a structure to store the row index, column index, and value of each non-zero element in the sparse matrix.
Array of Structs (
spMatrix
):- Represents the sparse matrix as an array of
Triplet
structs, where each struct contains the row, column, and value of a non-zero element.
- Represents the sparse matrix as an array of
Function
displayTriplets()
:- Takes the array of triplets and the count of non-zero elements and prints the triplet form of the matrix.
Function
transposeSparseMatrix()
:- Computes the transpose of the sparse matrix by swapping the row and column indices for each triplet.
Function
addSparseMatrices()
:Adds the original sparse matrix and its transpose by comparing the row and column indices of each element.
Merges the two arrays in sorted order based on row and column indices.
Main Function (
main()
):- Initializes the sparse matrix in triplet form, displays it, computes the transpose, adds the original matrix with its transpose, and then displays the result.
- Write a pseudo code/function to reverse only even position nodes' values in a Singly Linked List.
Answer
#include <stdio.h> #include <stdlib.h> // Define the structure for a singly linked list 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)); newNode->data = data; newNode->next = NULL; return newNode; } // Function to find the length of the list int getLength(struct Node* head) { int length = 0; struct Node* current = head; while (current != NULL) { length++; current = current->next; } return length; } // Function to reverse values at even positions void reverseEvenPositionValues(struct Node* head) { int length = getLength(head); if (length < 2) return; // No even positions to reverse struct Node *left = head, *right = head; int leftIndex = 2, rightIndex = length - (length % 2); // Move right pointer to the last even position for (int i = 1; i < rightIndex; i++) { right = right->next; } while (leftIndex < rightIndex) { struct Node* tempLeft = left; struct Node* tempRight = right; // Move left pointer to the next even position for (int j = 1; j < leftIndex; j++) { tempLeft = tempLeft->next; } // Move right pointer to the previous even position for (int j = length; j > rightIndex; j--) { tempRight = tempRight->next; } // Swap the values int temp = tempLeft->data; tempLeft->data = tempRight->data; tempRight->data = temp; // Update indices for next even positions leftIndex += 2; rightIndex -= 2; } } // Function to print the linked list void printList(struct Node* head) { while (head != NULL) { printf("%d -> ", head->data); head = head->next; } printf("NULL\n"); } // Example usage int main() { struct Node* head = createNode(1); head->next = createNode(2); head->next->next = createNode(3); head->next->next->next = createNode(4); head->next->next->next->next = createNode(5); head->next->next->next->next->next = createNode(6); printf("Original List:\n"); printList(head); reverseEvenPositionValues(head); printf("\nList after reversing even position nodes' values:\n"); printList(head); return 0; }