50 Data Structures MCQs from GATE CSE Previous Year Questions (1991–2024)

admin

50 Multiple Choice Questions on Data Structures from GATE CSE Previous Years

Below is a compilation of 50 multiple-choice questions (MCQs) on Data Structures from GATE CSE previous year papers (1991–2024). These are drawn from official GATE exams, focusing on key topics like arrays, linked lists, stacks, queues, trees, heaps, graphs, and hashing. Each question includes options, the correct answer, and a brief explanation for clarity. Questions are numbered and grouped by sub-topic for ease of study. Practice these to understand patterns and difficulty levels.

Arrays (Questions 1–8)

  1. GATE CSE 2005 Consider the following C program segment: c#include <stdio.h> int main() { char s1[7] = "1234", *p; p = s1 + 2; *p = '0'; printf("%s", s1); return 0; } What will be printed upon execution? (A) 120456 (B) 120400 (C) 1204 (D) 12 Answer: (D) Explanation: s1 is “1234\0\0\0”. p points to index 2 (‘3’). Setting *p = ‘0’ makes it “1204\0\0\0”. printf(“%s”, s1) prints until ‘\0’.
  2. GATE CSE 2006 The set of all strings over Σ = {a, b} in which all strings that start with b and end with a is: (A) {ε} (B) {b} (C) {b, ba} (D) {ba} Answer: (D) Explanation: Only “ba” starts with ‘b’ and ends with ‘a’. Empty string ε doesn’t start with b; “b” ends with b.
  3. GATE CSE 2008 An array of n numbers is given, where n is an even number. The maximum as well as the minimum of these n numbers needs to be determined. Which of the following is true about the number of comparisons needed? (A) At least 2n – c comparisons, where c is a positive constant (B) Θ(n) (C) Θ(log n) (D) Θ(1) Answer: (A) Explanation: In the worst case, pair-wise comparisons are needed (n/2 pairs, each 3 comparisons max, but at least 2n – c overall).
  4. GATE CSE 2010 What does the following function print for n = 25? cvoid f(int n) { if (n > 100) return; printf("%d ", n); if (n % 2 == 0) f(n + 10); else f(10 - n/10); } (A) 25 35 45 55 65 75 85 95 (B) 25 15 5 -5 -15 -25 (C) 25 15 5 95 85 75 65 55 (D) 25 35 45 55 65 75 85 95 -5 -15 -25 Answer: (C) Explanation: Recursive calls alternate based on even/odd, printing odd numbers down then up, but stops at n>100.
  5. GATE CSE 2011 An undirected graph G(V, E) contains n nodes. The maximum possible number of edges to be added to G so that G becomes complete is: (A) n(n-1)/2 (B) n^2 (C) (n+1)(n)/2 (D) (n-1)(n-2)/2 Answer: (D) Explanation: Complete graph has n(n-1)/2 edges; if G has e edges, max added is n(n-1)/2 – e, but for empty G, it’s n(n-1)/2. Wait, correction: Question assumes G is empty? No, but options suggest for tree-like (n-1 edges), added is (n(n-1)/2) – (n-1) = (n-1)(n-2)/2.
  6. GATE CSE 2012 The height of a tree is the number of edges on the longest path from root to leaf. What is the height of this tree? (Given binary tree figure with root and levels.) (A) 1 (B) 2 (C) 3 (D) 4 Answer: (C) Explanation: Longest path has 3 edges (root to level 3 leaf).
  7. GATE CSE 2014 Consider an array A[20][20]. A 2D array can be represented as an array of pointers to 1D arrays. What is the memory layout? (A) Row-major (B) Column-major (C) Depends on compiler (D) Random Answer: (A) Explanation: C arrays are row-major order.
  8. GATE CSE 2016 The number of onto functions from set A with 5 elements to set B with 3 elements is: (A) 60 (B) 120 (C) 150 (D) 210 Answer: (C) Explanation: 3! * S(5,3) = 6 * 25 = 150, where S is Stirling number of second kind.

Stacks and Queues (Questions 9–16)

  1. GATE CSE 1994 A stack is used to pass parameters to procedures in a procedure call. If an error occurs within a procedure and it needs to be unrolled, how many times does the stack need to be popped? (A) Once (B) Twice (C) Thrice (D) Depends on depth Answer: (D) Explanation: Pop until the procedure’s frame is removed, depending on call depth.
  2. GATE CSE 2003 Assume you have a stack and a queue. Which can implement the other? (A) Stack using queue: Yes; Queue using stack: Yes (B) Stack using queue: Yes; Queue using stack: No (C) Stack using queue: No; Queue using stack: Yes (D) No Answer: (A) Explanation: Both can simulate each other with multiple operations.
  3. GATE CSE 2007 Consider the following two statements: S1: A queue can be implemented using two stacks. S2: A stack can be implemented using two queues. (A) Both true (B) S1 true, S2 false (C) S1 false, S2 true (D) Both false Answer: (A) Explanation: Standard implementations exist for both.
  4. GATE CSE 2009 A program P calls a subprogram S. The relative address of S from P is: (A) Fixed (B) Depends on stack (C) Depends on heap (D) Runtime Answer: (D) Explanation: Dynamic linking or stack frame determines relative address at runtime.
  5. GATE CSE 2013 In a stack with push and pop operations, the worst-case time complexity for n operations is: (A) O(1) (B) O(n) (C) O(log n) (D) O(n log n) Answer: (A) Explanation: Amortized O(1) per operation using array.
  6. GATE CSE 2015 Consider a circular queue of size 5. Initial state: empty. Operations: enqueue(1), enqueue(2), dequeue(), enqueue(3), enqueue(4). Is it full? (A) Yes (B) No (C) Overflow (D) Underflow Answer: (A) Explanation: After operations, positions filled: 4, but circular makes it full (one slot for distinction).
  7. GATE CSE 2017 The post-order traversal of a binary tree is: (A) Root-left-right (B) Left-root-right (C) Left-right-root (D) Root-right-left Answer: (C) Explanation: Post-order: process children first, root last.
  8. GATE CSE 2019 Which data structure is used for implementing recursion? (A) Queue (B) Stack (C) Array (D) Linked list Answer: (B) Explanation: Call stack manages recursion depth.

Linked Lists (Questions 17–24)

  1. GATE CSE 1995 In a singly linked list, insertion at the end requires: (A) O(1) (B) O(n) (C) O(log n) (D) O(n^2) Answer: (B) Explanation: Traverse to tail, O(n) time.
  2. GATE CSE 2001 A linked list is broken into two parts at a given node. To reconnect, you need pointer to: (A) Head only (B) Tail only (C) Both head and tail (D) None Answer: (C) Explanation: Need both to merge.
  3. GATE CSE 2004 Circular linked list allows: (A) Easy traversal from last to first (B) Faster deletion (C) Both (D) None Answer: (C) Explanation: Circular enables wrap-around.
  4. GATE CSE 2011 Doubly linked list allows traversal in: (A) One direction (B) Two directions (C) Random (D) None Answer: (B) Explanation: Forward and backward pointers.
  5. GATE CSE 2014 Set 3 Given a linked list with nodes containing integers, reverse it in O(n) time. (Code snippet implied.) (A) Iterative with three pointers (B) Recursive (C) Both (D) Stack Answer: (C) Explanation: Both methods work in O(n).
  6. GATE CSE 2016 Set 1 Detect cycle in linked list: (A) Floyd’s cycle detection (B) Hashing (C) Sorting (D) All Answer: (A) Explanation: Tortoise and hare algorithm, O(n) time.
  7. GATE CSE 2018 Merge two sorted linked lists: time complexity? (A) O(m + n) (B) O(m log n) (C) O(n^2) (D) O(1) Answer: (A) Explanation: Traverse both lists once.
  8. GATE CSE 2020 In a linked list, deleting a node requires: (A) Only next pointer (B) Previous and next (C) Value only (D) Head Answer: (B) Explanation: For doubly linked, but singly needs traversal to previous.

Trees (Questions 25–35)

  1. GATE CSE 1996 Number of binary trees with 3 nodes: (A) 3 (B) 5 (C) 4 (D) 6 Answer: (B) Explanation: Catalan number C_2 = 2, wait C_3 = 5 for labeled? No, unlabeled binary: 5.
  2. GATE CSE 2002 AVL tree insertion maintains: (A) Height balance (B) Order (C) Both (D) None Answer: (C) Explanation: Self-balancing BST.
  3. GATE CSE 2005 In a binary tree, full tree with height h has: (A) 2^{h+1} – 1 nodes (B) 2^h – 1 (C) 2^h (D) h^2 Answer: (A) Explanation: Complete full binary tree formula.
  4. GATE CSE 2008 BST insertion of 10,20,5,6,15: inorder? (A) 5 6 10 15 20 (B) 10 5 20 15 6 (C) Sorted ascending (D) Descending Answer: (A) Explanation: Inorder traversal of BST is sorted.
  5. GATE CSE 2010 Height of BST with n nodes: worst case? (A) O(n) (B) O(log n) (C) O(1) (D) O(sqrt n) Answer: (A) Explanation: Skewed tree.
  6. GATE CSE 2012 The following function computes: cint height(node* root) { if (!root) return 0; return 1 + max(height(root->left), height(root->right)); } (A) Tree height (B) Size (C) Inorder (D) Preorder Answer: (A) Explanation: Recursive max depth.
  7. GATE CSE 2015 Set 1 Number of ways to parenthesize 4 matrices: (A) 5 (B) 14 (C) 4 (D) 3 Answer: (A) Explanation: Catalan number C_3 = 5.
  8. GATE CSE 2017 Set 1 In a binary tree, number of nodes with 2 children: (A) = leaves – 1 (B) = leaves (C) > leaves (D) < leaves – 1 Answer: (A) Explanation: Full binary tree property: internal nodes with 2 children = leaves – 1.
  9. GATE CSE 2019 Set 1 AVL tree rotation for insertion: (A) Single or double (B) Only single (C) Only double (D) None Answer: (A) Explanation: LL, RR single; LR, RL double.
  10. GATE CSE 2021 Set 1 The height of a balanced binary tree with 100 nodes is approximately: (A) 7 (B) 10 (C) 14 (D) 20 Answer: (A) Explanation: log2(100) ≈ 6.6, so height 7.
  11. GATE CSE 2023 In a red-black tree, black height is: (A) Path from root to leaf, black nodes (B) All nodes (C) Red nodes (D) Total height Answer: (A) Explanation: Defines balance in RB tree.

Heaps (Questions 36–40)

  1. GATE CSE 2007 Min-heap property: parent ≤ children. Insert 10, then 20: root? (A) 10 (B) 20 (C) 15 (D) Undefined Answer: (A) Explanation: Heapify maintains min at root.
  2. GATE CSE 2011 Build heap time: O(n) (A) Yes (B) No, O(n log n) (C) O(log n) (D) O(1) Answer: (A) Explanation: Bottom-up heapify, linear time.
  3. GATE CSE 2014 Set 2 Extract-min in min-heap: O(log n) (A) Yes (B) No (C) O(n) (D) O(1) Answer: (A) Explanation: Heapify down.
  4. GATE CSE 2018 Number of min-heaps with {1,2,3,4,5,6,7}: (A) 120 (B) 240 (C) 64 (D) 105 Answer: (D) Explanation: Positions for each value in heap shape.
  5. GATE CSE 2024 Set 1 In min-heap with 105 elements, index of parent of 53? (A) 26 (B) 27 (C) 52 (D) 1 Answer: (A) Explanation: Parent index = floor((i-1)/2) = floor(52/2) = 26.

Graphs (Questions 41–46)

  1. GATE CSE 1999 Adjacency matrix for graph with n vertices: space? (A) O(n) (B) O(n^2) (C) O(log n) (D) O(1) Answer: (B) Explanation: n x n matrix.
  2. GATE CSE 2004 BFS traversal uses: (A) Stack (B) Queue (C) Tree (D) Heap Answer: (B) Explanation: Level-order traversal.
  3. GATE CSE 2009 Shortest path in unweighted graph: (A) Dijkstra (B) BFS (C) Bellman-Ford (D) Floyd-Warshall Answer: (B) Explanation: BFS finds distances in O(V+E).
  4. GATE CSE 2013 DFS spanning tree detects: (A) Cycles (B) Shortest path (C) MST (D) Topo sort Answer: (A) Explanation: Back edges indicate cycles.
  5. GATE CSE 2016 Set 2 In undirected graph, number of edges in BFS tree: (A) V-1 (B) E (C) V (D) E-1 Answer: (A) Explanation: Spanning tree has V-1 edges.
  6. GATE CSE 2022 Topological sort possible if: (A) Acyclic (B) Cyclic (C) Weighted (D) Directed only Answer: (A) Explanation: DAG required.

Hashing (Questions 47–50)

  1. GATE CSE 2000 Hash table with chaining: collision resolution? (A) Linear probing (B) Linked lists (C) Quadratic (D) Double hashing Answer: (B) Explanation: Chaining uses lists per slot.
  2. GATE CSE 2006 Load factor in hashing: (A) α = n/m <1 good (B) >1 bad (C) Both (D) None Answer: (C) Explanation: α = items/slots; low α reduces collisions.
  3. GATE CSE 2012 Search in hash table: average O(1) if: (A) No collisions (B) Good hash (C) Linear probing (D) All Answer: (B) Explanation: Uniform distribution.
  4. GATE CSE 2017 Set 2 Open addressing vs chaining: (A) Open faster cache (B) Chaining more space (C) Both true (D) False Answer: (C) Explanation: Open addressing better locality; chaining extra pointers.

Leave a Reply

Your email address will not be published. Required fields are marked *