chapter

Data Structures Notes for GATE DA

GATE DA Data Structures: 3 chapters, 8 previous year questions (26% of Programming, Data Structures and Algorithms), 452 practice questions and one solved que

A question from this chapter

Question 1

Level 3: Exam Standard

Assertion (A): The number of distinct valid pop sequences for the input 1, 2, 3, 4, 5 pushed onto a single initially empty stack in that order is 42. Reason (R): A valid sequence of 5 pushes and 5 pops corresponds to a Dyck path of length 10. The total number of unrestricted paths is (5 10), and the number of invalid paths (which dip below the starting level) is (4 10), making the valid count (5 10) - \0 bin o m 104 = 42 .

Question 2

Level 3: Exam Standard

A hash table of size m = 12 uses linear probing for collision resolution. The table currently contains exactly 8 active keys and 2 tombstones (deleted markers). The remaining 2 slots are empty. To optimize search performance, the tombstones and empty slots are placed to minimize the maximum number of probes required for ANY successful search. What is the minimum possible value for this maximum number of probes?

Question 3

Level 3: Exam Standard

The pre-order traversal of a binary tree with 9 distinct integer-valued nodes is 8, 3, 1, 6, 4, 7, 10, 14, 13 and its in-order traversal is 1, 3, 4, 6, 7, 8, 10, 13, 14 . What is the value of the root of the right subtree of the root?

Free preview ends here

Login to view the complete notes

Creating an account is free. You get the rest of this chapter, step-by-step solutions, and a study plan built around the topics you are actually weak at.

Why MastersUp

Personalised first. High quality throughout.

Most platforms hand everyone the same content. Here the content moves with your performance, topic by topic.

Built around you, not around a syllabus PDF

Every answer you give moves your topic-level intelligence rate. The next question, the next revision card and tomorrow's plan all change with it.

Revision that hits your weak spots

We only revise topics you have actually attempted and are still below the safe bar on — never the same chapter on repeat.

Questions calibrated to the real exam

Each question carries a measured toughness. You are served a rung above your current level, so practice keeps stretching you.

Notes written for recall, not for volume

Full lesson cards for first study, curated short-note cards for the last mile — with derivations, traps and exam patterns marked.

One place for everything

Notes, chapter practice, previous-year questions, test series and full-length papers — all feeding one picture of your preparation.

Honest progress

No vanity streaks. Progress here means chapters mastered and accuracy that held up on harder questions.

Unlock the whole course

Full notes and short notes, the complete question bank with worked solutions, mock tests, full-length papers, and an adaptive plan that rebuilds itself as you improve.

View all plans Start free

Data Structures Notes for GATE DA

GATE DA Data Structures: 3 chapters, 8 previous year questions (26% of Programming, Data Structures and Algorithms), 452 practice questions and one solved question from each chapter.

About Data Structures Notes

Full study notes for Data Structures in GATE DA, organised across 3 chapters. Each chapter page explains concepts from the basics with worked examples and the formulas you need.

Data Structures Weightage in GATE DA

Data Structures accounts for 8 of 31 Programming, Data Structures and Algorithms previous year questions in our bank (26%), about 2.7 per paper across 3 papers.

Data Structures Chapter Matrix

Chapter	Topics	PYQs	Share of unit PYQs	Practice questions
Stacks, Queues and Deques	Stack Operations and Simulation, Queue and Deque Operations, ADT Properties: FIFO, LIFO and Lookup	3	38%	161
Hash Tables and Collision Resolution	Hash Tables with Open Addressing and Linear Probing, Uniform Hashing and Probe Complexity	2	25%	126
Binary Trees: Properties and Traversals	Binary Tree Traversals and Reconstruction, Binary Tree Structural Properties	3	38%	165

One Solved Question from Each Data Structures Chapter

Question 1 · Stacks, Queues and Deques MCQ

Assertion (A): The number of distinct valid pop sequences for the input $1, 2, 3, 4, 5$ pushed onto a single initially empty stack in that order is 42.

Reason (R): A valid sequence of 5 pushes and 5 pops corresponds to a Dyck path of length 10. The total number of unrestricted paths is $(5 10)$ , and the number of invalid paths (which dip below the starting level) is $(4 10)$ , making the valid count $(5 10) - \0 bin o m 104 = 42$ .

A.
Both A and R are true, and R is the correct explanation of A.
B.
Both A and R are true, but R is NOT the correct explanation of A.
C.
A is true, but R is false.
D.
A is false, but R is true.

Correct Answer:

Step-by-Step Solution

Key idea: The number of valid stack permutations of $n$ elements is given by the $n$ -th Catalan number, which is derived using the reflection principle on lattice paths.

Step 1: Evaluate Assertion (A). The number of valid pop sequences for $n = 5$ is the 5th Catalan number, $C_{5}$ .

Step 2: Calculate $C_{5} = \frac{1}{5 + 1} (5 2 \times 5) = \frac{1}{6} (5 10) = \frac{252}{6} = 42$ . Thus, A is true.

Step 3: Evaluate Reason (R). A push is an up-step $(+ 1)$ and a pop is a down-step $(- 1)$ . A valid sequence never has more pops than pushes at any prefix, corresponding to a Dyck path that never dips below the x-axis.

Step 4: The total number of paths with 5 up-steps and 5 down-steps is $(5 10) = 252$ .

Step 5: By the reflection principle, the number of invalid paths (those that touch $y = - 1$ ) is equal to the number of paths from $(0, 0)$ to $(10, - 2)$ , which requires 4 up-steps and 6 down-steps. This count is $(4 10) = 210$ .

Step 6: The number of valid paths is $(5 10) - (4 10) = 252 - 210 = 42$ . Thus, R is true.

Step 7: R provides the exact combinatorial proof (the reflection principle) for why the count in A is 42. Therefore, R is the correct explanation of A.

Answer: A

Question 2 · Hash Tables and Collision Resolution MCQ

A hash table of size $m = 12$ uses linear probing for collision resolution. The table currently contains exactly 8 active keys and 2 tombstones (deleted markers). The remaining 2 slots are empty.

To optimize search performance, the tombstones and empty slots are placed to minimize the maximum number of probes required for ANY successful search.

What is the minimum possible value for this maximum number of probes?

A.
3
B.
4
C.
5
D.
8

Correct Answer:

Step-by-Step Solution

Key idea: This is a bounding question involving primary clustering and deletion traps. The key insight is that tombstones DO NOT break probe chains; they are treated as occupied during a search. Only empty slots break the table into independent clusters.

Step 1: Identify the cluster separators.

There are 2 empty slots. These 2 empty slots divide the table into exactly 3 contiguous clusters of non-empty slots (active keys + tombstones).

Step 2: Calculate the total number of items in the clusters.

Total items = 8 active keys + 2 tombstones = 10 items.

Step 3: Bound the maximum cluster length.

We need to distribute 10 items into 3 clusters. By the Pigeonhole Principle, at least one cluster must contain $⌈ 10/3 ⌉ = 4$ items.

Therefore, the maximum cluster length is at least 4.

Step 4: Verify if a maximum length of 4 is achievable.

We can arrange the clusters to have lengths 3, 4, and 3.

For example:

Cluster 1: 2 active, 1 tombstone (length 3)
Empty slot
Cluster 2: 3 active, 1 tombstone (length 4)
Empty slot
Cluster 3: 3 active (length 3)

Total active = 2 + 3 + 3 = 8. Total tombstones = 1 + 1 = 2. Total slots = 3 + 1 + 4 + 1 + 3 = 12.

The worst-case successful search probes all items in the longest cluster, which takes 4 probes.

Answer: 4

Question 3 · Binary Trees: Properties and Traversals MCQ

The pre-order traversal of a binary tree with $9$ distinct integer-valued nodes is

$8, 3, 1, 6, 4, 7, 10, 14, 13$ and its in-order traversal is

$1, 3, 4, 6, 7, 8, 10, 13, 14$ .

What is the value of the root of the right subtree of the root?

A.
7
B.
10
C.
13
D.
14

Correct Answer:

Step-by-Step Solution

Key idea: This is a tree reconstruction question — the root's position in in-order determines left and right subtree sizes, which lets you split pre-order and read off the right subtree's root.

Why this method applies: The question gives pre-order and in-order, the classic pair for unique reconstruction. The first element of pre-order is always the root, and its index in in-order gives the exact left subtree size.

Step 1: Root $= 8$ (first element of pre-order).

Step 2: Find $8$ in the in-order array $[1, 3, 4, 6, 7, 8, 10, 13, 14]$ . It sits at 0-based index $5$ . So left subtree size $L = 5$ and right subtree size $R = 9 - 1 - 5 = 3$ .

Step 3: Split the remaining pre-order (after the root $8$ ) using $L = 5$ :

Left pre-order $= [3, 1, 6, 4, 7]$ (next $5$ elements).

Right pre-order $= [10, 14, 13]$ (remaining $3$ elements).

Step 4: The root of the right subtree is the first element of the right pre-order $= 10$ .

Answer: $10$ .

Wrong path (option A): Assuming the tree is balanced and using $L = (9 - 1) /2 = 4$ . Then right pre-order starts at index $5$ of the original pre-order: $[7, 10, 14, 13]$ , giving root $= 7$ . This breaks at Step 2 — the left subtree size is determined by the root's position in in-order, not by assuming balance.

Generalization: Never assume a tree is balanced unless explicitly stated; always use the in-order position of the root to compute subtree sizes.

Verification: In-order elements before $8$ are ${1, 3, 4, 6, 7}$ ( $5$ nodes). Elements after $8$ are ${10, 13, 14}$ ( $3$ nodes). Right pre-order $= [10, 14, 13]$ , first element $= 10$ . Consistent.

A question from this chapter

Login to view the complete notes

Personalised first. High quality throughout.

Built around you, not around a syllabus PDF

Revision that hits your weak spots

Questions calibrated to the real exam

Notes written for recall, not for volume

One place for everything

Honest progress

Unlock the whole course

Data Structures Notes for GATE DA

About Data Structures Notes

Data Structures Weightage in GATE DA

Data Structures Chapter Matrix

More from Programming, Data Structures and Algorithms

One Solved Question from Each Data Structures Chapter

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution