a) What are the different types of graph?

A graph is a data structure that consists of a set of nodes (also called vertices) and a set of
edges connecting pairs of nodes. Graphs are widely used in computer science to represent
networks such as social networks, computer networks, and route maps.

Types of Graphs:

1. Directed Graph (Digraph):

In this graph, edges have a direction. If there is an edge from vertex A to vertex B, you
can only move from A to B, not vice versa.

2. Undirected Graph:
Edges have no direction. If there is an edge between vertex A and B, movement is
allowed both ways.

3. Weighted Graph:
Each edge has an associated numerical value (weight or cost), often used in routing
and pathfinding algorithms.

4. Unweighted Graph:
Edges do not have weights; all connections are treated equally.

5. Cyclic Graph:
The graph contains at least one cycle — a path where the starting and ending node is
the same.

6. Acyclic Graph:
The graph does not contain any cycles. A Directed Acyclic Graph (DAG) is a special
kind used in scheduling and dependency resolution.

7. Connected Graph:
There is a path between every pair of vertices.

8. Disconnected Graph:
At least one vertex has no path to another vertex.

9. Complete Graph:
Every node is connected to every other node with an edge.

10. Sparse and Dense Graphs:

Based on the ratio of edges to vertices. Sparse has fewer edges, dense has many.

b) How to measure performance of an algorithm?

The performance of an algorithm is measured in terms of:
 1. Time Complexity:

○ Describes how the runtime of an algorithm grows with the input size.

○ Expressed using Big O notation: O(1), O(n), O(n²), O(log n), etc.

○ Measures the number of basic operations in the worst, best, or average case.

2. Space Complexity:

○ Measures the amount of memory an algorithm uses in relation to the input size.

○ Includes space for input, output, and auxiliary variables.

3. Asymptotic Analysis:

○ Best Case: Minimum time taken for the smallest input.

○ Average Case: Expected time for a typical input.

○ Worst Case: Maximum time for the most challenging input.

4. Empirical Analysis:

○ Running the algorithm on test data and measuring time and space usage in
practice.

c) What is a circular queue?

A circular queue is a linear data structure where the last position is connected back to the first
to make a circle. This allows efficient utilization of space and avoids the "false full" condition in a
linear queue.

Features:

● Follows FIFO (First-In-First-Out) principle.

● Two pointers: front and rear.

● When rear reaches the end, it wraps around to the beginning if space is available.

Example: Used in CPU scheduling, memory management, and buffering data streams.

d) List out different types of data structures

Data structures are categorized into several types:

1. Linear Data Structures:

○ Array: Fixed-size collection of elements stored in contiguous memory.

○ Linked List: Elements (nodes) connected via pointers.

○ Stack: Follows LIFO (Last In First Out).

○ Queue: Follows FIFO (First In First Out).

2. Non-Linear Data Structures:

○ Trees: Hierarchical data structure with root and child nodes.

○ Graphs: Set of nodes connected by edges.

3. Hash-Based Data Structures:

○ Hash Table / Hash Map: Stores data in key-value pairs using a hash function.

4. File Structures:

○ B-Trees, B+ Trees: Used in database indexing and file systems.

5. Advanced Structures:

○ Heap, Trie, AVL Tree, Segment Tree – used for specific algorithms and
problems.

e) What is the level of a node?

The level of a node in a tree data structure refers to its position in the hierarchy:

● Level 0: Root node

● Level 1: Children of the root

● Level 2: Grandchildren of the root, and so on

Level = Distance from the root node (count of edges from root to the node)

Example:

mathematica
CopyEdit
 A (Level 0)
/ \
B C (Level 1)
/ \
D E (Level 2)

f) What is meant by tree traversal?

Tree traversal is the process of visiting all the nodes of a tree in a specific order.

Types of Tree Traversals:

1. Inorder (Left, Root, Right):

Useful for binary search trees – gives sorted order.

2. Preorder (Root, Left, Right):

Used to create a copy of the tree or prefix notation.

3. Postorder (Left, Right, Root):

Used to delete or free the tree, or postfix evaluation.

4. Level-order (Breadth-First Search):

Visits nodes level by level using a queue.

g) What is sorting? State its techniques

Sorting is arranging data in a particular sequence, usually ascending or descending.

Purpose: Makes searching and organizing data easier.

Sorting Techniques:

1. Bubble Sort: Repeatedly swaps adjacent elements if they are in the wrong order.
Time: O(n²)

2. Selection Sort: Finds the minimum element and places it at the start.
Time: O(n²)

3. Insertion Sort: Builds the sorted list one element at a time.

Time: O(n²)

4. Merge Sort: Divides array, sorts each half, then merges them.
Time: O(n log n)
 5. Quick Sort: Selects a pivot and partitions the array.
Time: O(n log n) average

6. Heap Sort: Uses a binary heap to sort elements.

Time: O(n log n)

7. Radix Sort & Counting Sort: Non-comparison based, used for integers.
Time: Linear under specific conditions

h) What is DFS?
Depth-First Search (DFS) is an algorithm for traversing or searching tree or graph data
structures.

How it works:

● Starts at the root (or any arbitrary node).

● Explores as far as possible along each branch before backtracking.

● Typically uses a stack (or recursion).

Applications:

● Topological sorting

● Detecting cycles

● Solving puzzles (like mazes)

● Pathfinding

i) What are the advantages of a linked list over an array?

1. Dynamic Size:
Linked lists can grow or shrink at runtime without predefined size.

2. Efficient Insertions/Deletions:
No shifting required as in arrays; just update pointers.

3. Better Memory Utilization:

No need to allocate memory in bulk; nodes can be scattered.
 4. Ease of Implementation:
Useful in implementing stacks, queues, graphs, and hash tables.

Limitations of arrays that linked lists overcome:

● Fixed size

● Insertion/deletion is costly (due to shifting)

j) What is a binary tree? List its types.

A binary tree is a tree data structure in which each node has at most two children — referred to
as the left child and the right child.

Types of Binary Trees:

1. Full Binary Tree:

Every node has either 0 or 2 children.

2. Perfect Binary Tree:

All internal nodes have 2 children, and all leaves are at the same level.

3. Complete Binary Tree:

All levels are fully filled except possibly the last, which is filled from left to right.

4. Balanced Binary Tree:

Heights of left and right subtrees of any node differ by no more than one.

5. Degenerate (or Skewed) Tree:

Every node has only one child (can be left or right), resembling a linked list.
a) What is a height-balanced tree? Explain RR and RL rotations with an
example.
A height-balanced tree is a type of binary tree where the difference between the heights of
the left and right subtrees of every node is not more than 1. This kind of tree is also known
as an AVL tree (named after inventors Adelson-Velsky and Landis).

To maintain balance after insertions or deletions, AVL trees perform rotations. Two such
rotations are:

RR (Right-Right) Rotation:

● Occurs when a node is inserted into the right subtree of the right child.

● Solution: Perform a single left rotation.

Example: Insert in order: 10 → 20 → 30

markdown

CopyEdit

Before RR Rotation:

10

20

30

After RR Rotation:

markdown

CopyEdit

20

/ \

10 30
RL (Right-Left) Rotation:

● Occurs when a node is inserted into the left subtree of the right child.

● Solution: Perform a right rotation on the right child, then a left rotation on the current
node.

Example: Insert in order: 10 → 30 → 20

markdown

CopyEdit

Before RL Rotation:

10

30

20

After RL Rotation:

markdown

CopyEdit

20

/ \

10 30

b) Explain bubble sort technique with an example

Bubble Sort is a simple sorting technique where adjacent elements are compared and
swapped if they are in the wrong order. This process continues until the array is sorted.

Algorithm Steps:

1. Compare the first two elements.

2. Swap them if the first is greater than the second.

3. Move to the next pair, and repeat until the end of the array.

4. Repeat the process for all elements.

Example: Sort: [5, 2, 9, 1]

Pass 1:
Compare (5,2) → swap → [2, 5, 9, 1]
Compare (5,9) → no swap
Compare (9,1) → swap → [2, 5, 1, 9]

Pass 2:
Compare (2,5) → no swap
Compare (5,1) → swap → [2, 1, 5, 9]
Compare (5,9) → no swap

Pass 3:
Compare (2,1) → swap → [1, 2, 5, 9]
Now the array is sorted.

Time Complexity:

● Worst/Average Case: O(n²)

● Best Case (already sorted): O(n)

c) Explain BFS with example.

Breadth-First Search (BFS) is a graph or tree traversal technique that visits all nodes at the
current level before going to the next level.

Uses a Queue to keep track of nodes to visit.

Algorithm:

1. Enqueue the root node.

 2. While the queue is not empty:

○ Dequeue a node.

○ Visit it.

○ Enqueue its unvisited neighbors or children.

Example (Tree):

mathematica

CopyEdit

/ \

B C

/ \ \

D E F

BFS Traversal Order: A → B → C → D → E → F

Example (Graph):
Vertices = {A, B, C, D, E}
Edges = A-B, A-C, B-D, C-E

Start at A → Queue = [A]

● Visit A → Queue = [B, C]

● Visit B → Queue = [C, D]

● Visit C → Queue = [D, E]

● Visit D → Queue = [E]

● Visit E → Queue = []

BFS Order: A → B → C → D → E
d) What is the queue? Explain different operations performed on queue.
A queue is a linear data structure that follows the FIFO (First-In-First-Out) principle — the
element added first is removed first.

Basic Queue Operations:

1. Enqueue:

○ Add an element to the rear of the queue.

○ Example: Enqueue(10) → Queue = [10]

2. Dequeue:

○ Remove an element from the front of the queue.

○ Example: Dequeue() → Removes 10 → Queue = []

3. Front/Peek:

○ Returns the front element without removing it.

4. IsEmpty():

○ Checks whether the queue is empty.

5. IsFull(): (for fixed-size queues)

○ Checks whether the queue is full.

Types of Queues:

● Simple Queue: FIFO operations.

● Circular Queue: Last element connects to the first (better space use).

● Priority Queue: Elements are dequeued based on priority.

● Double-Ended Queue (Deque): Insertion/deletion from both ends.

e) Explain Binary search method with an example.

Binary Search is a highly efficient searching technique that works on sorted arrays. It
repeatedly divides the search space in half until the target is found or the space is empty.

Steps:
 1. Find the middle element.

2. If it matches the target, return success.

3. If the target is smaller, search the left half.

4. If the target is larger, search the right half.

5. Repeat until found or search space is empty.

Example: Search 13 in the sorted array: [5, 8, 12, 13, 17, 25]

● Low = 0, High = 5 → Mid = (0+5)//2 = 2 → arr[2]=12

● 13 > 12 → search in [13, 17, 25]

● Low = 3, High = 5 → Mid = (3+5)//2 = 4 → arr[4]=17

● 13 < 17 → search in [13]

● Low = 3, High = 3 → Mid = 3 → arr[3]=13 → Found

Time Complexity: O(log n)

a) Write a function for preorder traversal of the tree

c

CopyEdit

#include <stdio.h>

#include <stdlib.h>

// Define structure for a tree node

struct Node {

int data;

struct Node* left;

struct Node* right;

};
// Preorder Traversal Function: Root → Left → Right

void preorder(struct Node* root) {

if (root != NULL) {

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

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

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

b) Write a C program for static implementation of stack

c

CopyEdit

#include <stdio.h>

#define SIZE 5

int stack[SIZE];

int top = -1;

// Push function

void push(int value) {

if (top == SIZE - 1)

printf("Stack Overflow\n");

else
 stack[++top] = value;

// Pop function

int pop() {

if (top == -1) {

printf("Stack Underflow\n");

return -1;

return stack[top--];

// Display function

void display() {

if (top == -1)

printf("Stack is empty\n");

else {

printf("Stack: ");

for (int i = 0; i <= top; i++)

printf("%d ", stack[i]);

printf("\n");

}
int main() {

push(10);

push(20);

push(30);

display();

pop();

display();

return 0;

c) Write a function to delete the first node from a singly linked list
c

CopyEdit

#include <stdio.h>

#include <stdlib.h>

// Node structure

struct Node {

int data;

struct Node* next;

};

// Function to delete first node

void deleteFirstNode(struct Node** head) {

 if (*head == NULL) {

printf("List is empty\n");

return;

struct Node* temp = *head;

*head = (*head)->next;

free(temp);

printf("First node deleted\n");

d) Write a function to create a doubly circular linked list

c

CopyEdit

#include <stdio.h>

#include <stdlib.h>

// Node structure

struct Node {

int data;

struct Node* next;

struct Node* prev;

};

// Create a circular doubly linked list with n nodes

struct Node* createDoublyCircularList(int n) {

if (n <= 0) return NULL;

struct Node* head = NULL;

struct Node* temp = NULL;

struct Node* newNode;

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

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

newNode->data = i;

if (head == NULL) {

head = newNode;

head->next = head;

head->prev = head;

temp = head;

} else {

newNode->next = head;

newNode->prev = temp;

temp->next = newNode;

head->prev = newNode;

temp = newNode;

}
 return head;

e) Write a program to dynamically allocate memory for an array of integers

and then print the elements of the array
c

CopyEdit

#include <stdio.h>

#include <stdlib.h>

int main() {

int n, *arr;

printf("Enter number of elements: ");

scanf("%d", &n);

// Dynamic memory allocation

arr = (int*)malloc(n * sizeof(int));

if (arr == NULL) {

printf("Memory not allocated.\n");

return 1;

}
 // Input elements

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

printf("Enter element %d: ", i + 1);

scanf("%d", &arr[i]);

// Print elements

printf("Array elements are: ");

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

printf("%d ", arr[i]);

free(arr); // Free allocated memory

return 0;

a) What is the priority queue? Explain it with an example.

A priority queue is a special type of queue in which each element is

associated with a priority and served according to its priority
(highest priority first), not just by order of insertion (FIFO).

● Elements with higher priority are dequeued before elements with

lower priority.

● If two elements have the same priority, they are served based on
their order in the queue.

Types of Priority Queues:

1. Min-Priority Queue – Smallest value has highest priority.

 2. Max-Priority Queue – Largest value has highest priority.

Example (Max Priority Queue):

Insert elements with priorities:

(Data, Priority) → (Task1, 2), (Task2, 5), (Task3, 3)

Order of execution:
Task2 → Task3 → Task1 (based on priority 5 → 3 → 2)

b) Construct an AVL tree for: WED, TUE, MON, SAT, THUR, FRI

We'll insert these strings alphabetically and balance using AVL tree
rotations.

Step-by-Step Insertion:

1. Insert WED → root node

2. Insert TUE → left of WED

3. Insert MON → left of TUE → Unbalanced (Left-Left case)

○ Apply Right Rotation at WED

markdown

CopyEdit

TUE

/ \

MON WED

4. Insert SAT → left of TUE, right of MON → Unbalanced (Left-Right

case)

○ Apply Left-Right Rotation at TUE

Result:
markdown

CopyEdit

MON

/ \

SAT TUE

WED

5. Insert THUR → right of SAT

6. Insert FRI → left of MON → triggers further rotations to balance the

tree

Final AVL Tree (approximate structure due to alphabetical balancing):

markdown

CopyEdit

MON

/ \

FRI TUE

\ \

SAT WED

THUR

(Note: Actual structure may vary slightly based on rotation rules, as

string comparison is lexicographical.)
c) Sort the following data using quick sort: 10, 5, 75, 62,
49, 58

Initial Array: [10, 5, 75, 62, 49, 58]

Step-by-step using pivot:

1. Choose pivot = 10
Partition: [5] [10] [75, 62, 49, 58]

2. Right side → pivot = 75

Partition: [62, 49, 58] [75]

3. Partition [62, 49, 58] → pivot = 62

[49, 58] [62]

4. Partition [49, 58] → pivot = 49

[ ] [49] [58]

Final sorted array:

[5, 10, 49, 58, 62, 75]

d) Construct Binary Search Tree for data: 10, 12, 5, 4, 20,

8, 7, 15, 13

Step-by-step Insertion:

1. 10 → root

2. 12 → right of 10

3. 5 → left of 10

4. 4 → left of 5

5. 20 → right of 12

6. 8 → right of 5

7. 7 → left of 8
 8. 15 → left of 20

9. 13 → left of 15

Final BST:

markdown

CopyEdit

10

/ \

5 12

/ \ \

4 8 20

/ /

7 15

13

e) Write a ‘C’ program for dynamic implementation of stack

CopyEdit

#include <stdio.h>

#include <stdlib.h>

// Define node structure

struct Node {
 int data;

struct Node* next;

};

struct Node* top = NULL;

// Push operation

void push(int value) {

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

newNode->data = value;

newNode->next = top;

top = newNode;

// Pop operation

void pop() {

if (top == NULL) {

printf("Stack Underflow\n");

return;

struct Node* temp = top;

top = top->next;

free(temp);

}
// Display stack

void display() {

struct Node* temp = top;

printf("Stack: ");

while (temp != NULL) {

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

temp = temp->next;

printf("\n");

int main() {

push(10);

push(20);

push(30);

display(); // Stack: 30 20 10

pop();

display(); // Stack: 20 10

return 0;

Here is the detailed answer for Q5 – Attempt any TWO (2 × 3 = 6

marks):

a) Convert the following expressions into prefix

To convert infix expressions to prefix, use the rule:

Prefix (Polish Notation): Operator comes before the operands.

i) (A + B) * (C – D)
Step-by-step:

● Infix: (A + B) * (C - D)

● Prefix:

○ + A B → (A + B)

○ - C D → (C - D)

○ * (+ A B) (- C D) → * + A B - C D

✅ Answer: * + A B - C D

ii) P + (Q * R)(S – T)
Note: Assume multiplication between two brackets:
i.e., P + ((Q * R) * (S - T))

Step-by-step:

● Q * R → * Q R

● S - T → - S T

● (Q * R)(S - T) → * (* Q R) (- S T)

● Final expression: + P (* (* Q R) (- S T))

✅ Answer: + P * * Q R - S T

b) Define the following terms

i) Directed Graph:
A directed graph (digraph) is a graph where edges have directions.
That means each edge has a start vertex and an end vertex.
Example: A → B means there is a connection from A to B, but not from B to
A unless explicitly stated.

ii) Parent Node:

In a tree, a parent node is one that has at least one child node. It
is the node that connects to its children from the top.
Example: In a binary tree, if node A connects to node B and C, A is
the parent of B and C.

iii) Complete Binary Tree:

A complete binary tree is a tree in which all levels are completely
filled except possibly the last level, and the last level has all
nodes as far left as possible.
It is often used in heap implementations.

c) What is degree of a vertex? Find in-degree & out-degree

of each vertex in the given graph

Since the graph image wasn't uploaded, here's a general

explanation:

Definition:

● Degree of a vertex: Number of edges incident to the vertex.

● In-degree: Number of edges coming into the vertex.

● Out-degree: Number of edges going out from the vertex.

Example Graph:

Let's say the directed graph has these edges:

A → B, A → C, B → C, C → A

Verte In- Out-

x Degree Degree
A 1 2

B 1 1

C 2 1

If you share the actual graph or image, I can compute the exact values
for that.