Data structure 2

Q.1 Why to study data structures ? What are the major data structure used in the RDBMS, network
and hierarchical data model.

Ans:- Why Study Data Structures?

Studying data structures is essential because they are the foundation of efficient software
development. They help in:

1. Efficient Data Storage & Retrieval – Optimized storage and access to data.
2. Improved Algorithm Performance – Better performance and reduced complexity.
3. Scalability – Handling large datasets efficiently.
4. Memory Optimization – Managing memory effectively.
5. Problem Solving – Many real-world problems are easier to solve with proper data
structures.
6. Software Development & System Design – Used in databases, operating systems,
AI, and more.

Major Data Structures Used in Different Models

1. Relational Database Management System (RDBMS)

RDBMS organizes data in tables with predefined schemas. The major data structures used
include:

 Arrays – Used for indexing and temporary storage.

 Linked Lists – Used in query execution plans.
 Hash Tables – Used for indexing (e.g., hash indexing in PostgreSQL).
 B-Trees & B+ Trees – Used for efficient indexing and searching.
 Graphs – Used in SQL joins and relationships.

2. Network Data Model

Network databases use a graph-like structure with records connected by links. Major data
structures used:

 Graphs (Directed) – Nodes (records) connected with edges (pointers).

 Adjacency List / Matrix – To represent relationships.
 Hash Tables – To quickly access data via keys.

3. Hierarchical Data Model

Hierarchical databases follow a tree structure (like XML, LDAP). Major data structures
used:

 Trees (Binary, n-ary) – Parent-child relationships.

 Linked Lists – Used for navigating hierarchical relationships.
 Stacks – Used in traversal operations (e.g., depth-first search).
Q.2Consider the following specification of a graph G=(V,E)G = (V, E)G=(V,E):

 Vertices (V): {1,2,3,4}

 Edges (E): {(1,2),(1,3),(3,3),(3,4),(4,1)}
  Draw an undirected graph for the given specification.
  Represent graph GGG using an adjacency matrix.
  Represent graph GGG using an adjacency linked list.

Ans:- Step 1: Drawing the Undirected Graph

The given edges define the connections between vertices:

 (1,2) → Edge between 1 and 2

 (1,3) → Edge between 1 and 3
 (3,3) → Self-loop on vertex 3
 (3,4) → Edge between 3 and 4
 (4,1) → Edge between 4 and 1

Graph representation

1 ---- 2

|\

| \

4 -- 3

⤸ (Self-loop) Step 2: Adjacency Matrix Representation

An adjacency matrix is a 4×44 matrix where:

 If there is an edge between two vertices i and j, then M[i][j]=1, otherwise 0.

 Since it's undirected, the matrix is symmetric.
 A self-loop (e.g., (3,3)) is represented as 1 in M[3][3]

0111

1000

1011

1010

Step 3: Adjacency List Representation

Each vertex stores a list of its connected vertices.

1→2→3→4

2→1
3→1→3→4

4→1→3

Q.3Suppose the numbers: 50,15,62,5,20,58,91,3,8,37,60,24 are inserted in order into an initially

empty binary search tree . what is preorder, inorder and postorder traversal sequence of the tree ?

Ans:- Given sequence:

50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24

Step 1: Constructing the BST

1. Insert 50 → Root node.

2. Insert 15 → Left of 50.
3. Insert 62 → Right of 50.
4. Insert 5 → Left of 15.
5. Insert 20 → Right of 15.
6. Insert 58 → Left of 62.
7. Insert 91 → Right of 62.
8. Insert 3 → Left of 5.
9. Insert 8 → Right of 5.
10. Insert 37 → Right of 20.
11. Insert 60 → Right of 58.
12. Insert 24 → Left of 37.

Step 2: The BST Structure

markdown

50
/ \
15 62
/ \ / \
5 20 58 91
/ \ \ /
3 8 37 60
/
24

Step 3: Traversal Orders

1. Inorder Traversal (Left → Root → Right)

Inorder: 3, 5, 8, 15, 20, 24, 37, 50, 58, 60, 62, 91

2. Preorder Traversal (Root → Left → Right)

Preorder: 50, 15, 5, 3, 8, 20, 37, 24, 62, 58, 60, 91

3. Postorder Traversal (Left → Right → Root)

Postorder: 3, 8, 5, 24, 37, 20, 15, 60, 58, 91, 62, 50

Q.4 What is garbage collection ? who will run garbej collection program ? when it will be run ?

Ans:- What is Garbage Collection?

Garbage Collection (GC) is the process of automatically identifying and reclaiming

unused memory in a program. It helps prevent memory leaks by removing objects that are
no longer accessible, freeing up memory for new allocations.

Who Runs the Garbage Collection Program?

Garbage Collection is managed by the runtime environment of programming languages that

support automatic memory management.

 Java → JVM (Java Virtual Machine)

 C# → .NET CLR (Common Language Runtime)
 Python → Python Garbage Collector (part of the interpreter)
 JavaScript → JavaScript Engine (V8, SpiderMonkey, etc.)

In languages like C and C++, memory management is manual, meaning developers must
allocate (malloc/new) and deallocate (free/delete) memory themselves.

When is Garbage Collection Run?

Garbage Collection runs automatically, but the exact timing depends on the language and
implementation:

1. Memory Threshold Reached → When allocated memory exceeds a certain limit.

2. Idle CPU Time → Some GC algorithms run when the processor is idle.
3. Explicit Request → Some languages allow manual triggering:
o Java → System.gc() (only suggests GC, not guaranteed).
o Python → gc.collect() (forces collection).

Types of Garbage Collection Algorithms

 Reference Counting → Tracks the number of references to an object.

 Mark and Sweep → Marks reachable objects and sweeps unreferenced ones.
 Generational GC → Divides memory into young and old generations for optimization.
 Copying GC → Copies live objects to a new space and deletes everything else.
Q.5 Give the characteristics of good algorithm. Also explain how do we analyse the algorithm.

Ans:- Characteristics of a Good Algorithm

A good algorithm should have the following key characteristics:

1. Correctness – It should produce the correct output for all valid inputs.
2. Efficiency – It should be optimized in terms of time complexity and space complexity.
3. Finiteness – It should terminate after a finite number of steps.
4. Definiteness – Every step should be well-defined and clear.
5. Input & Output – It should take valid inputs and generate expected outputs.
6. Generality – It should be applicable to different problem instances, not just a specific case.
7. Simplicity & Maintainability – The algorithm should be easy to understand and modify.

How to Analyze an Algorithm?

Algorithm analysis helps determine its performance and efficiency in terms of time and
space complexity.

1. Time Complexity Analysis

 Measures how execution time increases as input size grows.

 Expressed using Big-O notation (O(n), O(log n), etc.).
 Categories:
o Best Case → Minimum time required.
o Average Case → Expected time for random inputs.
o Worst Case → Maximum time required.

Examples of Time Complexities

Complexity Example algorithm

O(1) Accessing an array element
O(log n) Binary search
O(n) Linear search
O(n log n) Merge sort, Quick sort (average case)
O(n2) Bubble sort, Insertion sort
O(2ⁿ) Recursive Fibonacci
O(n!) Traveling Salesman Problem (Brute Force)

2. Space Complexity Analysis

 Measures the amount of memory an algorithm needs.

 Includes:
o Fixed part → Constants, variables, program instructions.
o Variable part → Memory for dynamic structures (e.g., recursion stack, arrays).

Examples of Space Complexities

Complexity Example Algorithm
O(1) Variables, pointers
O(n) Arrays, linked lists
O(n²) 2D matrices, dynamic programming
3. Asymptotic Notations (Used for Analysis)

 Big-O (O) → Upper bound (worst case).

 Theta (Θ) → Tight bound (average case).
 Omega (Ω) → Lower bound (best case).

Q.6a) What is a Sparse Matrix? Convert the following sparse matrix into a non-sparse
matrix 1 0 0 0

Ans:- a) What is a Sparse Matrix?

A sparse matrix is a matrix that has a majority of its elements as zero. It is stored
efficiently using techniques such as compressed row storage (CRS), linked lists, or
coordinate lists, reducing memory usage and improving performance in certain
computations.

b) Conversion of Sparse Matrix to Non-Sparse Matrix

A non-sparse matrix (or dense matrix) should contain meaningful values replacing the zero
elements. Since the given matrix contains mostly zeros, we need to replace zeros with
meaningful values based on the problem context.

Example of a possible non-sparse matrix (if replacing zeros with small random values):

1 2 3 4

or

1 1 1 1

or

sql
1 X X X (where X represents relevant nonzero values)

Q.7 Write a short note on dynamic storage management . Explain how it is done in C.

Ans:- Short Note on Dynamic Storage Management

Dynamic Storage Management refers to the process of allocating and deallocating

memory at runtime as needed, rather than at compile-time. It allows efficient use of
memory by providing flexibility in handling variable-sized data structures such as linked
lists, trees, and dynamic arrays.
Dynamic Memory Management in C

C provides four standard library functions for dynamic memory management, available in the
<stdlib.h> library:

1. malloc(size) → Allocates a block of memory but does not initialize it.

2. calloc(n, size) → Allocates memory for an array of n elements and initializes them to
zero.
3. realloc(ptr, new_size) → Resizes a previously allocated memory block.
4. free(ptr) → Deallocates previously allocated memory.

#include <stdio.h>
#include <stdlib.h>
int main() {
int *ptr;
// Allocate memory for 5 integers
ptr = (int*) malloc(5 * sizeof(int));
if (ptr == NULL) {
printf("Memory allocation failed!\n");
return 1;
}
// Initialize and print values
for (int i = 0; i < 5; i++) {
ptr[i] = i + 1;
printf("%d ", ptr[i]);
}
// Free allocated memory
free(ptr);
return 0;
}

Key Points:

 Heap memory is used for dynamic allocation.

 Always free allocated memory to prevent memory leaks.
 malloc() and realloc() do not initialize memory, while calloc() does.
 free() does not reset pointer value (use ptr = NULL after freeing).
Q.8 Consider a stack with N = 6 memory cells allocated. Initially, the stack contains:
A, D, E, F, G (Top of Stack).

Perform the following operations in order, updating the stack accordingly:

i) Push(stack, K)
ii) Pop(stack, Item)
iii) Push(stack, L)
iv) Push(stack, S)
v) Pop(stack, Item)
vi) Push(stack, T)

Ans:-

Initial Stack State:

Bottom → [A, D, E, F, G,] ← Top

Step-by-Step Execution:

1 Push(stack, K) → Add K to the stack.

Bottom → [A, D, E, F, G, K] ← Top

✅ Successful (Stack is now full)

2 Pop(stack, Item) → Remove the top item (K).

Bottom → [A, D, E, F, G] ← Top

✅ Popped Item: K

3 Push(stack, L) → Add L to the stack.

Bottom → [A, D, E, F, G, L] ← Top

✅ Successful

4 Push(stack, S) → Stack is full, so we get Stack Overflow. ✅

5 Pop(stack, Item) → Remove the top item (L).

Bottom → [A, D, E, F, G] ← Top

✅ Popped Item: L

6 Push(stack, T) → Add T to the stack.

Bottom → [A, D, E, F, G, T] ← Top

✅ Successful
Final Stack State:
Bottom → [A, D, E, F, G, T] ← Top

Situations Encountered:

✅ Successful Operations: Push(K), Pop(K), Push(L), Pop(L), Push(T).

✅ Stack Overflow at Push(S) (Stack was full).

Q.9What is queue? Write an algorithm to implement insert item into queue using singly
linked list?

Ans:-

What is a Queue?

A queue is a linear data structure that follows the FIFO (First In, First Out) principle.

 Enqueue (Insertion): Adds an element to the rear of the queue.

 Dequeue (Deletion): Removes an element from the front of the queue.

Types of Queues:

1. Simple Queue – Follows FIFO.

2. Circular Queue – Connects the last node back to the first.
3. Priority Queue – Elements are dequeued based on priority.
4. Double-Ended Queue (Deque) – Insertion and deletion from both ends.

Algorithm to Insert (Enqueue) an Item into a Queue Using

a Singly Linked List
Node Structure:

Each node contains:

1. data – The value to be stored.

2. next – Pointer to the next node.

Algorithm (Enqueue Operation)

1. Create a new node with the given value.

2. If the queue is empty, set both front and rear to this new node.
3. Otherwise, set the next of the current rear to the new node.
4. Update rear to point to the new node.
5. End.

C Implementation:
CopyEdit
#include <stdio.h>
#include <stdlib.h>

// Define a structure for the queue node

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

// Define the front and rear of the queue

struct Node* front = NULL;
struct Node* rear = NULL;

// Function to insert an element into the queue

void enqueue(int value) {
// Create a new node
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation failed!\n");
return;
}
newNode->data = value;
newNode->next = NULL;

// If the queue is empty, set front and rear to new node

if (rear == NULL) {
front = rear = newNode;
} else {
// Attach new node to the end and update rear
rear->next = newNode;
rear = newNode;
}
printf("Inserted: %d\n", value);
}

// Function to display the queue

void display() {
struct Node* temp = front;
if (front == NULL) {
printf("Queue is empty!\n");
return;
}
printf("Queue: ");
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}

// Main function to test the queue

int main() {
enqueue(10);
enqueue(20);
enqueue(30);
display(); // Output: 10 -> 20 -> 30 -> NULL

return 0;
}
Time Complexity:

 Insertion (Enqueue): O(1) (constant time, as we insert at the rear).

 Deletion (Dequeue, if implemented): O(1) (rem

Q.10 Write an algorithm to evaluate postfix expression using stack and execute your
algorithm with postfix expression 10,5,6,*,+,8,/. Show intermediate stack content after each
operation ?

Ans:- Algorithm to Evaluate a Postfix Expression Using a Stack

Steps:

1. Create an empty stack.

2. Scan the postfix expression from left to right.
3. For each token in the expression:
o If the token is an operand (number), push it onto the stack.
o If the token is an operator (+, -, *, /, etc.):
1. Pop the top two elements from the stack.
2. Perform the operation.
3. Push the result back onto the stack.
4. After scanning all tokens, the final result will be at the top of the stack.

Execution of Algorithm with Postfix Expression:

Expression: 10 5 6 * + 8 /

(Equivalent Infix: (10 + (5 * 6)) / 8)

Step-by-Step Stack Operations:

Step Symbol Stack Content (Top → Bottom) Operation Performed

1 10 10 Push 10
2 5 5,10
3 6 6, 5, 10 Push 6
4 * 30, 10 Pop 6 and 5, Compute 5 * 6 = 30, Push 30
5 + 40 Pop 30 and 10, Compute 10 + 30 = 40, Push 40
6 8 8, 40 Push 8
7 / 5 Pop 40 and 8, Compute 40 / 8 = 5, Push 5

Final Result: 5

C Implementation:

#include <stdio.h>

#include <stdlib.h>
#include <ctype.h>

#define MAX 100

// Stack structure

struct Stack {

int top;

float items[MAX];

};

// Function to initialize stack

void initStack(struct Stack* s) {

s->top = -1;

// Function to check if stack is empty

int isEmpty(struct Stack* s) {

return (s->top == -1);

// Function to push an element onto stack

void push(struct Stack* s, float value) {

if (s->top == MAX - 1) {

printf("Stack Overflow!\n");

return;

s->items[++s->top] = value;

}
// Function to pop an element from stack

float pop(struct Stack* s) {

if (isEmpty(s)) {

printf("Stack Underflow!\n");

exit(1);

return s->items[s->top--];

// Function to evaluate a postfix expression

float evaluatePostfix(char* expression[]) {

struct Stack stack;

initStack(&stack);

for (int i = 0; expression[i] != NULL; i++) {

char* token = expression[i];

// If the token is an operand, push it to the stack

if (isdigit(token[0])) {

push(&stack, atof(token));

} else {

// Pop two operands

float val2 = pop(&stack);

float val1 = pop(&stack);

// Perform the operation

switch (token[0]) {
 case '+': push(&stack, val1 + val2); break;

case '-': push(&stack, val1 - val2); break;

case '*': push(&stack, val1 * val2); break;

case '/': push(&stack, val1 / val2); break;

return pop(&stack);

// Driver Code

int main() {

char* postfix[] = {"10", "5", "6", "*", "+", "8", "/", NULL};

printf("Result: %.2f\n", evaluatePostfix(postfix));

return 0;

Final Notes:

 The algorithm correctly follows LIFO (Last In, First Out) order of the stack.
 It handles multiple operators in left-to-right order.
 Time Complexity: O(n) (linear traversal of expression).
 Space Complexity: O(n) (due to stack usage).
Q.11Store the elements of the given binary tree using:

1. One-dimensional array representation

2. Linked list representation

/\

b c

/\ \

d e f

Ans:- 1. One-Dimensional Array Representation

A binary tree can be stored in an array using level-order indexing (0-based index):

 The root node is at index 0.

 If a node is at index i, then:
o Left child is at 2*i + 1
o Right child is at 2*i + 2

Array Representation:
Index 0123456

Node abc de- f

So, the array representation:

[a, b, c, d, e, -, f]

- represents an empty position in the array.

2. Linked List Representation (Binary Tree Using Pointers)

Each node in a linked list representation consists of:

1. Data (value of the node)

2. Pointer to the left child
3. Pointer to the right child

C Structure for Binary Tree Node:

#include <stdio.h>

#include <stdlib.h>
// Define a node structure

struct Node {

char data;

struct Node* left;

struct Node* right;

};

// Function to create a new node

struct Node* createNode(char data) {

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

newNode->data = data;

newNode->left = newNode->right = NULL;

return newNode;

// Main function

int main() {

// Creating nodes

struct Node* root = createNode('a');

root->left = createNode('b');

root->right = createNode('c');

root->left->left = createNode('d');

root->left->right = createNode('e');

root->right->right = createNode('f');
 printf("Binary tree created using linked list!\n");

return 0;

Explanation of Linked List Structure:

 Each node has three parts:

o Data (stores the character)
o Left pointer (points to left child)
o Right pointer (points to right child)
 The tree is dynamically allocated using malloc().

Q.12What is abstract data type (ADT)? Explain ,why queue is called ADT?

ANs:- Abstract Data Type (ADT)

An Abstract Data Type (ADT) is a mathematical model for a data structure that specifies:

1. What operations can be performed on the data.

2. How the data should behave, without specifying the exact implementation.

ADTs focus on the functionality rather than the implementation details. They define:

 The data it holds.

 The operations allowed (like insertion, deletion, etc.).
 The rules/restrictions on those operations.

Why is Queue Called an ADT?

A Queue is called an Abstract Data Type (ADT) because:

1. It defines a specific behavior:

o FIFO (First-In, First-Out) ordering of elements.
2. It allows basic operations:
o Enqueue (Insertion) → Adds an element to the rear.
o Dequeue (Removal) → Removes an element from the front.
o Peek/Front → Returns the front element without removing it.
o isEmpty() → Checks if the queue is empty.
o isFull() (if using a fixed-size array implementation).
3. The queue does not specify the internal implementation. It can be implemented using:
o Arrays
o Linked Lists
o Stacks
 o Circular Buffers

Thus, Queue is an ADT because it provides an interface for operations but does not enforce
a specific way of storing data.

Example Queue Implementations

1. Queue using an Array

#define SIZE 5
int queue[SIZE], front = -1, rear = -1;

void enqueue(int item) {

if (rear == SIZE - 1) {
printf("Queue Overflow\n");
} else {
if (front == -1) front = 0;
queue[++rear] = item;
}
}

int dequeue() {
if (front == -1 || front > rear) {
printf("Queue Underflow\n");
return -1;
}
return queue[front++];
}
2. Queue using a Linked List
struct Node {
int data;
struct Node* next;
};
struct Node* front = NULL, *rear = NULL;

void enqueue(int item) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = item;
newNode->next = NULL;
if (rear == NULL) {
front = rear = newNode;
} else {
rear->next = newNode;
rear = newNode;
}
}
 int dequeue() {
if (front == NULL) {
printf("Queue Underflow\n");
return -1;
}
int item = front->data;
struct Node* temp = front;
front = front->next;
free(temp);
return item;
}

Key Takeaways

 Queue is an ADT because it defines what operations can be performed, not how.
 It follows the FIFO principle.
 It can be implemented in multiple ways while still adhering to the defined operations.

Q.13 Explain the following graph terminologies with figures:

i) Undirected Graph
ii) Total Degree of a Vertex
iii) Simple Path
iv) Cycle

Ans:- 1. Undirected Graph

An undirected graph is a graph where edges have no direction. That is, if there is an edge
between two vertices A and B, you can move both ways (A → B and B → A).

✅ Example Figure:

A----B

| |

C----D

 The edges (A, B), (A, C), (B, D), and (C, D) do not have directions.

2. Total Degree of a Vertex

The degree of a vertex is the number of edges connected to it.

 If a vertex has self-loops, they are counted twice.

 Total Degree = Sum of degrees of all vertices.

✅ Example Figure: A----B----C

 Degree of A = 1
 Degree of B = 2
 Degree of C = 1
 Total Degree = 1 + 2 + 1 = 4

3. Simple Path

A simple path is a path between two vertices where:

1. No vertex is repeated.
2. No edge is traversed more than once.

✅ Example Figure:

A→B→C→D

 A simple path from A to D: A → B → C → D.

 If A is visited again, it is not a simple path.

4. Cycle

A cycle is a path where:

1. It starts and ends at the same vertex.

2. No edge is repeated.

✅ Example Figure:

A----B

| |

D----C

 Cycle: A → B → C → D → A

Summary Table

Term Definition Example

Undirected Graph Edges have no direction A—B—C
Total Degree of a Vertex Sum of edges at a vertex Degree (A) = 2
Simple Path Path without repetition A→B→C
Cycle Path starts & ends at same vertex A→B→C→A