1.

Define Data Structure

A data structure is a way of organizing and storing data in a computer so
that it can be accessed and modified efficiently. Examples: Arrays, Linked
Lists, Stacks, Queues.

2. Mention Types of Data Structure

Linear: Arrays, Linked Lists, Stacks, Queues
Non-linear: Trees, Graphs
Static: Arrays (fixed size)
Dynamic: Linked Lists (grow/shrink at runtime)

3. What is Abstract Data Type (ADT)?

An ADT is a mathematical model for data types that defines operations on
the data without specifying implementation. Example: Stack (with push,
pop operations).

4. Draw Abstract Data Type Model

+---------------------+
| ADT Stack |
+---------------------+
| - push(item) |
| - pop() |
| - peek() |
| - isEmpty() |
+---------------------+
(Implementation is hidden, only operations are exposed.)

5. Define Array
An array is a collection of elements of the same type stored in contiguous
memory locations.
Example in C:
int arr[5] = {1, 2, 3, 4, 5};

6. Define Multi-dimensional Array

An array with more than one dimension (e.g., 2D array as a matrix).
Example in C:
int matrix[2][3] = {{1, 2, 3}, {4, 5, 6}};

7. Define Asymptotic Notation

Mathematical notations to describe the running time or space complexity of
an algorithm in terms of input size (e.g., Big-O, Omega, Theta).

8. Define Big-O Notation

Big-O describes the upper bound of an algorithm's complexity (worst-case
scenario).
Example: O(n) for linear search.
9. Define Big-Omega Notation
Omega describes the lower bound of an algorithm's complexity (best-case
scenario).
Example: Ω(1) for accessing an array element.

10. Define Theta Notation

Theta describes tight bounds (both upper and lower) for an algorithm's
complexity.
Example: Θ(n) for traversing an array.

11. Define Time and Space Complexity

Time Complexity: Measures the amount of time an algorithm takes relative
to input size.
Space Complexity: Measures the memory used by an algorithm relative to
input size.

12. Define Algorithm

A step-by-step procedure to solve a problem or perform a computation.
Example: Sorting an array using Bubble Sort.

13. Define Linked List

A linear data structure where elements (nodes) are linked using pointers.
Each node contains data and a pointer to the next node.
Example in C:
struct Node {
int data;
struct Node* next;
};

14. Mention Types of Linked List

Singly Linked List
Doubly Linked List
Circular Linked List

15. Define Stack

A LIFO (Last-In-First-Out) data structure where insertion (push) and
deletion (pop) happen at the same end (top).
16. Memory Representation of Stacks
Array-based: Contiguous memory with a top index.
Linked List-based: Nodes dynamically allocated with a head pointer.

17. Infix to Postfix: (a+b)*(c+d)

Postfix: a b + c d + *

18. Define Tower of Hanoi Problem

A mathematical puzzle where disks are moved from one rod to another
following rules:
Only one disk can be moved at a time.
A larger disk cannot be placed on a smaller disk.

19. Recursive vs Non-Recursive Functions

Recursive: Calls itself (e.g., factorial using recursion).
Non-Recursive: Uses loops (e.g., factorial using iteration).

20. Define Queue

A FIFO (First-In-First-Out) data structure where insertion (enqueue)
happens at the rear and deletion (dequeue) at the front.

21. Define Types of Queues

Linear Queue
Circular Queue
Priority Queue
Double-Ended Queue (Deque)

22. Define Circular Queue

A queue where the rear connects back to the front to utilize empty spaces
efficiently.
Example in C:
int queue[MAX];
int front = -1, rear = -1;

23. Define Double-Ended Queue (Deque)

A queue where insertion/deletion can happen at both ends.

24. Define Circular Queue (Repeated)

Same as 22: A looped-back queue to avoid wastage of space.

25. What is Underflow and Overflow in Queues?

Underflow: Occurs when trying to dequeue from an empty queue.
Overflow: Occurs when trying to enqueue into a full queue (in fixed-size
implementations).

26. Define Tree

A tree is a non-linear hierarchical data structure with nodes connected by
edges, where one node is the root and others form subtrees.

27. Traversal Techniques of Tree

Inorder (Left-Root-Right)
Preorder (Root-Left-Right)
Postorder (Left-Right-Root)
Level-order (Breadth-First)

28. Define Binary Tree

A tree where each node has at most two children (left and right).
29. Define AVL Tree
A self-balancing Binary Search Tree (BST) where the height difference
(balance factor) of left and right subtrees is at most 1.

30. Define B-Tree

A balanced m-way tree where each node can have multiple keys and
children, used in databases for efficient disk access.

31. Define Trie

A tree-like structure for storing strings where each node represents a
character, used for efficient prefix-based searching.

32. Define Graph

A collection of vertices (nodes) connected by edges, representing
relationships (e.g., social networks).

33. Types of Graphs

Directed (Edges have direction)
Undirected (Edges are bidirectional)
Weighted (Edges have weights)
Cyclic (Contains cycles)
Acyclic (No cycles, e.g., trees)

34. Graph Traversal Techniques

Depth-First Search (DFS)
Breadth-First Search (BFS)
35. Define DFS
A traversal method that explores as far as possible along a branch before
backtracking (uses stack).

36. Define BFS

A traversal method that explores all neighbors at the present depth before
moving deeper (uses queue).

37. Define Hash Function

A function that maps data of arbitrary size to a fixed-size value (hash) for
efficient storage/retrieval.
Example: hash(key) = key % table_size

38. 5 Sorting Techniques

Bubble Sort
Selection Sort
Insertion Sort
Merge Sort
Quick Sort
39. Memory Representation of Queue
Array-based: Contiguous block with front and rear indices.
Linked List-based: Nodes with head (front) and tail (rear) pointers.

40. Define Hash Table

A data structure that stores key-value pairs using a hash function for O(1)
average-time lookups.

41. Elementary Data Organization

Primitive Data Types (int, float, char)
Non-Primitive (Arrays, Structures)
Linear (Arrays, Lists)
Non-Linear (Trees, Graphs)

42. What is Data?

Data refers to raw, unorganized facts (e.g., numbers, characters) that can be
processed to produce meaningful information.
Example in C:
c
int age = 25; // Integer data
char name[] = "Alice"; // String (character array) data
43. What is Algorithm Complexity?
Algorithm complexity measures the resources (time/space) required by an
algorithm as input size grows.
Types:
Time Complexity: Steps needed (e.g., O(n)
Space Complexity: Memory used (e.g., O(1)).
1. What is an Array? (5 Marks)
Definition:
An array is a contiguous block of memory storing elements of the same data
type, accessed via indices.
Linear Array:
Fixed-size, sequential collection (e.g., int arr[5] = {10, 20, 30, 40, 50}).
Array as ADT:
Abstract Data Type (ADT) with operations:
Traverse, Insert, Delete, Search.
Example:
c
struct Array {
int *data;
int size;
};
Memory Representation:
Contiguous allocation (address A[i] = base_address + i * sizeof(datatype)).
Example:
c
int arr[3] = {10, 20, 30};
// Memory: [10][20][30] (adjacent addresses)

2. Traversing, Insertion & Deletion in Arrays (5 Marks)

Traversing Algorithm:
Start at index 0.
Print/process each element until the last index.
Program:
c
void traverse(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
 }
}
Insertion Algorithm:
Shift elements right from the target index.
Insert the new element.
Program:
c
void insert(int arr[], int *n, int pos, int val) {
for (int i = *n; i > pos; i--) {
arr[i] = arr[i - 1];
}
arr[pos] = val;
(*n)++;
}
Deletion Algorithm:
Shift elements left from the target index.
Program:
c
void delete(int arr[], int *n, int pos) {
for (int i = pos; i < *n - 1; i++) {
arr[i] = arr[i + 1];
}
(*n)--;
}

3. Matrix Programs (5 Marks)

Square Matrix:
N × N matrix (e.g., 3×3).
Program to Add Two Matrices:
c
void addMatrices(int A[3][3], int B[3][3], int C[3][3]) {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
C[i][j] = A[i][j] + B[i][j];
}
}
}
Matrix Manipulation:
Transpose Program:
c
void transpose(int mat[3][3], int res[3][3]) {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
res[j][i] = mat[i][j];
}
}
}
4. Operations on Arrays (5 Marks)
Searching (Linear Search):
c
int search(int arr[], int n, int key) {
for (int i = 0; i < n; i++) {
if (arr[i] == key) return i;
}
return -1;
}
Sorting (Bubble Sort):
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;
}
}
}
}

5. Types of Arrays (5 Marks)

1. One-Dimensional (1D) Array:
Linear list (e.g., int arr[5]).

2. Two-Dimensional (2D) Array:

Matrix (e.g., int mat[3][3]).

3. Multi-Dimensional Array:
Higher dimensions (e.g., int arr[2][3][4]).

4. Dynamic Arrays:
Resizable (e.g., int *arr = malloc(n * sizeof(int))).

5. Jagged Arrays:
Rows of varying lengths (e.g., int *arr[] = {new int[2], new int[3]} in C++).

Key Takeaways
Arrays: Contiguous, fixed-size, O(1) access.
Matrix: 2D array for grids/matrices.
Operations: Insert/delete with shifting, search/sort.
Types: 1D, 2D, dynamic, jagged.
6. Memory Representation of Arrays – Row-Major & Column-Major (5
Marks)
Row-Major Order:
Definition: Elements are stored row-wise in memory.
Formula:
For a 2D array A[m][n], address of A[i][j] is:
text
Base Address + (i * n + j) * sizeof(datatype)
Example:
c
int A[2][3] = {{1, 2, 3}, {4, 5, 6}};
// Memory: [1][2][3][4][5][6]
Column-Major Order:
Definition: Elements are stored column-wise in memory.
Formula:
For a 2D array A[m][n], address of A[i][j] is:
text
Base Address + (j * m + i) * sizeof(datatype)
Example:
c
int A[2][3] = {{1, 2, 3}, {4, 5, 6}};
// Memory: [1][4][2][5][3][6]
Key Difference:
Row-Major: Used in C, Python (numpy default).
Column-Major: Used in Fortran, MATLAB.

7. What is Sorting? (5 Marks)

Definition:
Sorting arranges elements in a specific order (ascending/descending).
Types:
Comparison-Based: Bubble Sort, Quick Sort.
Non-Comparison-Based: Counting Sort.
Applications:
Databases (indexing), search algorithms (Binary Search).

8. Bubble Sort (5 Marks)

Algorithm:
Compare adjacent elements.
Swap if they are in the wrong order.
Repeat for n-1 passes.
Program:
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;
}
}
}
}
Manual Example:
Input: [5, 1, 4, 2]
Pass 1: [1, 4, 2, 5]
Pass 2: [1, 2, 4, 5]
Time Complexity: O(n²).

9. Quick Sort (5 Marks)

Algorithm:
Choose a pivot (last element).
Partition:
Elements < pivot → left.
Elements > pivot → right.
Recursively sort left and right partitions.
Program:
c
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i+1], &arr[high]);
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);
}
}
Manual Example:
Input: [10, 7, 8, 9]
Pivot = 9: Partition → [7, 8, 9, 10]
Time Complexity: O(n log n) (average).

10. Selection Sort (5 Marks)

Algorithm:
Find the minimum element in the unsorted part.
Swap it with the first unsorted element.
Repeat for n-1 passes.
Program:
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;
}
swap(&arr[i], &arr[min_idx]);
}
}
Manual Example:
Input: [5, 1, 4, 2]
Pass 1: [1, 5, 4, 2]
Pass 2: [1, 2, 4, 5]
Time Complexity: O(n²).

Key Takeaways
Memory Layout: Row-major (C), Column-major (Fortran).
Sorting:
Bubble Sort: Simple but slow (O(n²)).
Quick Sort: Fast (O(n log n)) but unstable.
Selection Sort: Minimizes swaps (O(n²)).

11. Merge Sort (5 Marks)

Algorithm:
Divide: Split the array into two halves.
Conquer: Recursively sort each half.
Merge: Combine the two sorted halves into a single sorted array.
Program:
c
#include <stdio.h>
void merge(int arr[], int l, int m, int r) {
int n1 = m - l + 1;
int 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) {
if (L[i] <= R[j]) arr[k++] = L[i++];
else arr[k++] = 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);
}
}

int main() {
int arr[] = {12, 11, 13, 5, 6};
int n = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, 0, n - 1);
for (int i = 0; i < n; i++) printf("%d ", arr[i]); // 5 6 11 12 13
return 0;
}
Manual Example:
Input: [12, 11, 13, 5, 6]
Steps:
Split into [12, 11] and [13, 5, 6].
Sort [12, 11] → [11, 12].
Sort [13, 5, 6] → [5, 6, 13].
Merge [11, 12] and [5, 6, 13] → [5, 6, 11, 12, 13].
Time Complexity: O(n log n).

12. Insertion Sort (5 Marks)

Algorithm:
Start from the second element (i = 1).
Compare with the previous elements and shift them right if greater.
Insert the current element in its correct position.
Program:
c
#include <stdio.h>
void insertionSort(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;
}
}
int main() {
int arr[] = {12, 11, 13, 5, 6};
int n = sizeof(arr) / sizeof(arr[0]);
insertionSort(arr, n);
for (int i = 0; i < n; i++) printf("%d ", arr[i]); // 5 6 11 12 13
return 0;
}
Manual Example:
Input: [12, 11, 13, 5, 6]
Pass 1: [11, 12, 13, 5, 6]
Pass 2: [5, 11, 12, 13, 6]
Pass 3: [5, 6, 11, 12, 13]
Time Complexity: O(n²) (worst-case), O(n) (best-case for sorted input).

13. Linear Search & Binary Search (5 Marks)

Linear Search:
Algorithm: Check each element sequentially.
Time Complexity: O(n).
Example:
c
int linearSearch(int arr[], int n, int key) {
for (int i = 0; i < n; i++) {
if (arr[i] == key) return i;
}
return -1;
}
Input: [10, 20, 30, 40], key = 30 → Output: 2.

Binary Search:
Algorithm: Divide the sorted array into halves.
Time Complexity: O(log n).
Example:
c
int binarySearch(int arr[], int l, int r, int key) {
while (l <= r) {
int mid = l + (r - l) / 2;
if (arr[mid] == key) return mid;
if (arr[mid] < key) l = mid + 1;
else r = mid - 1;
}
return -1;
}
Input: [10, 20, 30, 40], key = 30 → Output: 2.

14. Linked List & Memory Representation (5 Marks)

Definition:
A linked list is a linear data structure where elements (nodes) are
connected via pointers.

Memory Representation:
Each node contains:
Data: Value stored.
Next Pointer: Address of the next node.
Example:
c
struct Node {
int data;
struct Node *next;
};
Visualization: [10] -> [20] -> [30] -> NULL.

Types:
Singly Linked List: Unidirectional traversal.
Doubly Linked List: Bidirectional traversal (prev and next pointers).
Circular Linked List: Last node points back to the head.

15. Traversing a Linked List (5 Marks)

Algorithm:
Start at the head node.
Move to next until NULL is reached.
Program:
c
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *next;
};

void traverse(struct Node *head) {

struct Node *current = head;
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
}

int main() {
struct Node *head = (struct Node*)malloc(sizeof(struct Node));
head->data = 10;
head->next = (struct Node*)malloc(sizeof(struct Node));
head->next->data = 20;
head->next->next = NULL;
 traverse(head); // Output: 10 20
return 0;
}
Explanation:
head points to the first node.
Loop: Print current->data and move to current->next.

Key Takeaways
Merge Sort: Divide & conquer, O(n log n).
Insertion Sort: Builds sorted array incrementally, O(n²).
Searching:
Linear: Works on unsorted data.
Binary: Requires sorted data.
Linked List: Dynamic size, efficient insertions/deletions.

16. Memory Allocation in Linked Lists (5 Marks)

1. malloc (Memory Allocation)
Purpose: Allocates uninitialized memory for a node.
Syntax:
c
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
Example:
c
newNode->data = 10;
newNode->next = NULL;
2. calloc (Contiguous Allocation)
Purpose: Allocates zero-initialized memory.

Syntax:
c
struct Node* newNode = (struct Node*)calloc(1, sizeof(struct Node));
Use Case: When default zero values are needed.

3. realloc (Reallocation)
Purpose: Resizes memory (rarely used in linked lists).
Syntax:
c
ptr = (struct Node*)realloc(ptr, newSize);
4. free (Deallocation)
Purpose: Releases memory to prevent leaks.
Syntax:
c
free(nodeToDelete);
Critical: Always set freed pointers to NULL to avoid dangling pointers.

Example (Full Workflow):

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

int main() {
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
head->data = 10;
head->next = (struct Node*)malloc(sizeof(struct Node));
head->next->data = 20;
head->next->next = NULL;
free(head->next); // Deallocate second node
head->next = NULL;
free(head); // Deallocate head
head = NULL;
return 0;
}

17. What is Garbage Collection? (5 Marks)

Definition:
Garbage Collection (GC) is automatic memory management that reclaims
memory occupied by objects no longer in use.

Key Points:
Languages: Built into Java, Python, C# (not in C/C++).

Purpose: Prevents memory leaks and dangling pointers.

How It Works:
Mark: Identify reachable objects.
Sweep: Release unreachable memory.
Example (Manual GC in C):
c
void deleteList(struct Node** head) {
struct Node* current = *head;
while (current != NULL) {
struct Node* temp = current;
current = current->next;
free(temp); // Manual deallocation
}
*head = NULL;
}

18. Insertion & Deletion in Linked Lists (All Cases) (5 Marks)

1. Insertion
(a) At Head
c
void insertAtHead(struct Node** head, int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
 newNode->data = data;
newNode->next = *head;
*head = newNode;
}
Steps:
Allocate new node.
Point newNode->next to current head.
Update head to newNode.

(b) At Tail
c
void insertAtTail(struct Node** head, int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
if (*head == NULL) {
*head = newNode;
return;
}
struct Node* temp = *head;
while (temp->next != NULL) temp = temp->next;
temp->next = newNode;
}
Steps:
Traverse to the last node.
Link lastNode->next to newNode.

(c) After a Given Node

c
void insertAfter(struct Node* prevNode, int data) {
if (prevNode == NULL) return;
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = prevNode->next;
prevNode->next = newNode;
}
2. Deletion
(a) At Head
c
void deleteAtHead(struct Node** head) {
if (*head == NULL) return;
struct Node* temp = *head;
*head = (*head)->next;
free(temp);
}
(b) At Tail
c
void deleteAtTail(struct Node** head) {
if (*head == NULL) return;
if ((*head)->next == NULL) {
free(*head);
*head = NULL;
return;
}
struct Node* temp = *head;
while (temp->next->next != NULL) temp = temp->next;
free(temp->next);
temp->next = NULL;
}
(c) A Specific Value
c
void deleteNode(struct Node** head, int key) {
struct Node *temp = *head, *prev = NULL;
if (temp != NULL && temp->data == key) {
*head = temp->next;
free(temp);
return;
}
while (temp != NULL && temp->data != key) {
prev = temp;
temp = temp->next;
}
if (temp == NULL) return;
prev->next = temp->next;
free(temp);
}
Time Complexity:
Operation Time
Insert at Head O(1)
Insert at Tail O(n)
Delete by Value O(n)
Key Takeaways
Memory Allocation:

malloc/calloc for allocation, free for deallocation.

Garbage Collection:
Automatic in high-level languages; manual in C.

Linked List Operations:

Insertion: Head (O(1)), Tail (O(n)), Middle (O(n)).
Deletion: Similar to insertion.

19. Types of Linked Lists (5 Marks)

1. Singly Linked List
Structure: Each node has data and a next pointer.
Termination: Ends with NULL.
Example:
c
struct Node {
int data;
struct Node *next;
};
Visualization: [10] → [20] → [30] → NULL.

2. Doubly Linked List

Structure: Nodes have data, next, and prev pointers.

Example:
c
struct Node {
int data;
struct Node *prev;
struct Node *next;
};
Visualization: NULL ← [10] ⇄ [20] ⇄ [30] → NULL.

3. Circular Linked List

Structure: Last node points back to the head (no NULL).

Types:
Singly Circular: [10] → [20] → [30] → [10] (loop to head).
Doubly Circular: [10] ⇄ [20] ⇄ [30] ⇄ [10].
Use Case: Round-robin scheduling, multiplayer games.

Key Point:
Circular LL: Efficient for continuous loops (e.g., playlist rotation).

20. Difference Between Arrays and Linked Lists (5 Marks)

Feature Array Linked List
Memory Allocation Static (fixed size) Dynamic (grows/shrinks at
runtime)
Insertion/Deletion O(n) (shifting required) O(1) at head, O(n)
elsewhere
Access Time O(1) (random access) O(n) (sequential
access)
Memory Usage Contiguous (efficient for cache) Non-
contiguous (extra pointer overhead)
Use Case Fixed-size data, frequent access Frequent
insertions/deletions
Example:
Array: int arr[5] = {10, 20, 30};
Linked List: [10] → [20] → [30] → NULL.

21. Searching in a Singly Linked List (5 Marks)

Algorithm:
Start at the head node.
Traverse each node sequentially.
If current->data == key, return the node.
If the end (NULL) is reached, return "Not Found".
Program:
c
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *next;
};

int search(struct Node *head, int key) {

struct Node *current = head;
int position = 1;
while (current != NULL) {
if (current->data == key) return position;
current = current->next;
position++;
}
return -1; // Not found
}
int main() {
struct Node *head = (struct Node*)malloc(sizeof(struct Node));
head->data = 10;
head->next = (struct Node*)malloc(sizeof(struct Node));
head->next->data = 20;
head->next->next = NULL;

int key = 20;

int result = search(head, key);
if (result != -1) printf("Found at position: %d\n", result); // Output: 2
else printf("Not Found\n");
return 0;
}
Time Complexity:
Worst Case: O(n) (key at tail or absent).
Best Case: O(1) (key at head).

Key Takeaways
Linked List Types:
Circular LL is ideal for cyclic operations.
Arrays vs. LL:
Arrays for fast access, LL for dynamic operations.

Searching in LL:
Linear traversal (no binary search in unsorted LL).

22. Seven String Operations with C Programs (5 Marks)

1. String Length (strlen)
Purpose: Returns the length of a string (excluding \0).
Program:
c
#include <stdio.h>
#include <string.h>

int main() {
char str[] = "Hello";
printf("Length: %lu\n", strlen(str)); // Output: 5
return 0;
}
2. String Copy (strcpy)
Purpose: Copies a string to another.
Program:
c
#include <stdio.h>
#include <string.h>

int main() {
char src[] = "Copy Me";
char dest[20];
strcpy(dest, src);
printf("Copied: %s\n", dest); // Output: "Copy Me"
return 0;
}
3. String Concatenation (strcat)
Purpose: Appends one string to another.
Program:

c
#include <stdio.h>
#include <string.h>

int main() {
char str1[20] = "Hello";
char str2[] = " World";
strcat(str1, str2);
 printf("Concatenated: %s\n", str1); // Output: "Hello World"
return 0;
}
4. String Comparison (strcmp)
Purpose: Compares two strings lexicographically.
Program:

c
#include <stdio.h>
#include <string.h>

int main() {
char str1[] = "apple";
char str2[] = "banana";
int result = strcmp(str1, str2);
printf("Comparison: %d\n", result); // Output: -1 (str1 < str2)
return 0;
}
5. Substring Search (strstr)
Purpose: Finds the first occurrence of a substring.
Program:
c
#include <stdio.h>
#include <string.h>

int main() {
char str[] = "Hello World";
char sub[] = "World";
char *pos = strstr(str, sub);
printf("Found at: %s\n", pos); // Output: "World"
return 0;
}
6. String Reversal
Purpose: Reverses a string in-place.
Program:
c
#include <stdio.h>
#include <string.h>

void reverse(char *str) {

int n = strlen(str);
for (int i = 0; i < n / 2; i++) {
char temp = str[i];
str[i] = str[n - i - 1];
str[n - i - 1] = temp;
}
}
int main() {
char str[] = "Hello";
reverse(str);
printf("Reversed: %s\n", str); // Output: "olleH"
return 0;
}
7. String Tokenization (strtok)
Purpose: Splits a string into tokens using delimiters.
Program:
c
#include <stdio.h>
#include <string.h>

int main() {
char str[] = "Hello,World,C";
char *token = strtok(str, ",");
while (token != NULL) {
printf("Token: %s\n", token);
token = strtok(NULL, ",");
}
return 0;
}
Output:
text
Token: Hello
Token: World
Token: C

23. Pattern-Matching Algorithms with C Programs (5 Marks)

1. Naive Pattern Matching
Purpose: Checks for a pattern by sliding it over the text.
Program:
c
#include <stdio.h>
#include <string.h>

void naiveSearch(char *text, char *pattern) {

int n = strlen(text);
int m = strlen(pattern);
for (int i = 0; i <= n - m; i++) {
int j;
for (j = 0; j < m; j++) {
if (text[i + j] != pattern[j]) break;
}
if (j == m) printf("Pattern found at index %d\n", i);
}
}

int main() {
char text[] = "ABABDABACDABABCABAB";
char pattern[] = "ABABC";
naiveSearch(text, pattern); // Output: "Pattern found at index 10"
return 0;
}
2. Knuth-Morris-Pratt (KMP) Algorithm
Purpose: Optimizes pattern matching using the LPS (Longest Prefix Suffix)
array.
Program:
c
#include <stdio.h>
#include <string.h>

void computeLPS(char *pattern, int m, int *lps) {

int len = 0;
lps[0] = 0;
for (int i = 1; i < m; ) {
if (pattern[i] == pattern[len]) {
len++;
lps[i] = len;
i++;
} else {
if (len != 0) len = lps[len - 1];
else lps[i++] = 0;
}
}
}

void KMPSearch(char *text, char *pattern) {

int n = strlen(text);
int m = strlen(pattern);
int lps[m];
computeLPS(pattern, m, lps);
int i = 0, j = 0;
while (i < n) {
if (pattern[j] == text[i]) { i++; j++; }
if (j == m) {
printf("Pattern found at index %d\n", i - j);
j = lps[j - 1];
} else if (i < n && pattern[j] != text[i]) {
if (j != 0) j = lps[j - 1];
else i++;
}
}
}

int main() {
char text[] = "ABABDABACDABABCABAB";
char pattern[] = "ABABC";
KMPSearch(text, pattern); // Output: "Pattern found at index 10"
return 0;
}

24. Word Processing: Operations & Examples (5 Marks)

Definition:
Word processing involves creating, editing, formatting, and printing text
documents using software (e.g., MS Word, Google Docs).
Operations with Examples:
Text Editing:
Insert/delete characters.
Example: Correcting "Teh" → "The".
Formatting:
Font styles (bold, italic), alignment.
Example: Making headings bold and centered.
Spell Check:
Detects misspelled words (e.g., "recieve" → "receive").
Page Layout:
Margins, page size, columns.
Example: Setting 1-inch margins for a report.
Save & Print:
Save as .docx, .pdf, or print hard copies.
Example Workflow:
Draft a letter.
Edit text (fix typos).
Format with Arial font.
Spell-check.
Save as "[Link]".
Key Takeaways
String Operations: Use string.h functions for efficient manipulation.

Pattern Matching:
Naive: Simple but slow (O(mn)).
KMP: Optimized (O(n + m)).
Word Processing: Essential for document management in offices/education.

25. Syntax and Examples for if, if-else, while, for (5 Marks)
1. if Statement
Syntax:

c
if (condition) {
// Code to execute if condition is true
}
Example:

c
int x = 10;
if (x > 5) {
printf("x is greater than 5\n"); // Output: "x is greater than 5"
}
2. if-else Statement
Syntax:

c
if (condition) {
// Code if true
} else {
// Code if false
}
Example:
c
int age = 17;
if (age >= 18) {
printf("Adult\n");
} else {
printf("Minor\n"); // Output: "Minor"
}
3. while Loop
Syntax:

c
while (condition) {
// Code to repeat while condition is true
}
Example:

c
int i = 1;
while (i <= 3) {
printf("%d ", i); // Output: "1 2 3 "
i++;
}
4. for Loop
Syntax:

c
for (initialization; condition; update) {
// Code to repeat
}
Example:
c
for (int i = 0; i < 3; i++) {
printf("%d ", i); // Output: "0 1 2 "
}

26. Worst, Best, and Average Case Efficiency with Graphs (5 Marks)
1. Worst Case
Definition: Maximum time/space required for the largest input.

Example: Linear search when the key is not present (O(n)).

Graph:
plaintext
Time
↑
| Worst Case (O(n))
| /
| /
|____/________→ Input Size
2. Best Case
Definition: Minimum time/space required for the smallest input.
Example: Linear search when the key is at the first index (O(1)).
Graph:
plaintext
Time
↑
| Best Case (O(1))
| /
|_____/________→ Input Size
3. Average Case
Definition: Expected time/space for random inputs.
Example: Quicksort (O(n log n) on average).
Graph:

plaintext
Time
↑
| Average Case (O(n log n))
| /
| /
|____/________→ Input Size
Key Points:
Worst Case: Used for guarantees (e.g., real-time systems).
Best Case: Rarely used (optimistic scenarios).
Average Case: Most practical for general analysis.

27. malloc, calloc, realloc, free (5 Marks)

1. malloc (Memory Allocation)
Purpose: Allocates uninitialized memory.
Syntax:
c
ptr = (datatype*) malloc(size_in_bytes);
Example:
c
int *arr = (int*) malloc(5 * sizeof(int)); // Allocates 20 bytes (5 ints)
2. calloc (Contiguous Allocation)
Purpose: Allocates zero-initialized memory.
Syntax:
c
ptr = (datatype*) calloc(num_items, size_per_item);
Example:
c
int *arr = (int*) calloc(5, sizeof(int)); // Allocates and initializes to 0
3. realloc (Reallocation)
Purpose: Resizes previously allocated memory.
Syntax:
c
ptr = (datatype*) realloc(ptr, new_size_in_bytes);
Example:
c
arr = (int*) realloc(arr, 10 * sizeof(int)); // Resizes to 40 bytes
4. free (Deallocation)
Purpose: Releases allocated memory to prevent leaks.
Syntax:
c
free(ptr);
Example:
c
free(arr); // Frees the memory
arr = NULL; // Prevents dangling pointer

Key Differences:

Function Initialization Use Case

malloc No Dynamic arrays
calloc Yes (zero) Arrays needing zeros
realloc No Resizing memory

Key Takeaways
Control Structures:
if/else for decisions, while/for for loops.
Complexity Analysis:
Graphs show how time scales with input size.
Memory Management:
Always pair malloc/calloc with free to avoid leaks.

28. Different Storage Representations of Strings (5 Marks)

1. Fixed-Length (Array-Based) Representation
Description:
Strings are stored in fixed-size arrays with a null terminator (\0).
Max length is predefined (e.g., char str[100]).
Example:
c
char str[10] = "Hello"; // Stored as {'H', 'e', 'l', 'l', 'o', '\0', ...}
Pros:
Fast random access (O(1)).
Cons:
Wastes memory if unused.

2. Dynamic (Heap-Based) Representation

Description:
Strings are allocated dynamically using malloc/calloc.
Size can be adjusted with realloc.
Example:
c
char *str = (char*)malloc(6 * sizeof(char));
strcpy(str, "Hello"); // Stored as {'H', 'e', 'l', 'l', 'o', '\0'}
Pros:
Flexible size.
Cons:
Manual memory management (free required).

3. Linked List Representation

Description:
Each character is stored in a linked list node.
Example:
c
struct Node {
char data;
struct Node *next;
};
Pros:
No size limit.
Cons:
Slow random access (O(n)).

4. Length-Prefixed Representation
Description:
The first byte stores the string length.
Example:
c
char str[] = {5, 'H', 'e', 'l', 'l', 'o'}; // Length = 5
Pros:
Faster length calculation (O(1)).
Cons:
Limited to 255 characters (1-byte length).

29. Insert and Delete a String (Algorithm & Program) (5 Marks)

1. Insert a String
Algorithm:
Allocate memory for the new string (if dynamic).
Concatenate the new string at the desired position.

Program:
c
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void insertString(char **mainStr, const char *insertStr, int pos) {

int mainLen = strlen(*mainStr);
int insertLen = strlen(insertStr);
char *newStr = (char*)malloc(mainLen + insertLen + 1);

strncpy(newStr, *mainStr, pos); // Copy first part

newStr[pos] = '\0';
strcat(newStr, insertStr); // Insert new string
strcat(newStr, *mainStr + pos); // Append remaining part

free(*mainStr); // Free old string

*mainStr = newStr;
}

int main() {
char *str = strdup("Hello World"); // Dynamic string
insertString(&str, "C ", 6);
printf("After insertion: %s\n", str); // Output: "Hello C World"
free(str);
return 0;
}
2. Delete a Substring
Algorithm:
Find the substring using strstr.
Shift characters left to overwrite the substring.

Program:
c
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void deleteSubstring(char *str, const char *sub) {

char *pos = strstr(str, sub);
if (pos) {
int subLen = strlen(sub);
memmove(pos, pos + subLen, strlen(pos + subLen) + 1); // +1 for '\0'
}
}

int main() {
char str[] = "Hello World";
deleteSubstring(str, "World");
printf("After deletion: %s\n", str); // Output: "Hello "
return 0;
}
Key Takeaways
String Storage:
Fixed arrays for simplicity, dynamic for flexibility.
Insert/Delete:
Use strcat/memory move for efficient operations.
Dynamic strings require manual memory management.

30. What is a Stack? (5 Marks)

Definition:
A stack is a LIFO (Last-In-First-Out) linear data structure where elements
are inserted and deleted from the top only.
Operations:
Push: Insert an element.
Pop: Remove the top element.
Peek/Top: View the top element.
isEmpty: Check if the stack is empty.

Array Representation of Stack

Program:
c
#include <stdio.h>
#define MAX 100

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

void push(int item) {

if (top >= MAX - 1) {
printf("Stack Overflow\n");
return;
 }
stack[++top] = item;
}

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

int peek() {
if (top < 0) {
printf("Stack is Empty\n");
return -1;
}
return stack[top];
}

int isEmpty() {
return (top < 0);
}

int main() {
push(10);
push(20);
printf("Top element: %d\n", peek()); // 20
printf("Popped: %d\n", pop()); // 20
printf("Is empty? %d\n", isEmpty()); // 0 (False)
return 0;
}
Explanation:
Array stack stores elements.
top tracks the index of the top element.
Push: Increment top and insert.
Pop: Return stack[top] and decrement top.

Linked List Representation of Stack

Program:
c
#include <stdio.h>
#include <stdlib.h>

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

struct Node* top = NULL;

void push(int item) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = item;
newNode->next = top;
top = newNode;
}

int pop() {
if (top == NULL) {
printf("Stack Underflow\n");
return -1;
}
struct Node* temp = top;
int item = top->data;
top = top->next;
free(temp);
return item;
}

int peek() {
if (top == NULL) {
printf("Stack is Empty\n");
return -1;
}
return top->data;
}

int isEmpty() {
return (top == NULL);
}

int main() {
push(10);
push(20);
printf("Top element: %d\n", peek()); // 20
printf("Popped: %d\n", pop()); // 20
printf("Is empty? %d\n", isEmpty()); // 0 (False)
return 0;
}
Explanation:
top pointer points to the head of the linked list.
Push: Insert at the head.
Pop: Remove the head node.
31. Stack as an Abstract Data Type (ADT) (5 Marks)
Definition:
An ADT defines the behavior of a stack (operations) without specifying
implementation.

Stack ADT Operations:

push(x): Insert x at the top.
pop(): Remove and return the top element.
peek(): Return the top element without removal.
isEmpty(): Return True if the stack is empty.

Example:
c
// Abstract representation (no implementation)
void push(int x);
int pop();
int peek();
int isEmpty();
3. Polish Notation (Prefix, Infix, Postfix) (5 Marks)
Notation Operator Position Example
Infix Between operands A+B
Prefix Before operands +AB
Postfix After operands AB+
Examples:
Infix: (A + B) * C
Prefix: * + A B C
Postfix: A B + C *

32. Conversion of Infix to Postfix (5 Marks)

Algorithm:
Use a stack to hold operators.
Scan infix expression left to right:
Operand: Output it.
(: Push to stack.
): Pop and output until ( is found.
Operator: Pop higher/equal precedence operators, then push.

Program:
c
#include <stdio.h>
#include <string.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--]; }
int precedence(char op) {
switch(op) {
case '+': case '-': return 1;
case '*': case '/': return 2;
case '^': return 3;
default: return 0;
}
}

void infixToPostfix(char *infix, char *postfix) {

int i = 0, j = 0;
while (infix[i]) {
if (isalnum(infix[i])) postfix[j++] = infix[i++];
else if (infix[i] == '(') push(infix[i++]);
else if (infix[i] == ')') {
while (stack[top] != '(') postfix[j++] = pop();
pop(); // Remove '('
i++;
} else {
while (top != -1 && precedence(stack[top]) >= precedence(infix[i])) {
postfix[j++] = pop();
}
push(infix[i++]);
}
}
while (top != -1) postfix[j++] = pop();
postfix[j] = '\0';
}

int main() {
char infix[MAX] = "(A+B)*C-D";
char postfix[MAX];
infixToPostfix(infix, postfix);
printf("Postfix: %s\n", postfix); // Output: "AB+C*D-"
return 0;
}
Example:
Infix: (A + B) * C - D

Postfix: A B + C * D -

33. Evaluation of Postfix Expression (5 Marks)

Algorithm:
Use a stack to hold operands.
Scan postfix expression left to right:
Operand: Push to stack.
Operator: Pop top 2 operands, apply operator, push result.

Program:
c
#include <stdio.h>
#include <string.h>
#include <ctype.h>

#define MAX 100

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

void push(int x) { stack[++top] = x; }

int pop() { return stack[top--]; }

int evaluatePostfix(char *postfix) {

for (int i = 0; postfix[i]; i++) {
if (isdigit(postfix[i])) push(postfix[i] - '0');
else {
int op2 = pop(), op1 = pop();
switch(postfix[i]) {
case '+': push(op1 + op2); break;
case '-': push(op1 - op2); break;
case '*': push(op1 * op2); break;
case '/': push(op1 / op2); break;
}
}
}
return pop();
}

int main() {
char postfix[MAX] = "23+4*"; // (2+3)*4 = 20
printf("Result: %d\n", evaluatePostfix(postfix)); // Output: 20
return 0;
}
Example:
Postfix: 2 3 + 4 *

Steps:
Push 2, 3.
+ → 2 + 3 = 5 → Push 5.
Push 4.
* → 5 * 4 = 20 → Result.

Key Takeaways
Stack: LIFO structure with push, pop, peek.
ADT: Defines operations, not implementation.
Infix to Postfix: Use stack for operator precedence.
Postfix Evaluation: Stack for operand storage.

34. Applications of Stacks (5 Marks)

1. Function Call Management
Use: Stores return addresses and local variables during recursion.
Example: Call stack in C programs.

2. Expression Evaluation & Conversion

Use: Convert infix to postfix/prefix and evaluate postfix expressions.

3. Undo/Redo Operations
Use: Text editors (e.g., Ctrl+Z, Ctrl+Y).

4. Backtracking Algorithms
Use: Maze solving, puzzle games (e.g., Sudoku).

5. Memory Management
Use: Stack segment stores function calls and local variables.
35. Tower of Hanoi Using Recursion (5 Marks)
Problem Statement:
Move n disks from Source to Destination using an Auxiliary peg, following:
Only one disk can be moved at a time.
A larger disk cannot be placed on a smaller one.

Program:
c
#include <stdio.h>

void towerOfHanoi(int n, char source, char dest, char aux) {

if (n == 1) {
printf("Move disk 1 from %c to %c\n", source, dest);
return;
}
towerOfHanoi(n - 1, source, aux, dest);
printf("Move disk %d from %c to %c\n", n, source, dest);
towerOfHanoi(n - 1, aux, dest, source);
}

int main() {
int n = 3; // Number of disks
towerOfHanoi(n, 'A', 'C', 'B'); // A: Source, C: Destination, B: Auxiliary
 return 0;
}
Output:
text
Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C
Explanation:
Base Case: Move 1 disk from source to destination.
Recursive Steps:
Move n-1 disks from source to auxiliary.
Move the n-th disk to destination.
Move n-1 disks from auxiliary to destination.

Time Complexity: O(2ⁿ) (Exponential).

36. What is a Queue? (5 Marks)
Definition:
A queue is a FIFO (First-In-First-Out) linear data structure where elements
are:
Inserted (enqueue) at the rear.
Deleted (dequeue) from the front.
Array Representation of Queue
Program:
c
#include <stdio.h>
#define MAX 100

int queue[MAX];
int front = -1, rear = -1;

void enqueue(int item) {

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

int dequeue() {
if (front == -1 || front > rear) {
printf("Queue Underflow\n");
return -1;
 }
return queue[front++];
}

int isEmpty() {
return (front == -1 || front > rear);
}

int main() {
enqueue(10);
enqueue(20);
printf("Dequeued: %d\n", dequeue()); // 10
printf("Is empty? %d\n", isEmpty()); // 0 (False)
return 0;
}
Explanation:
front tracks the first element.
rear tracks the last element.
Enqueue: Insert at rear + 1.
Dequeue: Remove from front.

Linked List Representation of Queue

Program:
c
#include <stdio.h>
#include <stdlib.h>

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;
return;
}
rear->next = newNode;
rear = newNode;
}

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

int isEmpty() {
return (front == NULL);
}

int main() {
enqueue(10);
enqueue(20);
printf("Dequeued: %d\n", dequeue()); // 10
printf("Is empty? %d\n", isEmpty()); // 0 (False)
return 0;
}
Explanation:
front points to the head of the linked list.
rear points to the tail.
Enqueue: Insert at rear->next.
Dequeue: Remove front node.

38. Types of Queues (5 Marks)

1. Circular Queue
Use: Reuses empty slots after dequeue.
Example:
c
int queue[MAX];
int front = -1, rear = -1;
void enqueue(int item) {
if ((rear + 1) % MAX == front) printf("Queue Full\n");
else {
if (front == -1) front = 0;
rear = (rear + 1) % MAX;
queue[rear] = item;
}
}
2. Double-Ended Queue (Deque)
Use: Insert/delete at both ends.
Types:
Input-restricted: Insert at one end, delete at both.
Output-restricted: Delete at one end, insert at both.

3. Priority Queue
Use: Processes elements based on priority (not FIFO).
Implementation: Heap, linked list.

39. Operations on Queues (5 Marks)

1. Enqueue
Action: Insert at rear.
Time: O(1).

2. Dequeue
Action: Remove from front.
Time: O(1).

3. Peek
Action: View front element.
Time: O(1).

4. isEmpty/isFull
Action: Check if queue is empty/full.
Time: O(1).

40. Applications of Queues (5 Marks)

1. CPU Scheduling
Use: Round-Robin scheduling.

2. Printer Spooling
Use: Manages print jobs in order.

3. Breadth-First Search (BFS)

Use: Traverses graphs level-by-level.

4. Call Center Systems

Use: Holds incoming calls in FIFO order.

5. Buffering
Use: Streaming data (e.g., video buffers).

Key Takeaways
Stack: LIFO (undo/redo, recursion).

Queue: FIFO (CPU scheduling, BFS).

Circular Queue: Efficient memory reuse.
Priority Queue: Ordered processing (e.g., hospital triage).
Questions
1. What is data?*
2. What is a data structure?*
3. What is an abstract data type?*
4. What is algorithm complexity?
5. What are time and space complexities?
6. Explain asymptotic notations / Find the complexity of an algorithm.*
7. What are strings?
8. Name and explain any 7 string operations with programs.*
9. Pattern-matching algorithms with programs.*
10. What is word processing? Explain operations with examples.
11. Syntax and examples for if, if-else, while, for.
12. Explain worst case, best case, and average case efficiency with graphs.
13. malloc, calloc, realloc, free (uses and syntax).
14. Different storage representations of strings.
15. Insert a string, delete a string – algorithm and program.
16. What is an array? / Linear array / Array as an abstract data type /
Representation of array in memory
17. Traversing an array / Insertion and deletion – algorithm and
program*
18. Matrix programs / Square matrix / Matrix manipulation*
19. Operations on arrays – algorithm and program
20. Types of arrays
21. Memory representation of arrays – row-major and column-major
forms*
22. What is sorting?
23. Bubble sort – algorithm, program, and manual explanation with
example*
24. Quick sort – algorithm, program, and manual explanation with
example*
25. Selection sort – algorithm, program, and manual explanation with
example*
26. Merge sort – algorithm, program, and manual explanation with
example
27. Insertion sort – algorithm, program, and manual explanation with
example*
28. Linear search and binary search – explanation with example and
algorithm*
29. What is a linked list? Explain its representation in memory*
30. Traversing a linked list – algorithm, program, and explanation*
31. Memory allocation in linked lists – malloc, calloc, realloc, free
32. What is garbage collection?
33. Insertion and deletion in linked lists (all cases)*
34. Types of linked lists (mainly circular linked list)
35. Difference between arrays and linked lists*
36. Searching in a singly linked list – algorithm
37. What is a stack? / Array representation of stack / Linked list
representation with program and explanation*
38. Stack as an Abstract Data Type (ADT)
39. Polish notation (prefix, infix, postfix)*
40. Conversion of infix to postfix – program, explanation, and problem-
solving*
41. Evaluation of postfix expression – program, explanation, and
problem-solving*
42. Applications of stacks
43. Tower of Hanoi using recursion – program and explanation*
44. What is a queue? (Array and linked list representation with program
and explanation)*
45. Types of queues – mainly circular queue, double-ended queue
(deque), and priority queue*
46. Operations on queues – programs and explanations*
47. Applications of queues
48. What is a binary tree?*
49. Traversal of a binary tree (inorder, preorder, postorder)*
50. Height balancing in binary trees*
51. Binary Search Tree (BST) – definition, operations, and properties*
52. Hash table – definition and uses*
53. Collision in hashing*
54. Collision resolving techniques (e.g., chaining, open addressing, linear
probing, quadratic probing, double hashing)*