GATE DA & AI Engineering Programming, Data Structures and Algorithms Syllabus

Programming, Data Structures and Algorithms syllabus — full chapter and topic list

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

1. 1

   Programming in Python

   6 topics

   • Basic Data Structures
     • Stacks
     • Queues
     • Linked Lists
     • Trees
     • Hash Tables
   • Search Algorithms
     • Linear Search
     • Binary Search
   • Basic Sorting Algorithms
     • Selection Sort
     • Bubble Sort
     • Insertion Sort
   • Divide and Conquer
     • Mergesort
     • Quicksort
   • Introduction to Graph Theory
   • Basic Graph Algorithms
     • Traversals
     • Shortest Path

Programming, Data Structures and Algorithms flashcards for GATE DA & AI Engineering

21 of 52 cards from the Programming, Data Structures and Algorithms deck — real questions with worked answers.

1. What is a data structure?

   A data structure is a systematic way of organizing, storing, and managing data in memory so it can be accessed and modified efficiently. The choice of structure determines the time and space cost of operations like insertion, deletion, and search.

2. What is the difference between a linear and a non-linear data structure?

   In a linear data structure (array, stack, queue, linked list) elements are arranged sequentially, each with a single predecessor and successor. In a non-linear data structure (tree, graph) elements are connected hierarchically or in a network, so an element may have many predecessors/successors.

3. State the abstract behavior (ordering discipline) of a stack.

   A stack is a LIFO (Last-In, First-Out) structure: the last element pushed is the first one popped. All insertions and deletions occur at one end called the top.

4. Name the core stack operations and their time complexity in an array or linked-list implementation.

   $\text{push}$ (insert at top), $\text{pop}$ (remove top), $\text{peek/top}$ (read top), and $\text{isEmpty}$. Each runs in $O(1)$ time.

5. Give two classic applications of a stack.

   Function-call management (the runtime call stack / recursion), and expression evaluation and conversion (e.g., infix to postfix, checking balanced parentheses, backtracking, undo operations).

6. State the abstract behavior (ordering discipline) of a queue.

   A queue is a FIFO (First-In, First-Out) structure: the first element enqueued is the first dequeued. Insertion happens at the rear and removal at the front.

7. Name the core queue operations and their time complexity.

   $\text{enqueue}$ (insert at rear), $\text{dequeue}$ (remove from front), $\text{front/peek}$, and $\text{isEmpty}$. All run in $O(1)$ time with proper front/rear pointers.

8. What is a circular queue and why is it used?

   A circular queue treats the underlying array as a ring, where the position after the last index wraps to index $0$. It reuses freed front slots, eliminating the wasted space that a linear array queue suffers after repeated dequeues.

9. How does a deque differ from an ordinary queue?

   A deque (double-ended queue) allows insertion and deletion at both the front and the rear, generalizing both stacks and queues.

10. What is a singly linked list and what does each node store?

    A singly linked list is a linear sequence of nodes where each node stores a data field and a single pointer (next) to the following node. The last node's next pointer is null.

11. Compare the time complexity of access-by-index and insertion-at-head for an array versus a singly linked list.

    Array: random access by index is $O(1)$, but insertion at the head is $O(n)$ (shifting). Linked list: access by index is $O(n)$ (traversal), but insertion at the head is $O(1)$.

12. What advantage does a doubly linked list have over a singly linked list?

    Each node also stores a pointer to its predecessor (prev), enabling $O(1)$ bidirectional traversal and $O(1)$ deletion of a node given only a pointer to that node, without traversing from the head.

13. In a linked list, what is the time complexity of deleting a node when you have a pointer to the node before it?

    $O(1)$ — you simply redirect the predecessor's next pointer past the node to be deleted.

14. Define a tree as a data structure.

    A tree is a connected, acyclic hierarchical structure of nodes with one designated root, where every non-root node has exactly one parent. A tree with $n$ nodes has exactly $n-1$ edges.

15. Define the height and depth of a node in a tree.

    The depth of a node is the number of edges on the path from the root to that node (root has depth $0$). The height of a node is the number of edges on the longest downward path from that node to a leaf (leaves have height $0$).

16. What is a binary search tree (BST) and its ordering property?

    A BST is a binary tree where, for every node, all keys in its left subtree are less than the node's key and all keys in its right subtree are greater. This enables search, insert, and delete in $O(h)$ where $h$ is the height.

17. What is the search/insert time complexity in a BST in the average versus worst case?

    Average (balanced) case: $O(\log n)$. Worst case (a degenerate/skewed tree resembling a linked list): $O(n)$.

18. Name the three depth-first traversal orders of a binary tree.

    Inorder (Left, Root, Right), Preorder (Root, Left, Right), and Postorder (Left, Right, Root). For a BST, an inorder traversal visits keys in sorted ascending order.

19. What is the maximum number of nodes in a binary tree of height $h$?

    $2^{h+1} - 1$ nodes (counting height as edges, root at height $0$), which corresponds to a perfect binary tree with $h+1$ levels.

20. What is a hash table and what is its purpose?

    A hash table stores key–value pairs in an array, using a hash function to map each key to an array index (bucket). It supports average-case $O(1)$ insertion, deletion, and lookup.

21. What is a hash collision, and name two strategies to resolve it.

    A collision occurs when two distinct keys hash to the same index. Resolution strategies: (1) separate chaining — each bucket holds a linked list of entries; (2) open addressing — probe for another open slot (linear probing, quadratic probing, or double hashing).

See more Programming, Data Structures and Algorithms flashcards →

Planning Programming, Data Structures and Algorithms for GATE DA & AI Engineering

Programming, Data Structures and Algorithms (GATE DA & AI Engineering) FAQ