Data structures MCQs with answers and explanations

Revise arrays, linked lists, stacks, queues, trees and graphs with concept notes and explained questions. Build the data-structure foundations used in technical placement tests, interviews and GATE CS preparation.

218 practice questionsPage updated 24 Sept 2026Reviewed by AISEA Editorial DeskPractice questions

Practise this concept

Data structures organise data so that the operations a program needs can be performed clearly and efficiently. The right choice depends on access pattern, ordering, updates, memory and whether relationships are linear or hierarchical. Technical aptitude questions usually test the structure's invariant and the cost of its common operations, not memorisation in isolation.

Key formulas and rules

6 rules

Array index access is commonly $O (1)$ ; searching an unsorted array is $O (n)$ .

A linked-list insertion at a known head or node is $O (1)$ ; indexed access is $O (n)$ .

Stack push and pop are commonly $O (1)$ ; queue enqueue and dequeue are commonly $O (1)$ with a suitable front and rear representation.

A balanced binary search tree supports search, insertion and deletion in $O (lo g n)$ ; an unbalanced tree can degrade to $O (n)$ .

A hash table gives $O (1)$ average key lookup under a good hash distribution, but collisions can make the worst case $O (n)$ .

For a graph with V vertices and E edges, an adjacency-list representation uses $O (V + E)$ space.

Key concepts

Arrays and dynamic arrays

An array stores elements in indexed positions, often in contiguous memory. Direct access by index is fast because the address can be calculated from the base address and element size. Inserting or deleting near the beginning usually shifts later elements. A dynamic array grows by allocating a larger block and copying elements, so append is often amortized O(1) even though a resize itself costs O(n).

Linked lists

A linked list stores nodes connected by links rather than requiring adjacent memory. Inserting at a known head or after a known node can be constant time, but finding a position or accessing the kth item requires traversal. A doubly linked list stores both next and previous links, using more memory to support backward traversal and easier deletion when the node is known.

Stacks, queues and deques

A stack follows LIFO: the last item pushed is the first item popped. It suits undo history and function-call management. A queue follows FIFO: the first item enqueued is the first item dequeued. It suits scheduling and breadth-first search. A deque supports insertion and removal at both ends. Circular queues reuse freed positions instead of shifting every remaining item.

Trees and binary search trees

A tree represents hierarchical relationships with a root and child nodes. A binary tree has at most two children per node. In a binary search tree, values in the left subtree are smaller and values in the right subtree are larger according to the chosen ordering. Inorder traversal of a valid BST visits keys in sorted order, but a badly skewed BST loses the expected logarithmic performance.

Heaps and priority queues

A heap is a complete tree commonly stored in an array. In a min-heap, each parent is no greater than its children, so the minimum is at the root. Insertion and removal of the root are O( $lo g n$ ), while reading the root is O(1). A priority queue uses this ordering to repeatedly process the most or least important item.

Hash tables and collision handling

A hash table maps a key to a bucket using a hash function. Equal keys must be treated consistently, and a collision occurs when different keys select the same bucket. Chaining stores several entries in a bucket structure such as a linked list; open addressing searches for another slot. Load factor and hash distribution affect performance, so O(1) is an average-case expectation, not a universal guarantee.

Graphs and representations

A graph contains vertices connected by edges, which may be directed, undirected, weighted or unweighted. An adjacency matrix gives O(1) edge-existence checks but uses O(V²) space. An adjacency list uses space proportional to vertices and edges and is efficient for sparse graphs. BFS uses a queue, while DFS uses a stack or recursion.

Choose by operation and invariant

Choose an array for frequent indexed access, a linked list for link-based insertion, a stack for LIFO, a queue for FIFO, a heap for repeated priority access, a hash table for average-case key lookup, and a tree or graph for relationships. Always state the operation and the condition behind its complexity, such as a known pointer, a balanced tree or a good hash distribution.

Check the idea while it is fresh.Open a focused exercise without losing this article.Practise this concept

Worked examples

Example 1

You need to read the 500th item repeatedly by position, but insertions at the front are rare. Which structure is usually the better fit: an array or a singly linked list?

Solution

Step 1: Repeated indexed reads favour direct address calculation.
Step 2: An array commonly accesses an item by index in O(1).
Step 3: A singly linked list must follow links from the head, making indexed access O(n).
Step 4: Rare front insertions do not outweigh the dominant access pattern.
Answer: An array is usually the better fit.

Example 2

A text editor must undo the most recent action first. Which data structure matches this requirement, and why?

Solution

Step 1: The most recent action must be removed before older actions.
Step 2: This is a last-in, first-out requirement.
Step 3: A stack provides LIFO behavior through push and pop.
Answer: Use a stack; push each action and pop the latest action when undo is requested.

Example 3

A circular queue has capacity 5, front at index 3 and rear at index 4. The rear slot is occupied, but indices 0 and 1 have been freed by earlier dequeues. What should enqueue do?

Solution

Step 1: A circular queue treats the array as wrapping from the last index back to index 0.
Step 2: The next rear position is (4 + 1) mod $5 = 0$ .
Step 3: Because index 0 is free, the new item is placed there instead of shifting existing items.
Answer: Enqueue at index 0 and update the rear position.

Example 4

Insert 40, 20, 60, 10 and 30 into a binary search tree. Where is the smallest key, and what does inorder traversal produce?

Solution

Step 1: 20 becomes the left child of 40; 60 becomes the right child.
Step 2: 10 is placed left of 20, and 30 is placed right of 20.
Step 3: The leftmost node is 10, so it is the smallest key.
Step 4: Inorder traversal visits left subtree, root and right subtree, producing 10, 20, 30, 40, 60.
Answer: Smallest key = 10; inorder traversal = 10, 20, 30, 40, 60.

Example 5

A min-heap contains [3, 7, 9, 12, 15]. Which item is removed by extract-min, and what is the usual time complexity of the removal?

Solution

Step 1: The min-heap property keeps the smallest key at the root, index 0.
Step 2: Extract-min removes 3.
Step 3: The last element is moved to the root and the heap is restored by moving it downward.
Step 4: The height of a complete heap is O( $lo g n$ ), so restoration takes O( $lo g n$ ).
Answer: Remove 3; extract-min is O( $lo g n$ ).

Example 6

A hash table has 10 buckets and stores 7 keys. What is its load factor, and what happens if two different keys hash to the same bucket when chaining is used?

Solution

Step 1: Load factor = number of stored keys / number of buckets = 7 / 10 = 0.7.
Step 2: A collision means both keys select the same bucket.
Step 3: With chaining, the bucket keeps both entries in a secondary structure, commonly a linked list.
Answer: Load factor = 0.7; the colliding entries are chained in the same bucket.

Example 7

A sparse graph has V vertices and E edges. Which representation usually uses less space: an adjacency matrix or an adjacency list?

Solution

Step 1: An adjacency matrix reserves a cell for every possible pair, using O(V²) space.
Step 2: An adjacency list stores each vertex and its actual incident edges, using O(V + E) space.
Step 3: For a sparse graph, E is much smaller than V².
Answer: Use an adjacency list; it usually uses less space for a sparse graph.

Representative solved questions

See the kind of question in this topic before opening the full practice set.

Question 1

What is the time complexity of building a heap from an array of n elements?

O(n)
$O (n lo g n)$
$O (n^{2})$
$O (lo g n)$

Answer: A. O(n)

Explanation

Step 1: Naive approach (insert n elements) would be O(n $lo g n$ ).
Step 2: Heapify algorithm starts from last non-leaf node and moves up.
Step 3: Analysis shows total operations are bounded by O(n) due to decreasing work at upper levels.
Step 4: Most nodes are leaves requiring no heapify; higher nodes affect fewer elements.
Answer: O(n)

Sources and review notes

This is an AISEA-authored practice question.

Review status: accepted · Reviewed 2026-08-13 · structure and answer-key checks, editorial quality checks, duplicate screening

Question 2

In an AVL tree, what is the maximum height difference allowed between subtrees?

Answer: B. 1

Explanation

Step 1: AVL tree is a self-balancing binary search tree.
Step 2: Balance factor = height(left subtree) - height(right subtree).
Step 3: AVL property requires balance factor in {-1, 0, 1} for all nodes.
Step 4: Maximum allowed difference is 1.
Answer: 1

Sources and review notes

This is an AISEA-authored practice question.

Review status: accepted · Reviewed 2026-08-13 · structure and answer-key checks, editorial quality checks, duplicate screening

Question 3

What is the time complexity of inserting at the end of a dynamic array (amortized)?

O(1)
O(n)
$O (lo g n)$
$O (n^{2})$

Answer: A. O(1)

Explanation

Step 1: Most insertions at end are O(1) - just write to next available slot.
Step 2: When array is full, we resize: create new array (2x size), copy all elements.
Step 3: This occasional O(n) cost is spread over many O(1) insertions.
Step 4: Using amortized analysis (aggregate or potential method), average is O(1).
Answer: O(1)

Sources and review notes

This is an AISEA-authored practice question.

Review status: accepted · Reviewed 2026-08-13 · structure and answer-key checks, editorial quality checks, duplicate screening

Common mistakes and useful habits

Start with the required operation: indexed access, insertion, deletion, ordering, membership or priority retrieval.
Remember the invariants: stack is LIFO, queue is FIFO, BST left is smaller and a min-heap keeps the minimum at the root.
Do not quote O(1) without its condition. Hash tables are average-case, dynamic-array append is amortized, and linked-list insertion is constant only when the position is known.
For trees, distinguish height measured in edges from the number of levels and check whether the tree is balanced.
For graph questions, identify directedness, weights and density before choosing a representation or traversal.
Draw a small structure for pointer and tree questions. A diagram often reveals the operation more reliably than mental tracing.
Compare time and space together. A faster lookup may require extra memory, while a compact representation may require more traversal.

Sources and review notes

Reviewed by AISEA Editorial Desk on 1 Sep 2026.

Array, linked-list, stack, queue, tree, heap, hash-table and graph definitions were checked for operation-specific conditions.
Worked examples were recalculated for index access, circular-queue wraparound, BST traversal, heap removal, load factor and sparse graphs.
Complexity claims are qualified by assumptions such as balance, known position, amortization, density and hash distribution.

Data StructuresPython Documentation · Checked 1 Sep 2026Supports: list, set, dictionary and collection behavior as concrete data-structure examples
Introduction to CollectionsOracle Java Tutorials · Checked 1 Sep 2026Supports: collection interfaces, implementations, reusable data structures and algorithms
Open Data StructuresPat Morin · Checked 1 Sep 2026Supports: array-based lists, linked lists, hash tables, trees and graph data structures

Ready to test your understanding?

Work through 218 questions with explanations after each answer.

Start practice

Next topic: Algorithms

Data structures MCQs with answers and explanations

218 practice questionsPage updated 24 Sept 2026Reviewed by AISEA Editorial DeskPractice questions

Practise this concept

Key formulas and rules

6 rules

Array index access is commonly $O (1)$ ; searching an unsorted array is $O (n)$ .

A linked-list insertion at a known head or node is $O (1)$ ; indexed access is $O (n)$ .

Stack push and pop are commonly $O (1)$ ; queue enqueue and dequeue are commonly $O (1)$ with a suitable front and rear representation.

A balanced binary search tree supports search, insertion and deletion in $O (lo g n)$ ; an unbalanced tree can degrade to $O (n)$ .

A hash table gives $O (1)$ average key lookup under a good hash distribution, but collisions can make the worst case $O (n)$ .

For a graph with V vertices and E edges, an adjacency-list representation uses $O (V + E)$ space.

Key concepts

Arrays and dynamic arrays

Linked lists

Stacks, queues and deques

Trees and binary search trees

Heaps and priority queues

Hash tables and collision handling

Graphs and representations

Choose by operation and invariant

Check the idea while it is fresh.Open a focused exercise without losing this article.Practise this concept

Worked examples

Example 1

You need to read the 500th item repeatedly by position, but insertions at the front are rare. Which structure is usually the better fit: an array or a singly linked list?

Solution

Example 2

A text editor must undo the most recent action first. Which data structure matches this requirement, and why?

Solution

Example 3

A circular queue has capacity 5, front at index 3 and rear at index 4. The rear slot is occupied, but indices 0 and 1 have been freed by earlier dequeues. What should enqueue do?

Solution

Example 4

Insert 40, 20, 60, 10 and 30 into a binary search tree. Where is the smallest key, and what does inorder traversal produce?

Solution

Example 5

A min-heap contains [3, 7, 9, 12, 15]. Which item is removed by extract-min, and what is the usual time complexity of the removal?

Solution

Example 6

A hash table has 10 buckets and stores 7 keys. What is its load factor, and what happens if two different keys hash to the same bucket when chaining is used?

Solution

Example 7

A sparse graph has V vertices and E edges. Which representation usually uses less space: an adjacency matrix or an adjacency list?

Solution

Representative solved questions

See the kind of question in this topic before opening the full practice set.

Question 1

What is the time complexity of building a heap from an array of n elements?

O(n)
$O (n lo g n)$
$O (n^{2})$
$O (lo g n)$

Answer: A. O(n)

Explanation

Sources and review notes

This is an AISEA-authored practice question.

Review status: accepted · Reviewed 2026-08-13 · structure and answer-key checks, editorial quality checks, duplicate screening

Question 2

In an AVL tree, what is the maximum height difference allowed between subtrees?

Answer: B. 1

Explanation

Sources and review notes

This is an AISEA-authored practice question.

Review status: accepted · Reviewed 2026-08-13 · structure and answer-key checks, editorial quality checks, duplicate screening

Question 3

What is the time complexity of inserting at the end of a dynamic array (amortized)?

O(1)
O(n)
$O (lo g n)$
$O (n^{2})$

Answer: A. O(1)

Explanation

Sources and review notes

This is an AISEA-authored practice question.

Review status: accepted · Reviewed 2026-08-13 · structure and answer-key checks, editorial quality checks, duplicate screening

Common mistakes and useful habits

Start with the required operation: indexed access, insertion, deletion, ordering, membership or priority retrieval.
Remember the invariants: stack is LIFO, queue is FIFO, BST left is smaller and a min-heap keeps the minimum at the root.
Do not quote O(1) without its condition. Hash tables are average-case, dynamic-array append is amortized, and linked-list insertion is constant only when the position is known.
For trees, distinguish height measured in edges from the number of levels and check whether the tree is balanced.
For graph questions, identify directedness, weights and density before choosing a representation or traversal.
Draw a small structure for pointer and tree questions. A diagram often reveals the operation more reliably than mental tracing.
Compare time and space together. A faster lookup may require extra memory, while a compact representation may require more traversal.

Sources and review notes

Reviewed by AISEA Editorial Desk on 1 Sep 2026.

Array, linked-list, stack, queue, tree, heap, hash-table and graph definitions were checked for operation-specific conditions.
Worked examples were recalculated for index access, circular-queue wraparound, BST traversal, heap removal, load factor and sparse graphs.
Complexity claims are qualified by assumptions such as balance, known position, amortization, density and hash distribution.

Data StructuresPython Documentation · Checked 1 Sep 2026Supports: list, set, dictionary and collection behavior as concrete data-structure examples
Introduction to CollectionsOracle Java Tutorials · Checked 1 Sep 2026Supports: collection interfaces, implementations, reusable data structures and algorithms
Open Data StructuresPat Morin · Checked 1 Sep 2026Supports: array-based lists, linked lists, hash tables, trees and graph data structures

Ready to test your understanding?

Work through 218 questions with explanations after each answer.

Start practice

Next topic: Algorithms

Data StructuresPython Documentation · Checked 1 Sep 2026Supports: list, set, dictionary and collection behavior as concrete data-structure examples

Introduction to CollectionsOracle Java Tutorials · Checked 1 Sep 2026Supports: collection interfaces, implementations, reusable data structures and algorithms

Open Data StructuresPat Morin · Checked 1 Sep 2026Supports: array-based lists, linked lists, hash tables, trees and graph data structures

Key formulas and rules

Key concepts

Arrays and dynamic arrays

Linked lists

Stacks, queues and deques

Trees and binary search trees

Heaps and priority queues

Hash tables and collision handling

Graphs and representations

Choose by operation and invariant

Worked examples

Example 1

Solution

Example 2

Solution

Example 3

Solution

Example 4

Solution

Example 5

Solution

Example 6

Solution

Example 7

Solution

Representative solved questions

Question 1

Question 2

Question 3

Common mistakes and useful habits

Sources and review notes

Ready to test your understanding?

Keep building the same skill family.

Key formulas and rules

Key concepts

Arrays and dynamic arrays

Linked lists

Stacks, queues and deques

Trees and binary search trees

Heaps and priority queues

Hash tables and collision handling

Graphs and representations

Choose by operation and invariant

Worked examples

Example 1

Solution

Example 2

Solution

Example 3

Solution

Example 4

Solution

Example 5

Solution

Example 6

Solution

Example 7

Solution

Representative solved questions

Question 1

Question 2

Question 3

Common mistakes and useful habits

Sources and review notes

Ready to test your understanding?

Keep building the same skill family.