DATA STRUCTURES AND APPLICATIONS
Module 1
a. Define Data Structures. Explain with neat block schematic different types of data structures with
examples. What are the primitive operations that can be performed?
1. Data Structures are methods of organizing, managing, and storing data to perform operations
efficiently.
2. They can be broadly classified into primitive (e.g., int, float) and non-primitive (e.g., arrays, linked
lists) types.
3. Linear Data Structures include arrays, stacks, and queues, where elements follow a sequence.
4. Non-linear Data Structures include trees and graphs, where elements have hierarchical relationships.
5. Arrays store elements in a contiguous memory block, while linked lists use nodes with pointers.
6. Trees represent hierarchical data with parent-child relationships (e.g., a file directory).
7. Graphs are used to model connections like social networks or city maps.
8. Common operations include insertion, deletion, traversal, searching, and sorting.
9. Block diagrams show relationships between nodes, pointers, or memory blocks for each type.
10. Efficient data structure selection impacts algorithm performance significantly.
b. Differentiate between structures and unions with examples for both.
1. Structures and unions are used in C to group different data types under one name.
2. In structures, memory is allocated for all members, so all values can coexist.
3. In unions, memory is shared among members, and only one value can exist at a time.
4. Example of structure:
struct Student {
int roll;
char name[20];
};
5. Example of union:
union Data {
int i;
float f;
};
6. Structures are useful for grouping data, such as a record in a database.
7. Unions are used when memory is limited, such as storing one data type at a time.
8. Structures allow simultaneous access to all fields, while unions allow one field at a time.
9. Structures take more memory compared to unions.
10. Both are critical in managing memory efficiently.
c. What do you mean by pattern matching? Outline Knuth-Morris-Pratt pattern matching
algorithm.
1. Pattern matching is a process of finding occurrences of a substring (pattern) within a string (text).
2. The Knuth-Morris-Pratt (KMP) algorithm avoids redundant comparisons.
3. It preprocesses the pattern to create a prefix table (LPS array) for efficient searching.
4. The LPS array stores the length of the longest prefix that is also a suffix.
5. During searching, mismatches shift the pattern to skip unnecessary comparisons.
6. Example: For pattern "ABABCABAB," the LPS array is [0, 0, 1, 2, 0, 1, 2, 3, 4].
7. Time complexity of KMP is O(n + m), where n = text length and m = pattern length.
8. This algorithm is faster than naive methods for large strings.
9. KMP is widely used in text editors and bioinformatics.
10. It ensures linear time complexity for searching operations.
a. Define stack. Give the implementation of Push(), Pop(), and Display() functions by considering
empty and full conditions.
1. A stack is a linear data structure following the Last In, First Out (LIFO) principle.
2. It uses two primary operations: Push (insert) and Pop (remove).
3. Push(): Adds an element to the top of the stack if it's not full.
4. Pop(): Removes the topmost element if the stack is not empty.
5. Display(): Traverses and displays all elements in the stack.
6. Example implementation of Push:
void Push(int stack[], int *top, int item, int size) {
if (*top == size - 1) printf("Stack is full");
else stack[++(*top)] = item;
}
7. Example implementation of Pop:
int Pop(int stack[], int *top) {
if (*top == -1) printf("Stack is empty");
else return stack[(*top)--];
}
8. The Display function iterates from the top to the bottom of the stack.
9. Stacks are used in undo-redo systems, recursion, and parsing expressions.
10. Overflow occurs when the stack is full; underflow occurs when it's empty.
b. Write an algorithm to evaluate a postfix expression and apply the same for 6, 2, 1, 3, -, 4, 2, , +.
1. Algorithm:
Initialize an empty stack.
Scan the postfix expression from left to right.
If an operand is encountered, push it onto the stack.
If an operator is encountered, pop the required operands, perform the operation, and push the result.
Continue until the expression ends; the final result is at the stack's top.
2. Postfix expression: 6 2 1 3 - 4 2 * +.
3. Steps:
Push 6, 2 onto the stack.
Push 1, 3; compute 1 - 3 = -2.
Push -2; compute 4 * 2 = 8.
Add -2 + 8 = 6.
Add 6 + 6 = 12 (final result).
c. Write the Postfix form of the following using stack:
(i) A(BC+DE)+F*
1. Convert infix to postfix: ABC*DE*+*F+.
2. Start by handling parentheses and precedence.
(ii) (a + (b*c) / (d-e))
1. Postfix: abc*de-/+.
2. Follow BODMAS and operator precedence rules.
Module 3
c. For the given sparse matrix, give the diagrammatic linked representation.
1. A sparse matrix has most of its elements as zero, and only non-zero elements are stored.
2. The given matrix:
[2000] 4003 8001 0060
A = 0000
3. Each non-zero element is represented as a node containing row index, column index, and value.
4. For example, the first row has nodes: (0,0,2000), (0,1,4003), (0,2,8001), (0,3,60).
5. These nodes are linked row-wise or column-wise using pointers.
6. A header node points to the first node of each row or column.
7. Example diagram:
Header -> (0,0,2000) -> (0,1,4003) -> (0,2,8001) -> (0,3,60)
8. This representation reduces memory usage compared to a full matrix.
9. It is efficient for matrices with few non-zero elements.
10. Linked list representation simplifies traversals and operations like addition.
a. Discuss how binary trees are represented using:
(i) Array
1. A binary tree is stored in a 1D array where the root is at index 0.
2. For any node at index i:
Left child = 2*i + 1.
Right child = 2*i + 2.
3. Parent of a node = (i-1)/2.
4. Example: For the tree:
10
/ \
20 30
Array: [10, 20, 30].
5. This method is simple but wastes space for sparse trees.
6. Tree traversal becomes easy using index calculations.
(ii) Linked List
1. Each node in a binary tree is represented as a structure containing data and two pointers (left and right).
2. Structure:
struct Node {
int data;
struct Node *left, *right;
};
3. Example:
10
/ \
20 30
Nodes:
10 -> left = 20, right = 30
20 -> left = NULL, right = NULL
30 -> left = NULL, right = NULL
4. This method is space-efficient and dynamic.
b. Discuss inorder, preorder, postorder, and level order traversal with suitable recursive functions
for each.
1. Inorder Traversal: Visit left subtree, root, and then right subtree.
void inorder(struct Node *root) {
if (root != NULL) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
2. Preorder Traversal: Visit root, left subtree, and then right subtree.
void preorder(struct Node *root) {
if (root != NULL) {
printf("%d ", root->data);
preorder(root->left);
preorder(root->right);
}
}
3. Postorder Traversal: Visit left subtree, right subtree, and then root.
void postorder(struct Node *root) {
if (root != NULL) {
postorder(root->left);
postorder(root->right);
printf("%d ", root->data);
}
}
4. Level Order Traversal: Visit nodes level by level.
void levelOrder(struct Node *root) {
if (root == NULL) return;
Queue q; enqueue(q, root);
while (!isEmpty(q)) {
struct Node *temp = dequeue(q);
printf("%d ", temp->data);
if (temp->left) enqueue(q, temp->left);
if (temp->right) enqueue(q, temp->right);
}
}
c. Define Threaded Binary Tree. Discuss In-Threaded Binary Tree.
1. A Threaded Binary Tree uses null pointers to link nodes for traversal.
2. It replaces null pointers with threads pointing to the next node in traversal order.
3. In-threaded trees link nodes for inorder traversal.
4. This eliminates the need for a stack or recursion during traversal.
5. Example:
10
/ \
5 15
Threads: 5 -> 10 -> 15.
6. Traversal is faster due to pre-computed threads.
7. Structure:
struct TNode {
int data;
struct TNode *left, *right;
int isThreaded; // 1 if right is a thread
};
8. Threaded trees save space compared to traditional trees.
9. They are useful in memory-constrained applications.
10. Variants include pre-threaded and post-threaded trees.
Module 4
a. Write a function to perform the following operations on Binary Search Tree (BST):
(i) Inserting an element into BST
1. A Binary Search Tree is a binary tree where left child < root < right child.
2. Function to insert an element:
struct Node* insert(struct Node* root, int value) {
if (root == NULL) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value; newNode->left = NULL; newNode->right = NULL;
return newNode;
}
if (value < root->data) root->left = insert(root->left, value);
else if (value > root->data) root->right = insert(root->right, value);
return root;
}
3. This function recursively places the value in the correct position.
(ii) Recursive search of a BST
1. Function to search for an element:
int search(struct Node* root, int key) {
if (root == NULL) return 0;
if (root->data == key) return 1;
if (key < root->data) return search(root->left, key);
return search(root->right, key);
}
2. The search follows the BST property to navigate through the tree.
3. The time complexity is O(h), where h is the height of the tree.
b. Discuss selection trees with an example.
1. A selection tree is a binary tree used to find the smallest element from multiple sorted lists.
2. The leaf nodes represent elements from the lists, and internal nodes store the smallest value among
their children.
3. Example: Given arrays [1, 4, 9] and [2, 6, 8], the tree selects 1 from the first array and 2 from the
second.
4. At each step, the smallest value is removed, and the next element from the corresponding array replaces
it.
5. This process repeats until all elements are extracted in sorted order.
6. Selection trees are used in k-way merging algorithms, such as merge sort.
7. The tree height is O(log k), where k is the number of lists.
8. They optimize merging by minimizing comparisons.
9. Selection trees can be implemented using arrays or linked structures.
10. Applications include sorting, database management, and file merging.
a. Explain transforming a forest into a binary tree with an example.
1. A forest is a collection of disjoint trees.
2. To convert a forest into a binary tree:
The first child of each node becomes its left child.
The next sibling of each node becomes its right child.
3. Example:
Forest:
T1: A -> B, C
T2: D -> E
Transformed Binary Tree:
A
/\
B C
D
/
E
4. Each tree in the forest is processed separately.
5. The binary tree representation is memory-efficient and simplifies traversal.
6. This method is commonly used in tree encoding and compiler design.
7. Preorder traversal of the binary tree represents the forest.
8. Conversion does not alter the relative hierarchy of nodes.
9. It allows uniform processing of forests using binary tree algorithms.
10. Applications include data compression and hierarchical representations.
b. Define the following terminologies with examples:
(i) Digraph
1. A digraph is a directed graph where edges have a direction.
2. Example: In a graph with vertices A, B, and C, edges A → B and B → C form a digraph.
3. It is represented using adjacency matrices or lists.
4. Applications include road networks and dependency graphs.
(ii) Weighted graph
1. A graph where edges have weights (e.g., cost, distance).
2. Example: A → B (weight = 5), B → C (weight = 3).
3. It is used in shortest path algorithms like Dijkstra’s.
(iii) Self-loop
1. An edge connecting a vertex to itself.
2. Example: A → A.
3. Common in state machines.
(iv) Parallel edges
1. Two or more edges connecting the same pair of vertices.
2. Example: A ↔ B with weights 2 and 3.
3. Found in multigraphs.
c. Explain in detail elementary graph operations.
1. Graph operations include insertion, deletion, searching, and traversal.
2. Insertion: Add a vertex or edge to the graph.
3. Deletion: Remove a vertex or edge while maintaining the structure.
4. Search: Check for the existence of a vertex or edge.
5. Traversal: Visit all vertices in a specific order (DFS, BFS).
6. Adjacency Matrix Representation: 2D array tracks connections.
7. Adjacency List Representation: Array of lists stores neighbors for each vertex.
8. Operations depend on the representation used.
9. Graph algorithms optimize operations for specific applications.
10. Applications include social networks, routing, and game development.
Module 5
a. What is collision? What are the methods to resolve collision? Explain linear probing with an
example.
1. Collision occurs when two keys hash to the same index.
2. Methods to resolve collisions:
Chaining: Store colliding elements in a linked list.
Open Addressing: Probe for the next available slot.
3. Linear Probing checks the next slot sequentially until an empty one is found.
4. Example: If key 5 hashes to index 2
index 2 is occupied, check index 3.
5. Pros: Simple and easy to implement.
6. Cons: Clustering reduces efficiency.
b. Explain in detail about static and dynamic hashing.
1. Static hashing uses a fixed hash table size throughout its lifetime.
2. It maps keys to buckets using a hash function, e.g., h(key) = key % table_size.
3. If the table becomes full, collisions are resolved using chaining or open addressing.
4. Limitation: It may cause overflow or waste memory if the size isn’t optimal.
5. Dynamic hashing allows the hash table to grow or shrink dynamically.
6. It uses advanced techniques like extendible hashing or linear hashing.
7. When the table is full, new buckets are allocated, and keys are redistributed.
8. It adapts to varying data sizes, avoiding overflow or underutilization.
9. Example: Extendible hashing doubles table size when the bucket capacity is exceeded.
10. Applications: Database systems and file systems requiring scalable solutions.
c. Discuss Leftist Trees with an example.
1. A Leftist Tree is a binary tree used in priority queue operations.
2. It maintains a null path length (NPL) for every node.
NPL of a node = shortest path to a node without two children.
3. Rule: The left child must have a greater or equal NPL than the right child.
4. During insertion or merging, the tree structure is adjusted to maintain this property.
5. Example: Insert elements [10, 20, 5] into a leftist tree.
Step 1: Insert 10 → Root = 10.
Step 2: Insert 20 → Merge 10 and 20 → 10 becomes parent of 20.
Step 3: Insert 5 → 5 becomes the new root.
6. Leftist trees efficiently support merge, insert, delete-min operations.
7. Time complexity for operations is O(log n).
8. They are used in memory management and event simulation systems.
a. Explain different types of hash functions with examples.
1. Division Method: Key is divided by table size, and the remainder is used.
Example: h(key) = key % table_size.
2. Multiplication Method: Key is multiplied by a constant, and the fractional part is scaled.
Example: h(key) = floor(table_size * (key * A % 1)).
3. Folding Method: Key is divided into parts, which are added or XORed.
Example: Key = 123456 → Fold into 123 + 456 = 579.
4. Mid-Square Method: Square the key and extract the middle digits.
Example: Key = 45 → 45² = 2025 → Middle = 02.
5. Universal Hashing: Randomly selects a hash function to minimize collisions.
b. Discuss AVL Tree with an example. Write a function for insertion into an AVL Tree.
1. An AVL Tree is a height-balanced binary search tree.
2. For any node, the height difference between its left and right subtrees is at most 1.
3. During insertion or deletion, the tree self-balances by performing rotations (LL, RR, LR, RL).
4. Example: Insert [10, 20, 30] into an AVL tree.
Step 1: Insert 10 → Tree = 10.
Step 2: Insert 20 → Tree = 10 → 20.
Step 3: Insert 30 → Unbalanced → Perform left rotation → Balanced tree = 20 → 10, 30.
5. Function for insertion:
struct Node* insert(struct Node* root, int key) {
if (root == NULL) return newNode(key);
if (key < root->data) root->left = insert(root->left, key);
else if (key > root->data) root->right = insert(root->right, key);
root = balance(root); // Perform rotations if unbalanced
return root;
}
c. Define Red-Black Tree, Splay Tree. Discuss the method to insert an element into a Red-Black
Tree.
1. A Red-Black Tree is a balanced binary search tree with properties:
Nodes are red or black.
Root and leaves are black.
Red nodes cannot have red children.
Every path from a node to its descendant leaves has the same number of black nodes.
2. Insertion adjusts colors and performs rotations to maintain balance.
3. A Splay Tree is a self-adjusting binary search tree.
Recently accessed nodes are moved to the root using splay operations.
It improves access time for frequently accessed nodes.
4. Insertion in Red-Black Tree:
Insert as a red node.
Fix violations using recoloring and rotations.
Example: Insert [10, 20, 30].
Insert 10 (root, black).
Insert 20 (red, no violation).
Insert 30 (violates red-red rule) → Perform left rotation → Balance.