DATA STRUCTURE

Q1) Attempt any EIGHT of the following. [8×2=16]

1) **What is self-referential structure?**
A structure that contains a pointer to a structure of the same type is called
a self-referential structure.

2) **What are the different types of graph?**

The different types of graphs are:
- Directed Graph
- Undirected Graph
- Weighted Graph
- Unweighted Graph
- Connected Graph
- Disconnected Graph

3) **What are the applications of stack?**

Applications of stack include:
- Function calls (recursion)
- Expression evaluation (infix to postfix)
- Undo operations in text editors
- Depth-first search (DFS) in graph traversal

4) **List out different types of tree.**

 Types of trees include:
- Binary Tree
- Binary Search Tree (BST)
- AVL Tree
- Red-Black Tree
- B-tree
- Heap

5) **What is searching?**
Searching is the process of finding the location of a specific element in a
collection of elements.

6) **What is pointer to pointer?**

A pointer to pointer is a pointer that stores the address of another pointer.

7) **What is non-primitive data structure?**

Non-primitive data structures are derived from primitive data types, such
as arrays, lists, stacks, and queues.

8) **Define Data structure.**

A data structure is a way of organizing and storing data efficiently for
operations like retrieval and modification.

9) **What is sorting? State the techniques of sorting.**

 Sorting is the process of arranging data in a specific order (ascending or
descending). The techniques of sorting include:
- Bubble Sort
- Selection Sort
- Insertion Sort
- Merge Sort
- Quick Sort

10) **What is almost complete binary tree?**

An almost complete binary tree is a binary tree where all levels are
completely filled except possibly for the last level, which is filled from the
left.

11) **How to measure performance of an algorithm?**

The performance of an algorithm is measured in terms of time complexity
and space complexity, based on the number of steps and memory usage.

12) **What is polynomial? How is it different from structure?**

A polynomial is an expression consisting of variables and coefficients. A
structure is a collection of variables under one name in programming
languages like C, and it can store different data types.

13) **What is balance factor? How is it calculated?**

The balance factor is the difference between the heights of the left and
right subtrees in an AVL tree. It is calculated as:
 \[
\text{Balance Factor} = \text{Height of left subtree} - \text{Height of right
subtree}
\]

14) **What are Abstract Data Types (ADT)?**

Abstract Data Types are models for data structures that specify the type
of data stored, the operations supported, and the types of parameters
without specifying how the operations are implemented.

15) **What is Ancestor of Node?**

An ancestor of a node is any node that appears on the path from the root
to that node in a tree.

16) **State the types of graph.**

The types of graphs are:
- Directed Graph
- Undirected Graph
- Weighted Graph
- Unweighted Graph
- Cyclic Graph
- Acyclic Graph

17) **Differentiate array and structure.**

 - Array: A collection of elements of the same data type.
- Structure: A collection of elements of different data types.

18) **What is space and time complexity?**

- Time complexity: The time required by an algorithm as a function of
input size.
- Space complexity: The memory required by an algorithm as a function of
input size.

19) **What is pointer to pointer? What is spanning tree?**

- Pointer to pointer: A pointer that points to another pointer.
- Spanning tree: A subgraph of a graph that includes all vertices and is a
tree.

20) **What are the advantages of linked list over an array?**

The advantages of linked lists over arrays include:
- Dynamic size
- Ease of insertions and deletions
- No need for contiguous memory allocation

21) **How to measure performance of an algorithm?**

The performance of an algorithm is measured by time complexity
(execution time) and space complexity (memory usage).
22) **What is adjacency matrix?**
An adjacency matrix is a 2D array used to represent a graph, where
matrix[i][j] indicates if there is an edge between vertex i and vertex j.

23) **What is complete binary tree?**

A complete binary tree is a binary tree where every level is fully filled, and
all nodes are as far left as possible.

24) **What is Priority queue?**

A priority queue is a data structure where each element has a priority, and
elements with higher priority are dequeued before elements with lower
priority.

25) **State the difference between stack & linked list.**

- Stack: A linear data structure with LIFO (Last In First Out) order.
- Linked List: A sequence of nodes where each node points to the next.

26) **What is the need for the header?**

The header file provides function declarations, macros, constants, and
data type definitions that are shared between different program files.

27) **What is balance factor? How is it calculated?**

The balance factor is the difference between the height of the left and
right subtree in an AVL tree. It is calculated as:
\[
 \text{Balance Factor} = \text{Height of left subtree} - \text{Height of right
subtree}
\]

28) **What is data structure?**

A data structure is an organized format for storing and managing data to
enable efficient access and modification.

29) **Mention the features of ADT.**

Features of Abstract Data Types (ADT) include:
- Encapsulation
- Abstraction
- Defined operations
- Hidden implementation details

30) **What are the types of linked list?**

The types of linked lists are:
- Singly Linked List
- Doubly Linked List
- Circular Linked List

31) **List down the applications of list.**

Applications of lists include:
- Dynamic memory allocation
 - Implementing stacks and queues
- Handling polynomial expressions

32) **What is polynomial? How is it represented?**

A polynomial can be represented using arrays or linked lists where each
node contains a coefficient and an exponent.

33) **Differentiate array & structure.**

- Array: A collection of homogeneous elements (same data type).
- Structure: A collection of heterogeneous elements (different data types).

Q2) Attempt any FOUR of the following. [4x4=16]

### 1) **What is a height-balanced tree? Explain LL and LR rotations with
an example.**
A height-balanced tree is a binary tree where the difference in height
between the left and right subtrees of any node is at most 1. This is also
known as an AVL tree.
- **LL Rotation**: It occurs when a node is inserted into the left subtree of
the left child, causing an imbalance. The rotation shifts nodes to the right.
**Example**:
Before rotation:
30
/
20
 /
10
After LL Rotation:
20
/ \
10 30
- **LR Rotation**: It occurs when a node is inserted into the right subtree of
the left child, causing an imbalance. It requires two rotations: left rotation
on the left child followed by right rotation on the root.
**Example**:
Before rotation:
30
/
10
\
20
After LR Rotation:
20
/ \
10 30
### 2) **Explain selection sort technique with an example.**
Selection Sort is a sorting algorithm that repeatedly selects the smallest (or
largest) element from the unsorted part of the array and swaps it with the
first unsorted element.
**Algorithm**:
1. Start from the first element.
2. Find the smallest element in the unsorted part.
3. Swap it with the first unsorted element.
4. Repeat the process for all elements until the array is sorted.
**Example**:
For array: `[64, 25, 12, 22, 11]`
Pass 1: `[11, 25, 12, 22, 64]`
Pass 2: `[11, 12, 25, 22, 64]`
Pass 3: `[11, 12, 22, 25, 64]`
Pass 4: `[11, 12, 22, 25, 64]`

### 3) **What is stack? Explain different operations used in stack.**

A stack is a linear data structure that follows the Last In, First Out (LIFO)
principle.
**Operations**:
1. **Push**: Add an element to the top of the stack.
2. **Pop**: Remove and return the top element of the stack.
3. **Peek**: Return the top element without removing it.
4. **isEmpty**: Check if the stack is empty.
5. **isFull**: Check if the stack is full (in a fixed-size implementation).
### 4) **What is Graph? Explain adjacency list of a graph.**
A graph is a data structure consisting of a set of nodes (vertices) and edges
that connect pairs of nodes.
- **Adjacency List**: It is a way of representing a graph using an array or list
where each element corresponds to a node and stores a list of its adjacent
nodes.
**Example** (Graph with vertices A, B, C, D):
A -> B, C
B -> A, D
C -> A
D -> B

### 5) **Write an algorithm to convert a given infix expression to a postfix

expression.**
**Algorithm**:
1. Initialize an empty stack and an empty output list.
2. Traverse the infix expression from left to right.
3. If the character is an operand, add it to the output list.
4. If the character is an operator, pop from the stack to the output list until
the top of the stack has an operator of lower precedence, then push the
current operator onto the stack.
5. If the character is '(', push it onto the stack.
6. If the character is ')', pop from the stack to the output until '(' is
encountered.
7. At the end of the expression, pop all remaining operators from the stack
to the output.

### 6) **Explain Insertion sort technique with an example.**

Insertion Sort is a sorting algorithm where elements are picked from an
unsorted array and inserted into their correct position in the sorted part of
the array.
**Example**:
For array `[12, 11, 13, 5, 6]`:
Step 1: `[11, 12, 13, 5, 6]`
Step 2: `[11, 12, 13, 5, 6]`
Step 3: `[5, 11, 12, 13, 6]`
Step 4: `[5, 6, 11, 12, 13]`

### 7) **What is circular queue? How does it differ from a static queue?**
A circular queue is a linear data structure in which the last position is
connected to the first position, forming a circle.
**Difference from static queue**:
- In a circular queue, when the rear reaches the end of the queue, it wraps
around to the front if there is free space, whereas in a static queue, this
wrap-around does not occur, and rear cannot move beyond the last index.

### 8) **What is stack? What are the various applications of stack? List
operations performed on stack.**
A stack is a linear data structure based on the LIFO principle.
**Applications**:
- Function call management
- Expression evaluation (postfix, prefix)
- Undo functionality in software
- Depth-first search in graph traversal
**Operations**:
- **Push**: Insert an element.
- **Pop**: Remove and return the top element.
- **Peek**: View the top element without removing.
- **isEmpty**: Check if the stack is empty.

### 9) **Explain different types of AVL rotations with an example.**

In AVL trees, rotations are used to maintain balance after insertions or
deletions.
- **LL Rotation**: Used when the left subtree of the left child is imbalanced.
- **LR Rotation**: First left rotation on the left child, then right rotation on
the root.
- **RR Rotation**: Used when the right subtree of the right child is
imbalanced.
- **RL Rotation**: First right rotation on the right child, then left rotation on
the root
### 10) **Explain various types of Dynamic Memory Allocation
functions.**
1. **malloc()**: Allocates memory block of specified size and returns a void
pointer.
2. **calloc()**: Allocates memory for an array of elements, initializes to
zero, and returns a pointer.
3. **realloc()**: Resizes previously allocated memory.
4. **free()**: Deallocates memory previously allocated by malloc, calloc, or
realloc.

### 11) **What is height-balanced tree? Explain RR and RL rotations with

an example.**
A height-balanced tree is a tree where the difference in height between the
left and right subtrees of any node is at most 1.
- **RR Rotation**: Happens when a node is inserted into the right subtree
of the right child. A left rotation is performed to restore balance.
Before rotation:
10
\
20
\
30
After RR Rotation:
20
/ \
10 30
- **RL Rotation**: Happens when a node is inserted into the left subtree of
the right child. First, a right rotation on the right child is performed, followed
by a left rotation on the root.
### 12) **What is linked list? Explain its types in detail.**
A linked list is a dynamic data structure where elements (nodes) are
connected using pointers.
**Types**:
1. **Singly Linked List**: Each node points to the next node.
2. **Doubly Linked List**: Each node points to both the previous and the
next node.
3. **Circular Linked List**: The last node points to the first node, forming a
loop.

### 13) **Explain different types of asymptotic notation in detail.**

Asymptotic notations describe the time complexity of algorithms:
1. **O (Big-O)**: Represents the upper bound, worst-case complexity.
2. **Ω (Big-Omega)**: Represents the lower bound, best-case complexity.
3. **Θ (Big-Theta)**: Represents the exact bound, average case complexity.
4. **o (little-o)**: Represents a strict upper bound.
5. **ω (little-omega)**: Represents a strict lower bound.

### 14) **Differentiate array and structure.**

- **Array**: A collection of elements of the same data type.
- **Structure**: A collection of elements of different data types grouped
under a single name.
### 15) **Explain Linear Data structure with examples.**
Linear data structures store data sequentially.
**Examples**:
- **Array**: Fixed-size collection of elements of the same type.
- **Linked List**: Dynamic data structure where elements (nodes) are
connected using pointers.
- **Stack**: Follows LIFO principle for data access.
- **Queue**: Follows FIFO principle for data access.

### 16) **What is algorithm? Explain its characteristics.**

An algorithm is a step-by-step procedure to solve a problem or perform a
computation.
**Characteristics**:
1. **Input**: Takes zero or more inputs.
2. **Output**: Produces at
least one output.
3. **Definiteness**: Clear and unambiguous steps.
4. **Finiteness**: Should terminate after a finite number of steps.
5. **Effectiveness**: Each step should be simple and doable.

Q3) Attempt any Four of the following. [4x4=16]

### 1) **Function to create and display a circular singly linked list**
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
void createCircularLinkedList(struct Node** head, int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
if (*head == NULL) {
*head = newNode;
newNode->next = *head;
} else {
struct Node* temp = *head;
while (temp->next != *head) {
temp = temp->next;
}
temp->next = newNode;
newNode->next = *head;
}
}
void displayCircularLinkedList(struct Node* head) {
if (head == NULL) return;
struct Node* temp = head;
 do {
printf("%d -> ", temp->data);
temp = temp->next;
} while (temp != head);
printf("HEAD\n");
}
int main() {
struct Node* head = NULL;
createCircularLinkedList(&head, 10);
createCircularLinkedList(&head, 20);
createCircularLinkedList(&head, 30);
displayCircularLinkedList(head);
return 0;
}

### 2) **Function for dynamic implementation of stack**

#include <stdio.h>
#include <stdlib.h>
struct StackNode {
int data;
struct StackNode* next;
};
struct StackNode* newNode(int data) {
 struct StackNode* stackNode = (struct StackNode*)malloc(sizeof(struct
StackNode));
stackNode->data = data;
stackNode->next = NULL;
return stackNode;
}
int isEmpty(struct StackNode* root) {
return !root;
}
void push(struct StackNode** root, int data) {
struct StackNode* stackNode = newNode(data);
stackNode->next = *root;
*root = stackNode;
printf("%d pushed to stack\n", data);
}
int pop(struct StackNode** root) {
if (isEmpty(*root))
return -1;
struct StackNode* temp = *root;
*root = (*root)->next;
int popped = temp->data;
free(temp);
return popped;
}
int peek(struct StackNode* root) {
if (isEmpty(root))
return -1;
return root->data;
}
int main() {
struct StackNode* root = NULL;
push(&root, 10);
push(&root, 20);
push(&root, 30);
printf("%d popped from stack\n", pop(&root));
printf("Top element is %d\n", peek(root));
return 0;
}

### 3) **Function to traverse a graph using DFS technique**

#include <stdio.h>
#include <stdlib.h>
#define MAX 100
int visited[MAX] = {0};
struct Graph {
int vertices;
 int adj[MAX][MAX];
};
void DFS(struct Graph* graph, int startVertex) {
printf("%d -> ", startVertex);
visited[startVertex] = 1;
for (int i = 0; i < graph->vertices; i++) {
if (graph->adj[startVertex][i] == 1 && !visited[i]) {
DFS(graph, i);
}
}
}
int main() {
struct Graph graph;
[Link] = 4;
int adjMatrix[4][4] = {
{0, 1, 1, 0},
{1, 0, 0, 1},
{1, 0, 0, 1},
{0, 1, 1, 0}
};
for (int i = 0; i < [Link]; i++) {
for (int j = 0; j < [Link]; j++) {
[Link][i][j] = adjMatrix[i][j];
 }
}
printf("DFS Traversal starting from vertex 0:\n");
DFS(&graph, 0);
return 0;
}

### 4) **Function to remove a given node from a singly linked list and add
it at the given position**
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
void insertAtPosition(struct Node** head, int data, int position) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
if (position == 1) {
newNode->next = *head;
*head = newNode;
return;
}
 struct Node* temp = *head;
for (int i = 1; i < position - 1; i++) {
temp = temp->next;
}
newNode->next = temp->next;
temp->next = newNode;
}
void deleteNode(struct Node** head, int key) {
struct Node* temp = *head;
struct Node* prev = NULL;
if (temp != NULL && temp->data == key) {
*head = temp->next;
free(temp);
return;
}
while (temp != NULL && temp->data != key) {
prev = temp;
temp = temp->next;
}
if (temp == NULL) return;
prev->next = temp->next;
free(temp);
}
void display(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
int main() {
struct Node* head = NULL;
insertAtPosition(&head, 10, 1);
insertAtPosition(&head, 20, 2);
insertAtPosition(&head, 30, 3);
display(head);
deleteNode(&head, 20);
insertAtPosition(&head, 20, 2);
display(head);
return 0;
}
### 5) **Function to check whether a given string is a palindrome using
Stack**
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX 100
struct Stack {
int top;
char arr[MAX];
};
void push(struct Stack* stack, char ch) {
stack->arr[++stack->top] = ch;
}
char pop(struct Stack* stack) {
return stack->arr[stack->top--];
}
int isPalindrome(char str[]) {
int n = strlen(str);
struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
stack->top = -1;
for (int i = 0; i < n; i++) {
push(stack, str[i]);
}
 for (int i = 0; i < n; i++) {
if (str[i] != pop(stack)) {
return 0; // Not palindrome
}
}
return 1; // Palindrome
}
int main() {
char str[] = "madam";
if (isPalindrome(str))
printf("%s is a palindrome\n", str);
else
printf("%s is not a palindrome\n", str);
return 0;
}

### 6) **Function to create and display a doubly linked list**

#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
void createDoublyLinkedList(struct Node** head, int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
newNode->prev = NULL;
if (*head == NULL) {
*head = newNode;
} else {
struct Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
newNode->prev = temp;
}
}
void displayDoublyLinkedList(struct Node* head) {
struct Node* temp = head;
printf("NULL <- ");
while (temp != NULL) {
printf("%d", temp->data);
if (temp->next != NULL) {
 printf(" <-> ");
}
temp = temp->next;
}
printf(" -> NULL\n");
}
int main() {
struct Node* head = NULL;
createDoublyLinkedList(&head, 10);
createDoublyLinkedList(&head, 20);
createDoublyLinkedList(&head, 30);
displayDoublyLinkedList(head);
return 0;
}

### 7) **Recursive functions for inorder, preorder, and postorder

traversal**
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* left;
struct Node* right;
};
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;
}
void inorder(struct Node* root) {
if (root == NULL) return;
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
void preorder(struct Node* root) {
if (root == NULL) return;
printf("%d ", root->data);
preorder(root->left);
preorder(root->right);
}
void postorder(struct Node* root) {
if (root == NULL) return;
postorder(root->left);
 postorder(root->right);
printf("%d ", root->data);
}
int main() {
struct Node* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
printf("Inorder Traversal: ");
inorder(root);
printf("\n");
printf("Preorder Traversal: ");
preorder(root);
printf("\n");
printf("Postorder Traversal: ");
postorder(root);
printf("\n");
return 0;
}

### 8) **Function to delete the first node from a singly linked list**
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
void deleteFirstNode(struct Node** head) {
if (*head == NULL) return;
struct Node* temp = *head;
*head = (*head)->next;
free(temp);
}
void display(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
int main() {
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
head->data = 10;
head->next = (struct Node*)malloc(sizeof(struct Node));
 head->next->data = 20;
head->next->next = NULL;
printf("Original List: ");
display(head);
deleteFirstNode(&head);
printf("After Deleting First Node: ");
display(head);
return 0;
}

### 9) **Function to reverse a string using stack**

#include <stdio.h>
#include <string.h>
#define MAX 100
struct Stack {
int top;
char arr[MAX];
};
void push(struct Stack* stack, char ch) {
stack->arr[++stack->top] = ch;
}
char pop(struct Stack* stack) {
return stack->arr[stack->top--];
}
void reverseString(char str[]) {
struct Stack stack;
[Link] = -1;
int n = strlen(str);
for (int i = 0; i < n; i++) {
push(&stack, str[i]);
}
for (int i = 0; i < n; i++) {
str[i] = pop(&stack);
}
}
int main() {
char str[] = "Hello";
printf("Original String: %s\n", str);
reverseString(str);
printf("Reversed String: %s\n", str);
return 0;
}

### 10) **C program for the evaluation of polynomial**

#include <stdio.h>
#include <math.h>
float evaluatePolynomial(float coeff[], int degree, float x) {
float result = 0.0;
for (int i = 0; i <= degree; i++) {
result += coeff[i] * pow(x, i);
}
return result;
}
int main() {
int degree = 3;
float coeff[] = {2, -6, 3, 5}; // Polynomial: 5x^3 + 3x^2 - 6x + 2
float x = 2.0;
printf("Value of the polynomial at x = %.2f: %.2f\n", x,
evaluatePolynomial(coeff, degree, x));
return 0;
}

### 11) **Function to insert an element into a circular queue

(implemented as array)**
#include <stdio.h>
#define SIZE 5
int queue[SIZE];
int front = -1, rear = -1;
int isFull() {
return (front == (rear + 1) % SIZE);
}
int isEmpty() {
return (front == -1);
}
void enqueue(int value) {
if (isFull()) {
printf("Queue is full\n");
} else {
if (front == -1) front = 0;
rear = (rear + 1) % SIZE;
queue[rear] = value;
printf("%d enqueued\n", value);
}
}
void display() {
if (isEmpty()) {
printf("Queue is empty\n");
} else {
printf("Queue: ");
int i = front;
while (i != rear) {
printf("%d ", queue[i]);
i = (i + 1) % SIZE;
 }
printf("%d\n", queue[rear]);
}
}
int main() {
enqueue(10);
enqueue(20);
enqueue(30);
enqueue(40);
enqueue(50); // Queue is now full
display();
return 0;
}

### 12) **Function for inorder traversal of a tree**

#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* left;
struct Node* right;
};
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;
}
void inorderTraversal(struct Node* root) {
if (root == NULL) return;
inorderTraversal(root->left);
printf("%d ", root->data);
inorderTraversal(root->right);
}
int main() {
struct Node* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
printf("Inorder Traversal: ");
inorderTraversal(root);
printf("\n");
return 0;}
### 13) **Function to search an element from an array using binary
search**
#include <stdio.h>
int binarySearch(int arr[], int size, int target) {
int left = 0, right = size - 1
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target)
return mid;
if (arr[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
return -1; // Element not found
}
int main() {
int arr[] = {2, 5, 8, 12, 16, 23, 38, 45, 56, 72};
int size = sizeof(arr) / sizeof(arr[0]);
int target = 23;
int result = binarySearch(arr, size, target);

if (result != -1)
 printf("Element %d found at index %d\n", target, result);
else
printf("Element %d not found\n", target);
return 0;
}

### 14) **Function to create & display a singly linked list**

#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node* next;
};
void createLinkedList(struct Node** head, int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
if (*head == NULL) {
*head = newNode;
} else {
struct Node* temp = *head;
while (temp->next != NULL) {
 temp = temp->next;
}
temp->next = newNode;
}
}
void displayLinkedList(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
int main() {
struct Node* head = NULL;
createLinkedList(&head, 10);
createLinkedList(&head, 20);
createLinkedList(&head, 30);
displayLinkedList(head);
return 0;
}
### 15) **Function to insert an element into a queue (implemented as
array)**
#include <stdio.h>
#define SIZE 5
int queue[SIZE];
int front = -1, rear = -1;
int isFull() {
return (rear == SIZE - 1);
}
int isEmpty() {
return (front == -1);
void enqueue(int value) {
if (isFull()) {
printf("Queue is full\n");
} else {
if (front == -1) front = 0;
queue[++rear] = value;
printf("%d enqueued\n", value);
}
}
void display() {
if (isEmpty()) {
printf("Queue is empty\n");
 } else {
printf("Queue: ");
for (int i = front; i <= rear; i++) {
printf("%d ", queue[i]);
}
printf("\n");
}
}
int main() {
enqueue(10);
enqueue(20);
enqueue(30);
display();
return 0;
}

### 16) **Explain BFS traversing technique with an example**

**Breadth-First Search (BFS)** is a graph traversal technique that starts
from a selected node (usually the root or any arbitrary node) and explores
the neighbor nodes first, before moving on to the next level neighbors.
#### Example of BFS on a graph:
Consider the following graph:
1 -- 2 -- 3
| |
 4 -- 5
1. **Queue initialization**: Start from node 1, mark it as visited, and
enqueue it.
2. **Visit neighbors**: Dequeue node 1 and visit its neighbors (2 and 4).
Enqueue them and mark them as visited.
3. **Next level**: Dequeue node 2 and visit its neighbor 3. Enqueue it and
mark it as visited. Continue this process until all nodes are visited.
BFS will visit nodes in the following order for this example: `1 -> 2 -> 4 -> 3 ->
5`.

### 17) **Algorithm to convert infix expression to postfix expression**

#### Infix to Postfix Conversion Algorithm:
1. **Initialize**:
- Create an empty stack and an empty output string.
- Scan the infix expression from left to right
2. **Operand**:
- If the scanned character is an operand, append it to the output string.
3. **Operator**:
- If the scanned character is an operator, pop from the stack and append
to the output string until the top of the stack has an operator with less
precedence or the stack is empty.
- Push the scanned operator to the stack.
4. **Parentheses**:
- If the scanned character is '(', push it to the stack.
 - If the scanned character is ')', pop from the stack and append to the
output string until '(' is found. Discard the '('.
5. **End**:
- After the entire infix expression has been scanned, pop all operators
from the stack and append them to the output string.
#### Example:
Infix Expression:
`A + B * (C - D)`
Postfix Expression:
`A B C D - * +`

Q4) Attempt any Four of the following. [4×4=16]

### 1) **Sort the following data using insertion sort: 18, 7, 22, 3, 14, 2**
**Insertion Sort Algorithm:**
1. Start with the second element in the array (i.e., 7).
2. Compare it with the element before it and insert it into the correct
position.
3. Continue this process for all elements until the entire array is sorted.
**Steps**:
- Initial Array: `[18, 7, 22, 3, 14, 2]`
- Step 1: Compare 7 with 18 → Insert 7 before 18 → `[7, 18, 22, 3, 14, 2]`
- Step 2: Compare 22 with 18 → No change needed → `[7, 18, 22, 3, 14, 2]`
- Step 3: Compare 3 with 22, 18, and 7 → Insert 3 at the beginning → `[3, 7,
18, 22, 14, 2]`
- Step 4: Compare 14 with 22, 18, and 7 → Insert 14 after 7 → `[3, 7, 14, 18,
22, 2]`
- Step 5: Compare 2 with 22, 18, 14, 7, and 3 → Insert 2 at the beginning →
`[2, 3, 7, 14, 18, 22]`
**Sorted Array**: `[2, 3, 7, 14, 18, 22]`

### 2) **Construct Binary Search Tree of following data: 15, 30, 20, 5, 10,
2, 7**
To construct a Binary Search Tree (BST), we insert elements such that:
- The left subtree contains nodes with values less than the node's key.
- The right subtree contains nodes with values greater than the node's key.
**Steps**:
1. Start with 15 as the root.
2. Insert 30 to the right of 15.
3. Insert 20 to the left of 30.
4. Insert 5 to the left of 15.
5. Insert 10 to the right of 5.
6. Insert 2 to the left of 5.
7. Insert 7 to the right of 5 and left of 10.
**Binary Search Tree**:
```
15
/ \
5 30
 /\ /
2 10 20
/
7

### 3) **Construct an AVL tree of the following data: SRI, IND, AUS, FRA,
CAN, DEN**
An AVL tree is a self-balancing binary search tree. After each insertion, the
tree is checked for balance, and rotations are performed if needed.
**Steps**:
1. Insert `SRI`.
2. Insert `IND` (left of `SRI`).
3. Insert `AUS` (left of `IND`) → **Perform right rotation** at `SRI`.
4. Insert `FRA` (right of `IND`).
5. Insert `CAN` (left of `FRA`).
6. Insert `DEN` (right of `CAN`).
**AVL Tree after insertions**:
IND
/ \
AUS SRI
/
FRA
/ \
CAN DEN
### 4) **What is double-ended queue (Deque)? Explain with an
example.**
A **Double-Ended Queue (Deque)** is a linear data structure that allows
insertion and deletion of elements from both ends (front and rear).
- **Operations**:
- **InsertFront**: Inserts an element at the front.
- **InsertRear**: Inserts an element at the rear.
- **DeleteFront**: Removes an element from the front.
- **DeleteRear**: Removes an element from the rear.
**Example**:
Deque: [Empty]
InsertRear(10): [10]
InsertFront(20): [20, 10]
InsertRear(30): [20, 10, 30]
DeleteFront(): [10, 30]
DeleteRear(): [10]

### 5) **C Program to count the number of nodes in a singly linked list**
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
int countNodes(struct Node* head) {
int count = 0;
struct Node* current = head;
while (current != NULL) {
count++;
current = current->next;
}
return count;
}
void insertAtEnd(struct Node** head, int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
if (*head == NULL)
*head = newNode;
return;
}
struct Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
int main() {
struct Node* head = NULL;
insertAtEnd(&head, 10);
insertAtEnd(&head, 20);
insertAtEnd(&head, 30);
printf("Number of nodes: %d\n", countNodes(head));
return 0;
}

### 6) **Construct an AVL tree for the following sequential data: Jan, Feb,
Apr, May, July, Aug, June**
**Steps**:
1. Insert `Jan`.
2. Insert `Feb` (right of `Jan`).
3. Insert `Apr` (right of `Feb`).
4. Insert `May` (right of `Apr`).
5. Insert `July` (right of `May`) → **Perform left rotation** at `Feb`.
6. Insert `Aug` (right of `July`).
7. Insert `June` (left of `July`).
**Final AVL Tree**:
May
/ \
 Feb July
/ / \
Jan Apr Aug
/
June

### 7) **Use merge sort technique on the following data: 45, 85, 96, 78,
34, 12, 49, 38, 18**
**Steps**:
1. Split the array into smaller subarrays.
2. Sort the subarrays and merge them back.
**Sorted Array**:
- Start with: `[45, 85, 96, 78, 34, 12, 49, 38, 18]`
- After sorting and merging: `[12, 18, 34, 38, 45, 49, 78, 85, 96]`

### 8) **C Program to create a linked list where each node contains
individual digits of a number**
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
void insertAtEnd(struct Node** head, int data) {
 struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
if (*head == NULL) {
*head = newNode;
return;
}
struct Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
void createListFromNumber(struct Node** head, int number) {
while (number > 0) {
int digit = number % 10;
insertAtEnd(head, digit);
number /= 10;
}
}
void displayList(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
 printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
int main() {
struct Node* head = NULL;
int number = 12345;
createListFromNumber(&head, number);
printf("Linked list of digits: ");
displayList(head);
return 0;
}

### 9) **What is circular queue? Explain it with an example.*

A **Circular Queue** is a type of queue in which the last position is
connected back to the first position, forming a circle. In this queue, the rear
pointer wraps around to the front when it reaches the end of the array,
preventing the queue from needing to shift elements.
- **Example**:
Consider a circular queue of size 5:
Queue: [ , , , , ] (empty queue)
Enqueue(10): [10, , , , ]
Enqueue(20): [10, 20, , , ]
 Enqueue(30): [10, 20, 30, , ]
Enqueue(40): [10, 20, 30, 40, ]
Enqueue(50): [10, 20, 30, 40, 50]
Dequeue(): [ , 20, 30, 40, 50] (front moves to index 1)

### 10) **Construct Binary Search Tree of the following data: RAM, SITA,
AMIT, JOEL, IVAN, ASHA**
1. Start with `RAM` as the root.
2. Insert `SITA` to the right of `RAM`.
3. Insert `AMIT` to the left of `RAM`.
4. Insert `JOEL` to the right of `AMIT`.
5. Insert `IVAN` to the left of `JOEL`.
6. Insert `ASHA` to the left of `AMIT`.
**Binary Search Tree**
RAM
/ \
AMIT SITA
/ \
ASHA JOEL
/
IVAN
### 11) **Sort the following data using Quick Sort: 10, 5, 75, 62, 49, 58*
**Quick Sort Steps**:
1. Choose a pivot (e.g., 10).
2. Partition the array so that elements less than the pivot are on the left, and
elements greater are on the right.
3. Recursively apply this process to the left and right subarrays
**Sorted Array**:
- Initial Array: `[10, 5, 75, 62, 49, 58]`
- After sorting: `[5, 10, 49, 58, 62, 75]`

### 12) **C Program to traverse a linked list**

#include <stdio.h>
#include <stdlib.h
struct Node {
int data;
struct Node* next;
};
void traverse(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
 printf("NULL\n");
}
int main() {
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
struct Node* second = (struct Node*)malloc(sizeof(struct Node));
struct Node* third = (struct Node*)malloc(sizeof(struct Node));
head->data = 1;
head->next = second;
second->data = 2;
second->next = third;
third->data = 3;
third->next = NULL;
traverse(head);
return 0;
}

### 13) **What is Dequeue? Explain its operations with an example.**

A **Dequeue (Double Ended Queue)** is a linear data structure that allows
insertion and deletion of elements from both ends (front and rear).
- **Operations**:
- **InsertFront**: Inserts an element at the front.
- **InsertRear**: Inserts an element at the rear.
- **DeleteFront**: Removes an element from the front.
 - **DeleteRear**: Removes an element from the rear.
**Example**:
Dequeue: [Empty]
InsertRear(10): [10]
InsertFront(20): [20, 10]
InsertRear(30): [20, 10, 30]
DeleteFront(): [10, 30]
DeleteRear(): [10]

### 14) **Construct an AVL Tree of the following data: 20, 10, 30, 5, 15, 25,
35, 13, 17**
**Steps**:
1. Insert `20`.
2. Insert `10` (left of `20`).
3. Insert `30` (right of `20`).
4. Insert `5` (left of `10`).
5. Insert `15` (right of `10`).
6. Insert `25` (left of `30`).
7. Inser `35` (right of `30`).
8. Insert `13` (left of `15`).
9. Insert `17` (right of `15`).
**Balanced AVL Tree**:
20
 / \
10 30
/ \ / \
5 15 25 35
/ \
13 17

### 15) **Construct Binary Search Tree for the following data: 78, 95, 2,
57, 13, 29, 61, 10**
**Steps**:
1. Start with `78` as the root.
2. Insert `95` to the right of `78`.
3. Insert `2` to the left of `78`.
4. Insert `57` to the left of `78` and right of `2`.
5. Insert `13` to the right of `2`.
6. Insert `29` to the right of `13`.
7. Insert `61` to the right of `57`.
8. Insert `10` to the left of `13`.
**Binary Search Tree**:
78
/ \
2 95
\
 57
/ \
13 61
/ \
10 29

### 16) **Sort the following data using selection sort: 12, 11, 13, 5, 6*
**Steps**:
1. Find the minimum element and swap it with the first element.
2. Repeat this process for the remaining unsorted array.
**Sorted Array**:
- Initial Array: `[12, 11, 13, 5, 6]`
- After sorting: `[5, 6, 11, 12, 13]`

### 17) **C Program to display a linked list in reverse order**

#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
void reversePrint(struct Node* head) {
if (head == NULL) return;
 reversePrint(head->next);
printf("%d -> ", head->data);
}
int main() {
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
struct Node* second = (struct Node*)malloc(sizeof(struct Node));
struct Node* third = (struct Node*)malloc(sizeof(struct Node));
head->data = 1;
head->next = second;
second->data = 2;
second->next = third;
third->data = 3;
third->next = NULL;
printf("Linked list in reverse: ");
reversePrint(head);
printf("NULL\n")
return 0;
}

### 18) **What is Graph? Explain its representation techniques in

detail.**
A **Graph** is a data structure consisting of a set of vertices (nodes) and
edges connecting them. It can represent networks like social networks,
transportation systems, etc.
**Representation Techniques**:
1. **Adjacency Matrix**:
- A 2D array where rows and columns represent vertices, and the entries
represent the edges between them.
- Example:
Matrix for graph with

Q5) Attempt any TWO of the following [2×3=6]

### 1) Convert the following expression into prefix:
- i) `pq-rls` → Prefix: `-pq rls`
- ii) `(A+B)/(C+D*E)` → Prefix: `/ + A B + C * D E`

### 2) Define the following terms:

- **i) Leaf node**: A node in a tree data structure that does not have any
child nodes.
- **ii) Cyclic graph**: A graph that contains at least one cycle, meaning
there is a path that starts and ends at the same vertex.
- **iii) Parent node**: A node in a tree that has one or more child nodes
connected to it.

### 3) What is the degree of a vertex?

- The **degree of a vertex** is the number of edges incident to that
vertex.
- **Indegree**: The number of incoming edges to a vertex.
 - **Outdegree**: The number of outgoing edges from a vertex.
- For the graph given, you would need to analyze the connections to each
vertex to find the indegree and outdegree.

### 4) Define the following terms:

- **i) Directed graph**: A graph in which the edges have a direction,
meaning they go from one vertex to another in a specified direction.
- **ii) Strict binary tree**: A binary tree where each node has either
exactly two children or no children.

### 5) Convert the following expression into postfix:

- i) `A/B S CDE-A "C` → Postfix: `A B / S C D E A - C `
- ii) `(A+BC-D)/E$F` → Postfix: `A B C + D - / E F $`

### 6) What is the degree of a vertex? Find the indegree and outdegree of
the following graph for each vertex:
- The degree of a vertex is the total number of edges connected to it.
- To find **indegree** and **outdegree**, you need to analyze the
incoming and outgoing edges for each vertex in the graph.

### 7) Convert the following expression into postfix:

- i) `(A+B) C-D` → Postfix: `A B + C - D`
- ii) `A+B CD/E F` → Postfix: `A B + C D E / F`

### 8) Define the following terms:

 - **i) Degree of node**: The number of children a node has in a tree.
- **ii) Child node**: A node directly connected to another node when
moving away from the root.
- **iii) Path**: A sequence of edges that connects a sequence of vertices in
a graph.

### 9) Convert the following expression into prefix:

- i) `A+B/C*(D-A)^F^H` → Prefix: `+ A / B * C ^ - D A ^ F H`
- ii) `A (B+C+DE) + F` → Prefix: `+ A + + B C D E F`

### 10) Define the following terms:

- **i) Subtree**: A tree formed from a node and all its descendants in a
larger tree.
- **ii) Directed graph**: A graph where edges have a direction, indicating
a one-way relationship between vertices.