2 mark question

1. What are the advantages of linked list over an array?

 Dynamic Size:
Linked lists can grow or shrink at runtime, while arrays have a fixed size.

 Easy Insertion/Deletion:
Inserting or deleting elements is easier and more efficient (no shifting of elements
needed), especially in the middle of the list.

2. How to measure performance of an algorithm'?

1. Time Complexity:
Measures how much time an algorithm takes as the input size increases.
2. Space Complexity:
Measures how much extra memory an algorithm uses during execution.
3. What is adjacency of Matrix
An adjacency matrix is a 2D matrix used to represent a graph, where:

 Rows and columns represent the vertices.

 Each cell (i, j) contains:
o 1 if there is an edge between vertex i and j
o 0 if there is no edge.

It is commonly used for representing dense graphs.

4. What is pointer to pointer

A pointer to pointer is a variable that stores the address of another pointer.
It is used when we need multiple levels of indirection, such as dynamic memory allocation for
2D arrays.
5. What is complete binary tree
A complete binary tree is a type of binary tree where:

1. All levels are fully filled except possibly the last level.
2. In the last level, all nodes are filled from left to right without gaps.

This ensures the tree is as compact as possible.

6. What is polynomial? How it differ from structure?

Polynomial:
A polynomial is a mathematical expression made up of variables and coefficients with
non-negative integer powers (e.g., 3x2+5x+23x^2 + 5x + 23x2+5x+2).
Difference from Structure:
A polynomial is a math expression, while a structure is a user-defined data type in
programming used to group different types of data together.
 7. What is Priority queue?
A priority queue is a special type of queue in which each element has a priority, and
the element with the highest (or lowest) priority is removed first instead of following
FIFO.
It is often implemented using heaps.
8. State the difference between stack & linked list
 A stack is a linear data structure that follows LIFO (Last In, First Out) order for
insertion and deletion.
 A linked list is a collection of nodes where each node points to the next, allowing
insertion and deletion at any position.
9. What is the need for the header?

Header files are needed because they:

1. Contain declarations of functions, macros, constants, and data types used in a program.
2. Allow code reusability and modularity by letting multiple source files share the same
declarations.

10. What is balance factor? How is it calculated?

The balance factor is a value used in an AVL Tree to determine whether a node is
balanced.
Calculation:
Balance Factor = Height of Left Subtree − Height of Right Subtree
If the value is -1, 0, or +1, the node is considered balanced.
11. What is data structure?
A data structure is a way of organizing, storing, and managing data so that it can be used
efficiently.
Examples include arrays, linked lists, stacks, queues, trees, and graphs.
12. What is sorting? State the techniques of sorting.
Sorting is the process of arranging data in a specific order, either ascending or
descending.
Techniques of Sorting:
Bubble sort, Selection sort, Insertion sort, Merge sort, Quick sort.
13. What is non-primitive data structure?
A non-primitive data structure is a complex data structure made using primitive data types. It
stores multiple values and can handle large and complex data.
14. What is searching?
Searching is the process of finding the location of a specific element in a data structure.

15. Mention the features of ADT

Encapsulation: Data and operations on the data are bundled together.

 Interface and Implementation Separation: The user knows only the operations, not
the internal implementation.

Reusability: Can be used in different programs without knowing internal details.

Abstraction: Focuses on what operations are performed, not how they are performed.

16. What are the types of linked list?

 singly Linked List: Each node contains data and a pointer to the next node.
 Doubly Linked List: Each node contains data, a pointer to the next node, and a
pointer to the previous node.
 Circular Linked List: The last node points back to the first node, forming a circle.
17. List down the applications of list
 Implementation of Stacks and Queues – Lists can be used to implement these
abstract data types.
 Dynamic Memory Allocation – Efficient insertion and deletion of elements at any
position.
 Graph and Tree Representations – Adjacency lists in graphs and linked structures
in trees.
 Polynomial Manipulation – Storing and operating on polynomial expressions.
18. What is polynomial? How is it represented?

A polynomial is a mathematical expression consisting of variables and coefficients combined

using addition, subtraction, and multiplication, with non-negative integer powers of the variable.
Example: 5x3+2x2−7x+45x^3 + 2x^2 - 7x + 45x3+2x2−7x+4

Representation:

 Array Representation: Store coefficients in an array where the index represents the
power of the variable.
 Linked List Representation: Each node stores a coefficient and exponent, and nodes
are linked in order of decreasing or increasing powers.

19. Differentiate array & structure.

Array Structure
Stores homogeneous data (same data Stores heterogeneous data (different data
type). types).
All elements are accessed by index. Members are accessed by name.
Fixed size, defined at compile time. Can contain different types and sizes of

20. What are the applications of stack

Expression Evaluation: Used in infix, postfix, and prefix expression evaluation.

 Function Calls: Manages function call and return in recursion (call stack).

Undo/Redo Operations: In text editors and software applications.

Syntax Parsing: Used in compilers for checking balanced parentheses and syntax

21. What is space and time complexity?

 Time Complexity: Measures the time taken by an algorithm with respect to input
size.
 Space Complexity: Measures the memory used by an algorithm during execution.
22. What is balance factor? How is it calculated?

Balance Factor: Used in AVL trees to check if a node is balanced.

Calculation: Balance Factor = Height of Left Subtree − Height of Right Subtree.

Value -1, 0, or +1 indicates a balanced node.

23. What are Abstract Data types?

 ADT is a logical description of a data type specifying operations without
implementation details.
 Features: Encapsulation, Abstraction, and Reusability.

24. What is Ancestor of Node?

An ancestor of a node in a tree is any node on the path from the root to that node, including
the root but not the node itself.
25. State the types of graph.
 Directed Graph (Digraph): Edges have a direction.
 Undirected Graph: Edges have no direction.
 Weighted Graph: Edges carry weights or costs.
 Unweighted Graph: Edges have no weights.
 Cyclic and Acyclic Graphs

26. Differentiate array and structure.

27. Array Structure
Stores homogeneous data. Stores heterogeneous data.
Accessed by index. Accessed by member names.

[Link] is spanning tree?

A spanning tree of a connected graph is a subgraph that includes all vertices with no
cycles and minimum possible edges.
4 mark answer
1. What is height balanced tree? Explain RR and RL rotations with an
example

height balanced tree is a binary tree in which for every node, the difference in height between
its left and right subtrees (balance factor) is at most 1.
It ensures the tree remains balanced, improving search, insertion, and deletion efficiency (like in
AVL trees).

Rotations in AVL Tree

When inserting a node causes the balance factor to go out of range (-1, 0, 1), rotations are
performed to restore balance.

1. Right-Right (RR) Rotation

 Occurs when a node is inserted into the right subtree of the right child of an
unbalanced node.
 Solution: Single left rotation at the unbalanced node.

Before RR Rotation:

10

20

30

After RR Rotation:

20

/ \

10 30

Right-Left (RL) Rotation

 Occurs when a node is inserted into the left subtree of the right child of an unbalanced
node.
 Solution: First right rotation on the right child, then left rotation on the unbalanced
node.

Example:

Before RL Rotation:
 10
\
30
/
20

After RL Rotation:
20
/ \
10 30

2. What is linked list? Explain its types in detail.

A linked list is a linear data structure where elements, called nodes, are connected using
pointers. Each node contains:

1. Data – the value stored.

2. Pointer – the address of the next node.

Advantages over array:

 Dynamic size.
 Efficient insertion and deletion.

Types of Linked List:

1. Singly Linked List:

o Each node points to the next node.
o Traversal is one-way.
o Example: Head → Node1 → Node2 → NULL
2. Doubly Linked List:
o Each node has two pointers: next and previous.
o Traversal is both forward and backward.
o Example: NULL ← Node1 ↔ Node2 ↔ Node3 → NULL
3. Circular Linked List:
o The last node points back to the first node.
o Can be singly circular or doubly circular.
o Useful in buffer management.

3. Explain different types of asymptotic notation in detail.

Asymptotic notation is used to measure algorithm efficiency in terms of time or space.

1. Big O Notation (O):

o Represents upper bound (worst-case) of algorithm complexity.
o Example: Searching in a list → O(n)
2. Omega Notation (Ω):
 oRepresents lower bound (best-case) of algorithm complexity.
oExample: Searching in a sorted list → Ω(1)
3. Theta Notation (Θ):
o Represents tight bound (average-case) of algorithm complexity.
o Example: Linear search → Θ(n)

4. Explain insertion sort technique with an example.

Insertion Sort:

 Sorts an array by building a sorted portion one element at a time.

 Picks one element and inserts it in the correct position in the sorted part.

Example: Sort [5, 2, 4, 6, 1] in ascending order

Step-by-step:

1. [5] | 2, 4, 6, 1 → Insert 2 → [2, 5] | 4, 6, 1

2. [2, 5] | 4, 6, 1 → Insert 4 → [2, 4, 5] | 6, 1
3. [2, 4, 5] | 6, 1 → Insert 6 → [2, 4, 5, 6] | 1
4. [2, 4, 5, 6] | 1 → Insert 1 → [1, 2, 4, 5, 6]

Time Complexity: O(n²)

Space Complexity: O(1)

5. Differentiate array and structure

Array Structure
Stores homogeneous data (same type). Stores heterogeneous data (different types).
Accessed by index. Accessed by member names.
Fixed size, defined at compile time. Can store different types and sizes of data.
Used for mathematical computations. Used to group related data logically.

6. write a function to create & display, circular singly, linked list.

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

struct Node {
int data;
struct Node* next;
};

// Create circular linked list

struct Node* createCircularList(int n) {
struct Node *head = NULL, *temp, *last;
int i, value;
 for(i = 0; i < n; i++) {
printf("Enter value: ");
scanf("%d", &value);
temp = (struct Node*)malloc(sizeof(struct Node));
temp->data = value;
temp->next = head; // temporary link

if(head == NULL) {
head = temp;
last = temp;
} else {
last->next = temp;
last = temp;
}
}
last->next = head; // make it circular
return head;
}

// Display circular linked list

void displayCircularList(struct Node* head) {
struct Node* temp = head;
if(head != NULL) {
do {
printf("%d ", temp->data);
temp = temp->next;
} while(temp != head);
}
printf("\n");
}

int main() {
int n;
printf("Enter number of nodes: ");
scanf("%d", &n);
struct Node* head = createCircularList(n);
printf("Circular Linked List: ");
displayCircularList(head);
return 0;
}

7. write a function to insert an element into a circular queue, in which the

queue is implemented as an array.
#include <stdio.h>
#define SIZE 5

void insertCircularQueue(int queue[], int *front, int *rear, int

value) {
if((*front == 0 && *rear == SIZE-1) || (*rear + 1) % SIZE ==
*front) {
printf("Queue Overflow\n");
return;
}
if(*front == -1) *front = 0; // first element
*rear = (*rear + 1) % SIZE;
queue[*rear] = value;
 printf("%d inserted\n", value);
}
8. Write a function for in order traversal of the tree.
struct Node {
int data;
struct Node* left;
struct Node* right;
};

void inorderTraversal(struct Node* root) {

if(root != NULL) {
inorderTraversal(root->left);
printf("%d ", root->data);
inorderTraversal(root->right);
}
}
9. write a function to delete first node from singly linked list.
void deleteFirstNode(struct Node** head) {
if(*head == NULL) return;
struct Node* temp = *head;
*head = (*head)->next;
free(temp);
printf("First node deleted\n");
}
[Link] a function to search the element from array using binary search
int binarySearch(int arr[], int n, int key) {
int low = 0, high = n - 1, mid;
while(low <= high) {
mid = (low + high) / 2;
if(arr[mid] == key) return mid; // found
else if(arr[mid] < key) low = mid + 1;
else high = mid - 1;
}
return -1; // not found
}
11. Construct an AVL tree for given data :
WED, TUE, MON, SAT, THUR, FRI

Step 1: Insert in order and balance using rotations

1. Insert WED → Tree: WED

2. Insert TUE → TUE left of WED → Balanced
3. Insert MON → MON left of TUE → Imbalance at WED (LL case) → Right rotation

Right Rotation:
WED TUE
/ / \
TUE → MON WED
/
MON
 4. Insert SAT → Right of WED → Balanced
5. Insert THUR → Right of TUE, left of WED → Balanced
6. Insert FRI → Inserted → Rebalance if necessary

Final AVL Tree (simplified structure):

TUE
/ \
MON WED
/ \
THUR SAT
/
FRI

12. For given data. construct a binary search tree :

15,30,20,5,10,2,7

Step 1: Insert in order respecting BST property

15
/ \
530
/ \ /
2 10 20
/
7

13. Sort the following data using quick sort.

10, 5, 75, 62, 49, 58

Quick Sort Example: 10, 5, 75, 62, 49, 58

Step 1: Choose pivot (last element = 58)

 Partition: [10, 5, 49] | 58 | [75, 62]

Step 2: Recursively sort left [10, 5, 49]

 Pivot = 49 → [10, 5] | 49
 Sort [10, 5] → Pivot = 5 → [5] | 10

Step 3: Recursively sort right [75, 62]

 Pivot = 62 → [ ] | 62 | [75]
Final sorted array: [5, 10, 49, 58, 62, 75]

14. Write a C-program to traverse the Iinked 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("\n");
}

int main() {
struct Node *head, *second, *third;
head = (struct Node*)malloc(sizeof(struct Node));
second = (struct Node*)malloc(sizeof(struct Node));
third = (struct Node*)malloc(sizeof(struct Node));

head->data = 10; head->next = second;

second->data = 20; second->next = third;
third->data = 30; third->next = NULL;

printf("Linked List: ");

traverse(head);
return 0;
}
15. What is Dequeue? Explain its operation with .example

Deque (Double-Ended Queue):

 A deque allows insertion and deletion at both ends (front and rear).

Operations:

1. Insert Front / Insert Rear – Add element at front or rear

2. Delete Front / Delete Rear – Remove element from front or rear
3. Peek / Display – View elements without removing
Example (using array representation):

Initial Deque: []
Insert Rear 10 → [10]
Insert Front 5 → [5, 10]
Delete Rear → [5]
Insert Rear 15 → [5, 15]

Convert the following expression into postfix.

i) (A +B) * C-D
ii) i, A+BxC-D/E*"'F

i) (A + B) * C - D

 Postfix: A B + C * D -

ii) A + B × C - D / E * F

 Operator precedence: * / >+ -

 Stepwise:
1. B × C → B C *
2. D / E → D E /
3. (D / E) * F → D E / F *
4. A + (B × C) → A B C * +
5. A + (B × C) - ((D / E) * F) → A B C * + D E / F * -

Postfix: A B C * + D E / F * -

b) Define the following terms :

i) Degree of, node
ii) Child node
iii) path

i) Degree of a Node:

 Number of children a node has in a tree.

ii) Child Node:

 A node that is directly connected and below a parent node.

iii) Path:

 A sequence of vertices and edges connecting two nodes in a graph or tree.

 c) What is degree of vertix? Find in degree & out degree of
each vertex for the following graph

 Degree of a vertex: Number of edges connected to it.

 In-degree: Number of edges coming into the vertex.
 Out-degree: Number of edges going out of the vertex.

Example:

Graph edges: A → B, A → C, B → C, C → A

Vertex In-degree Out-degree

A 1 2
B 1 1
C 2 1

I can also draw the graph and show postfix conversion with a stack diagram to make it
visually easy for exams.

Explain different types of Dynamic Memory Allocation functions.

Dynamic Memory Allocation Functions

Dynamic memory allocation allows allocating memory at runtime in C.

1. malloc() – Allocates memory for a given size and returns a pointer.

2. int *p = (int*)malloc(5 * sizeof(int));

3. calloc() – Allocates memory for an array and initializes all elements to 0.

4. int *p = (int*)calloc(5, sizeof(int));

5. realloc() – Changes the size of previously allocated memory.

6. p = (int*)realloc(p, 10 * sizeof(int));

7. free() – Deallocates previously allocated memory.

8. free(p);

b) Explain Linear Data structure with examples.

Linear Data Structure

 Data structures where elements are arranged sequentially.

 Traversal is linear (one after another).
 Examples:
1. Array: [10, 20, 30]
2. Linked List: 10 → 20 → 30
3. Stack and Queue

c) What is stack? Explain different operations used in stack.

 Stack: Linear data structure that follows LIFO (Last In First Out).

Operations:

1. Push: Insert element at the top.

2. Pop: Remove element from the top.
3. Peek/Top: View top element without removing.
4. isEmpty: Check if stack is empty.
5. isFull: Check if stack is full (in case of array implementation).

d) What is algorithm? Explain its characteristics.

 Algorithm: A step-by-step procedure to solve a problem or perform a task.

Characteristics:

1. Input: Takes zero or more inputs.

2. Output: Produces at least one output.
3. Finiteness: Must terminate after a finite number of steps.
4. Definiteness: Each step is clearly defined.
5. Effectiveness: Steps are simple and executable.

e) Explain selection sort technique with example.

 Selection Sort: Repeatedly selects the minimum element from the unsorted part and
moves it to the beginning.

Example: Sort [29, 10, 14, 37, 13]

1. Find min = 10 → Swap with 29 → [10, 29, 14, 37, 13]

2. Find min = 13 → Swap with 29 → [10, 13, 14, 37, 29]
3. Find min = 14 → Already in place
4. Find min = 29 → Swap with 37 → [10, 13, 14, 29, 37]

Final Sorted Array: [10, 13, 14, 29, 37]

Write a function to create & display singly linked list.

#include <stdio.h>

#include <stdlib.h>

struct Node {

int data;

struct Node* next;

};

// Create a singly linked list

struct Node* createList(int n) {

struct Node *head = NULL, *temp, *last;

int i, value;

for(i = 0; i < n; i++) {

printf("Enter value: ");

scanf("%d", &value);

temp = (struct Node*)malloc(sizeof(struct Node));

temp->data = value;

temp->next = NULL;

if(head == NULL) {

head = temp;

last = temp;

} else {

last->next = temp;
 last = temp;

return head;

// Display linked list

void displayList(struct Node* head) {

struct Node* temp = head;

while(temp != NULL) {

printf("%d ", temp->data);

temp = temp->next;

printf("\n");

int main() {

int n;

printf("Enter number of nodes: ");

scanf("%d", &n);

struct Node* head = createList(n);

printf("Linked List: ");

displayList(head);

return 0;

}
b) Write a function to insert an element into a queue, in which the queue is
implemented as array.

#include <stdio.h>

#define SIZE 5

void enqueue(int queue[], int *rear, int value) {

if(*rear == SIZE - 1) {

printf("Queue Overflow\n");

return;

(*rear)++;

queue[*rear] = value;

printf("%d inserted\n", value);

c) Explain BFS traversing technique with an example.

 BFS (Breadth-First Search): Traverses a graph level by level using a queue.

Steps:

1. Start from the source node, mark it visited.

2. Enqueue the node.
3. Repeat until the queue is empty:
o Dequeue a node and process it.
o Enqueue all unvisited adjacent nodes.

Example: Graph edges: A → B, A → C, B → D, C → D

BFS Traversal: A → B → C → D

d) Write a function to preorder traversal of the tree.

struct Node {
 int data;

struct Node* left;

struct Node* right;

};

void preorderTraversal(struct Node* root) {

if(root != NULL) {

printf("%d ", root->data); // Visit node

preorderTraversal(root->left); // Traverse left subtree

preorderTraversal(root->right); // Traverse right subtree

e) Write an algorithm to convert infix expression to postfix expression.

Steps:

1. Initialize an empty stack for operators and an empty postfix string.

2. Read the infix expression from left to right.
3. If the symbol is an operand, append it to postfix.
4. If the symbol is '(', push it onto the stack.
5. If the symbol is ')', pop and append from stack until '(' is found.
6. If the symbol is an operator:
o Pop operators from stack with higher or equal precedence and append to
postfix.
o Push current operator onto stack.
7. Repeat until all symbols are read.
8. Pop any remaining operators from stack and append to postfix.

Example:

 Infix: (A + B) * C
 Postfix: A B + C *
Construct an AVL tree of following data.

20, 10, 30, 5, 15, 25, 35, 13, 17

Step 1: Insert nodes one by one and balance

1. Insert 20 → Root
2. Insert 10 → Left of 20 → Balanced
3. Insert 30 → Right of 20 → Balanced
4. Insert 5 → Left of 10 → Balanced
5. Insert 15 → Right of 10 → Balanced
6. Insert 25 → Left of 30 → Balanced
7. Insert 35 → Right of 30 → Balanced
8. Insert 13 → Left of 15 → Balance check → Already balanced
9. Insert 17 → Right of 15 → Balance check → Already balanced

Final AVL Tree (simplified structure):

20
/ \
10 30
/ \ / \
5 15 25 35
/ \
13 17

b) Construct Binary search tree for following data.

78, 95, 2, 57, 13, 29, 61, 10

BST Construction:

78
/ \
2 95
\
57
/ \
13 61
/
10
\
29

c) Sort the following data by using selection sort

12, 11, 13, 5, 6

Sort [12, 11, 13, 5, 6]

Step-by-step:

1. Min = 5 → Swap with 12 → [5, 11, 13, 12, 6]

2. Min = 6 → Swap with 11 → [5, 6, 13, 12, 11]
3. Min = 11 → Swap with 13 → [5, 6, 11, 12, 13]
4. Min = 12 → Already in place
5. Min = 13 → Already in place

Sorted Array: [5, 6, 11, 12, 13]

d) Write a C- program to display a linked list in Reverse order.

#include <stdio.h>

#include <stdlib.h>

struct Node {

int data;

struct Node* next;

};

void displayReverse(struct Node* head) {

if(head == NULL) return;

displayReverse(head->next); // Recursive call

printf("%d ", head->data); // Print after recursion

int main() {

struct Node *head, *second, *third;

head = (struct Node*)malloc(sizeof(struct Node));

 second = (struct Node*)malloc(sizeof(struct Node));

third = (struct Node*)malloc(sizeof(struct Node));

head->data = 10; head->next = second;

second->data = 20; second->next = third;

third->data = 30; third->next = NULL;

printf("Linked List in Reverse: ");

displayReverse(head);

return 0;

e) What is Graph? Explain its representation techniques in detail

Graph:

 A graph is a collection of vertices (nodes) and edges (connections) between them.

 Can be directed or undirected, weighted or unweighted.

Representation Techniques:

1. Adjacency Matrix:
o 2D array of size V×V for V vertices.
o matrix[i][j] = 1 if there is an edge between vertex i and j, else 0.
o Suitable for dense graphs.
2. Adjacency List:
o Each vertex has a list of adjacent vertices.
o More space-efficient for sparse graphs.
3. Edge List:
o Simply lists all edges as pairs (u, v).
o Easy to store, but not efficient for searching adjacency.

Convert the following expression into prefix

i) A+B/C*(D – A) ^ F ^ H
ii) A* (B*C+D*E) + F

i) A + B / C * (D – A) ^ F ^ H

Step 1: Identify operator precedence:

 ^ (highest), then * and /, then + and -

Step 2: Convert to prefix:

1. (D – A) → - D A
2. (D – A) ^ F → ^ - D A F
3. ((D – A) ^ F) ^ H→^ ^ - D A F H
4. B / C→/ B C
5. B / C * ((D – A) ^ F ^ H) → * / B C ^ ^ - D A F H
6. A + ... → + A * / B C ^ ^ - D A F H

Prefix: + A * / B C ^ ^ - D A F H

ii) A * (B * C + D * E) + F

1. B * C→* B C
2. D * E→* D E
3. (B * C + D * E) → + * B C * D E
4. A * (B * C + D * E) → * A + * B C * D E
5. Add F → + * A + * B C * D E F

Prefix: + * A + * B C * D E F

b) Define the following terms

i) Parent Node

ii) Sub tree

Directed Graph

i) Parent Node:

 A node that has one or more child nodes in a tree.

ii) Subtree:

 A portion of a tree that consists of a node and all its descendants.

iii) Directed Graph:

 A graph in which edges have a direction.

 Represented as arrows from a vertex u → v.

Explain Insertion sort technique with an example.

Insertion Sort:

 A sorting algorithm that builds the sorted array one element at a time.
 Each new element is inserted into its correct position in the sorted portion.

Example: Sort [5, 2, 4, 6, 1]

Steps:

1. [5] | 2, 4, 6, 1 → Insert 2 → [2, 5] | 4, 6, 1

2. [2, 5] | 4, 6, 1 → Insert 4 → [2, 4, 5] | 6, 1
3. [2, 4, 5] | 6, 1 → Insert 6 → [2, 4, 5, 6] | 1
4. [2, 4, 5, 6] | 1 → Insert 1 → [1, 2, 4, 5, 6]

Time Complexity: O(n²), Space Complexity: O(1)

b) What is circular queue? How it is differ from static queue?

Circular Queue:

 A queue where the last position is connected to the first, forming a circle.
 Efficiently utilizes memory by reusing empty slots after dequeuing.

Difference from Static Queue:

Static Queue Circular Queue

Linear structure Circular structure
Memory not reused after dequeue Memory is reused
Can show "Overflow" even if empty space exists Avoids false overflow

c) What is stack? What are the various applications of stack. List operations
performed on stack.

Stack:

 Linear data structure following LIFO (Last In First Out) principle.

Applications:
 1. Expression evaluation: Prefix, Postfix, Infix
2. Function calls: Managing recursion (Call Stack)
3. Undo/Redo operations in editors
4. Syntax parsing in compilers
5. Backtracking algorithms

Operations on Stack:

1. Push: Insert element at top

2. Pop: Remove element from top
3. Peek/Top: View top element
4. isEmpty: Check if stack is empty
5. isFull: Check if stack is full (array implementation)

Explain different types of AVL rotations with an example.

AVL rotations are used to balance a tree when the balance factor of a node goes out of range (-
1, 0, +1).

1. LL (Left-Left) Rotation:
o Occurs when a node is inserted in left subtree of left child
o Solution: Right rotation
o Example:

Before: 30
/
20
/
10
After LL: 20
/ \
10 30

2. RR (Right-Right) Rotation:
o Occurs when a node is inserted in right subtree of right child
o Solution: Left rotation
o Example:

Before: 10
\
20
\
30
After RR: 20
/ \
 10 30

3. LR (Left-Right) Rotation:
o Node inserted in right subtree of left child
o Solution: Left rotation on left child → Right rotation on root
o Example:

Before: 30
/
10
\
20
After LR: 20
/ \
10 30

4. RL (Right-Left) Rotation:
o Node inserted in left subtree of right child
o Solution: Right rotation on right child → Left rotation on root
o Example:

Before: 10
\
30
/
20
After RL: 20
/ \
10 30
explain various types of dynamic memory allocation function

Dynamic memory allocation allows a program to request memory at runtime instead of at

compile time. It helps in efficient memory usage.

Types of Functions:

1. malloc() (Memory Allocation)

o Allocates a block of memory of given size.
o Returns a void pointer which can be typecast.
o Memory is not initialized.
2. int *p = (int*)malloc(5 * sizeof(int));
3. calloc() (Contiguous Allocation)
o Allocates memory for an array of elements and initializes all to 0.
o Syntax: calloc(number_of_elements, size_of_element)
4. int *p = (int*)calloc(5, sizeof(int));
5. realloc() (Reallocation)
o Resizes a previously allocated memory block to a new size.
o Useful for growing or shrinking arrays dynamically.
6. p = (int*)realloc(p, 10 * sizeof(int));
 7. free()
o Frees the allocated memory, preventing memory leaks.
8. free(p);

Summary Table:

Function Purpose Initialization

malloc Allocate memory block No
calloc Allocate array of blocks Yes (0)
realloc Resize previously allocated memory Same as before
free Deallocate memory N/A
write a function to create and display doubly link list
#include <stdio.h>
#include <stdlib.h>

// Define structure for doubly linked list node

struct Node {
int data;
struct Node* next;
struct Node* prev;
};

// Function to create doubly linked list

struct Node* createList(int n) {
struct Node *head = NULL, *temp, *last;
int i, value;

for(i = 0; i < n; i++) {

printf("Enter value: ");
scanf("%d", &value);

temp = (struct Node*)malloc(sizeof(struct Node));

temp->data = value;
temp->next = NULL;
temp->prev = NULL;

if(head == NULL) {
head = temp; // First node
last = temp;
} else {
last->next = temp; // Link previous last node
temp->prev = last; // Set previous pointer
last = temp; // Update last
}
}
return head;
}

// Function to display doubly linked list

void displayList(struct Node* head) {
struct Node* temp = head;
printf("Doubly Linked List: ");
while(temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}

// Main function
int main() {
int n;
printf("Enter number of nodes: ");
scanf("%d", &n);

struct Node* head = createList(n);

displayList(head);

return 0;
}
write a recursive function to transverse a tree by using inorder(), preorder() and
postorder transversing function
#include <stdio.h>
#include <stdlib.h>

// Define structure for tree node

struct Node {
int data;
struct Node* left;
struct Node* right;
};

// Function to create a new tree node

struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}

// 1. Inorder Traversal (Left, Root, Right)

void inorder(struct Node* root) {
if(root != NULL) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}

// 2. Preorder Traversal (Root, Left, Right)

void preorder(struct Node* root) {
 if(root != NULL) {
printf("%d ", root->data);
preorder(root->left);
preorder(root->right);
}
}

// 3. Postorder Traversal (Left, Right, Root)

void postorder(struct Node* root) {
if(root != NULL) {
postorder(root->left);
postorder(root->right);
printf("%d ", root->data);
}
}

// Main function
int main() {
// Creating a simple tree manually
struct Node* root = createNode(10);
root->left = createNode(20);
root->right = createNode(30);
root->left->left = createNode(40);
root->left->right = createNode(50);

printf("Inorder Traversal: ");

inorder(root);
printf("\n");

printf("Preorder Traversal: ");

preorder(root);
printf("\n");

printf("Postorder Traversal: ");

postorder(root);
printf("\n");

return 0;
}
write a function to reverse a string using a stack
#include <stdio.h>
#include <string.h>
#define MAX 100

// Stack implementation
char stack[MAX];
int top = -1;

// Push character onto stack

void push(char ch) {
if(top == MAX - 1) {
printf("Stack Overflow\n");
return;
}
 stack[++top] = ch;
}

// Pop character from stack

char pop() {
if(top == -1) {
printf("Stack Underflow\n");
return '\0';
}
return stack[top--];
}

// Function to reverse a string using stack

void reverseString(char str[]) {
int i;
int len = strlen(str);

// Push all characters onto stack

for(i = 0; i < len; i++) {
push(str[i]);
}

// Pop characters and put back into string

for(i = 0; i < len; i++) {
str[i] = pop();
}
}

int main() {
char str[100];
printf("Enter a string: ");
scanf("%s", str);

reverseString(str);
printf("Reversed string: %s\n", str);

return 0;
}

write a c program for evaluation of a polynomial

#include <stdio.h>

#include <math.h>

int main() {

int degree, i;
 float x, result = 0.0;

printf("Enter the degree of the polynomial: ");

scanf("%d", &degree);

float coeff[degree + 1];

// Input coefficients

printf("Enter the coefficients (highest degree to constant term):\n");

for(i = 0; i <= degree; i++) {

scanf("%f", &coeff[i]);

printf("Enter the value of x: ");

scanf("%f", &x);

// Evaluate polynomial

for(i = 0; i <= degree; i++) {

result += coeff[i] * pow(x, degree - i);

printf("Value of the polynomial at x = %.2f is %.2f\n", x, result);

return 0;

}
 construct an avl tree for the sequential data: jan feb april may
july aug june

Data (sequential insertion):

Jan, Feb, April, May, July, Aug, June

Step 1: Insert Jan

 Tree:

Jan

Step 2: Insert Feb

 Inserted to the right of Jan → Balanced.

Jan
\
Feb

Step 3: Insert April

 Inserted left of Feb → Check balance:

o Jan balance factor = height(left) - height(right) = 0 - 2 = -2 → Unbalanced
(Right-Left Case)

RL Rotation:

1. Right rotation on Feb’s left child → no effect as April has no child.

2. Left rotation on Jan → Root becomes April

After RL Rotation:

April
/ \
Jan Feb
Step 4: Insert May

 Insert right of Feb → Balanced.

April
/ \
Jan Feb
\
May

 Check balance: April’s BF = -1 → Balanced

Step 5: Insert July

 Insert right of May → BF of Feb = -2 → RR Rotation on Feb

After Rotation:

April
/ \
Jan May
/ \
Feb July

Step 6: Insert Aug

 Insert right of July → BF of May = -2 → RR Rotation on May

After Rotation:

April
/ \
Jan July
/ \
May Aug
/
Feb

Step 7: Insert June

 Insert left of July → BF adjustments: Balanced after insertion

 Final AVL Tree:

April
/ \
 Jan July
/ \
May Aug
/ \
Feb June

Use merge sort technique on following data:

45, 85, 96, 78, 34, 12, 49, 38, 18.

Step 1: Divide (Split array into halves recursively)

[45,85,96,78,34,12,49,38,18]
→ [45,85,96,78,34] , [12,49,38,18]
→ [45,85,96], [78,34], [12,49], [38,18]
→ [45,85], [96], [78], [34], [12,49], [38,18]
→ [45],[85],[96],[78],[34],[12],[49],[38],[18]

Step 2: Conquer (Merge)

1. Merge [45] and [85] → [45,85]

2. Merge [78] and [34] → [34,78]
3. Merge [12] and [49] → [12,49]
4. Merge [38] and [18] → [18,38]

Step 3: Merge larger arrays

 [45,85] and [96] → [45,85,96]

 [34,78] → already sorted
 [12,49] and [18,38] → [12,18,38,49]

Step 4: Final Merge

 [45,85,96] and [34,78] → [34,45,78,85,96]

 [34,45,78,85,96] and [12,18,38,49] → [12,18,34,38,45,49,78,85,96]

Sorted Array:

12, 18, 34, 38, 45, 49, 78, 85, 96

c) Write a 'C' program to create link list with given number in

which data part of each node contains individual digits of the
numbers.

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

struct Node {

int data;

struct Node* next;

};

// Function to create linked list for individual digits

struct Node* insertDigits(int num, struct Node* head) {

int digits[10], i=0;

// Extract digits

while(num > 0) {

digits[i++] = num % 10;

num /= 10;

// Insert digits in correct order

for(i = i-1; i >= 0; i--) {

struct Node* temp = (struct Node*)malloc(sizeof(struct

Node));

temp->data = digits[i];

temp->next = head;

head = temp;

return head;
}

// Display linked list

void display(struct Node* head) {

while(head != NULL) {

printf("%d ", head->data);

head = head->next;

printf("\n");

int main() {

int n, num;

struct Node* head = NULL;

printf("Enter number of integers: ");

scanf("%d", &n);

for(int i=0;i<n;i++){

printf("Enter number: ");

scanf("%d", &num);

head = insertDigits(num, head);

}
 printf("Linked List (digits of numbers): ");

display(head);

return 0;

e) Construct Binary search tree of following data:

RAM, SITA, AMIT, JOEL, IVAN, ASHА

Step 1: Insert nodes in order (alphabetical comparison)

1. RAM → root
2. SITA → right of RAM
3. AMIT → left of RAM
4. JOEL → left of RAM? Compare with AMIT → right of AMIT
5. IVAN → left of RAM? Compare with AMIT → right of AMIT? Compare with JOEL →
right of JOEL
6. ASHA → left of RAM? Compare with AMIT → right of AMIT? Compare with JOEL →
left of JOEL

BST Structure:

RAM
/ \
AMIT SITA
\
JOEL
/ \
ASHA IVAN

Define the following terms: estionP

i) Directed graph

ii) Strict binary tree

iv) Cyclic graph

i) Directed Graph:
  A graph in which edges have a direction.
 Represented as arrows from a vertex u → v.

ii) Strict Binary Tree:

 A binary tree in which every non-leaf node has exactly two children.
 Also called a full binary tree.

iii) Cyclic Graph:

 A graph that contains at least one cycle (a path that starts and ends at the same vertex).

b) Convert the following expression into postfix

i) A/B $ CD * E-A *C

ii) (A+ B * C -D)/ E$ F

Operator Precedence:

1. () → highest
2. $ (exponent)
3. * and /
4. + and -

i) A / B $ C D * E - A * C

Stepwise (assume $ is exponentiation, left-to-right precedence):

1. B $ C→B C $
2. B $ C D *→ B C $ D *
3. / with A → A B C $ D * /
4. E - A→E A -
5. * C→E A - C *
6. Combine all →A B C $ D * / E A - C *

Postfix:

A B C $ D * / E A - C *

ii) (A + B * C - D) / E $ F

Stepwise:

1. B * C→B C *
2. A + (B * C) → A B C * +
3. (A + B*C) - D → A B C * + D -
4. Divide by E → A B C * + D - E /
 5. Exponent F → A B C * + D - E / F $

Postfix:

A B C * + D - E / F $