Quiz: Data Structures & Algorithms
Can you BS a Binary Tree?
Welcome to my Data Structures and Algorithms quiz!
This quiz will test your knowledge of data structures (Stacks, Lists, Trees, etc), and algorithms (), and time complexity.
20 Questions… Begin!
Which data structure is best suited for a LIFO (Last In, First Out) access pattern?
Look at the access pattern, not the name of the structure. The correct answer usually follows from what must happen first or last.
Stacks are best suited for LIFO access patterns. Queues are best suited for FIFO (First In, First Out) access patterns.
What is the time complexity of an algorithm that always takes the same amount of time to run, regardless of the input size?
Look at the access pattern, not the name of the structure. The correct answer usually follows from what must happen first or last.
O(1) represents constant time complexity. It means the algorithm always takes the same amount of time to run, regardless of the input size.
What is the time complexity for calculating the length of a singly linked list?
Look at the access pattern, not the name of the structure. The correct answer usually follows from what must happen first or last.
To calculate the length of a singly linked list, you must traverse every node from head to tail, resulting in O(n) time complexity.
What is the average time complexity for looking up an element in a balanced Binary Search Tree?
Look at the access pattern, not the name of the structure. The correct answer usually follows from what must happen first or last.
In a balanced BST, the average time complexity for lookup is O(log n) because each level allows the search space to be halved.
What is the time complexity of the Merge Sort algorithm in the worst case?
Look at the access pattern, not the name of the structure. The correct answer usually follows from what must happen first or last.
Merge Sort always operates with a worst-case complexity of O(n log n) as it repeatedly splits the array in half and merges the sorted subarrays.
What data structure is typically used to implement Breadth-First Search (BFS)?
Look at the access pattern, not the name of the structure. The correct answer usually follows from what must happen first or last.
BFS uses a Queue to explore nodes level by level, processing nodes in a breadth-first manner (by “row”).
Which algorithm is commonly used to detect cycles in a directed graph?
Look at the access pattern, not the name of the structure. The correct answer usually follows from what must happen first or last.
Depth-First Search (DFS) is typically used to detect cycles in a graph by maintaining a recursion stack to track visited nodes.
What is the time complexity of Heap Sort in the worst case?
Look at the access pattern, not the name of the structure. The correct answer usually follows from what must happen first or last.
Heap Sort maintains a worst-case time complexity of O(n log n), as it builds a heap and repeatedly extracts the maximum element.
What is the average time complexity for accessing an element in a hash table?
Look at the access pattern, not the name of the structure. The correct answer usually follows from what must happen first or last.
Hash tables have an average time complexity of O(1) for accessing elements, assuming a good hash function that minimizes collisions.
Which set contains typical operations performed on a stack?
Look at the access pattern, not the name of the structure. The correct answer usually follows from what must happen first or last.
The primary operations of a stack are Push (add element), Pop (remove element), and Peek (view the top element without removing it).
Which algorithm is commonly used to find the shortest path in a weighted graph with non-negative edges?
Look at the access pattern, not the name of the structure. The correct answer usually follows from what must happen first or last.
Dijkstra’s Algorithm is frequently used for finding the shortest path in graphs with non-negative edge weights. It employs a priority queue to determine the shortest distance efficiently.
Which set contains examples of self-balancing binary search tree data structures?
Look at the access pattern, not the name of the structure. The correct answer usually follows from what must happen first or last.
AVL Trees and Red-Black Trees are types of self-balancing trees, which ensure that the tree remains balanced after each insertion or deletion.
What must be defined in a recursive function to prevent infinite recursion?
Look at the access pattern, not the name of the structure. The correct answer usually follows from what must happen first or last.
A base case is necessary in a recursive function to stop the recursive calls when a specific condition is met, preventing infinite recursion.
What are the two primary operations for a queue?
Look at the access pattern, not the name of the structure. The correct answer usually follows from what must happen first or last.
The two primary operations in a queue are Enqueue (add an element to the back) and Dequeue (remove an element from the front).
What are the conditions for performing topological sorting on a graph?
Look at the access pattern, not the name of the structure. The correct answer usually follows from what must happen first or last.
Topological sorting can be performed on a graph if it is directed and acyclic (DAG). This type of ordering is useful in task scheduling problems.
What is the time complexity of a naive recursive implementation of the Fibonacci series?
Look at the access pattern, not the name of the structure. The correct answer usually follows from what must happen first or last.
The naive recursive implementation of the Fibonacci series has a time complexity of O(2^n) due to the extensive repeated calculations for each Fibonacci number.
Which data structure is commonly used to implement a priority queue?
Look at the access pattern, not the name of the structure. The correct answer usually follows from what must happen first or last.
A priority queue is most often implemented using a heap because it allows efficient extraction of the highest or lowest priority element.
Which set lists the common depth-first traversal orders for a binary tree?
Look at the access pattern, not the name of the structure. The correct answer usually follows from what must happen first or last.
In-order, Pre-order, and Post-order are the three common depth-first traversal orders for binary trees, each with a different order of visiting nodes. Breadth-first traversal is also common, but it is a different traversal category.
Which of the following properties are true for a min-heap?
Look at the access pattern, not the name of the structure. The correct answer usually follows from what must happen first or last.
In a min-heap, the root is always the smallest element, and the height of the tree is O(log n), making insertion and extraction efficient.
Is the Bubble Sort algorithm stable?
Look at the access pattern, not the name of the structure. The correct answer usually follows from what must happen first or last.
Bubble Sort is a stable sorting algorithm as it preserves the relative order of equal elements during sorting.