Evaluation Key – Advanced Data Structures (M.

Tech CSE)-2025
SECTION-A (1 Mark Questions)
1.a) Describe the properties of heap data structure.

Answer: A heap is a complete binary tree where the key at each node satisfies the heap
property:
- Max Heap: Parent node is ≥ its children.
- Min Heap: Parent node is ≤ its children.
- The height of a heap is O(log n).

1.b) What is the role of NPL in leftist trees?

Answer: NPL (Null Path Length) of a node is the length of the shortest path to a leaf
without two children. It helps in efficiently merging two leftist trees by ensuring the
leftist property.

1.c) What is the folding method in hashing?

Answer: The folding method splits a key into equal parts, adds them, and applies a
modulus operation to generate the hash index, reducing collisions.

1.d) What is rehashing?

Answer: Rehashing is the process of resizing the hash table and using a new hash
function when the load factor exceeds a threshold, improving efficiency and reducing
collisions.

1.e) Formulate the balance criteria of an AVL tree.

Answer: In an AVL tree, the balance factor of every node must be -1, 0, or 1, calculated
as:
Balance Factor = Height of Left Subtree - Height of Right Subtree
If this condition is violated, rotations are performed to restore balance.

1.f) Define a Splay tree.

Answer: A splay tree is a self-adjusting binary search tree (BST) where frequently
accessed nodes move to the root using splaying (a combination of rotations), improving
search efficiency for repeated accesses.

1.g) Give some applications of Digital search trees.

Answer: Digital search trees are used in:

- IP Routing (networking)
- Autocomplete & Spell Checkers
- Dictionary and Prefix Matching
- Genomic Data Search

1.h) Define the concept of Patricia.

Answer: Patricia (Practical Algorithm to Retrieve Information Coded in Alphanumeric) is

a compressed binary trie where common prefixes are shared, reducing space usage and
improving search efficiency.

1.i) Write the applications of pattern matching algorithm.

Answer: Pattern matching algorithms are used in:

- Text searching (search engines, word processors)
- DNA sequence analysis
- Spam filtering & Plagiarism detection
- Intrusion detection systems (IDS)

1.j) What is the key concept behind the Knuth-Morris-Pratt algorithm?

Answer: The KMP algorithm optimizes pattern matching by using a prefix table (LPS -
Longest Prefix Suffix) to avoid redundant comparisons, improving efficiency from O(m
× n) to O(m + n).

PART-B[MARKS:50]

2.a) Create a min-heap and max-heap for the following list (5, 8, 3, 9, 2, 10, 1, 40).
(5M)
Answer: Answer:
A min-heap is a complete binary tree where each parent node is smaller than or equal to
its children.
A max-heap is a complete binary tree where each parent node is greater than or equal to
its children.

Steps to create a Min-Heap:

1. Insert elements one by one while maintaining heap order.
2. After inserting all elements, the min-heap structure is:

1
/ \
2 3
/\ /\
5 8 10 9
/
40

Steps to create a Max-Heap:

1. Insert elements while maintaining heap order.
2. The max-heap structure is:

40
/ \
10 9
/ \ / \
 8 3 5 2
/
1

2.b) What are the practical applications of min-max heaps? (5M)

Answer:
Min-max heaps are widely used in various applications, including:

1. Priority Queues: Used in operating systems for task scheduling.

2. Graph Algorithms: Utilized in Dijkstra’s shortest path and Prim’s minimum spanning
tree algorithms.
3. Heap Sort:Efficient sorting algorithm based on min/max heaps.
4. Dynamic Median Finding:Helps in maintaining medians in streaming data.
5. Memory Management:Used in garbage collection and memory allocation in
programming languages like Java and Python.

3. Explain the components and operation of Fibonacci heaps, including their time
complexities. (10M)
Answer:
A Fibonacci Heap is an advanced data structure that supports efficient merging and key
reduction operations, making it useful for graph algorithms.
Components of Fibonacci Heap:
1. Collection of Trees: Maintains a group of min-heap-ordered trees.
2. Min Pointer: Points to the root with the smallest key.
3. Degree Property: Nodes track their number of children.
4. Marked Nodes: Helps in decrease-key operations.
5. Circular Doubly Linked List: Enables fast merging of heaps.

Operations and Their Time Complexities:

| Operation | Complexity |
|-----------------|------------|
| Insert | O(1) |
| Find Min | O(1) |
| Merge (Union) | O(1) |
| Extract Min | O(log n) |
| Decrease Key | O(1) (amortized) |
| Delete | O(log n) |

Explanation of Key Operations:

- Insertion: New elements are added as separate trees in O(1) time.
- Merging: Two Fibonacci heaps are merged in O(1) time.
- Extract Min:The minimum node is removed, and its children are added to the root list.
The heap is then restructured in O(log n) time.
- Decrease Key: A node’s key is reduced, and if the heap property is violated, a cut
operation is performed in O(1) amortized time.
- Delete:A node is removed using decrease-key and extract-min operations, making it
O(log n).

Fibonacci heaps are highly efficient in applications such as network routing and graph
algorithms (e.g., Dijkstra’s shortest path).

4.a) What are Hash functions? List some techniques that are used to implement
Hash functions. (5M)
Answer:
A hash function is a function that converts an input (or key) into a fixed-size numeric
value (hash code) to be used as an index in a hash table.

Techniques for Implementing Hash Functions:

1. Division Method: The key is divided by a prime number, and the remainder is taken as
the index.
- Formula: h(k) = k mod m
2. Multiplication Method:The key is multiplied by a constant fraction, and the fractional
part is taken as the index.
- Formula: h(k) = floor(m * (k * A mod 1))
3. Folding Method: The key is split into equal parts, summed, and then reduced using
modulus.
4. Mid-Square Method:The key is squared, and the middle portion of the result is taken as
the index.
5. Universal Hashing: Uses randomization to reduce collisions by selecting different hash
functions dynamically.

4.b) Differentiate between Double Hashing and Rehashing. (5M)

Answer:

Double Hashing: A secondary hash function is used to compute the probe sequence
when collisions occur.

Rehashing: When the load factor exceeds a threshold, the table is expanded, and all
elements are reinserted using a new hash function.
Difference Between Double Hashing and Rehashing:
Feature Double Hashing Rehashing

Uses a second hash

Expands the hash table and rehashes all
Definition function to resolve
elements when the load factor is high.
collisions.

h(k, i) = (h₁(k) + i * h₂(k)) A new hash function is applied after

Formula
mod m resizing the table.

Reduces clustering and

Improves performance by maintaining an
Purpose improves collision
optimal load factor.
resolution.

When collisions occur in When the table reaches a high load factor
When used
open addressing. threshold.

5. How will you handle overflow and collision detection in a hash table? Discuss
different methods. (10M)

Answer:Handling Overflow and Collision Detection in a Hash Table

A hash table uses a hash function to compute an index, but collisions occur when
multiple keys hash to the same index. Different methods handle collisions and overflow.

Methods to Handle Collisions:

1. Chaining (Separate Chaining)

2. Open Addressing

o Linear Probing

o Quadratic Probing

o Double Hashing

1. Chaining (Separate Chaining)

 Uses a linked list at each index to store multiple keys mapping to the same hash.

 When a collision occurs, the new key is added to the list.

Implementation of Chaining

#include <iostream>

#include <list>

using namespace std;

class HashTableChaining {

int size;

list<pair<int, string>> *table;

public:

HashTableChaining(int size) {

this->size = size;

table = new list<pair<int, string>>[size];

int hashFunction(int key) {

return key % size;

void insert(int key, string value) {

int index = hashFunction(key);

table[index].push_back({key, value});

void display() {

for (int i = 0; i < size; i++) {

cout << "Index " << i << ": ";

for (auto pair : table[i])

cout << "[" << pair.first << ", " << pair.second << "] -> ";

cout << "NULL\n";

 }

};

int main() {

HashTableChaining ht(5);

ht.insert(10, "A");

ht.insert(15, "B");

ht.insert(20, "C");

ht.display();

return 0;

2. Open Addressing

Instead of using linked lists, open addressing finds another available slot inside the array.

a) Linear Probing

 If the target slot is occupied, move to the next available slot.

C++ Implementation of Linear Probing

#include <iostream>

using namespace std;

class HashTableLinearProbing {

int size;

pair<int, string> *table;

bool *occupied;

public:

HashTableLinearProbing(int size) {
 this->size = size;

table = new pair<int, string>[size];

occupied = new bool[size] {false};

int hashFunction(int key) {

return key % size;

void insert(int key, string value) {

int index = hashFunction(key);

while (occupied[index]) {

index = (index + 1) % size;

table[index] = {key, value};

occupied[index] = true;

void display() {

for (int i = 0; i < size; i++) {

if (occupied[i])

cout << "Index " << i << ": [" << table[i].first << ", " << table[i].second <<
"]\n";

else

cout << "Index " << i << ": NULL\n";

}
 }

};

int main() {

HashTableLinearProbing ht(5);

ht.insert(10, "A");

ht.insert(15, "B");

ht.insert(20, "C");

ht.display();

return 0;

b) Quadratic Probing

 Instead of moving linearly, it jumps quadratically.

C++ Implementation of Quadratic Probing

#include <iostream>

using namespace std;

class HashTableQuadraticProbing {

int size;

pair<int, string> *table;

bool *occupied;

public:

HashTableQuadraticProbing(int size) {

this->size = size;

table = new pair<int, string>[size];

 occupied = new bool[size] {false};

int hashFunction(int key) {

return key % size;

void insert(int key, string value) {

int index = hashFunction(key);

int i = 1;

while (occupied[index]) {

index = (index + i * i) % size;

i++;

table[index] = {key, value};

occupied[index] = true;

};

c) Double Hashing

 Uses a second hash function to determine step size.

Implementation of Double Hashing

#include <iostream>

using namespace std;

class HashTableDoubleHashing {

int size;

pair<int, string> *table;

 bool *occupied;

public:

HashTableDoubleHashing(int size) {

this->size = size;

table = new pair<int, string>[size];

occupied = new bool[size] {false};

int hashFunction1(int key) {

return key % size;

int hashFunction2(int key) {

return 1 + (key % (size - 1));

void insert(int key, string value) {

int index = hashFunction1(key);

int step = hashFunction2(key);

while (occupied[index]) {

index = (index + step) % size;

table[index] = {key, value};

occupied[index] = true;

};
Q 6: Explain the insertion and deletion processes in Red-Black trees, focusing on
color changes that balance the tree. (10 Marks)

Answer:

A Red-Black Tree is a self-balancing binary search tree that ensures logarithmic time
complexity for insertion, deletion, and search operations. It maintains balance by
following these properties:

1. Every node is either Red or Black.

2. The root node is always Black.

3. Red nodes cannot have Red children (No two consecutive Red nodes).

4. Every path from a node to its descendant NULL nodes must have the same
number of Black nodes.

5. A new node is always inserted as Red.

Insertion in Red-Black Tree:

1. Insert the node as in a normal BST (Binary Search Tree).

2. Color the newly inserted node Red.

3. Check for violations of Red-Black Tree properties:

o If the parent is Black, no violation occurs.

o If the parent is Red, check the uncle node:

 Case 1: Uncle is Red → Recoloring is performed.

 Case 2: Uncle is Black or NULL → Rotation is performed (Left or

Right Rotation).

4. Ensure the root remains Black.

Example of Insertion with Color Changes:

Let’s insert nodes in order: 10, 20, 30.

1. Insert 10 (Root) → Color it Black.

(10B)

2. Insert 20 → It becomes Red (no violation).

 (10B)

(20R)

3. Insert 30 → It is inserted as Red, causing a violation (consecutive Red nodes).

(10B)

(20R)

(30R) ❌ (Violation: Two consecutive Red nodes)

4. Fixing Violation:

o Uncle is NULL (Black), so we perform a left rotation.

o After rotation, recolor nodes to maintain balance.

Final Red-Black Tree after fixing violations:

(20B)

/ \

(10R) (30R)

Now, the tree remains balanced.

Deletion in Red-Black Tree:

1. Delete the node as in a normal BST.

2. If the deleted node was Black, fix violations using:

o Case 1: Sibling is Red → Recoloring and rotation.

o Case 2: Sibling is Black with at least one Red child → Rotation and
recoloring.

o Case 3: Sibling is Black with both children Black → Recolor and move
up.
 3. Ensure the tree remains balanced after deletion.

Example of Deletion with Fixing Violations:

Let’s delete 30 from the previous tree:

(20B)

(10R)

1. Delete 30 (Black Node) → Causes an extra Black deficiency.

2. Fix Violation:

o Since 10 is Red, we recolor it Black to compensate for the Black

deficiency.

3. Final Tree after Fixing:

(20B)

(10B)

The tree remains balanced.

Q7 a) Evaluate the benefits of using Splay Trees in practice. (5 Marks)

Answer: Splay Trees are a type of self-adjusting binary search tree that performs
operations such as insertion, deletion, and search in an efficient manner. The key benefits
of using Splay Trees in practice are:

1. Self-Balancing Property: Splay trees automatically restructure themselves after

every access, ensuring frequently accessed elements are moved closer to the root.

2. Amortized Efficiency: The time complexity of operations is O(log n) on average,

but frequently accessed elements can be accessed in O(1) time.

3. No Extra Storage Cost: Unlike AVL or Red-Black trees, splay trees do not require
extra memory for storing balancing information.

4. Good for Cache Optimization: Since frequently accessed elements stay near the
root, splay trees are effective in scenarios where locality of reference is important.
 5. Simpler Implementation: Compared to other self-balancing trees, splay trees have
simpler rotation rules and no need for additional balancing factors.

Example: Consider a scenario where we frequently access certain elements in a list (e.g.,
a cache system). A splay tree will ensure that these elements are quickly retrievable,
optimizing search performance.

Q7 b) How suitable are B-Trees for use in file systems and databases? (5 Marks)

Answer: B-Trees are highly suitable for use in file systems and databases due to their
ability to handle large amounts of data efficiently. The reasons for their suitability
include:

1. Balanced Structure: B-Trees maintain balance at all times, ensuring search, insert,
and delete operations run in O(log n) time.

2. Efficient Disk Access: B-Trees are designed to minimize disk I/O by storing
multiple keys in a single node, reducing the number of disk reads.

3. Large Branching Factor: Unlike binary trees, B-Trees have a high branching
factor, reducing tree height and improving performance for large datasets.

4. Ordered Data Storage: B-Trees maintain sorted data, making range queries and
ordered traversals efficient.

5. Used in Real-world Systems: Many modern databases (such as MySQL and

PostgreSQL) and file systems (such as NTFS and EXT4) use B-Trees for
indexing and storage management.

Example: A database indexing system uses B-Trees to store indexes efficiently. When
searching for a record, the database can quickly navigate the tree with minimal disk
reads, ensuring fast data retrieval.

Q8 a) Define Tries and discuss the function Suffix Tries with an example. (5 Marks)

Answer:
A Trie is a tree data structure used for storing and retrieving strings efficiently. It is
commonly used in applications like dictionary storage, autocomplete suggestions, and IP
routing.

Features of Trie:

 Each node represents a character in a word.

  Words are stored in a path from the root to a leaf node.

 Searching and insertion operations take O(m) time, where m is the length of the
word.

Suffix Trie:

A Suffix Trie is a special type of Trie that stores all possible suffixes of a given string. It
is mainly used in text processing tasks like substring searching and pattern matching.

Example:

Consider the string "banana". The Suffix Trie stores all suffixes:

 "banana"

 "anana"

 "nana"

 "ana"

 "na"

 "a"

This allows fast substring searching.

Q8 b) How do Compressed Tries work? Explain its operations. (5 Marks)

Answer:
A Compressed Trie is a space-optimized version of a Trie that reduces unnecessary nodes
by merging chains of single-child nodes.

Working of Compressed Tries:

 It reduces the number of nodes by compressing consecutive nodes into a single

node.

 Instead of storing one character per node, it stores whole substrings.

 This improves space efficiency while maintaining fast search times.

Operations in Compressed Trie:

1. Insertion: Similar to a normal Trie, but it merges common substrings to avoid

redundant storage.
 2. Search: It follows the path of substrings instead of single characters.

3. Deletion: Nodes are removed or merged while maintaining the compressed

structure.

Example:

For words "car", "cart", and "care", a normal Trie would store them character by
character. In a Compressed Trie, the structure would look like this:
(root)

├── ar

├── t

└── e

This reduces space usage significantly.

Q9 a) Explain Standard Tries with an example. (5 Marks)

Answer:
A Standard Trie is a basic Trie structure where:

 Each node stores only one character.

 Every path from the root to a leaf node represents a word.

 Used in applications like autocomplete and spell checking.

Example:

For the words "cat", "car", and "bat", the Trie structure would be:
(root)
├── C

│ ├── A

│ │ ├── T

│ │ └── R

│ │ └── T

└── B

└── A

└── T

Each branch represents a stored word.

Q9 b) Differentiate Binary Tries and Multiway Tries. (5 Marks)

Answer:

Feature Binary Trie Multiway Trie

Branching Factor 2 (Binary) More than 2 (Multiway)

Memory Usage Higher due to more depth Lower due to wide branches

Efficiency Slower due to deep tree Faster due to fewer levels

Dictionary storage, text

Used In Binary search, IP lookup
search
Example:

 Binary Trie: Used for storing binary strings (0s and 1s).

 Multiway Trie: Used in dictionaries and autocomplete systems.

Q10: Explain the implementation of the Rabin-Karp algorithm and its advantages.
(10 Marks)

Answer:Introduction to Rabin-Karp Algorithm

The Rabin-Karp Algorithm is a string-searching algorithm that uses hashing to find the
occurrence of a pattern in a text efficiently. Instead of checking character-by-character
like brute force, it calculates a hash value for the pattern and compares it with substrings
of the text. If the hash values match, a direct character-by-character comparison is
performed to confirm the match.

Working of Rabin-Karp Algorithm

The algorithm follows these steps:

1. Compute the hash value of the pattern (P) and the first substring of the text (T) of
the same length.

2. Compare the hash values:

o If they are equal, check the characters to confirm the match.

o If they are not equal, slide the window one position to the right and
recalculate the hash for the next substring.

3. Repeat the process until the end of the text is reached.

Hashing in Rabin-Karp

A common hash function used is the rolling hash, where the hash of the next substring is
derived from the previous hash:

H(Ti+1)=[d(H(Ti)−T[i]⋅dm−1)+T[i+m]]mod qH(T_{i+1}) = [d(H(T_i) - T[i] \cdot

d^{m-1}) + T[i+m]] \mod qH(Ti+1)=[d(H(Ti)−T[i]⋅dm−1)+T[i+m]]modq

Where:

 ddd is the number of characters in the input alphabet.

 qqq is a large prime number to reduce collisions.

  mmm is the length of the pattern.

Example of Rabin-Karp Algorithm

Consider Text = "abcxabcd" and Pattern = "abc".

1. Compute hash values for "abc" and the first substring "abc" in text.

2. Since the hash values match, compare "abc" with "abc" → Match found at index
0.

3. Slide the window and compute new hash values for "bcx", "cxa", "xab", etc.

4. A match is found when the hash values match again.

Advantages of Rabin-Karp Algorithm

1. Efficient for multiple pattern searching – Instead of checking each pattern

separately, Rabin-Karp can find multiple patterns at once.

2. Uses hashing to speed up matching – Only performs a full character comparison

when hash values match.

3. Works well for large texts – Ideal for DNA sequence matching, plagiarism
detection, and pattern-matching applications.

Time Complexity

 Best Case: O(n)O(n)O(n) (when there are no hash collisions)

 Worst Case: O(nm)O(nm)O(nm) (when all substrings have hash collisions)

Q11: Which pattern matching algorithm scans the characters from right to left?
Explain it with a suitable example. (10 Marks)

Answer:Introduction to Boyer-Moore Algorithm

The Boyer-Moore Algorithm is a pattern-matching algorithm that scans the text from
right to left instead of the usual left-to-right approach. It is highly efficient because it uses
preprocessing techniques to skip unnecessary comparisons, making it faster than brute-
force matching.

Key Features of Boyer-Moore Algorithm

1. Right-to-left scanning – Starts comparing the pattern’s last character with the text.

2. Uses two preprocessing techniques to improve efficiency:

 o Bad Character Heuristic

o Good Suffix Heuristic

3. Skips unnecessary comparisons – Moves the pattern forward by large jumps

instead of one character at a time.

Working of Boyer-Moore Algorithm

1. Preprocess the pattern using bad character rule and good suffix rule.

2. Align the pattern with the text and compare characters from right to left.

3. If a mismatch occurs:

o Use Bad Character Heuristic → Move the pattern forward based on the
mismatched character’s position.

o Use Good Suffix Heuristic → Move the pattern forward using known
suffix matches.

4. Repeat the process until the text is fully scanned.

Example of Boyer-Moore Algorithm

Consider Text = "ABAAABCD" and Pattern = "ABC".

1. Align "ABC" with "ABAAABCD".

2. Start comparison from right to left:

o "C" in "ABC" ≠ "A" in "ABAAABCD".

o Use the Bad Character Rule → Shift "ABC" forward by 2 positions.

3. Align "ABC" with "ABAAABCD" again:

o "C" ≠ "B", shift again.

4. Continue shifting until "ABC" aligns with "ABAAABCD" → Match found at

index 4.

Advantages of Boyer-Moore Algorithm

1. Faster than brute force – Uses jumps instead of checking every character.

2. Efficient for large texts – Used in text searching software like grep.
 3. Reduces unnecessary comparisons – Uses preprocessed information to improve
speed.

Time Complexity

 Best Case: O(n/m)O(n/m)O(n/m) (when mismatches happen early)

 Worst Case: O(nm)O(nm)O(nm) (if all characters mismatch)