DS · GATE CS 2027
9 topics and 20 sheets. Open a topic for its sheets and the topics it depends on.
Row-major and column-major address formulas for 2-D and 3-D arrays with any lower bounds, reverse problems that recover the base or a dimension from two addresses, triangular, symmetric and tridiagonal storage formulas, sparse matrices in triplet and CSR form, and the shift cost of insertion and deletion.
Stack operations and their costs in array and linked implementations, two stacks in one array, balanced brackets, recursion and the call stack, valid pop sequences and Catalan counts, and infix, prefix and postfix conversion and evaluation with full stack traces.
Linear and circular queues with the full and empty tests for each convention, deques and restricted deques, priority queue implementations, a queue built from two stacks and a stack built from two queues with exact operation counts, and linked queues.
Singly, doubly and circular lists: insertion and deletion with safe pointer order, costs with and without a tail pointer, sentinel nodes, reversal, middle node, Floyd cycle detection with cycle start and length, merging sorted lists, and list questions with compiled C.
Binary tree terminology and the node, leaf and height relations, full, complete and perfect trees, k-ary trees, array representation, traversals and reconstruction from two traversals, expression trees, Catalan counts of shapes and labelled trees, and threaded trees.
Binary search tree search, insertion and deletion in all three cases, inorder successor and predecessor, height bounds, BST from a preorder, insertion orders, valid search paths, and AVL trees (beyond the named syllabus): balance factor, the four rotations, insertion traces and the minimum nodes for a height.
Binary heap array indexing, insertion and deletion with sift-up and sift-down traces, heap property checks, bottom-up build-heap in linear time, where the k-th smallest key can sit, counting heaps, and d-ary heaps.
Adjacency matrix and adjacency list with their space and operation costs, degree sum, in-degree and out-degree for directed graphs, graphical degree sequences, edge and graph counts, and how to choose a representation.
A master complexity table for every structure, the traps that cost marks with their fixes, question patterns with the first step to take, and a one-page last-day sheet.
Address formulas for one-, two- and three-dimensional arrays in row-major and column-major order with arbitrary lower bounds, the general n-dimensional rule, element counts, reverse problems that recover the base address or a dimension from two known addresses, and a compiled C program showing that C stores arrays row by row. All worked values are computed by a verification script.
Packed storage for lower and upper triangular, symmetric, diagonal and tridiagonal matrices with the offset formulas for row-major and column-major packing, sparse matrices in triplet and compressed sparse row form with their space break-even points, and the shift cost of inserting into and deleting from an array. Every formula was checked against a brute-force enumeration for n up to 12.
The stack abstract data type and its constant-time operations, array and linked implementations with their overflow and underflow tests, two stacks sharing one array, balanced-bracket checking with traces, recursion and the call stack (frames and call counts), and valid pop sequences: the Catalan count, the greedy check and the forbidden 3-1-2 pattern. Counts are verified by brute force over all permutations.
Operator precedence and associativity, the operator-stack algorithm from infix to postfix with a full token-by-token trace, prefix by expression tree or by the reverse method, postfix evaluation traced by a compiled C program, prefix evaluation from right to left, the rank rule for valid postfix strings and postfix back to infix. Every conversion and value is computed by a verification script.
Linear and circular array queues with the full, empty and count tests for each common convention, a traced circular queue, deques and input- or output-restricted deques with their reachable output orders, priority queue implementations compared, a queue built from two stacks and a stack built from two queues with exact operation counts (each queue item costs four stack operations), and linked queues.
Singly, doubly and circular linked lists and sentinel nodes: insertion and deletion with the pointer updates in a safe order, the cost of every common operation with and without a tail pointer, the copy-next deletion trick and where it fails, empty and one-node cases, and arrays compared with lists.
Compiled C for in-place reversal with three pointers, the middle node with slow and fast pointers (and which middle each loop condition returns), Floyd cycle detection with the cycle start and length, merging two sorted lists with comparison bounds, the k-th node from the end, and GATE CS 2010 Q.36 (moving the last node to the front), all with outputs produced by the compiler.
Binary tree terminology with the height convention made explicit, the node, leaf, edge and NULL-link relations, maximum and minimum nodes for a height, full, complete and perfect trees with their counts, full k-ary trees, and the array representation with its worst-case waste. Every relation is checked by brute force over all tree shapes with up to 9 nodes.
Preorder, inorder, postorder and level-order traversal with their time and space costs, iterative inorder with a stack, rebuilding a binary tree from preorder or postorder plus inorder with two worked traces, which traversal pairs fix a unique tree and how many trees share an ambiguous pair, positional facts about first and last nodes, and threaded binary trees. Uniqueness claims are checked by brute force.
Expression trees and how preorder, inorder and postorder give prefix, infix and postfix, building one from a postfix string, Catalan counts of binary tree shapes, labelled trees and binary search trees (also with a fixed root), chains and full trees, the left-child right-sibling form of general trees, and recursive tree functions in compiled C. Counts are brute-forced over all shapes and permutations.
The binary search tree property and its consequences, search and insertion paths, minimum and maximum, inorder successor and predecessor in both cases, deletion of a leaf, a node with one child and a node with two children (successor or predecessor replacement) traced on one tree, height bounds and the cost of every operation. All paths, successors and post-deletion trees come from a verification script.
Rebuilding a BST from its preorder (GATE CS 2026 Set 1 Q.62), depth after a sequence of insertions (GATE CS 2025 Set 2 Q.35), which keys can come third when building a complete BST (GATE CS 2026 Set 1 Q.40), valid search paths with the range method, how insertion order changes height, how many orders build one BST, k-th smallest and checking the BST property. Every answer is recomputed by a script.
AVL trees (beyond the named syllabus) as height-balanced binary search trees: balance factor, the four imbalance cases and their single and double rotations, insertion traces with every rotation named, the minimum number of nodes for a height (a Fibonacci-like recurrence), the largest possible height for n nodes, and the cost of search, insertion and deletion. Rotations and counts are checked by an AVL implementation and brute force.
The binary heap as a complete binary tree stored in an array: 1-based and 0-based index maps, leaf range and height, insertion with sift-up and delete-min with sift-down traced swap by swap, the heap property test (with the corrected inequality), where the maximum of a min-heap can be, and the cost of every heap operation. Every array and count is produced by a verification script.
Bottom-up build-heap traced on GATE CS 2024 Set 1 Q.41, why it is linear (exact worst-case swap count), build-heap compared with repeated insertion, the depths where the k-th smallest key can sit (brute force over every heap on 10 and 12 keys), leaf positions (GATE CS 2024 Set 1 Q.43 and 2026 Set 1 Q.23), the number of distinct heaps on n keys, and d-ary heaps with their index maps, height and costs.
Graph vocabulary, the degree-sum rule for undirected and directed graphs, edge and graph counts, adjacency matrix and adjacency list compared operation by operation, worked degree and space examples, graphical degree sequences by Havel-Hakimi, matrix powers as walk counts, incidence matrices and edge lists, and how to choose a representation. Graph algorithms are in the Algorithms pack.
One full-width table with the cost of access, search, insertion, deletion and minimum or maximum for arrays, linked lists, stacks, queues, binary trees, binary search trees, AVL trees (beyond the named syllabus) and binary heaps, a table of whole-structure tasks such as build-heap, traversals, reconstruction and graph traversal per representation, and the complexity slips that cost marks. Each row points to the sheet that derives it.
Twenty-seven wrong intuitions about arrays, stacks, queues, linked lists, binary trees, binary search trees, AVL trees (beyond the named syllabus), heaps and graph representations, each next to the correct rule and a verified number or a pointer to the sheet that explains it.
The recurring shapes of data structure questions, each with the cue that identifies it, the first step, the method, the assumption to check and the usual failure, plus a table matching needs to structures. Patterns describe past question shapes, not a forecast.
The whole Data Structures pack on one page: address and packing formulas, stack, expression and queue rules, list costs, tree counts and traversal facts, BST rules, AVL rules (beyond the named syllabus), heap indexing and build-heap, graph representation costs, and the five conventions to read from every stem.
Programming in CAlgorithmsCompiler DesignOperating SystemsEngineering MathematicsDatabase Management Systems
