Programming and Data Structures Short Notes for GATE CS

GATE CS Programming and Data Structures: 7 chapters, 66 previous year questions (100% of Programming and Data Structures), 563 practice questions and one solved question from each chapter.

About Programming and Data Structures Short Notes

Quick revision sheets for Programming and Data Structures in GATE CS. Every chapter is condensed into key formulas, shortcuts and common traps so you can revise 7 chapters fast before the exam.

Programming and Data Structures Weightage in GATE CS

Programming and Data Structures accounts for 66 of 66 Programming and Data Structures previous year questions in our bank (100%), about 6.6 per paper across 10 papers.

Programming and Data Structures Chapter Matrix

Chapter	Topics	PYQs	Share of unit PYQs	Practice questions
C Programming, Control Flow and Array Algorithms	Loop Tracing and Iterative Computation, Function Calls, Evaluation Order and Static State, Bitwise and Character Expressions, Array Processing and Iterative Algorithms, Variable Scope, Shadowing and Compilation	13	20%	193
Pointers, Arrays, Strings and Memory Management	Pointer Assignment, Dereferencing and Arithmetic, Strings and Character Pointers, Multidimensional Arrays and Memory Layout, Runtime Memory and Dynamic Allocation	10	15%	153
Recursion and Recursive Program Analysis	Recursive Array and String Traversal, Recursive Arithmetic Algorithms, Nested Recursion and Return-Value Analysis	6	9%	0
Stacks, Queues and Linked Lists	Stack Operations and Augmented Stacks, Queue Operations, Reversal and Stack-Queue Interaction, Linked List Manipulation, Recursion and Complexity	11	17%	60
Binary Trees, Binary Search Trees and Traversals	Binary Tree Structure, Height and Node Counts, Binary Search Tree Construction and Ordering Properties, Tree Traversals and Recursive Tree Processing, Complete Binary Search Trees in Array Representation	13	20%	127
Heaps, Priority Queues and Data Structure Operations	Heap Structure, Height and Leaf Positions, Heap Construction and Array Validation, Priority Queue Operations and Heap Extrema, Meld Operations and Data Structure Complexity	8	12%	30
Hashing and Collision Resolution	Open Addressing and Probe Sequences, Uniform Hashing and Expected Load, Dynamic Hashing and Collision Buckets, Separate Chaining and Chain Length	5	8%	0

One Solved Question from Each Programming and Data Structures Chapter

Question 1 · C Programming, Control Flow and Array Algorithms MCQ

Consider the following two statements regarding ANSI C evaluation:

\textbf{Assertion (A):} The decimal value of the expression (char)( ('~' | 'a') + 50 ) is $- 79$ .

\textbf{Reason (R):} The bitwise OR of '~' (126) and 'a' (97) yields 127. Adding 50 gives 177, which exceeds the maximum signed char value of 127. The explicit (char) cast truncates the integer result to 8 bits, wrapping around to $- 79$ due to two's complement representation.

Which one of the following options is correct?

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: Integer promotion occurs during arithmetic, but an explicit cast to char forces truncation to 8 bits, invoking signed overflow behavior.

Step 1: Evaluate the bitwise OR. The ASCII value of '~' is 126 (0111 1110). The ASCII value of 'a' is 97 (0110 0001).

$126 | 97 = 01111111 = 127$ .

Step 2: Evaluate the addition. Due to integer promotion, the addition $127 + 50$ is performed as an int, yielding $177$ .

Step 3: Apply the explicit cast. The expression casts the int 177 to char. In 8-bit two's complement, 177 is 1011 0001.

Step 4: Interpret as signed char. The most significant bit is 1, indicating a negative number. The value is $- 128 + 32 + 16 + 1 = - 79$ .

Step 5: Verify the statements. Assertion (A) correctly states the final value is $- 79$ . Reason (R) correctly identifies the intermediate sum (177), the boundary limit (127), and the mechanism of two's complement wrap-around via casting. R perfectly explains A.

Answer: Both A and R are true, and R is the correct explanation of A.

Question 2 · Pointers, Arrays, Strings and Memory Management MCQ

Consider the character array char s[30] = "GATE2024";. A programmer wishes to transform this string into "GATEGATE20242024" by performing in-place character assignments. The transformation is done in two steps:

Shift the necessary existing characters to the right to create a gap.
Copy the required characters into the gap.

Assuming the programmer uses the most efficient sequence of single-character assignments (and avoids undefined behavior from overlapping reads/writes), what is the MINIMUM number of character assignments required to complete this transformation, including the final null terminator placement?

A.
8
B.
9
C.
13
D.
16

Correct Answer:

Step-by-Step Solution

Key idea: When shifting a string to a higher address (rightward) in-place, you must copy backwards to avoid overwriting unread characters. Only the characters that actually need to move should be shifted.

Step 1: Analyze the initial and target states.

Initial: $"GATE2024\0"$ (Indices 0 to 8).

Target: $"GATEGATE20242024\0"$ (Indices 0 to 16).

Step 2: Identify what needs to move. The prefix $"GATE"$ (indices 0-3) is already in the correct position. The suffix $"2024\0"$ (indices 4-8, exactly 5 bytes) must be shifted right by 4 positions to indices 8-12.

Step 3: Execute the shift safely. Since the destination (8) is greater than the source (4), a forward copy would overwrite the null terminator before it is read. We must copy backwards:

$s[12] = s[8]$ ( $\0$ )

$s[11] = s[7]$ ('4')

$s[10] = s[6]$ ('2')

$s[9] = s[5]$ ('0')

$s[8] = s[4]$ ('2')

This requires exactly 5 assignments.

Step 4: Fill the gap. The gap at indices 4-7 must be filled with $"GATE"$ .

$s[4] = ’G’, s[5] = ’A’, s[6] = ’T’, s[7] = ’E’$ .

This requires exactly 4 assignments.

Step 5: Sum the operations. $5 (shift) + 4 (fill) = 9$ total assignments.

Answer: B

Question 3 · Stacks, Queues and Linked Lists MCQ

Consider a queue $Q_{1}$ of size $N = 10$ containing elements $1, 2, \dots, 10$ (with $1$ at the front). We wish to reverse the queue into an initially empty queue $Q_{2}$ using only $Enqueue$ and $Dequeue$ operations, without any additional storage. During the complete execution of the standard optimal two-queue reversal algorithm, how many more $Dequeue$ operations are performed on $Q_{2}$ than on $Q_{1}$ ?

A.
35
B.
45
C.
55
D.
-35

Correct Answer:

Step-by-Step Solution

Key idea: This is an operation counting problem. We must separately count the Dequeue operations on $Q_{1}$ and $Q_{2}$ and find their difference.

Step 1: Every element is removed from $Q_{1}$ exactly once. Thus, total Dequeue operations on $Q_{1}$ = $N = 10$ .

Step 2: For the $k$ -th element (from $1$ to $N$ ), after it is moved to $Q_{2}$ , the $k - 1$ elements already in $Q_{2}$ must be rotated. Each rotation requires 1 Dequeue from $Q_{2}$ .

Step 3: Total Dequeue operations on $Q_{2}$ = $\sum_{k = 1}^{N} (k - 1) = \frac{N ( N - 1 )}{2}$ .

Step 4: For $N = 10$ , Dequeue on $Q_{2}$ = $\frac{10 \times 9}{2} = 45$ .

Step 5: The difference (Dequeue on $Q_{2}$ minus Dequeue on $Q_{1}$ ) = $45 - 10 = 35$ .

Answer: 35

Question 4 · Binary Trees, Binary Search Trees and Traversals NAT

Consider a binary tree with $100$ nodes. Find the maximum possible number of leaf nodes in such a tree.

Correct Answer:

50.00

Step-by-Step Solution

Key idea: To maximize leaf nodes $N_{0}$ , we must minimize internal nodes. Use the constraint $N_{0} = N_{2} + 1$ and optimize.

Step 1: We want to maximize $N_{0}$ subject to:

$N_{0} + N_{1} + N_{2} = 100$
$N_{0} = N_{2} + 1$

Step 2: Substitute $N_{0} = N_{2} + 1$ :

$(N_{2} + 1) + N_{1} + N_{2} = 100$

$2 N_{2} + N_{1} + 1 = 100$

$2 N_{2} + N_{1} = 99$

Step 3: Since $N_{0} = N_{2} + 1$ , maximizing $N_{0}$ means maximizing $N_{2}$ .

Step 4: From $2 N_{2} + N_{1} = 99$ with $N_{1} \geq 0$ :

Maximum $N_{2}$ occurs when $N_{1}$ is minimized
If $N_{1} = 0$ : $2 N_{2} = 99 ⟹ N_{2} = 49.5$ (not integer!)
If $N_{1} = 1$ : $2 N_{2} = 98 ⟹ N_{2} = 49$ ✓

Step 5: With $N_{2} = 49$ :

$N_{0} = N_{2} + 1 = 49 + 1 = 50$

Verification: $N_{0} = 50$ , $N_{1} = 1$ , $N_{2} = 49$ . Total = $50 + 1 + 49 = 100$ ✓

Answer: 50

Question 5 · Heaps, Priority Queues and Data Structure Operations MCQ

Consider a binary min-heap with $1$ -based indexing that stores $1024$ distinct elements. The maximum number of elements in the heap that can be strictly greater than the element at index $2$ is

A.
1020
B.
1021
C.
1022
D.
1023

Correct Answer:

Step-by-Step Solution

Key idea: In a min-heap, $A [1]$ is the minimum, so $A [1] < A [2]$ . When counting elements strictly greater than $A [2]$ , we must exclude $A [1]$ and $A [2]$ itself.

Step 1: $n = 1024$ . $A [1]$ is the minimum, so $A [1] < A [2]$ . Thus $A [1]$ is NOT strictly greater than $A [2]$ .

Step 2: $A [2]$ itself is NOT strictly greater than $A [2]$ .

Step 3: All proper descendants of node $2$ are $> A [2]$ by the min-heap property. The subtree of node $2$ contains $2^{10 - 1} = 512$ nodes (including node $2$ ), so there are $511$ proper descendants.

Step 4: The subtree of node $3$ contains $511$ nodes (excluding node $3$ ). All of these can be $> A [2]$ if we arrange the heap appropriately (e.g., $A [2]$ is the second smallest element).

Step 5: Maximum elements $> A [2] = 511 + 511 = 1022 = n - 2$ .

Answer: 1022

A question from this chapter

Login to view the complete short 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

Programming and Data Structures Short Notes for GATE CS

About Programming and Data Structures Short Notes

Programming and Data Structures Weightage in GATE CS

Programming and Data Structures Chapter Matrix

More from Programming and Data Structures

One Solved Question from Each Programming and Data Structures Chapter

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution