GATE CS & IT Engineering Programming and Data Structures Syllabus

Programming and Data Structures syllabus — full chapter and topic list

Expand any chapter to see its topics and sub-topics. This is the whole examinable outline for Programming and Data Structures in GATE CS & IT Engineering, not a summary of it.

1. 1

   Programming in C

   overview

   Examined as a single unit within Programming and Data Structures — no further topic split in the official outline.

2. 2

   Recursion

   overview

   Examined as a single unit within Programming and Data Structures — no further topic split in the official outline.

3. 3

   Arrays

   overview

   Examined as a single unit within Programming and Data Structures — no further topic split in the official outline.

4. 4

   Stacks

   overview

   Examined as a single unit within Programming and Data Structures — no further topic split in the official outline.

5. 5

   Queues

   overview

   Examined as a single unit within Programming and Data Structures — no further topic split in the official outline.

6. 6

   Linked Lists

   overview

   Examined as a single unit within Programming and Data Structures — no further topic split in the official outline.

7. 7

   Trees

   overview

   Examined as a single unit within Programming and Data Structures — no further topic split in the official outline.

8. 8

   Binary Search Trees

   overview

   Examined as a single unit within Programming and Data Structures — no further topic split in the official outline.

9. 9

   Binary Heaps

   overview

   Examined as a single unit within Programming and Data Structures — no further topic split in the official outline.

10. 10

    Graphs

    overview

    Examined as a single unit within Programming and Data Structures — no further topic split in the official outline.

Programming and Data Structures flashcards for GATE CS & IT Engineering

20 of 50 cards from the Programming and Data Structures deck — real questions with worked answers.

1. In C, what is the difference between an array name and a pointer when used as an operand of the sizeof operator?

   For an array, sizeof returns the total bytes of the whole array ($n \times \text{sizeof(element)}$). For a pointer, sizeof returns only the size of the pointer itself (typically 4 or 8 bytes), regardless of what it points to.

2. What is the time complexity of accessing the $i$-th element of an array versus a singly linked list?

   Array access is $O(1)$ (random access via base address + $i \times \text{size}$). Singly linked list access is $O(n)$ because you must traverse from the head node.

3. Define a recursive function and state the two essential components every correct recursion must have.

   A recursive function calls itself to solve smaller instances of a problem. It must have (1) a base case that stops recursion, and (2) a recursive case that progresses toward the base case.

4. What is the recurrence relation and time complexity of computing the $n$-th Fibonacci number by naive recursion?

   $T(n) = T(n-1) + T(n-2) + O(1)$, which gives exponential time $O(\phi^{n})$ where $\phi = \frac{1+\sqrt{5}}{2}$ (about $O(2^{n})$).

5. In C, what does the storage class specifier 'static' do to a local variable inside a function?

   It gives the local variable static storage duration: it is initialized once and retains its value between function calls, while still having block scope (only visible inside the function).

6. What is the output type and behavior of pointer arithmetic: if 'p' is 'int *p' pointing to address 1000, what is 'p + 1' (assume 4-byte int)?

   $p + 1$ yields address $1000 + 1 \times 4 = 1004$. Pointer arithmetic scales by the size of the pointed-to type.

7. Distinguish call by value from call by reference in C function parameter passing.

   Call by value copies the argument; changes inside the function do not affect the caller. C is strictly call by value, but call by reference is simulated by passing pointers, allowing the function to modify the caller's variable through dereferencing.

8. What is a stack and which principle does it follow? Name its two primary operations.

   A stack is a linear data structure following LIFO (Last In, First Out). Its primary operations are push (insert at top) and pop (remove from top), both $O(1)$.

9. What is a queue and which principle does it follow? Name its enqueue/dequeue ends.

   A queue is a linear data structure following FIFO (First In, First Out). Insertion (enqueue) happens at the rear; deletion (dequeue) happens at the front.

10. Why is a circular queue preferred over a simple linear array queue?

    A circular queue reuses freed slots by wrapping the rear/front indices with modulo arithmetic ($\text{rear} = (\text{rear}+1) \bmod n$), avoiding the false-full condition that wastes space in a linear array queue.

11. How do you detect 'full' and 'empty' in a circular queue of size $n$ using front and rear pointers (with one slot kept empty)?

    Empty when $\text{front} = \text{rear}$. Full when $(\text{rear}+1) \bmod n = \text{front}$. One slot is sacrificed to distinguish the two states.

12. Convert the infix expression $A + B \times C$ to postfix (Reverse Polish) notation.

    $A\ B\ C\ \times\ +$. Multiplication has higher precedence, so $B\ C\ \times$ is evaluated first, then added to $A$.

13. Which data structure is used to evaluate a postfix expression, and what is the basic algorithm?

    A stack. Scan left to right: push operands; on an operator, pop the top two operands, apply the operator, and push the result. The final stack value is the answer.

14. What is the defining property of a binary search tree (BST)?

    For every node, all keys in its left subtree are smaller than the node's key, and all keys in its right subtree are larger. An inorder traversal yields keys in sorted order.

15. State the time complexity of search, insert, and delete in a BST in the average and worst case.

    Average case $O(\log n)$ (balanced). Worst case $O(n)$ when the tree degenerates into a skewed/linear chain (e.g., inserting sorted data).

16. List the three depth-first binary tree traversals and the order in which the root is visited in each.

    Preorder: Root, Left, Right. Inorder: Left, Root, Right. Postorder: Left, Right, Root.

17. What is the maximum number of nodes in a binary tree of height $h$ (root at height 0)?

    $2^{h+1} - 1$ nodes. Each level $i$ holds at most $2^{i}$ nodes, summed from $i=0$ to $h$.

18. What is the minimum height of a binary tree with $n$ nodes?

    $h = \lfloor \log_{2} n \rfloor$, equivalently $\lceil \log_{2}(n+1) \rceil - 1$. A complete binary tree achieves this minimum height.

19. Define a complete binary tree and a full (proper) binary tree.

    A complete binary tree has all levels full except possibly the last, which is filled left to right. A full (proper) binary tree has every node with either 0 or 2 children.

20. What is a max-heap, and how are parent/child indices computed in a 0-indexed array representation?

    A max-heap is a complete binary tree where every parent $\geq$ its children. For index $i$: parent $= \lfloor (i-1)/2 \rfloor$, left child $= 2i+1$, right child $= 2i+2$.

See more Programming and Data Structures flashcards →

Planning Programming and Data Structures for GATE CS & IT Engineering

Programming and Data Structures (GATE CS & IT Engineering) FAQ