Back to Study Material GATE Exam

Topic Wise Quiz on Data Structures

Practising topic-wise quiz questions on data structures is the fastest way to identify gaps in your understanding before GATE. This section presents challe...

Topic Wise Quiz on Data Structures

Practice Questions on Arrays, Stacks, and Queues

Practising topic-wise quiz questions on data structures is the fastest way to identify gaps in your understanding before GATE. This section presents challenging questions with explanations to help you build the pattern recognition skills needed for the exam.

Question 1: An array A of size 10 is declared as int A[10]. Element A[0] is stored at address 1000. If the size of int is 4 bytes, what is the address of A[7]? Answer: 1000 + 7 times 4 = 1028. Address calculation is a guaranteed source of easy marks; never skip these questions.

Question 2: What is the maximum number of elements in a stack implemented using an array of size n, if the stack uses a top pointer initialised to -1? Answer: n elements (indices 0 through n-1). The stack overflows when top equals n-1 before a push.

Question 3: A circular queue is implemented using an array of size 6. Initially, front = 0 and rear = 0 (empty). After inserting 5 elements, what is the state? Answer: rear = 5, front = 0. The queue now has 5 elements. Inserting one more would make rear = (5+1) mod 6 = 0, which equals front, indicating a full queue. This is why a circular queue of size n holds only n-1 elements in the standard implementation.

Question 4: Which data structure is most appropriate for implementing a browser's back button? Answer: a stack. Each visited page is pushed onto the stack. Pressing back pops the top page and navigates to it.

Question 5: Given the infix expression A + B * C - D, convert it to postfix. Using the operator precedence algorithm: A is output. Plus is pushed to stack. B is output. Multiplication has higher precedence than plus, so it is pushed. C is output. Minus has lower or equal precedence than multiplication, so multiplication is popped and output. Minus has lower precedence than plus, so plus is popped and output. Minus is pushed. D is output. Minus is popped. Final postfix: A B C * + D -. Verify by evaluating with sample values to check correctness.

Question 6: How many stacks are needed to implement a queue such that each enqueue and dequeue operates in amortised O(1) time? Answer: two stacks. One stack is used for enqueue; the other for dequeue. When the dequeue stack is empty, all elements from the enqueue stack are transferred to the dequeue stack. Each element is transferred at most once, giving amortised O(1) cost per operation.

Tree and Graph Quiz with Explanations

Quiz questions on trees and graphs form the core of GATE DSA questions in the 2-mark category. The following questions cover the most frequently tested patterns.

Question 1: How many distinct binary trees can be formed with 3 nodes? Answer: 5. This is the 3rd Catalan number: C(3) = (6 choose 3) / 4 = 20 / 4 = 5. The Catalan number formula C(n) = (2n choose n) / (n+1) counts unlabelled binary trees. For labelled BSTs with distinct keys, the count is also the Catalan number.

Question 2: In a min-heap, the element at index 5 (1-indexed) in the array representation has its parent at which index? Answer: index 2 (integer division of 5 by 2). Its left child would be at index 10 and its right child at index 11.

Question 3: A BST is formed by inserting the keys 10, 5, 15, 3, 7 in that order. What is the inorder traversal? Answer: 3, 5, 7, 10, 15. Inorder traversal of any BST always produces the keys in sorted order. This is a property you should be able to state and use without drawing the tree.

Question 4: An undirected graph has 7 vertices and 9 edges. Is it possible for this graph to be a tree? Answer: no. A tree on n vertices has exactly n-1 edges. A tree on 7 vertices has 6 edges. Since this graph has 9 edges, it cannot be a tree (it has cycles).

Question 5: In a BFS of an undirected graph starting from vertex 1 with adjacency list representation (vertices given in sorted order), which vertices are at distance 2 from vertex 1 if the edges are (1,2), (1,3), (2,4), (2,5), (3,6)? Answer: vertices 4, 5, and 6 are at distance 2. Distance 1 vertices are 2 and 3. BFS expands level by level.

Question 6: Dijkstra's algorithm is run on a graph with 5 vertices and 7 edges using a binary heap. What is the time complexity? Answer: O((V + E) log V) = O((5 + 7) log 5) = O(12 times 2.32) which is O(12 log 5). In general terms for this question type, the answer is O((V + E) log V).

Question 7: What is the minimum number of edges in a connected graph with n vertices? Answer: n-1, which forms a spanning tree. A connected graph must have at least n-1 edges; fewer edges would leave the graph disconnected.

Hashing and Sorting Quiz

Hashing and sorting questions in GATE range from straightforward complexity recall to detailed tracing problems. This quiz section targets the patterns that appear most frequently.

Question 1: A hash table has 7 slots (indices 0 to 6). The hash function is h(k) = k mod 7. Keys 15, 22, 29 are inserted using linear probing. What are their positions? h(15) = 1, h(22) = 1 (collision, probe to 2), h(29) = 1 (collision, probe to 2, probe to 3). Final positions: 15 at index 1, 22 at index 2, 29 at index 3.

Question 2: After how many comparisons does bubble sort place the largest element in its final position in the first pass over an array of n elements? Answer: n-1 comparisons. In the first pass, bubble sort compares elements at positions 0 and 1, then 1 and 2, and so on up to n-2 and n-1, making exactly n-1 comparisons.

Question 3: Selection sort is applied to the array [64, 25, 12, 22, 11]. What is the array after the second pass? In pass 1, find minimum (11), swap with position 0: [11, 25, 12, 22, 64]. In pass 2, find minimum of remaining (12 at index 2), swap with position 1: [11, 12, 25, 22, 64].

Question 4: Which sorting algorithm is best suited for sorting a linked list? Answer: merge sort. It can be performed on a linked list without random access by splitting and merging using pointer manipulation. Quick sort requires random access for efficient partitioning, and heap sort requires array indexing.

Question 5: What is the time complexity of building a max-heap from an unsorted array using the bottom-up heapification method? Answer: O(n). Although each call to heapify takes O(log n), most calls are made on subtrees with small height. The total work sums to O(n) by the harmonic series analysis.

Question 6: Radix sort is applied to 1000 integers, each with at most 4 decimal digits. How many passes are required and what is the time complexity of each pass? Answer: 4 passes (one per digit position), each pass uses counting sort on 10 buckets (digits 0-9) and takes O(n + 10) = O(n) time. Total: O(4n) = O(n).

Question 7: Merge sort uses a divide-and-conquer strategy. For an input array of 8 elements, how many levels does the recursion tree have? Answer: 4 levels (including the base case). The array is divided log2(8) = 3 times, giving 3 levels of division plus 1 base level.