Description:

Top 50+ University Data Structures Exam Questions and Answers (2025): Prepare for university exams with the most detailed, copyright-free questions and answers, including C code, expert explanations, and practical tips.

URL:
/50-university-data-structures-exam-questions-answers-2025

Top 50+ University Data Structures Exam Questions and Answers (2025)

Welcome to the Top 50+ University Data Structures Exam Questions and Answers (2025) blog post. If you’re preparing for university exams in data structures, this guide covers the most expected questions and detailed answers, including C code and practical explanations. The focus keyword appears throughout this post to help you find exactly what you need for your 2025 exam success.

Unit 1: C Programming Review & Linear Data Structures

1. What is a linked list? Explain its types and give a C code example for insertion at the beginning.

A linked list is a linear data structure where each element, called a node, contains data and a pointer (or reference) to the next node in the sequence. Unlike arrays, linked lists do not require contiguous memory allocation, which makes them flexible for dynamic memory usage. There are several types of linked lists:

Linked lists are useful for applications where frequent insertion and deletion of elements are required, such as implementing stacks, queues, and polynomial arithmetic. The main advantage of linked lists over arrays is that they can grow or shrink in size dynamically without the need to reallocate or reorganize the entire structure. However, they have slower access time for elements, as traversal is required from the head node.

c

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

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

void insertAtBeginning(struct Node** head, int newData) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = newData;
newNode->next = *head;
*head = newNode;
}

void printList(struct Node* node) {
while (node != NULL) {
printf(“%d -> “, node->data);
node = node->next;
}
printf(“NULL\n”);
}

int main() {
struct Node* head = NULL;
insertAtBeginning(&head, 10);
insertAtBeginning(&head, 20);
insertAtBeginning(&head, 30);
printList(head);
return 0;
}

2. How is a polynomial represented using a linked list? Write a C function to add two polynomials.

Polynomials can be efficiently represented using linked lists, where each node contains two fields: the coefficient and the exponent of a term. The nodes are linked in the order of decreasing exponents. This representation allows easy addition, subtraction, and multiplication of polynomials, as terms with the same exponent can be combined by traversing the lists.

To add two polynomials, traverse both lists simultaneously, compare the exponents, and add the coefficients if exponents match. If one exponent is higher, add that term to the result and move forward in that list. This approach is more memory-efficient for sparse polynomials (where many coefficients are zero) compared to using arrays.

c

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

struct PolyNode {
int coeff;
int exp;
struct PolyNode* next;
};

struct PolyNode* addPolynomials(struct PolyNode* poly1, struct PolyNode* poly2) {
struct PolyNode* result = NULL;
struct PolyNode** lastPtr = &result;
while (poly1 && poly2) {
if (poly1->exp > poly2->exp) {
*lastPtr = poly1;
poly1 = poly1->next;
} else if (poly1->exp < poly2->exp) {
*lastPtr = poly2;
poly2 = poly2->next;
} else {
poly1->coeff += poly2->coeff;
*lastPtr = poly1;
poly1 = poly1->next;
poly2 = poly2->next;
}
lastPtr = &((*lastPtr)->next);
}
*lastPtr = poly1 ? poly1 : poly2;
return result;
}

3. Explain the difference between arrays and linked lists with respect to memory allocation and operations. Give a code example for array insertion.

Arrays and linked lists are both linear data structures but differ significantly in memory allocation and operation efficiency.

c

#include <stdio.h>

void insertElement(int arr[], int* n, int pos, int value) {
for (int i = *n; i > pos; i–) {
arr[i] = arr[i – 1];
}
arr[pos] = value;
(*n)++;
}

int main() {
int arr[10] = {1, 2, 4, 5};
int n = 4;
insertElement(arr, &n, 2, 3); // Insert 3 at position 2
for (int i = 0; i < n; i++) {
printf(“%d “, arr[i]);
}
return 0;
}

4. Describe memory representation of a doubly linked list and write code for node deletion.

A doubly linked list consists of nodes where each node contains three fields: data, a pointer to the next node, and a pointer to the previous node. This allows traversal in both directions and makes deletion of a node more efficient, as you can directly access both neighbors. The head node’s previous pointer and the tail node’s next pointer are set to NULL.

c

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

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

void deleteNode(struct DNode** head, struct DNode* del) {
if (*head == NULL || del == NULL) return;
if (*head == del) *head = del->next;
if (del->next != NULL) del->next->prev = del->prev;
if (del->prev != NULL) del->prev->next = del->next;
free(del);
}

5. What is dynamic memory allocation in C? How is it used in linked lists? Give an example.

Dynamic memory allocation in C allows programs to request memory at runtime using functions like malloc, calloc, realloc, and to release it using free. This is essential for data structures like linked lists, where the number of elements is not known in advance and can change during execution. When a new node is needed in a linked list, memory is allocated using malloc. When a node is deleted, its memory is released using free. This efficient memory management avoids wastage and allows flexible data structures.

c

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

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

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

int main() {
struct Node* head = createNode(10);
head->next = createNode(20);
printf(“%d -> %d\n”, head->data, head->next->data);
free(head->next);
free(head);
return 0;
}

Unit 2: Stacks and Queues

1. What is a stack? Explain its applications and give a C code for push and pop operations.

A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle, meaning the last element added is the first to be removed. Stacks are widely used in programming for function call management (call stack), expression evaluation, undo mechanisms in editors, and backtracking algorithms. The main operations are push (add to top), pop (remove from top), peek (view top element), and isEmpty (check if stack is empty). Stacks can be implemented using arrays or linked lists. Here’s a simple C code for stack push and pop using an array:

c

#define MAX 100
int stack[MAX], top = -1;

void push(int value) {
if (top == MAX – 1) printf(“Stack Overflow\n”);
else stack[++top] = value;
}

int pop() {
if (top == -1) {
printf(“Stack Underflow\n”);
return -1;
}
return stack[top–];
}

2. How can you implement a stack using a linked list in C?

A stack can be efficiently implemented using a singly linked list, where each node contains data and a pointer to the next node. The top of the stack is represented by the head of the list. Push inserts a new node at the head, and pop removes the node from the head. This approach allows dynamic stack size and avoids overflow unless memory is exhausted.

c

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

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

void push(struct Node** top, int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = *top;
*top = newNode;
}

int pop(struct Node** top) {
if (*top == NULL) return -1;
struct Node* temp = *top;
int val = temp->data;
*top = temp->next;
free(temp);
return val;
}

3. Describe how stack is used in infix to postfix conversion. Provide code for the conversion.

Infix to postfix conversion uses a stack to temporarily hold operators and ensure correct precedence and associativity. Operands are added directly to the output. Operators are pushed to the stack, but if the stack top has higher or equal precedence, pop operators to output before pushing the new one. Parentheses are used to control precedence: push ‘(‘ and pop until ‘(‘ when ‘)’ is encountered. At the end, pop any remaining operators to output. This ensures the resulting postfix expression can be evaluated without parentheses.

#include <stdio.h>
#include <ctype.h>
#define MAX 100

char stack[MAX];
int top = -1;

void push(char c) { stack[++top] = c; }
char pop() { return stack[top–]; }
char peek() { return stack[top]; }
int precedence(char op) {
if (op == ‘+’ || op == ‘-‘) return 1;
if (op == ‘*’ || op == ‘/’) return 2;
return 0;
}

void infixToPostfix(char* exp) {
for (int i = 0; exp[i]; i++) {
char c = exp[i];
if (isalnum(c)) printf(“%c”, c);
else if (c == ‘(‘) push(c);
else if (c == ‘)’) {
while (top != -1 && peek() != ‘(‘) printf(“%c”, pop());
pop();
} else {
while (top != -1 && precedence(peek()) >= precedence(c)) printf(“%c”, pop());
push(c);
}
}
while (top != -1) printf(“%c”, pop());
}

4. What is recursion? How does the stack help in recursion? Give a C example.

Recursion is a programming technique where a function calls itself to solve smaller instances of a problem. Each recursive call creates a new entry on the call stack, storing local variables and return addresses. The stack ensures that each function call has its own context, and when a base case is reached, the stack unwinds, returning results back up the chain. A classic example is the factorial function:c

int factorial(int n) {
if (n == 0) return 1; // base case
else return n * factorial(n - 1); // recursive case
}

Each call to factorial waits on the stack until the base case is reached, then the results are multiplied as the stack unwinds.

5. What is a queue? List its main types and operations.

A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle, meaning the first element added is the first to be removed. Main operations are enqueue (add to rear), dequeue (remove from front), front/peek (view front element), and isEmpty (check if the queue is empty). Types of queues include:

6. How is a circular queue implemented in C? What are its advantages?

A circular queue uses an array with two pointers, front and rear. When rear reaches the end, it wraps around to the beginning if space is available. This avoids the “false overflow” problem of linear queues, making efficient use of available space.

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

void enqueue(int val) {
if ((rear + 1) % SIZE == front) printf(“Queue Full\n”);
else {
if (front == -1) front = 0;
rear = (rear + 1) % SIZE;
queue[rear] = val;
}
}

int dequeue() {
if (front == -1) {
printf(“Queue Empty\n”);
return -1;
}
int val = queue[front];
if (front == rear) front = rear = -1;
else front = (front + 1) % SIZE;
return val;
}

7. What is a double-ended queue (deque)? Where is it used?

A deque (double-ended queue) is a data structure that allows insertion and deletion at both the front and rear ends. It supports operations like InsertFront, InsertRear, DeleteFront, and DeleteRear. Deques are used in algorithms that require both stack and queue operations, such as palindrome checking, undo operations in editors, and implementing sliding window problems.

8. Explain the concept of a priority queue with a code example.

A priority queue is a data structure where each element has a priority, and elements with higher priority are served before those with lower priority. Priority queues are commonly implemented using heaps for efficient insertion and removal. Here’s a simple C code using arrays (not efficient for large data):

#define MAX 100
int pq[MAX], n = 0;

void insert(int val) {
int i = n – 1;
while (i >= 0 && pq[i] < val) {
pq[i + 1] = pq[i];
i–;
}
pq[i + 1] = val;
n++;
}

int removeMax() {
if (n == 0) return -1;
return pq[–n];
}

In this example, higher values have higher priority.

9. How are queues used in operating systems?

Queues are fundamental in operating systems for managing processes and resources. For example:

Queues ensure fairness and order in servicing requests, preventing starvation and deadlock.

10. Write a C program to implement a queue using a linked list.

A queue can be implemented using a linked list with two pointers: front and rear. Enqueue adds a node at the rear, and dequeue removes a node from the front.

c

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

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

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

void enqueue(int val) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = val;
newNode->next = NULL;
if (rear == NULL) {
front = rear = newNode;
} else {
rear->next = newNode;
rear = newNode;
}
}

int dequeue() {
if (front == NULL) return -1;
struct Node* temp = front;
int val = temp->data;
front = front->next;
if (front == NULL) rear = NULL;
free(temp);
return val;
}

Unit 3: Trees

1. What is a binary tree? Explain its properties and applications.

A binary tree is a hierarchical data structure in which each node has at most two children, referred to as the left and right child. The topmost node is called the root. Properties include the height (longest path from root to leaf), depth (distance from root to a node), and degree (number of children). Binary trees are used in expression parsing, hierarchical data storage, and as the basis for more advanced structures like binary search trees and heaps. They are also used in Huffman coding for data compression and in file system indexing. The structure allows efficient searching, insertion, and deletion, making them fundamental in computer science.

2. What is a binary search tree (BST)? Write C code to insert a node.

A binary search tree (BST) is a special type of binary tree where each node’s left child contains values less than the node and the right child contains values greater than the node. This property enables efficient searching, insertion, and deletion, typically in O(log n) time for balanced trees. BSTs are widely used in searching applications, database indexing, and maintaining sorted data. Insertion involves traversing from the root and placing the new node at the correct position.

c

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

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

struct Node* insert(struct Node* root, int key) {
if (root == NULL) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = key;
newNode->left = newNode->right = NULL;
return newNode;
}
if (key < root->data) root->left = insert(root->left, key);
else if (key > root->data) root->right = insert(root->right, key);
return root;
}

3. Describe inorder, preorder, and postorder tree traversals with C code.

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

c

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

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

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

4. What is an AVL tree? How is it different from a BST? Provide a rotation example.

An AVL tree is a self-balancing binary search tree where the difference in heights of left and right subtrees (the balance factor) is at most one for every node. AVL trees maintain O(log n) time for search, insertion, and deletion by performing rotations after modifications. Unlike a plain BST, which can become unbalanced and degrade to O(n) time, AVL trees guarantee balance. Rotations (LL, RR, LR, RL) are performed to restore balance. For example, in a left-left (LL) case, a right rotation is used to balance the tree.

5. Explain the concept of a heap. How is a max-heap implemented in C?

A heap is a complete binary tree where each node satisfies the heap property: in a max-heap, every parent node is greater than or equal to its children. Heaps are used in priority queues and heap sort. A max-heap can be efficiently implemented using an array, where for any index i, left child is at 2i+1 and right child at 2i+2. Heapify is used to maintain the heap property.

c

void heapify(int arr[], int n, int i) {
int largest = i, l = 2*i + 1, r = 2*i + 2;
if (l < n && arr[l] > arr[largest]) largest = l;
if (r < n && arr[r] > arr[largest]) largest = r;
if (largest != i) {
int temp = arr[i]; arr[i] = arr[largest]; arr[largest] = temp;
heapify(arr, n, largest);
}
}

6. What is a B-tree? Where is it used?

A B-tree is a self-balancing, multi-way search tree used for storing large amounts of sorted data. Each node can have multiple keys and children, reducing the tree’s height and making disk reads/writes efficient. B-trees are widely used in databases and file systems for indexing and efficient data retrieval. All leaves are at the same level, and internal nodes have a variable number of children within a specified range, ensuring balance and minimizing disk access.

7. Explain the difference between a B-tree and a B+ tree.

Both are balanced multi-way search trees, but B-trees store data in both internal and leaf nodes, while B+ trees store data only in leaf nodes. B+ trees link leaf nodes, making range queries and sequential access faster. B+ trees are preferred in databases for efficient range queries, as all records are found at the leaf level and leaves are linked for fast traversal.

8. What is a red-black tree? List its properties.

A red-black tree is a self-balancing binary search tree with an extra bit for color (red or black) in each node. Properties include: every node is either red or black, the root is always black, red nodes cannot have red children, and every path from a node to its descendant NULL nodes has the same number of black nodes. These properties ensure the tree remains balanced, guaranteeing O(log n) time for insertion, deletion, and search.

9. How are trees used in file systems?

Trees, especially hierarchical trees, are used to represent file system structures. The root node represents the root directory, internal nodes represent folders, and leaf nodes represent files. Traversing the tree allows navigation through directories and files, enabling efficient searching, insertion, and deletion. Trees also support hierarchical organization and access control in modern file systems.

10. Write C code for searching a value in a binary search tree.

BST search starts from the root and recursively traverses left or right based on value comparison.

c

struct Node* search(struct Node* root, int key) {
if (root == NULL || root->data == key) return root;
if (key < root->data) return search(root->left, key);
else return search(root->right, key);
}

Unit 4: Graphs

1. What is a graph? Explain its types and applications.

A graph is a collection of vertices (nodes) and edges (connections) that can represent relationships or networks. Types include directed graphs (edges have direction), undirected graphs (edges have no direction), weighted graphs (edges have weights), and unweighted graphs. Applications include social networks, computer networks, maps, GPS navigation, and modeling dependencies in project management. Graphs are fundamental for representing any interconnected data.

2. How can a graph be represented in memory? Give C code for adjacency list representation.

Graphs can be represented as adjacency matrices (2D arrays) or adjacency lists (array of linked lists). Adjacency lists are more memory efficient for sparse graphs.

#define V 5
struct Node {
int dest;
struct Node* next;
};
struct Node* adjList[V];

void addEdge(int src, int dest) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->dest = dest;
newNode->next = adjList[src];
adjList[src] = newNode;
}

3. What is Depth First Search (DFS)? Write a C function for DFS.

DFS is a graph traversal algorithm that explores as far as possible along each branch before backtracking. It uses a stack or recursion. DFS is used for path finding, cycle detection, and topological sorting.c

void DFS(int v, int visited[], struct Node* adjList[]) {
visited[v] = 1;
printf("%d ", v);
for (struct Node* p = adjList[v]; p; p = p->next)
if (!visited[p->dest]) DFS(p->dest, visited, adjList);
}

4. What is Breadth First Search (BFS)? Write a C function for BFS.

BFS is a graph traversal algorithm that explores all neighbors of a node before moving to the next level. It uses a queue. BFS is used for shortest path in unweighted graphs, level order traversal, and connectivity checking.

#define V 5

#define V 5
void BFS(int start, struct Node* adjList[]) {
int visited[V] = {0}, queue[V], front = 0, rear = 0;
visited[start] = 1;
queue[rear++] = start;
while (front < rear) {
int v = queue[front++];
printf("%d ", v);
for (struct Node* p = adjList[v]; p; p = p->next)
if (!visited[p->dest]) {
visited[p->dest] = 1;
queue[rear++] = p->dest;
}
}
}

5. Explain Kruskal’s algorithm for Minimum Spanning Tree (MST).

Kruskal’s algorithm finds an MST in a weighted, undirected graph. It sorts all edges by weight and adds the smallest edge to the MST, avoiding cycles, until all vertices are connected. Union-Find data structure is used to detect cycles efficiently. Kruskal’s algorithm is efficient for sparse graphs and is used in network design and clustering.

6. Describe Prim’s algorithm for MST.

Prim’s algorithm also finds an MST but starts from a chosen vertex and grows the MST one edge at a time. At each step, it adds the smallest edge connecting the MST to a new vertex. Prim’s algorithm is efficient for dense graphs and can be implemented using priority queues. It is commonly used in designing network topologies.

7. What is Dijkstra’s algorithm? Where is it used?

Dijkstra’s algorithm finds the shortest path from a source node to all other nodes in a weighted graph with non-negative edges. It initializes distances, uses a priority queue to pick the minimum distance vertex, and updates distances of adjacent vertices. Dijkstra’s algorithm is used in GPS navigation, network routing protocols, and game AI pathfinding.

8. Compare DFS and BFS.

DFS uses stack/recursion, explores deep before backtracking, and is good for pathfinding and cycle detection. BFS uses a queue, explores all neighbors at the current depth before moving deeper, and is better for finding shortest paths in unweighted graphs. BFS guarantees shortest path, while DFS may not.

9. What is a weighted graph? Give an example.

A weighted graph assigns a numerical value (weight or cost) to each edge. For example, in a road map, intersections are vertices, roads are edges, and distances are weights. Weighted graphs are used in shortest path algorithms like Dijkstra and network optimization.

10. How are graphs used in real-world applications?

Graphs model relationships and networks:

Unit 5: Sorting, Searching, Hashing, and Applications

1. Explain bubble sort with a C code example.

Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process is repeated until the list is sorted. Bubble sort is easy to implement but inefficient for large datasets (O(n^2) time).

c

void bubbleSort(int arr[], int n) {
for (int i = 0; i < n-1; i++)
for (int j = 0; j < n-i-1; j++)
if (arr[j] > arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}

2. Describe quick sort and provide a C function for it.

Quick sort is a divide-and-conquer algorithm that selects a pivot element, partitions the array into two subarrays (less than and greater than the pivot), and recursively sorts the subarrays. It has average time complexity O(n log n).

c

int partition(int arr[], int low, int high) {
int pivot = arr[high], i = low-1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
}
}
int temp = arr[i+1]; arr[i+1] = arr[high]; arr[high] = temp;
return i+1;
}

void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi-1);
quickSort(arr, pi+1, high);
}
}

3. What is selection sort? Write its algorithm and C code.

Selection sort repeatedly finds the minimum element from the unsorted part and puts it at the beginning. It is simple but has O(n^2) time complexity.

c

void selectionSort(int arr[], int n) {
for (int i = 0; i < n-1; i++) {
int min_idx = i;
for (int j = i+1; j < n; j++)
if (arr[j] < arr[min_idx]) min_idx = j;
int temp = arr[min_idx]; arr[min_idx] = arr[i]; arr[i] = temp;
}
}

4. Explain heap sort with C code.

Heap sort uses a binary heap to sort elements.

c

void heapify(int arr[], int n, int i) {
int largest = i, l = 2*i+1, r = 2*i+2;
if (l < n && arr[l] > arr[largest]) largest = l;
if (r < n && arr[r] > arr[largest]) largest = r;
if (largest != i) {
int temp = arr[i]; arr[i] = arr[largest]; arr[largest] = temp;
heapify(arr, n, largest);
}
}

void heapSort(int arr[], int n) {
for (int i = n/2-1; i >= 0; i–) heapify(arr, n, i);
for (int i = n-1; i >= 0; i–) {
int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp;
heapify(arr, i, 0);
}
}

5. What is merge sort? Write its C implementation.

Merge sort is a divide-and-conquer algorithm that divides the array into halves, sorts each half, and merges them. It has O(n log n) time complexity and is stable.

c

void merge(int arr[], int l, int m, int r) {
int n1 = m-l+1, n2 = r-m;
int L[n1], R[n2];
for (int i = 0; i < n1; i++) L[i] = arr[l+i];
for (int j = 0; j < n2; j++) R[j] = arr[m+1+j];
int i=0, j=0, k=l;
while (i < n1 && j < n2)
arr[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
}

void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l+(r-l)/2;
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}

6. Describe radix sort and its use cases.

Radix sort is a non-comparative sorting algorithm for integers. It processes digits from least significant to most significant, using counting sort as a subroutine. It is efficient (O(nk)) for sorting large numbers or strings of fixed length. Radix sort is used in sorting phone numbers, IDs, and large datasets where comparison-based sorts are slow.

7. What is binary search? Write a C function for it.

Binary search finds an element in a sorted array by repeatedly dividing the search interval in half. It has O(log n) time complexity.

c

int binarySearch(int arr[], int n, int key) {
int low = 0, high = n-1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == key) return mid;
else if (arr[mid] < key) low = mid + 1;
else high = mid - 1;
}
return -1;
}

8. Explain hashing and how collisions are resolved.

Hashing maps keys to indices in an array using a hash function. Collisions occur when two keys map to the same index. Collision resolution techniques include chaining (using linked lists at each index) and open addressing (probing for next available slot). Hashing is used in hash tables, symbol tables, and databases for fast search and retrieval.

9. What is indexing in databases? How do B+ trees help?

Indexing speeds up data retrieval in databases by creating a data structure (index) that allows fast searches. B+ trees are used for indexing because they are balanced, ensuring O(log n) search time. All data is stored at the leaf level, and leaves are linked for fast range queries. B+ trees minimize disk reads/writes due to high branching factor.

10. Give real-world applications of sorting and searching algorithms.

Sorting and searching are fundamental in e-commerce (product listings), search engines (query results), databases (data retrieval), operating systems (process scheduling), and networking (routing tables). Efficient algorithms improve performance and user experience in these applications.