DSA

Important Ques ons

1. Define B-tree and explain its proper es.

A B-tree is a self-balancing search tree designed to keep data sorted and allow search, sequen al
access, inser ons, and dele ons in logarithmic me. It is widely used in database and file systems.
Proper es of a B-tree:

1. Each node can have at most m children, where m is the order of the B-tree.
2. Every node (except the root) must have at least ceil(m/2) children.
3. A node can contain at most m-1 keys and at least ceil(m/2)-1 keys.
4. All leaves appear at the same level, maintaining balance.
5. Keys within a node are stored in ascending order.
6. The tree grows and shrinks dynamically while remaining balanced.

Algorithm for inser on in a B-tree:

1. Start at the root.

2. Find the correct child where the key should be inserted (similar to binary search).
3. Insert the key in the sorted order within the node.
• If the node has space, insert directly.
• If the node is full, split the node into two.

4. Move the middle key to the parent.

5. Repeat the process recursively if necessary.
What are the advantages of B-Tree over binary search trees?

1. Balanced Tree: B-Trees are always balanced, ensuring logarithmic me opera ons.
2. Efficient Disk Access: Designed for minimizing disk I/O opera ons, making it ideal for databases.
3. Support Mul -way Nodes: Unlike binary search trees, B-Trees allow mul ple keys in a single node,
reducing tree height.
4. Handles Large Data: Can efficiently handle large datasets by grouping keys in nodes.
#include <iostream>
using namespace std;

void inser onSort(int arr[], int n) {

for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}

void printArray(int arr[], int n) {

for (int i = 0; i < n; i++) {
 cout << arr[i] << " ";
}
cout << endl;
}

int main() {
int arr[] = {12, 11, 13, 5, 6};
int n = sizeof(arr) / sizeof(arr[0]);
inser onSort(arr, n);
cout << "Sorted array: ";
printArray(arr, n);
return 0;
}
2. Write a code of inser on sort?
#include <iostream>
using namespace std;

void selec onSort(int arr[], int n) {

for (int i = 0; i < n - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
}
swap(arr[minIdx], arr[i]);
}
}

void printArray(int arr[], int n) {

for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
}

int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);
selec onSort(arr, n);
cout << "Sorted array: ";
printArray(arr, n);
return 0;
}
Write a code of selec on sort?
#include <iostream>
using namespace std;

void selec onSort(int arr[], int n) {

for (int i = 0; i < n - 1; i++) {
int minIdx = i;
 for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
}
swap(arr[minIdx], arr[i]);
}
}

void printArray(int arr[], int n) {

for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
}

int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);
selec onSort(arr, n);
cout << "Sorted array: ";
printArray(arr, n);
return 0;
}

Data Structure:
Data structure is the linear and non-linear data type that performs storage and calcula on to manage
the data with efficiency.
The Data Structure is not a specific programming language. It's a set of algorithms that can use in any
programming language for structuring data in memory.
Data Structure:

• Primi ve Data Structure

• Int, float, char

• Non-Primi ve Data Structure

• Linear
• Array
• Linked List
• Stack
• Queue

• Non-Linear
• Tree
• Graph

Linear Data Structure:

• The arrangement of data in the sequen al manner is known as Linear Data Structure. The data is
some mes used for this purpose.
• Array, Linked List, Stacks, and Queues,
• In this data structure, one element is connected to any one another element in a linear form.

Non-linear data:

• When an element is connected to the 'n' number of elements, known as non-linear data structure.
• Example: Trees and graphs.
• In this case, elements are arranged in a random manner.
Tree Graph

• Tree is a linear data structure. Graph is a non-linear data structure.

• Tree is a collec on of nodes, edges. - Graph is a collec on of (ver ces and edges).

T=(Nodes, Edges) T=(Ver ces, Edges)

• There is a unique node called root in a There is no unique node called root in

tree. graph.

• There will not be any cycle or loop. A cycle can be present/perform in graph.
• There is a hierarchical model. Graph is a network model.
• It always contains N-1 edges It can contain no. of edges depends upon graph.

Applica on: • For finding shortest path in network graph. It is used.

• It is used to take decisions for searching,

dele ng and inser ng any element in tree.

The provided text describes the concept of a linked list in computer science. Here's a breakdown:
Linked List

• A linked list is a linear data structure where elements, called nodes, are stored in a sequence.
• Each node contains a pointer to the next node in the sequence.
• Unlike arrays, linked lists do not store elements in con guous memory loca ons.

Structure of Linked List Nodes

Each node in a linked list consists of two parts:

1. Data: The value or informa on stored in the node.

2. Next: A pointer or reference to the next node in the list.

Types of Linked Lists

1. Singly Linked List: Each node points only to the next node in the sequence.

Doubly Linked List

Each node has two pointers: one poin ng to the next node and the other poin ng to the previous
node.
Circular Linked List
The last node points back to the first node.
Basic Opera ons

• Inser on: Adding a node at the beginning, end, or a specific posi on.
• Dele on: Removing a node from the beginning, end, or a specific posi on.
• Traversal: Accessing and displaying the nodes in the list.
• Searching: Finding a node with a specific value.

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

// Define the structure of the node.

void insertBeg(Node* &start, int value) {
Node* newNode = new Node();
// Allocate a new node and store the address of the node
newNode->data = value;
newNode->next = start;
start = newNode;
// Make the new node point to the previous start
// Update the start to the new node.
}

// Func on to display the linked list

void displayList(Node* start) {
Node* current = start;
while (current != nullptr) {
std::cout << current->data << " ";
current = current->next;
}
std::cout << std::endl;
}

Applica on of Queues and Des na on:

• Defini on: A Queue is a linear data structure following FIFO (First In, First Out) principle.
• Insert: Remove elements
• Remove: Add elements

• Types of Queues:
1. Simple Queue: Basic FIFO queue
2. Circular Queue: Rear connects to the front
3. Priority Queue: Dequeue based on priority
4. Deque: Add/remove from both ends

• Applica ons:
 1. CPU Scheduling: Manages tasks in opera ng systems
2. Disk Scheduling: Handles data access requests
3. BFS Algorithms: Traverses graphs level by level
4. Network Systems: Manages data packets in network protocols
5. Call Centers: Handles customer requests in order
6. Real Life: Ticket booking, load ordering etc.

It is important to note that while some OCR (Op cal Character Recogni on) tools and methods can
convert images to editable text or tables, the accuracy can vary. Reviewing and correc ng the
converted text may be necessary.

Applica ons:

• Storing Sparse matrix

• Graph Representa on
• Machine learning
• Database Systems

Disadvantages:

• Overhead of storing informa on

• Slower access compared to linear arrays

Tree Traversal: Tree traversal refers to visi ng all nodes in a systema c way. There are two types of
traversal:

1. Depth-First Traversal (DFS):

• Explore as far as possible along each branch before backtracking.

2. Breadth-First Traversal (BFS):

• Explore all nodes at the current level before moving to the next level.

| Row | Colun | Data |

| --- | --- | --- |
|1|2|5 |
|2|1|4 |
|3|2|3 |

Applica on of Tree Traversal

• In-order: Binary Search Tree (BST) Forward

• Pre-order: Expression trees and crea ng copies
• Post-order: Dele ng nodes, evalua ng expressions
• BFS: Finding the shortest path in unweighted graphs
Tridiagonal Array A tridiagonal array is a special type of square matrix where only the main diagonal,
the diagonal above it, and the diagonal below it have non-zero elements. All other elements are zero.
Main diagonal (d) = \[d1, d2, d3, d4] Upper diagonal (u) = \[u1, u2, u3] Lower diagonal (l) = \[l1, l2, l3]

(
d1 u1 0 0
u2 d2 u2 0
0 u3 d3 u3
0 0 b3 d4
)

Applica ons:
1. Numerical Solu ons
2. Physics and Engineering
3. Efficient memory usage

Advantages:
1. Reduced memory usage (stores only non-zero elements)
2. Faster computa on for solving linear systems.
Binary Search Tree (BST):
A Binary Search Tree is a type of binary tree in which each node has at most two children, with the
following proper es held:

1. Le Subtree Property: All nodes in the le subtree of a node have values less than the node's
value.
2. Right Subtree Property: All nodes in the right subtree of a node have values greater than the
node's value.
3. No Duplicate Values: BST does not allow duplicate values.

Structure:
Each node of a BST contains:

• A key/value
• A pointer/reference to its le child
• A pointer/reference to its right child
Example:
50
/ \
20 70
/ \ / \
10 40 60 80

• Le Subtree: 20, 10, 40 (all values < 50)

• Right Subtree: 70, 60, 80 (all values > 50)

Applica on:

• Searching
• Sor ng
• Data Organiza on
• Symbol Tables
Advantages:

• Efficient searching, inser on, and dele on O(log n) for balanced BST

Disadvantages:

• Performance degrades to O(n) for skewed BSTs (like a linked list)

Applica on of Linked Lists in Computer Science:

1. Dynamic Memory Alloca on: Linked lists are used to allocate memory dynamically. Unlike arrays,
linked lists do not require a fixed size, which helps in efficient memory u liza on.
2. Implementa on of Data Structures:
• Stacks and Queues: Linked lists are used to implement stacks and queues where the data
structure grows or shrinks dynamically.
• Graphs: Linked lists are used to represent graphs as adjacency lists.

3. Hash Tables: Chaining in hash tables can be implemented using linked lists to handle collisions.

File Management Systems:

• Linked lists are used in file systems to maintain files in dynamic sequence.

Database Management Systems:

• They are used to implement indexes and structures that need fast inser on and dele on.

Memory Management:

• Linked lists are used in memory management systems to track free and allocated memory blocks.

Polynomial Representa on:

• Linked lists can represent polynomials where each node stores the coefficient and exponent of the
polynomial term.

Why is the linked list known as a Dynamic Data Structure?

The provided image shows C++ code snippets related to linked lists. These snippets demonstrate
traversal and inser on opera ons.
Traversal of a Linked List
void traversalList(Node* head) {
Node* current = head;
while (current != NULL) {
cout << current->data << " ";
current = current->next;
}
}

This func on, traversalList, takes the head of a linked list as input and iterates through it. For each
node, it prints the data and moves to the next node un l the end of the list (NULL) is reached.
Inser on at the Beginning of a Linked List
Node* insertAtBeginning(Node* head, int newData) {
Node* newNode = new Node();
newNode->data = newData;
newNode->next = head;
head = newNode;
return head;
}

The func on insertAtBeginning inserts a new node with the given newData at the beginning of the
linked list. It creates a new node, assigns the data, points the new node's next to the original head,
and then updates the head to the new node. The func on returns the updated head of the list.

Linked lists are well-suited to dynamic data structures because:

• Dynamic Size: The size of a linked list can grow or shrink during run me. Unlike arrays, the memory
required for a linked list is allocated as needed, and nodes can be inserted or deleted easily.
• Efficient Memory U liza on: Memory is allocated only when needed and nodes are linked
dynamically, meaning no pre-defined memory is comprised like in arrays.
• Opera ons on Linked Lists: Traversal and Inser on (Pseudocode)
• Traversal Opera on: Traversal involves visi ng each node in the linked list one by one.

Produces a fixed-size output (hash value or hash code).

Example: For a key k, the hash func on h(k) maps the key to a value in the range [0 to m-1], where m
is the size of the hash table.
Proper es of a good hash func on:

• Uniform Distribu on: Distributes keys evenly across the table to minimize collisions.
• Determinis c: Given input produces the same hash value for the same key.
• Fast to Compute: Should compute the hash value quickly.

Hash Table:

• A data structure that stores key-value pairs.

• Uses the hash value of a key to determine the index where the value is stored.

Collisions occur when two different keys produce the same hash value. Collision resolu on strategies
are used to handle this.
Process of hashing:

1. Key Mapping: The key is passed to the hash func on, which computes a hash value.
2. Index Determina on: The hash value determines the index in the hash table where the data is
stored.
3. Storage: The data is stored at the computed index.
4. Retrieval: The key is passed to the hash func on again, and the corresponding data is accessed
using the index.

Collision Resolu on Techniques are used to manage situa ons where different keys result in the
same hash value.

Advantages of hashing:

• Fast Access: O(1) average me complexity for retrieval, inser on, and dele on.
• Efficient Storage: Reduces memory usage by only storing the keys and values. [noted from image]

Versa lity: Supports dynamic sets and is widely used in various applica ons.
Disadvantages:

• Collisions: Can degrade performance if not handled efficiently.

• Fixed size: Hash tables have a fixed size, lead leading to wasted memory or overflow.
• Complexity: Requires a good hash func on to minimize collisions and ensure performance.

Illustra ng the process/type of inser on and dele on of nodes in a circular linked list:
Circular Linked List
A circular linked list is a varia on where the last node points to the first node, forming a circle. This
unique structure ensures that traversal can con nue indefinitely from any node.
Inser on in a Circular Linked List
Inser on can occur at three posi ons:

1. At the beginning
2. At the end
3. At a specific posi on

Inser on at the Beginning

Steps:

1. Create a new node.

2. Point the new node's next to the start node.
3. Traverse to the last node and update its next to the new node.
4. Update the head pointer to the new node.

Inser on at a Specific Posi on

Steps:

1. Create a new node (desired inser on point)

2. Traverse to the posi on before the
3. Update the new node's next to
4. Update the current node's next to the new node

Illustra on:

• Ini al: 10 -> 20 -> 30 -> 40

• Insert: 25 a er 20
• Final: 10 -> 20 -> 25 -> 30 -> 40

Dele on in Circular Linked List: Dele on occurs at three posi ons:

1. At Beginning
2. At the end
3. At a specific posi on

Abs e at the Specific Posi ons:

1. Check if the list is empty. If not, obtain traverse to the node before the to be deleted node.
2. Update the node's next to skip the node to be deleted. Delete the unwanted node.

Illustra on: Ini al: In -> 20 -> 30 -> 10 Delete: 20 Result: In -> 30 -> 10
Diagram: Provide diagrams for both inser on and dele on processes. For example,
Traversal at the Beginning: Before: In -> 10 -> 20 -> 30 -> (head In) A er: 40 -> 10 -> 20 -> 30 ->
(head 40)
Dele on at Specific Posi on: Before: In -> 10 -> 20 -> 30 (head In) At Ami: In -> 10 -> 30 (head In)