What is the time complexity of counting sort for n integers whose values lie in the range 0 to k?
Correct answer B. O(n + k)
Topic / 90 questions
Data Structures MCQs
Data Structures MCQs test how data is organised and processed in programs, a core subject for computer science students, programming job tests and exams such as GATE and university papers. Questions cover arrays, linked lists, stacks, queues, trees, heaps, graphs, hashing, searching and sorting. Computed answers such as traversal orders and postfix results were checked with code, and every answer is explained.
What is a collision in a hash table?
Correct answer D. Two different keys hash to the same index
How does separate chaining resolve collisions in a hash table?
Correct answer B. Each slot holds a linked list of all keys that hash to it
Advertisement
Keys 15, 22 and 8 are inserted in that order into a hash table of size 7 using h(k) = k mod 7 and linear probing. At which index is 8 stored?
Correct answer B. 3
Keys 23, 34 and 45 are inserted in that order into a hash table of size 11 using h(k) = k mod 11 and quadratic probing, h(k, i) = (h(k) + i²) mod 11. At which index is 45 stored?
Correct answer A. 5
A hash table has 40 slots and currently stores 30 keys. What is its load factor?
Correct answer D. 0.75
Which problem is most closely associated with linear probing in open-addressing hash tables?
Correct answer C. Primary clustering
What is the average time complexity of search in a well-designed hash table with a low load factor?
Correct answer D. O(1)
Which condition must hold before binary search can be applied to an array?
Correct answer C. The array must be sorted
Advertisement
What does the array look like after the first pass of bubble sort in ascending order?
Correct answer D. [3, 7, 1, 5, 9]
What does the array look like after two passes of selection sort in ascending order?
Correct answer A. [10, 13, 14, 37, 29]
What is the best-case time complexity of insertion sort, and when does it occur?
Correct answer C. O(n), when the input is already sorted
Quick sort always chooses the last element as the pivot. Which input causes its worst-case O(n²) running time?
Correct answer A. An array that is already sorted
Using Lomuto partitioning with the last element as pivot, what is the array after one partition step?
Correct answer B. [3, 1, 4, 8, 9, 7]
Which statement about merge sort is correct?
Correct answer A. It is stable and runs in O(n log n) time in every case, but needs O(n) extra space for arrays
Advertisement
Which of these sorting algorithms is not stable in its standard form?
Correct answer B. Heap sort
What is the maximum number of comparisons binary search needs to find a key in a sorted array of 1000 elements?
Correct answer D. 10
The array is turned into a max-heap using the bottom-up build-heap method, sifting down from the last internal node to the root. What is the resulting array?
Correct answer C. [9, 4, 5, 1, 3, 2]
The keys 10, 4, 7, 1, 8, 3 are inserted one at a time into an empty binary min-heap stored in an array. What is the final array?
Correct answer B. [1, 4, 3, 10, 8, 7]
How does a B+ tree differ from a B-tree?
Correct answer C. All data records are stored in the leaves, and the leaves are linked for sequential access
About Data Structures MCQs
The set begins with basic ideas such as abstract data types, linear and non-linear structures and Big-O notation for common operations. Arrays and linked lists follow, including address calculation, insertion and deletion costs, doubly and circular lists, and cycle detection.
Stack and queue questions cover push and pop, overflow and underflow, infix-to-postfix conversion, postfix evaluation, circular queues, deques and priority queues. Tree questions deal with binary tree properties, traversals, binary search trees, AVL rotations, B-trees and heaps.
The final part covers graph representations, breadth-first and depth-first search, topological sorting, minimum spanning trees and shortest paths, then hashing with collision resolution and load factor, and finally searching and sorting algorithms with their time complexity, stability and in-place behaviour.
Key facts to remember
- A stack is LIFO (last in, first out); a queue is FIFO (first in, first out).
- Binary search needs a sorted array and runs in O(log n) time.
- An inorder traversal of a binary search tree visits keys in ascending order.
- Breadth-first search uses a queue; depth-first search uses a stack or recursion.
- Merge sort runs in O(n log n) in every case; quicksort is O(n^2) in the worst case.
Exams that include Data Structures MCQs
Pakistan
- NTS
- PPSC Computer Science Lecturer
- FPSC IT posts
- University exams
India
- GATE CS
- UGC NET Computer Science
- Campus placements
- ISRO and BARC scientist exams
Bangladesh
- BCS (technical cadre)
- Bank IT officer tests
- Government programmer posts
How to prepare for Data Structures MCQs
- Draw small trees and run traversals by hand before choosing an answer.
- Memorise best, average and worst-case complexities of the main sorting algorithms.
- For heaps stored in arrays, learn the parent and child index formulas.
- Use a stack on paper when converting infix expressions to postfix.
Frequently asked questions
What is the difference between a stack and a queue?
A stack removes the most recently added item first (LIFO), using push and pop at one end. A queue removes the oldest item first (FIFO), adding at the rear and removing from the front.
Which data structure topics are asked most in GATE and job tests?
Tree traversals and binary search trees, heaps, stack applications such as postfix evaluation, hashing with collisions, graph traversal, and the time complexity of searching and sorting algorithms appear most often.
Last reviewed October 2026