Space complexity MCQs

By: Prof. Dr. Fazal Rehman | Last updated: September 20, 2024

What is space complexity?

a) The amount of memory an algorithm uses.
b) The amount of time an algorithm takes to complete.
c) The number of steps an algorithm performs.
d) The amount of data an algorithm processes.
Answer: a) The amount of memory an algorithm uses.
What is the space complexity of storing an array of n integers?

a) O(1)
b) O(n)
c) O(log n)
d) O(n^2)
Answer: b) O(n)
What is the space complexity of a function that uses a constant amount of extra space?

a) O(n)
b) O(log n)
c) O(1)
d) O(n^2)
Answer: c) O(1)
What is the space complexity of the recursive implementation of Fibonacci sequence without memoization?

a) O(1)
b) O(n)
c) O(n^2)
d) O(2^n)
Answer: b) O(n)
What is the space complexity of the iterative implementation of Fibonacci sequence?

a) O(1)
b) O(n)
c) O(n^2)
d) O(2^n)
Answer: a) O(1)
What is the space complexity of depth-first search (DFS) in a graph with n nodes and e edges using recursion?

a) O(n)
b) O(e)
c) O(n + e)
d) O(n^2)
Answer: a) O(n)
What is the space complexity of breadth-first search (BFS) in a graph with n nodes and e edges?

a) O(n)
b) O(e)
c) O(n + e)
d) O(n^2)
Answer: c) O(n + e)
What is the space complexity of merge sort?

a) O(n log n)
b) O(n)
c) O(log n)
d) O(n^2)
Answer: b) O(n)
What is the space complexity of quicksort in the worst case?

a) O(n log n)
b) O(n)
c) O(log n)
d) O(n^2)
Answer: b) O(n)
What is the space complexity of quicksort in the best case?

a) O(n log n)
b) O(n)
c) O(log n)
d) O(n^2)
Answer: c) O(log n)
What is the space complexity of an algorithm that uses an auxiliary array of size n/2?

a) O(n/2)
b) O(n)
c) O(log n)
d) O(n^2)
Answer: b) O(n)
What is the space complexity of an algorithm that uses a stack for recursion and the depth of the recursion is n?

a) O(1)
b) O(n)
c) O(n log n)
d) O(n^2)
Answer: b) O(n)
What is the space complexity of storing a binary tree with n nodes?

a) O(1)
b) O(log n)
c) O(n)
d) O(n^2)
Answer: c) O(n)
What is the space complexity of dynamic programming solution for the knapsack problem with n items and capacity W?

a) O(n)
b) O(W)
c) O(nW)
d) O(n + W)
Answer: c) O(nW)
What is the space complexity of an algorithm that uses an adjacency matrix to represent a graph with n nodes?

a) O(n)
b) O(n^2)
c) O(n log n)
d) O(n + e)
Answer: b) O(n^2)
What is the space complexity of an algorithm that uses an adjacency list to represent a graph with n nodes and e edges?

a) O(n)
b) O(n + e)
c) O(e)
d) O(n^2)
Answer: b) O(n + e)
What is the space complexity of a hash table with n elements?

a) O(1)
b) O(n)
c) O(log n)
d) O(n^2)
Answer: b) O(n)
What is the space complexity of a depth-first search (DFS) in a graph with n nodes and e edges using an iterative approach?

a) O(1)
b) O(n)
c) O(n + e)
d) O(n^2)
Answer: b) O(n)
What is the space complexity of the selection sort algorithm?

a) O(1)
b) O(n)
c) O(log n)
d) O(n^2)
Answer: a) O(1)
What is the space complexity of the insertion sort algorithm?

a) O(1)
b) O(n)
c) O(log n)
d) O(n^2)
Answer: a) O(1)

 

Data Structures MCQs

Basic Concepts

1. Introduction to Data Structures
   • Abstract Data Types (ADT) MCQs
2. Complexity Analysis MCQs
   • Time complexity MCQs
   • Space complexity MCQs
   • Big O, Big Ω, Big Θ notations MCQs

Linear Data Structures MCQs

1. Arrays MCQs
   • One-dimensional arrays MCQs
   • Multi-dimensional arrays MCQs
   • Operations: traversal, insertion, deletion MCQs
2. Linked Lists MCQs
   • Singly linked list MCQs
   • Doubly linked list MCQs
   • Circular linked list MCQs
3. Stacks MCQs
   • Stack operations (push, pop, peek) MCQs
   • Applications of stacks (expression evaluation, recursion) MCQs
4. Queues MCQs
   • Queue operations (enqueue, dequeue, front, rear) MCQs
   • Types: Simple queue, circular queue, priority queue, deque MCQs

Non-Linear Data Structures MCQs

1. Trees MCQs
   • Binary trees MCQs
   • Binary Search Trees (BST) MCQs
   • AVL Trees MCQs
   • B-trees and B+ trees MCQs
   • Tree traversal methods (in-order, pre-order, post-order) MCQs
2. Heaps MCQs
   • Min-heap MCQs
   • Max-heap MCQs
   • Heap operations (insertion, deletion, heapify) MCQs
   • Applications of heaps (priority queues, heap sort) MCQs
3. Graphs MCQs
   • Graph representation (adjacency matrix, adjacency list) MCQs
   • Graph traversal algorithms (DFS, BFS) MCQs
   • Shortest path algorithms (Dijkstra’s, Bellman-Ford) MCQs
   • Minimum Spanning Tree (Kruskal’s, Prim’s) MCQs

Hashing MCQs MCQs

1. Hash Tables
   • Hash functions MCQs
   • Collision resolution techniques (chaining, open addressing) MCQs
   • Applications of hashing MCQs

Sorting and Searching Algorithms MCQs 

1. Sorting Algorithms MCQs
   • Bubble sort MCQs
   • Selection sort MCQs
   • Insertion sort MCQs
   • Merge sort MCQs
   • Quick sort MCQs
   • Heap sort MCQs
2. Searching Algorithms MCQs
   • Linear search MCQs
   • Binary search MCQs
   • Interpolation search MCQs

Miscellaneous

1. Memory Management in data structures MCQs
   • Dynamic memory allocation MCQs
   • Garbage collection MCQs
2. String Manipulation Algorithms MCQs
   • Pattern matching (KMP, Rabin-Karp) MCQs
   • String hashing MCQs

1. Data Structures MCQs 1
2. Data Structures MCQs 2
3. Data Structures MCQs 3
4. Data Structures MCQs 4
5. Data Structures MCQs 5
6. Stacks Solved MCQs
7. Queues MCQs
8. pointer mcqs
9. Array MCQs