Algorithms and Data Structures Practice Exam Quiz
Which of the following is the time complexity of quicksort in the best case?
A) O(n)
B) O(n log n)
C) O(n^2)
D) O(log n)
In a binary search algorithm, what is the time complexity for searching an element in a sorted array?
A) O(n)
B) O(log n)
C) O(n^2)
D) O(1)
Which algorithm is considered the best for sorting when dealing with a small list of elements?
A) Merge Sort
B) Quick Sort
C) Insertion Sort
D) Heap Sort
Which of the following is a characteristic of the divide-and-conquer algorithmic technique?
A) Breaks the problem into smaller subproblems
B) Solves the problem using recursion
C) Combines results from subproblems
D) All of the above
In the worst case, how many comparisons does merge sort perform on an array of size n?
A) O(n log n)
B) O(n^2)
C) O(n)
D) O(log n)
Which data structure uses the principle of LIFO (Last In, First Out)?
A) Queue
B) Stack
C) Linked List
D) Tree
Which of the following is an example of a greedy algorithm?
A) Dijkstra’s Algorithm
B) Merge Sort
C) Quick Sort
D) Binary Search
In a graph, which of the following describes a depth-first search (DFS)?
A) Explores neighbors before going deeper into the graph
B) Uses a queue to explore the nodes
C) Follows one path from the start node to the end node until no further nodes are left
D) Searches through all possible paths in parallel
The time complexity of the insertion sort algorithm in the worst case is:
A) O(n log n)
B) O(n^2)
C) O(n)
D) O(log n)
Which data structure is used to implement breadth-first search (BFS)?
A) Stack
B) Queue
C) Array
D) Binary Search Tree
Which of the following is NOT a characteristic of a binary search tree (BST)?
A) Left child is less than the parent node
B) Right child is greater than the parent node
C) Every node has exactly two children
D) Each node contains at most one key
Which of the following sorting algorithms has the best average-case time complexity?
A) Quick Sort
B) Merge Sort
C) Bubble Sort
D) Heap Sort
What is the space complexity of the recursive merge sort algorithm?
A) O(1)
B) O(n)
C) O(n log n)
D) O(log n)
In a hash table, what is used to resolve collisions?
A) Linked list
B) Binary search
C) Chaining
D) Linear search
What is the time complexity of accessing an element in an array?
A) O(n)
B) O(log n)
C) O(n^2)
D) O(1)
Which of the following is an application of dynamic programming?
A) Fibonacci sequence calculation
B) Binary search
C) Merge sort
D) Depth-first search
In a directed graph, what does a cycle mean?
A) A path that begins and ends at the same node
B) A path that visits every node in the graph
C) A disconnected set of nodes
D) A path with no repeated edges
The Bellman-Ford algorithm is used to find the shortest path in:
A) Weighted graphs with non-negative edges
B) Unweighted graphs
C) Graphs with negative weight edges
D) Trees
Which of the following is NOT a valid operation for a heap data structure?
A) Insert
B) Delete
C) Find maximum/minimum
D) Swap elements randomly
Which of the following is true about a doubly linked list?
A) It only allows traversal in one direction
B) Each node has a reference to the previous and next node
C) It is faster than a singly linked list for insertion at the beginning
D) It cannot be used to implement a stack
In an algorithm, what does O(log n) time complexity typically indicate?
A) Linear growth of execution time
B) Growth of execution time at a constant rate
C) Growth of execution time with a decrease in problem size
D) Growth of execution time proportional to the logarithm of the input size
In a graph traversal, what does a breadth-first search (BFS) use to track nodes?
A) Recursion
B) Stack
C) Queue
D) Array
In the context of sorting algorithms, which one has a time complexity of O(n log n) in the average case?
A) Quick Sort
B) Bubble Sort
C) Heap Sort
D) Insertion Sort
Which algorithm is used to find the minimum spanning tree of a graph?
A) Dijkstra’s Algorithm
B) Bellman-Ford Algorithm
C) Prim’s Algorithm
D) Quick Sort
Which of the following is the correct description of a depth-first search (DFS) in a graph?
A) Uses a queue to explore nodes level by level
B) Recursively explores as deep as possible from the starting node
C) Finds the shortest path from a source node
D) Avoids revisiting the same nodes
In an AVL tree, what is the condition for balance?
A) The height difference between the left and right subtrees is at most 1
B) The left subtree has more nodes than the right subtree
C) Every node must have two children
D) All nodes must have the same value
In which case does a bubble sort algorithm become inefficient?
A) When the input array is already sorted
B) When the input array is large and unsorted
C) When all the elements in the array are equal
D) When the array contains negative values
Which algorithm is typically used to find the shortest path in a graph with weighted edges?
A) Depth-first search
B) Quick Sort
C) Dijkstra’s Algorithm
D) Merge Sort
What is the space complexity of a recursive depth-first search (DFS) on a graph?
A) O(n)
B) O(log n)
C) O(n^2)
D) O(1)
In a directed graph, which of the following algorithms can be used to detect cycles?
A) Dijkstra’s Algorithm
B) Depth-First Search (DFS)
C) Merge Sort
D) Bellman-Ford Algorithm
Which of the following algorithms is best for finding the shortest path in an unweighted graph?
A) Dijkstra’s Algorithm
B) Bellman-Ford Algorithm
C) Breadth-First Search (BFS)
D) Depth-First Search (DFS)
What is the time complexity of the binary search algorithm in the worst case?
A) O(n)
B) O(n log n)
C) O(log n)
D) O(n^2)
In which of the following scenarios would you prefer to use quicksort over merge sort?
A) When the input array is already sorted
B) When memory space is limited
C) When the input array is very large
D) When sorting linked lists
Which of the following best describes a “min-heap”?
A) A heap where the parent node is greater than both of its children
B) A heap where the parent node is smaller than both of its children
C) A binary tree with two children per node
D) A tree structure that supports binary search operations
Which of the following statements is true for a linked list?
A) It requires a contiguous block of memory
B) It allows for fast insertions and deletions at the end
C) It is slower than an array when accessing elements by index
D) It allows for random access to elements
Which of the following is true for a breadth-first search (BFS)?
A) It uses a stack to explore the graph
B) It explores the graph level by level
C) It requires a recursive approach
D) It always finds the longest path
What is the worst-case time complexity for heap sort?
A) O(n)
B) O(n log n)
C) O(n^2)
D) O(log n)
Which of the following data structures is ideal for implementing a breadth-first search?
A) Stack
B) Queue
C) Binary Search Tree
D) Hash Table
Which algorithm is used to find the strongly connected components of a directed graph?
A) Quick Sort
B) Dijkstra’s Algorithm
C) Kosaraju’s Algorithm
D) Merge Sort
What is the time complexity of finding the maximum element in a heap?
A) O(1)
B) O(n)
C) O(log n)
D) O(n log n)
What does a red-black tree guarantee about the nodes?
A) Every node has two children
B) The tree is always balanced
C) Every path from the root to the leaves has the same number of black nodes
D) The height of the tree is always logarithmic in the number of nodes
What is the best case time complexity for insertion sort?
A) O(n log n)
B) O(n^2)
C) O(n)
D) O(log n)
Which of the following algorithms works by recursively dividing the problem into smaller subproblems?
A) Merge Sort
B) Quick Sort
C) Binary Search
D) All of the above
Which of the following is an example of an algorithm with a time complexity of O(n^2)?
A) Merge Sort
B) Quick Sort
C) Insertion Sort
D) Binary Search
In which situation would a breadth-first search (BFS) be preferred over depth-first search (DFS)?
A) When searching for the shortest path in an unweighted graph
B) When the graph is sparse
C) When you want to explore as deep as possible first
D) When working with a graph that contains cycles
Which of the following sorting algorithms is stable?
A) Quick Sort
B) Heap Sort
C) Merge Sort
D) Selection Sort
Which of the following is a disadvantage of a hash table?
A) Slow lookups
B) Difficulty handling collisions
C) Limited to small datasets
D) It requires a large amount of memory
Which of the following graphs is a tree?
A) A graph with no cycles
B) A graph where every node has exactly two children
C) A graph where there is exactly one path between any two nodes
D) A graph with no edges
What is the time complexity of searching for an element in a balanced binary search tree (BST)?
A) O(n)
B) O(log n)
C) O(n log n)
D) O(n^2)
Which of the following is the best approach for finding the shortest path in a graph with both positive and negative edge weights?
A) Dijkstra’s Algorithm
B) Bellman-Ford Algorithm
C) Depth-First Search
D) Floyd-Warshall Algorithm
Which of the following is a key characteristic of a heap data structure?
A) It is always a complete binary tree
B) It is always a balanced binary search tree
C) It stores elements in ascending order
D) It can only be implemented using arrays
Which algorithm is known for finding the longest common subsequence of two strings?
A) Knapsack Problem Algorithm
B) Dynamic Programming Algorithm
C) Longest Path Algorithm
D) Floyd-Warshall Algorithm
Which of the following is true for merge sort?
A) It is a comparison-based sorting algorithm
B) It is an in-place sorting algorithm
C) It has a time complexity of O(n^2)
D) It does not require additional memory for sorting
What is the primary advantage of using a balanced binary search tree (BST) over an unsorted array?
A) Faster insertions and deletions
B) More efficient sorting of elements
C) Faster lookups, insertions, and deletions in logarithmic time
D) Ability to store duplicate elements efficiently
Which algorithm is best for finding the minimum spanning tree in a graph?
A) Dijkstra’s Algorithm
B) Prim’s Algorithm
C) Quick Sort
D) Merge Sort
Which of the following is NOT a graph traversal method?
A) Depth-First Search (DFS)
B) Breadth-First Search (BFS)
C) Merge Sort
D) In-order traversal
Which of the following statements is true for quicksort?
A) It always runs in O(n^2) time
B) It is slower than merge sort on average
C) It has an average-case time complexity of O(n log n)
D) It is not a comparison-based sorting algorithm
What is the worst-case time complexity of a depth-first search (DFS) on a graph with V vertices and E edges?
A) O(V + E)
B) O(V^2)
C) O(V log E)
D) O(E)
Which of the following is a characteristic of a graph that contains no cycles?
A) It is a tree
B) It is a directed graph
C) It is an undirected graph
D) It contains no edges
Which of the following is a disadvantage of using an array-based implementation for a stack?
A) It allows fast push and pop operations
B) It has a fixed size
C) It requires a large amount of memory
D) It has no restrictions on the types of data it can hold
Which of the following algorithms is most efficient for finding the kth largest element in an unsorted array?
A) Merge Sort
B) Quick Select
C) Bubble Sort
D) Heap Sort
Which of the following is true about depth-first search (DFS) in a graph?
A) DFS is faster than BFS in all cases
B) DFS uses a queue for traversal
C) DFS is guaranteed to find the shortest path
D) DFS is implemented using a stack
Which of the following data structures is most commonly used to implement the Dijkstra algorithm for finding the shortest path?
A) Array
B) Stack
C) Queue
D) Priority Queue
In which case is a binary search tree (BST) considered unbalanced?
A) When the left and right subtrees have equal heights
B) When the left subtree is deeper than the right subtree
C) When the difference between the heights of the left and right subtrees is greater than 1
D) When the tree has only one element
Which of the following sorting algorithms is best when the input data is nearly sorted?
A) Quick Sort
B) Merge Sort
C) Heap Sort
D) Insertion Sort
What is the space complexity of a recursive implementation of the quicksort algorithm?
A) O(1)
B) O(n)
C) O(log n)
D) O(n log n)
Which of the following is true about hash tables?
A) Hash tables guarantee constant time complexity for lookup, insertion, and deletion
B) Hash tables store elements in a specific order
C) Hash tables handle collisions using linear probing, chaining, or double hashing
D) Hash tables are always implemented using linked lists
Which of the following algorithms can be used to find the strongly connected components in a directed graph?
A) Prim’s Algorithm
B) Bellman-Ford Algorithm
C) Kosaraju’s Algorithm
D) Dijkstra’s Algorithm
Which of the following is true about a red-black tree?
A) It is a self-balancing binary search tree
B) It is a heap-based binary tree
C) It stores elements in a fixed order
D) It allows for faster lookups than an AVL tree
What is the time complexity of an efficient merge sort?
A) O(n^2)
B) O(n log n)
C) O(log n)
D) O(n)
Which of the following is an advantage of a hash map over an array?
A) It allows for fast lookups based on key values
B) It stores elements in a sorted order
C) It supports fast index-based access to elements
D) It requires less memory than an array
Which of the following is NOT a characteristic of a heap?
A) It is a complete binary tree
B) It supports priority-based element removal
C) It is not necessarily a balanced binary search tree
D) It always supports efficient search operations
Which of the following statements is true about an AVL tree?
A) It is an unbalanced binary search tree
B) It uses a stack to perform in-order traversal
C) It automatically rebalances itself to maintain its height balance property
D) It allows for constant time complexity for search, insert, and delete operations
What is the best-case time complexity of the bubble sort algorithm?
A) O(n log n)
B) O(n^2)
C) O(n)
D) O(log n)
In which of the following scenarios would you use a depth-first search (DFS) rather than a breadth-first search (BFS)?
A) When finding the shortest path in an unweighted graph
B) When traversing a tree in a top-down manner
C) When traversing a graph with few edges
D) When solving problems like topological sorting or detecting cycles
What is the time complexity of accessing an element in an array using its index?
A) O(n)
B) O(n log n)
C) O(log n)
D) O(1)
Which of the following is the most appropriate data structure for implementing a priority queue?
A) Stack
B) Queue
C) Binary Heap
D) Linked List
Which of the following is true about the Floyd-Warshall algorithm?
A) It is used for finding the shortest path in a graph with negative edge weights
B) It works by repeatedly applying the greedy method
C) It finds the minimum spanning tree in a graph
D) It is used only for directed graphs with positive weights
What is the space complexity of an adjacency matrix representation of a graph?
A) O(V + E)
B) O(V^2)
C) O(E)
D) O(log V)
In which situation would you use a trie data structure?
A) Storing an ordered collection of elements
B) Performing quick lookups for prefixes in a string
C) Storing key-value pairs where the keys are integers
D) Storing a sequence of elements that require frequent sorting
What is the worst-case time complexity for the bubble sort algorithm?
A) O(n log n)
B) O(n)
C) O(n^2)
D) O(log n)
Which of the following statements is true about a directed acyclic graph (DAG)?
A) It contains no edges
B) It has no cycles
C) It is a tree
D) It has only one vertex
Which of the following data structures is used to implement recursive function calls in most programming languages?
A) Array
B) Stack
C) Queue
D) Linked List
Which of the following is true for a topological sort of a directed graph?
A) It can be applied only to cyclic graphs
B) It orders the vertices in a linear sequence where each vertex comes before all of its outgoing edges
C) It is only applicable to undirected graphs
D) It can be done only if the graph is fully connected
Which of the following is an example of a greedy algorithm?
A) Merge Sort
B) Prim’s Algorithm for Minimum Spanning Tree
C) Depth-First Search
D) Dijkstra’s Algorithm for Shortest Path
What is the time complexity for performing a lookup in a hash table, assuming a good hash function?
A) O(n)
B) O(log n)
C) O(1)
D) O(n^2)
Which of the following is true about merge sort?
A) It is an in-place sorting algorithm
B) It uses divide-and-conquer to recursively divide the problem and merge the results
C) It has a worst-case time complexity of O(n^2)
D) It is not a comparison-based sorting algorithm
What is the space complexity of the quicksort algorithm?
A) O(1)
B) O(n)
C) O(log n)
D) O(n log n)
Which of the following algorithms is commonly used to detect cycles in an undirected graph?
A) Floyd-Warshall
B) Depth-First Search (DFS)
C) Dijkstra’s Algorithm
D) Breadth-First Search (BFS)
Which data structure is most efficient for implementing a graph that requires fast lookups of edges between vertices?
A) Adjacency List
B) Adjacency Matrix
C) Stack
D) Queue
Which of the following sorting algorithms has the best average-case time complexity?
A) Quick Sort
B) Merge Sort
C) Heap Sort
D) Bubble Sort
What is the time complexity of the binary search algorithm?
A) O(n)
B) O(n log n)
C) O(log n)
D) O(n^2)
In a hash table, what is the worst-case time complexity for an insert operation?
A) O(1)
B) O(log n)
C) O(n)
D) O(n^2)
Which of the following algorithms is used for finding the shortest path in a weighted graph with negative edge weights?
A) Bellman-Ford Algorithm
B) Dijkstra’s Algorithm
C) Floyd-Warshall Algorithm
D) A* Search Algorithm
What is the time complexity of inserting an element in a balanced binary search tree?
A) O(log n)
B) O(n)
C) O(n log n)
D) O(1)
Which of the following is an example of a divide-and-conquer algorithm?
A) Merge Sort
B) Bubble Sort
C) Quick Sort
D) Both A and C
Which of the following is true about a binary heap?
A) It can be used to implement a priority queue
B) It is a binary search tree
C) It guarantees the order of elements
D) It supports efficient insertions but inefficient deletions
Which of the following is true about the depth-first search (DFS) traversal of a tree?
A) DFS visits all nodes at the current depth level before moving to the next level
B) DFS explores each node recursively, going as deep as possible before backtracking
C) DFS requires the use of a queue to store nodes
D) DFS guarantees visiting nodes in the shortest path first
Which of the following is the correct time complexity of the insertion sort algorithm in the worst case?
A) O(n log n)
B) O(n^2)
C) O(n)
D) O(log n)
What is the primary disadvantage of a linked list compared to an array?
A) Linked lists require more memory due to storing pointers
B) Linked lists have slower search times
C) Linked lists cannot store data efficiently
D) Linked lists are not dynamic in size
What is the worst-case time complexity of the bubble sort algorithm?
A) O(n)
B) O(n^2)
C) O(log n)
D) O(n log n)
Which of the following operations has the best average time complexity for a hash table with a good hash function?
A) Search
B) Insert
C) Delete
D) All of the above
Which of the following is an advantage of using a stack data structure?
A) It allows for fast insertion and deletion at both ends
B) It supports last-in-first-out (LIFO) access to elements
C) It allows for direct access to any element
D) It requires less memory than other data structures
What is the space complexity of an adjacency list representation of a graph with V vertices and E edges?
A) O(V + E)
B) O(V^2)
C) O(E)
D) O(V)
Which of the following is true about a greedy algorithm?
A) It always guarantees the globally optimal solution
B) It makes decisions based on local optimization in each step
C) It works by dividing the problem into smaller subproblems
D) It is a type of dynamic programming algorithm
What is the time complexity of accessing an element in a linked list by its index?
A) O(1)
B) O(n)
C) O(log n)
D) O(n log n)
Which of the following is the most suitable data structure for implementing a breadth-first search (BFS) algorithm?
A) Stack
B) Queue
C) Linked List
D) Binary Tree
Which of the following sorting algorithms is based on partitioning?
A) Merge Sort
B) Quick Sort
C) Heap Sort
D) Insertion Sort
What is the time complexity of performing a pre-order traversal of a binary tree?
A) O(n log n)
B) O(n)
C) O(log n)
D) O(n^2)
Which of the following is NOT a characteristic of a graph represented by an adjacency matrix?
A) It uses O(V^2) space, where V is the number of vertices
B) It allows fast edge lookup
C) It is efficient for sparse graphs
D) It allows easy edge deletion
Which of the following is the best approach to avoid collisions in a hash table?
A) Use a perfect hash function
B) Use a small table size
C) Use linear probing
D) Use double hashing or chaining
In a directed graph, what does a strongly connected component (SCC) represent?
A) A set of vertices with no outgoing edges
B) A set of vertices with no incoming edges
C) A set of vertices such that there is a directed path between any two vertices in the set
D) A set of vertices that are isolated from each other
What is the time complexity of performing a breadth-first search (BFS) on a graph with V vertices and E edges?
A) O(V + E)
B) O(V^2)
C) O(V log E)
D) O(E log V)
Which of the following is an appropriate scenario for using a trie data structure?
A) Searching for the longest substring of a given string
B) Searching for keys in a dictionary where keys are strings
C) Sorting a large set of numerical data
D) Finding the kth smallest element in an array
What is the worst-case time complexity of accessing an element in a binary search tree (BST)?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
Which of the following statements is true about quicksort?
A) Quicksort is a comparison-based sorting algorithm
B) Quicksort has a worst-case time complexity of O(n^2)
C) Quicksort is always faster than merge sort
D) Quicksort uses dynamic programming to divide the problem into subproblems
Which of the following is true about merge sort?
A) It is an in-place sorting algorithm
B) It guarantees O(n log n) time complexity in all cases
C) It is not a stable sorting algorithm
D) It is faster than quicksort in all cases
In which of the following situations is a queue the best data structure to use?
A) For implementing recursive algorithms
B) For handling tasks in a real-time operating system
C) For maintaining a stack of function calls
D) For implementing depth-first search
Which of the following is a valid operation for a heap data structure?
A) Insert a new element in O(n) time
B) Find the maximum element in O(log n) time
C) Remove the minimum element in O(log n) time
D) Perform an in-order traversal in O(log n) time
What is the best sorting algorithm when the input data is partially sorted?
A) Quick Sort
B) Merge Sort
C) Insertion Sort
D) Heap Sort
What is the primary disadvantage of using a linked list over an array?
A) Linked lists have slower search times
B) Linked lists cannot store data efficiently
C) Linked lists require more memory due to storing pointers
D) Linked lists are not dynamic in size
In the quicksort algorithm, the “pivot” is used to:
A) Divide the array into two parts for recursive sorting
B) Track the position of the smallest element
C) Determine the middle element in the array
D) Find the maximum element for partitioning
What is the time complexity of merging two sorted arrays of size n and m in merge sort?
A) O(n log n)
B) O(n + m)
C) O(log n)
D) O(n^2)
In a binary heap, the root node:
A) Contains the smallest element
B) Contains the largest element
C) Can be any random element
D) Does not have any special property
Which of the following sorting algorithms is best for sorting a linked list?
A) Merge Sort
B) Bubble Sort
C) Quick Sort
D) Selection Sort
Which algorithm is commonly used for finding the shortest path in an unweighted graph?
A) Dijkstra’s Algorithm
B) Bellman-Ford Algorithm
C) Floyd-Warshall Algorithm
D) Breadth-First Search (BFS)
What does the term “time complexity” refer to?
A) The amount of space required by an algorithm
B) The amount of time an algorithm takes to complete as a function of the size of the input
C) The number of operations an algorithm performs
D) The memory usage of an algorithm
Which data structure is most suitable for implementing recursion?
A) Stack
B) Queue
C) Array
D) Linked List
What is the space complexity of a depth-first search (DFS) algorithm implemented using a recursive approach?
A) O(1)
B) O(log n)
C) O(n)
D) O(n^2)
What is the primary advantage of using the merge sort algorithm over other sorting algorithms?
A) It is faster for small data sets
B) It does not require additional memory
C) It guarantees O(n log n) time complexity in all cases
D) It is an in-place sorting algorithm
What is the worst-case time complexity of the insertion sort algorithm?
A) O(n)
B) O(log n)
C) O(n^2)
D) O(n log n)
Which of the following is NOT a type of graph traversal?
A) Depth-First Search
B) Breadth-First Search
C) Top-Down Search
D) In-order Traversal
In an AVL tree, the balance factor of a node is the difference between:
A) The number of left and right children
B) The number of left and right subtrees’ heights
C) The total number of elements in the left and right subtrees
D) The sum of the heights of the left and right subtrees
Which of the following is true about dynamic programming?
A) It is used to solve problems by solving subproblems independently
B) It requires the use of recursion
C) It is most effective when problems have overlapping subproblems and optimal substructure
D) It cannot be used for optimization problems
Which of the following is NOT a valid tree traversal method?
A) Pre-order Traversal
B) Post-order Traversal
C) In-order Traversal
D) Linear Traversal
In which case would a graph be considered a “cyclic graph”?
A) It contains no vertices
B) It contains at least one loop or cycle
C) It contains all connected components
D) It has an equal number of vertices and edges
What does the term “greedy algorithm” refer to?
A) A solution approach that looks for a global optimal solution
B) A solution approach that looks for the best solution by taking the best choice at each step
C) A solution approach that uses recursion and divides the problem
D) A solution approach that minimizes memory usage
What is the worst-case time complexity of the quicksort algorithm?
A) O(n)
B) O(n log n)
C) O(log n)
D) O(n^2)
Which of the following is a characteristic of a min-heap?
A) The parent node is smaller than both of its children
B) The parent node is greater than both of its children
C) The tree is always balanced
D) The root node contains the maximum value
In a priority queue, which operation is typically the most efficient?
A) Insert
B) Delete-min
C) Decrease key
D) Find-min
Which of the following is the best case time complexity for a quicksort algorithm?
A) O(n log n)
B) O(n^2)
C) O(n)
D) O(log n)
What is the primary use of a trie data structure?
A) To store string data in a way that allows fast searching
B) To store elements in a sorted order
C) To optimize search times in a binary search tree
D) To implement a priority queue efficiently
Which of the following graph traversal methods is most suitable for finding the shortest path in an unweighted graph?
A) Depth-First Search
B) Breadth-First Search
C) Dijkstra’s Algorithm
D) Bellman-Ford Algorithm
In which of the following cases does a hash table suffer from collisions?
A) When two different keys hash to the same index
B) When keys are inserted in sorted order
C) When a table size is too large
D) When a key is removed from the table
Which of the following is the space complexity of the breadth-first search (BFS) algorithm?
A) O(1)
B) O(V)
C) O(E)
D) O(V + E)
Which of the following algorithms is used to solve the “knapsack problem”?
A) Dynamic Programming
B) Depth-First Search
C) Greedy Algorithm
D) Dijkstra’s Algorithm
Which of the following is true about a binary search tree (BST)?
A) It allows for efficient search, insert, and delete operations
B) It is always balanced, so operations have O(log n) complexity
C) It stores elements in a linked list-like structure
D) It guarantees that the smallest element is always at the root
Which of the following is a drawback of the bubble sort algorithm?
A) It is difficult to implement
B) It has a high space complexity
C) It is inefficient for large data sets due to its O(n^2) time complexity
D) It cannot sort strings
Which of the following sorting algorithms is the best for small data sets?
A) Merge Sort
B) Quick Sort
C) Bubble Sort
D) Heap Sort
Which of the following is NOT a type of graph?
A) Directed Graph
B) Undirected Graph
C) Binary Tree
D) Complete Graph
What is the best case time complexity of bubble sort?
A) O(n log n)
B) O(n)
C) O(n^2)
D) O(log n)
Which of the following is NOT a characteristic of a hash table?
A) It stores key-value pairs
B) It provides constant time complexity for search operations
C) It requires elements to be ordered
D) It handles collisions using techniques like chaining or open addressing
In which type of graph traversal is the “visited” set updated as nodes are explored?
A) Depth-First Search (DFS)
B) Breadth-First Search (BFS)
C) Both DFS and BFS
D) None of the above
Which of the following best describes a greedy algorithm?
A) It solves subproblems recursively
B) It makes decisions based on a global view of the problem
C) It makes locally optimal choices at each step
D) It divides the problem into smaller subproblems and combines them
Which of the following is the main reason to use a binary search tree (BST) over an unordered array?
A) Faster access times
B) Ability to maintain sorted data
C) Simpler implementation
D) Faster insertion times
What is the space complexity of an iterative depth-first search (DFS)?
A) O(1)
B) O(log n)
C) O(n)
D) O(n^2)
In which of the following situations is a linked list more efficient than an array?
A) Accessing elements by index
B) Inserting elements at the end of the list
C) Removing elements from the middle
D) Searching for an element
Which of the following sorting algorithms is NOT a comparison-based sort?
A) Merge Sort
B) Quick Sort
C) Heap Sort
D) Counting Sort
Which of the following is a key difference between a queue and a stack?
A) A queue is FIFO, and a stack is LIFO
B) A queue allows access to the top element, while a stack allows access to the bottom element
C) A queue is used for recursion, while a stack is used for iteration
D) A queue can only store unique elements, while a stack can store duplicates
In a graph, what is the difference between a directed edge and an undirected edge?
A) A directed edge has a direction, while an undirected edge does not
B) A directed edge can be part of a cycle, but an undirected edge cannot
C) A directed edge connects nodes in two directions, while an undirected edge connects nodes in one direction
D) There is no difference between the two
Which algorithm is used to detect cycles in a directed graph?
A) Dijkstra’s Algorithm
B) Depth-First Search (DFS)
C) Floyd-Warshall Algorithm
D) Prim’s Algorithm
In a min-heap, what is the relationship between the value of the parent and its children?
A) The parent value is smaller than or equal to its children’s values
B) The parent value is greater than or equal to its children’s values
C) The parent value is always equal to the children’s values
D) There is no specific relationship
In dynamic programming, which of the following is used to store solutions to subproblems?
A) Recursion
B) Backtracking
C) Memoization or Tabulation
D) Divide and Conquer
What is the time complexity of finding the minimum value in a min-heap?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
What is the space complexity of the merge sort algorithm?
A) O(1)
B) O(n)
C) O(log n)
D) O(n log n)
Which of the following is an advantage of using a trie data structure for storing strings?
A) It minimizes the space required to store strings
B) It supports fast lookups for prefix matching
C) It allows for sorting strings in lexicographical order
D) It reduces the time complexity of insertion
Which of the following is true for a breadth-first search (BFS) algorithm when applied to a graph?
A) It explores nodes based on their distance from the source node
B) It explores nodes from deepest to shallowest
C) It only works on directed graphs
D) It uses a stack for node storage
In a directed acyclic graph (DAG), what can be said about its cycles?
A) A DAG contains exactly one cycle
B) A DAG contains no cycles
C) A DAG contains multiple cycles
D) A DAG can contain both cycles and acyclic components
In which situation would you use a breadth-first search (BFS) algorithm over a depth-first search (DFS) algorithm?
A) When you need to find the shortest path in an unweighted graph
B) When you want to explore as deeply as possible before backtracking
C) When the graph is too large to store in memory
D) When the graph has very few vertices
Which of the following describes the process of “divide and conquer”?
A) Solving a problem by breaking it down into smaller subproblems, solving each recursively, and combining the results
B) Solving a problem by breaking it down into smaller subproblems and solving them independently
C) Solving a problem by iterating through all possible solutions
D) Solving a problem by eliminating one solution at a time
What is the average-case time complexity of quicksort?
A) O(n log n)
B) O(n^2)
C) O(n)
D) O(log n)
Which data structure is best used for implementing an undo/redo functionality in an application?
A) Queue
B) Stack
C) Linked List
D) Array
Which of the following is an example of an NP-complete problem?
A) Sorting a list of integers
B) Solving the traveling salesman problem
C) Searching for an element in a sorted array
D) Finding the shortest path in a graph with positive weights
Which of the following algorithms is used for finding the shortest path between all pairs of nodes in a weighted graph?
A) Dijkstra’s Algorithm
B) Bellman-Ford Algorithm
C) Floyd-Warshall Algorithm
D) Prim’s Algorithm
What is the worst-case time complexity of the insertion sort algorithm?
A) O(n log n)
B) O(n^2)
C) O(n)
D) O(log n)
In a balanced binary search tree (BST), what is the time complexity for searching for an element?
A) O(n)
B) O(log n)
C) O(n^2)
D) O(n log n)
What type of graph representation uses an adjacency matrix?
A) A graph with a dense set of edges
B) A graph with a sparse set of edges
C) A graph where the vertices are connected in a sequential pattern
D) A graph with weighted edges only
What is the time complexity of checking if a binary search tree is balanced?
A) O(1)
B) O(n)
C) O(log n)
D) O(n log n)
Which of the following is a drawback of using a queue for breadth-first search (BFS)?
A) It uses too much memory
B) It does not handle weighted edges
C) It requires sorting elements
D) It can cause inefficient memory access due to non-contiguous storage
In a Fibonacci sequence, what is the recursive relation between two consecutive terms?
A) F(n) = F(n-1) + F(n-2)
B) F(n) = F(n-2) – F(n-1)
C) F(n) = F(n-1) * F(n-2)
D) F(n) = F(n-1) / F(n-2)
Which of the following is true for a binary search tree (BST)?
A) The left child’s value is always greater than the parent’s value
B) The right child’s value is always smaller than the parent’s value
C) Inorder traversal of a BST produces a sorted sequence
D) A BST must be balanced to function properly
What is the time complexity of deleting a node from a doubly linked list?
A) O(1)
B) O(n)
C) O(log n)
D) O(n log n)
Which of the following algorithms is used to find the shortest path in a graph with negative weights?
A) Dijkstra’s Algorithm
B) Bellman-Ford Algorithm
C) Floyd-Warshall Algorithm
D) Kruskal’s Algorithm
What is the time complexity of merging two sorted lists using merge sort?
A) O(n)
B) O(n log n)
C) O(log n)
D) O(n^2)
In which of the following cases would you use depth-first search (DFS) over breadth-first search (BFS)?
A) When you want to find the shortest path in an unweighted graph
B) When you need to explore as deeply as possible in a graph before backtracking
C) When you are processing nodes level by level
D) When you need to detect cycles in a graph
Which of the following best describes a binary heap?
A) A binary heap is always balanced
B) It is a complete binary tree where the parent is always greater (or smaller) than its children
C) A binary heap is implemented using a linked list
D) It is a graph where each node can have more than two children
What is the time complexity of finding the maximum value in a max-heap?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
Which of the following sorting algorithms is considered to be an unstable sorting algorithm?
A) Merge Sort
B) Quick Sort
C) Bubble Sort
D) Insertion Sort
What is the space complexity of the quicksort algorithm?
A) O(n)
B) O(log n)
C) O(1)
D) O(n log n)
Which of the following is an advantage of using a priority queue over a regular queue?
A) It allows insertion of elements in constant time
B) It stores elements in a sorted order
C) It allows for efficient access to the highest or lowest priority element
D) It requires more memory than a regular queue
Which algorithm is used to find the minimum spanning tree of a graph?
A) Dijkstra’s Algorithm
B) Prim’s Algorithm
C) Bellman-Ford Algorithm
D) Kruskal’s Algorithm
In a depth-first search (DFS) algorithm, what data structure is typically used to store nodes to be explored?
A) Queue
B) Stack
C) Hash Table
D) Array
Which of the following is a characteristic of the quicksort algorithm?
A) It has a worst-case time complexity of O(n log n)
B) It always performs well on large datasets
C) It is based on divide and conquer
D) It is not a comparison-based sort
What is the purpose of the “visited” set in graph traversal algorithms?
A) To store the graph’s edge weights
B) To keep track of the nodes that have already been visited
C) To store the shortest path between nodes
D) To sort the nodes before traversal
In a hash table, which operation is responsible for handling collisions?
A) Load balancing
B) Hashing
C) Chaining or open addressing
D) Rehashing
Which of the following is the main advantage of using a linked list over an array?
A) Faster access times
B) Easy to resize dynamically
C) Better cache locality
D) Easier to implement than an array
What is the time complexity of finding the predecessor of a node in a balanced binary search tree?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
Which of the following graph traversal algorithms uses a queue for storing nodes to be explored?
A) Depth-First Search (DFS)
B) Breadth-First Search (BFS)
C) Dijkstra’s Algorithm
D) Kruskal’s Algorithm
In which of the following situations would you use dynamic programming instead of a greedy algorithm?
A) When the problem has overlapping subproblems and optimal substructure
B) When the problem has a simple greedy choice property
C) When the problem has no subproblems
D) When the problem can be solved with a divide and conquer approach
What is the time complexity of deleting a node from a singly linked list, given the reference to the node?
A) O(1)
B) O(n)
C) O(log n)
D) O(n^2)
Which of the following best describes the “divide and conquer” strategy?
A) It solves subproblems independently and combines the results
B) It breaks a problem into subproblems that are solved recursively
C) It splits a problem into smaller parts and solves them sequentially
D) It reduces the problem size by eliminating one possibility at a time
What is the time complexity of accessing an element in an array by its index?
A) O(1)
B) O(n)
C) O(log n)
D) O(n log n)
Which of the following operations is NOT performed on a binary search tree?
A) Insertion
B) Deletion
C) Rotation
D) Merging
What is the main purpose of the Floyd-Warshall algorithm?
A) To find the shortest path from a single source to all other nodes
B) To find the shortest path between every pair of nodes in a graph
C) To find the minimum spanning tree of a graph
D) To detect negative cycles in a graph
Which of the following sorting algorithms has the best worst-case time complexity?
A) Quick Sort
B) Bubble Sort
C) Merge Sort
D) Selection Sort
What is the space complexity of the depth-first search (DFS) algorithm?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
Which of the following operations is most efficient in a hash table with chaining?
A) Search
B) Insert
C) Delete
D) All operations have the same efficiency
In a graph, what is the difference between a directed edge and an undirected edge?
A) A directed edge has a direction, while an undirected edge does not
B) A directed edge can be part of a cycle, while an undirected edge cannot
C) A directed edge can only connect two vertices, while an undirected edge connects more than two
D) A directed edge does not affect graph traversal, while an undirected edge does
What is the time complexity of insertion in a red-black tree?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
What is the space complexity of the merge sort algorithm?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
What is the time complexity of searching for an element in a hash table with a good hash function?
A) O(1)
B) O(n)
C) O(log n)
D) O(n log n)
What is the primary purpose of a depth-first search (DFS) traversal?
A) To visit all vertices level by level
B) To explore as deeply as possible before backtracking
C) To find the shortest path between two nodes
D) To identify the minimum spanning tree of the graph
Which of the following operations does not alter the time complexity of a binary search tree (BST)?
A) Searching for an element
B) Inserting an element
C) Deleting an element
D) Rebalancing the tree
Which of the following is NOT a stable sorting algorithm?
A) Merge Sort
B) Insertion Sort
C) Quick Sort
D) Bubble Sort
In which of the following cases is the binary search algorithm used?
A) To search for an element in an unsorted list
B) To search for an element in a sorted array
C) To search for an element in a linked list
D) To search for an element in a tree
Which of the following best describes a linked list?
A) It is a type of binary tree
B) It is a linear data structure where each element points to the next
C) It stores elements in contiguous memory locations
D) It is a non-linear data structure
Which of the following algorithms is commonly used for solving problems on trees, such as finding the height of a tree?
A) Dynamic Programming
B) Depth-First Search (DFS)
C) Merge Sort
D) Dijkstra’s Algorithm
In which of the following scenarios is a red-black tree used over a binary search tree (BST)?
A) When all operations should be done in constant time
B) When there is a need for self-balancing
C) When the tree should not be allowed to grow beyond a certain height
D) When no balancing is required for efficient searching
Which of the following is a property of a priority queue?
A) The element with the lowest priority is dequeued first
B) The elements are dequeued in a sorted order
C) The element with the highest priority is dequeued first
D) It allows direct access to elements at any position
What is the best case time complexity for quicksort?
A) O(n^2)
B) O(n log n)
C) O(log n)
D) O(n)
Which of the following is a key feature of dynamic programming?
A) It divides the problem into equal-sized subproblems
B) It solves problems in a top-down manner
C) It stores solutions to subproblems to avoid redundant calculations
D) It requires recursion to solve the problem
Which of the following is true about a heap data structure?
A) A binary heap can be used to implement a priority queue
B) A binary heap is always balanced
C) A binary heap is a type of graph
D) A binary heap requires linear time to remove the root element
What is the space complexity of an algorithm that uses an array to store data and performs operations on the data?
A) O(1)
B) O(n)
C) O(log n)
D) O(n^2)
Which of the following is NOT true about a doubly linked list?
A) It allows traversal in both directions
B) Each node has a reference to the next node and the previous node
C) It allows random access to elements
D) It requires more memory than a singly linked list
Which of the following is a disadvantage of using a hash table?
A) It requires a large amount of memory
B) It does not support insertion of new elements
C) It may suffer from collisions, which need to be handled
D) It is slow for searching elements
What is the primary function of the merge step in merge sort?
A) To divide the array into two halves
B) To compare elements and build a sorted array
C) To swap elements to sort them
D) To partition the array into smaller subarrays
In which of the following situations is a breadth-first search (BFS) algorithm useful?
A) When searching for the shortest path in an unweighted graph
B) When you need to explore a tree or graph as deeply as possible
C) When you need to find the largest value in a tree
D) When performing a post-order traversal
Which of the following is true about a complete binary tree?
A) Every level of the tree is fully populated except possibly the last one
B) All leaf nodes are at the same level
C) Every non-leaf node has at least two children
D) It is always balanced
In a hash table, what happens when a collision occurs?
A) The table is resized
B) The new element is simply ignored
C) A new hash function is generated
D) The element is inserted at the next available position, using a collision resolution strategy
What is the time complexity of accessing an element by index in an array?
A) O(1)
B) O(n)
C) O(log n)
D) O(n log n)
Which of the following sorting algorithms is an example of an in-place sort?
A) Merge Sort
B) Quick Sort
C) Bubble Sort
D) Selection Sort
What is the time complexity of finding the maximum value in a binary heap?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
Which of the following is NOT a feature of a binary search tree (BST)?
A) Left child’s value is smaller than the parent’s value
B) Right child’s value is greater than the parent’s value
C) Inorder traversal of a BST yields a sorted sequence
D) A BST must be balanced
Which of the following is the best sorting algorithm to use when the data is already nearly sorted?
A) Merge Sort
B) Insertion Sort
C) Quick Sort
D) Heap Sort
Which of the following is a feature of a doubly linked list?
A) Each node contains a reference to both the next and the previous node
B) Nodes can only be traversed in one direction
C) Each node contains a reference to only the previous node
D) It uses a contiguous block of memory
What is the time complexity of searching for an element in an unsorted array?
A) O(1)
B) O(log n)
C) O(n)
D) O(n^2)
Which of the following is true about the Floyd-Warshall algorithm?
A) It finds the shortest path between a single source and all other vertices
B) It finds the shortest path between every pair of nodes in a weighted graph
C) It only works for unweighted graphs
D) It uses a greedy approach to find the shortest path
Which of the following describes a greedy algorithm?
A) It solves a problem by considering all possible solutions
B) It breaks the problem into subproblems and solves each independently
C) It makes a locally optimal choice at each step, aiming for a global optimum
D) It stores intermediate solutions to avoid redundant calculations
In a binary search tree (BST), how is a node deleted?
A) By simply removing the node and adjusting the tree
B) By replacing the node with its parent
C) By replacing the node with the minimum value node from the right subtree or the maximum value node from the left subtree
D) By deleting the left and right children first
What is the primary benefit of using a heap over an unsorted array or list for implementing a priority queue?
A) Faster insertion of new elements
B) Faster access to the minimum element
C) Allows random access to elements
D) It requires less memory
Which of the following best describes the time complexity of an average-case scenario for quicksort?
A) O(n^2)
B) O(log n)
C) O(n log n)
D) O(n)
What is the time complexity for deleting an element from a singly linked list, given that you have a reference to the node to be deleted?
A) O(1)
B) O(log n)
C) O(n)
D) O(n^2)
Which of the following data structures is typically used to implement a recursive algorithm?
A) Queue
B) Stack
C) Array
D) Linked List
What does the Bellman-Ford algorithm compute?
A) The shortest path from a single source to all other vertices in a graph
B) The minimum spanning tree of a graph
C) The longest path in a weighted graph
D) The maximum flow in a network
Which of the following is true about a depth-first search (DFS) traversal of a graph?
A) DFS is not used for traversing trees
B) DFS uses a stack for its implementation
C) DFS guarantees the shortest path to any node
D) DFS is slower than breadth-first search (BFS) for finding the shortest path
What is the time complexity of accessing an element in a singly linked list by index?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
In the context of dynamic programming, what is the primary purpose of memoization?
A) To minimize the number of subproblems by solving them only once
B) To store solutions to all subproblems
C) To break down a problem into smaller subproblems
D) To create a recursive function
Which of the following is the most efficient algorithm for finding the shortest path in an unweighted graph?
A) Dijkstra’s Algorithm
B) A* Algorithm
C) Bellman-Ford Algorithm
D) Breadth-First Search (BFS)
What is the time complexity of bubble sort in the worst case?
A) O(1)
B) O(log n)
C) O(n^2)
D) O(n log n)
Which of the following algorithms is typically used to solve problems that require finding a minimum spanning tree?
A) Kruskal’s Algorithm
B) Quick Sort
C) Bellman-Ford Algorithm
D) Depth-First Search (DFS)
What is the space complexity of the recursive implementation of the quicksort algorithm?
A) O(n)
B) O(log n)
C) O(n log n)
D) O(1)
In a directed acyclic graph (DAG), which algorithm is used to find the topological ordering of vertices?
A) Kruskal’s Algorithm
B) Dijkstra’s Algorithm
C) Topological Sort
D) Bellman-Ford Algorithm
In an AVL tree, what action is taken when the tree becomes unbalanced?
A) The tree is restructured using a rotation
B) A new node is added at the bottom of the tree
C) The tree is rebuilt from scratch
D) A balancing factor is calculated
Which of the following graph traversal algorithms guarantees the shortest path in a weighted graph with non-negative weights?
A) Depth-First Search (DFS)
B) Dijkstra’s Algorithm
C) Bellman-Ford Algorithm
D) Breadth-First Search (BFS)
Which of the following is the best case time complexity for insertion sort?
A) O(n)
B) O(n log n)
C) O(n^2)
D) O(1)
Which of the following data structures is used to implement a breadth-first search (BFS)?
A) Stack
B) Queue
C) Priority Queue
D) Linked List
What is the best case time complexity of merge sort?
A) O(n)
B) O(n log n)
C) O(n^2)
D) O(log n)
What is the main disadvantage of using a binary search tree (BST)?
A) It requires extra space to store pointers to the next node
B) It cannot be used for dynamic sets of data
C) It can become unbalanced, leading to poor performance
D) It is inefficient for finding the smallest element
Which of the following statements about a hash table is true?
A) Hash tables use binary search trees to organize data
B) Hash tables guarantee O(1) time complexity for all operations
C) Collisions in hash tables can be resolved using chaining or open addressing
D) Hash tables are always slower than binary search trees for searching
Which of the following algorithms is efficient for finding the median of two sorted arrays?
A) Merge Sort
B) Quickselect
C) Dijkstra’s Algorithm
D) Depth-First Search (DFS)
Which of the following is a characteristic of a greedy algorithm?
A) It solves problems by breaking them into smaller subproblems
B) It always produces the optimal solution
C) It makes the best possible decision at each step without looking ahead
D) It uses dynamic programming to solve problems
Which of the following is NOT a stable sorting algorithm?
A) Merge Sort
B) Insertion Sort
C) Quick Sort
D) Bubble Sort
What is the time complexity of searching for an element in a sorted array using binary search?
A) O(1)
B) O(n)
C) O(log n)
D) O(n log n)
Which of the following is a characteristic of a binary search tree (BST)?
A) The left child’s value is greater than the parent’s value
B) The right child’s value is less than the parent’s value
C) The left child’s value is less than the parent’s value
D) The right child’s value is greater than the parent’s value
What is the main advantage of using a heap data structure over an array when implementing a priority queue?
A) It allows direct access to all elements in constant time
B) It guarantees that elements are sorted
C) It allows for faster insertion and removal of the highest (or lowest) priority element
D) It uses less memory
Which of the following is an example of a divide-and-conquer algorithm?
A) Merge Sort
B) Bubble Sort
C) Insertion Sort
D) Quick Sort
Which data structure is most commonly used for implementing the depth-first search (DFS) algorithm?
A) Stack
B) Queue
C) Priority Queue
D) Array
What is the time complexity of accessing an element at a specific index in an array?
A) O(1)
B) O(log n)
C) O(n)
D) O(n^2)
In a graph, what does it mean for the graph to be “connected”?
A) There is at least one path between every pair of vertices
B) Every vertex has an edge to all other vertices
C) The graph has no cycles
D) All edges in the graph are directed
What is the worst-case time complexity for searching in a balanced binary search tree (BST)?
A) O(n)
B) O(log n)
C) O(n log n)
D) O(1)
Which of the following algorithms is best suited for finding the shortest path between all pairs of vertices in a graph?
A) Dijkstra’s Algorithm
B) Bellman-Ford Algorithm
C) Floyd-Warshall Algorithm
D) Prim’s Algorithm
Which of the following is an essential property of a binary heap?
A) The tree is always balanced
B) The children of a node are always larger than the parent
C) The root is always the smallest or largest element, depending on the heap type
D) Every node has exactly two children
Which of the following is the time complexity of inserting an element into a hash table (in the best case)?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
What is the key idea behind the quicksort algorithm?
A) Divide the input array into two halves and sort them separately
B) Divide the input array into multiple smaller subarrays based on a pivot element
C) Merge two sorted arrays into one sorted array
D) Repeatedly find the minimum element and place it at the beginning of the array
Which of the following algorithms has the best time complexity in the worst case?
A) Quick Sort
B) Merge Sort
C) Bubble Sort
D) Insertion Sort
What is the time complexity for finding the maximum element in a binary search tree (BST)?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
What is a “cut” in the context of Kruskal’s algorithm?
A) A way to identify whether an edge is part of the minimum spanning tree
B) A division of the graph into two sets of vertices
C) A division of the graph into connected subgraphs
D) A process used for finding the shortest path
What is the time complexity of a breadth-first search (BFS) algorithm for a graph with V vertices and E edges?
A) O(V + E)
B) O(V * E)
C) O(V log E)
D) O(E log V)
What is the main advantage of using dynamic programming (DP) to solve problems over traditional recursive approaches?
A) DP guarantees the optimal solution with less time complexity
B) DP solves problems without using recursion
C) DP eliminates the need for an input matrix
D) DP is easier to implement than recursion
Which of the following algorithms uses a greedy strategy?
A) Merge Sort
B) Dijkstra’s Algorithm
C) Floyd-Warshall Algorithm
D) Depth-First Search (DFS)
What is the space complexity of a recursive implementation of the quicksort algorithm?
A) O(n)
B) O(log n)
C) O(n log n)
D) O(1)
What is the primary disadvantage of using an array-based implementation of a stack?
A) It takes up too much memory
B) It does not allow for efficient search operations
C) It requires resizing when it reaches its capacity
D) It is slower than using a linked list
Which of the following operations is performed first in the heap sort algorithm?
A) Heapify the array
B) Build the minimum heap
C) Build the maximum heap
D) Perform the quicksort
Which algorithm is best suited for solving the “knapsack problem”?
A) Dynamic Programming
B) Quick Sort
C) Breadth-First Search (BFS)
D) Divide and Conquer
Which of the following operations on a binary search tree (BST) has the worst-case time complexity of O(n)?
A) Searching for an element
B) Inserting an element
C) Deleting an element
D) All of the above
What is the key advantage of using a priority queue?
A) Efficient access to the minimum or maximum element
B) Ability to store elements in sorted order
C) Efficient search for an arbitrary element
D) Faster sorting of elements
Which of the following is a correct property of a doubly linked list?
A) Each node has only one pointer
B) Each node has two pointers, one to the next node and one to the previous node
C) It supports faster search operations compared to a singly linked list
D) It is always sorted
Which of the following algorithms uses a divide-and-conquer strategy?
A) Heap Sort
B) Quick Sort
C) Insertion Sort
D) Selection Sort
In the context of graph theory, which of the following is true about a directed acyclic graph (DAG)?
A) It contains at least one cycle
B) It has no directed edges
C) It can be used for topological sorting
D) It must be strongly connected
What is the time complexity of performing a linear search on an unsorted array?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
Which of the following data structures is best suited for implementing a breadth-first search (BFS) algorithm in a graph?
A) Stack
B) Queue
C) Array
D) Linked List
Which of the following is the primary difference between a singly linked list and a doubly linked list?
A) A singly linked list has one pointer, whereas a doubly linked list has two pointers
B) A singly linked list stores more data per node
C) A doubly linked list is always sorted
D) A doubly linked list can only be traversed from the last node
What is the time complexity of performing a binary search on a sorted array?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
Which of the following is an essential property of a binary search tree (BST)?
A) Every node must have exactly two children
B) The left subtree of a node contains only nodes with values less than the node’s value
C) The right subtree of a node contains only nodes with values less than the node’s value
D) It is always a balanced tree
What is the time complexity of inserting an element in a balanced binary search tree (BST)?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
Which of the following is NOT a property of a hash table?
A) It allows for fast search, insertion, and deletion operations
B) It uses a hash function to map keys to indices
C) It requires that the keys be unique
D) It allows for sorted traversal of the elements
What is the primary advantage of using a linked list over an array?
A) Linked lists allow for fast access to elements at specific indices
B) Linked lists are more space-efficient because they don’t require a fixed size
C) Linked lists support fast insertions and deletions at any position
D) Linked lists allow for better cache locality
Which of the following is true about merge sort?
A) Merge sort is an in-place sorting algorithm
B) Merge sort has a time complexity of O(n^2) in the worst case
C) Merge sort uses the divide-and-conquer strategy
D) Merge sort is not stable
What is the time complexity of finding the minimum element in a max heap?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
In which scenario would you prefer using a depth-first search (DFS) over a breadth-first search (BFS)?
A) When you need to find the shortest path between two nodes
B) When the graph is large and you want to minimize memory usage
C) When you need to explore all neighbors of a node at once
D) When you want to explore nodes level by level
Which of the following sorting algorithms has the best worst-case time complexity?
A) Quick Sort
B) Merge Sort
C) Heap Sort
D) Bubble Sort
What is the primary characteristic of a stack data structure?
A) It allows elements to be inserted and removed from both ends
B) It follows the Last In First Out (LIFO) principle
C) It stores elements in a sorted order
D) It allows direct access to any element
Which of the following is the correct time complexity of accessing an element by index in a singly linked list?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
What is the time complexity of the quicksort algorithm in the average case?
A) O(1)
B) O(log n)
C) O(n log n)
D) O(n^2)
Which of the following algorithms is best for sorting an array that is already partially sorted?
A) Bubble Sort
B) Merge Sort
C) Insertion Sort
D) Heap Sort
In which of the following cases would you use a priority queue?
A) To find the middle element of an array
B) To implement a scheduling system where jobs are processed in order of importance
C) To store elements in sorted order
D) To perform quick lookups of elements based on their frequency
What is the time complexity of deleting the root node in a max heap?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
In the context of a graph, what does the term “strongly connected” refer to?
A) Every vertex has a direct edge to every other vertex
B) There is a directed path from any vertex to any other vertex
C) The graph contains no cycles
D) The graph is undirected
Which of the following algorithms is used for finding the minimum spanning tree in a graph?
A) Dijkstra’s Algorithm
B) Kruskal’s Algorithm
C) Bellman-Ford Algorithm
D) Floyd-Warshall Algorithm
Which of the following is the time complexity of traversing a binary tree in-order?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
What is the space complexity of the recursive version of quicksort?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
Which of the following operations can be performed in constant time in a stack?
A) Searching for an element
B) Inserting an element
C) Accessing an element by index
D) Deleting an element from the middle
What is the primary benefit of using a bloom filter?
A) It allows for quick lookups and saves memory, but may produce false positives
B) It guarantees no false positives
C) It stores large sets of data efficiently
D) It works best for sorted data
What is the time complexity of removing the minimum element from a min heap?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
Which of the following is true about a red-black tree?
A) It is always balanced
B) It ensures that the tree height is O(log n)
C) It is a type of binary search tree that supports faster search operations
D) It is not self-balancing
What is the time complexity of finding the maximum element in a binary search tree (BST)?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
Which of the following is a key feature of a depth-first search (DFS) traversal?
A) It explores all nodes at the current level before moving to the next level
B) It uses a queue to explore nodes
C) It uses a stack or recursion to explore nodes in a deep path first
D) It is used primarily for finding the shortest path in a graph
In which of the following scenarios would you prefer using an adjacency matrix to represent a graph?
A) When the graph is sparse with many edges
B) When the graph is dense with few edges
C) When you want to minimize the space complexity
D) When the graph is very large and sparse
What is the time complexity of the selection sort algorithm in the worst case?
A) O(1)
B) O(n log n)
C) O(n^2)
D) O(n)
What type of data structure is commonly used to implement a graph traversal algorithm such as BFS?
A) Stack
B) Queue
C) Linked List
D) Array
What is the purpose of the pivot element in the quicksort algorithm?
A) To partition the array into two subarrays for further sorting
B) To minimize the number of recursive calls
C) To ensure that the array is sorted in O(log n) time
D) To find the median element
What is the time complexity of inserting an element in a binary heap?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
Which of the following sorting algorithms is classified as a stable sort?
A) Quick Sort
B) Merge Sort
C) Heap Sort
D) Selection Sort
Which of the following is true about a heap data structure?
A) It is a binary tree where the parent node is smaller than its children
B) It is a tree structure used for sorting elements in ascending order
C) It is always a balanced tree
D) It is a priority queue implementation
What is the time complexity of accessing an element at a given index in a linked list?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
What is the worst-case time complexity of the bubble sort algorithm?
A) O(1)
B) O(n log n)
C) O(n^2)
D) O(n)
Which of the following data structures is best suited for implementing an undo feature in a text editor?
A) Stack
B) Queue
C) Linked List
D) Array
Which of the following graph traversal algorithms is guaranteed to find the shortest path in an unweighted graph?
A) Depth-first search (DFS)
B) Breadth-first search (BFS)
C) Dijkstra’s algorithm
D) Bellman-Ford algorithm
Which of the following best describes the time complexity of accessing an element in an array?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
Which of the following sorting algorithms is the best choice when memory is constrained?
A) Merge Sort
B) Quick Sort
C) Insertion Sort
D) Heap Sort
Which of the following is a characteristic of a binary search tree (BST)?
A) The left child’s value is greater than the parent node’s value
B) The right child’s value is always greater than the parent node’s value
C) The left child’s value is less than the parent node’s value
D) The left and right subtrees can have random values
Which of the following is NOT a valid operation for a stack?
A) Push
B) Pop
C) Dequeue
D) Peek
What is the time complexity of deleting the root node in a min-heap?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
In which of the following cases is it optimal to use a hash table?
A) When you need fast lookups by key
B) When you need to store data in sorted order
C) When the data is represented as a graph
D) When you need to store elements in a multi-level hierarchy
What is the primary disadvantage of using the adjacency matrix representation for sparse graphs?
A) It requires O(n) space for storage
B) It is inefficient for searching for the neighbors of a node
C) It requires O(n^2) space even for sparse graphs
D) It does not support weighted edges
What is the worst-case time complexity of the insertion sort algorithm?
A) O(1)
B) O(log n)
C) O(n)
D) O(n^2)
In a min heap, which of the following is true about the root node?
A) It contains the largest value
B) It contains the smallest value
C) It contains the middle value
D) It contains a random value
Which of the following is a characteristic of the quicksort algorithm?
A) It is always stable
B) It divides the array into two subarrays around a pivot element
C) It requires O(n^2) time in the best case
D) It is not suitable for large datasets
What is the time complexity of finding the shortest path using Dijkstra’s algorithm with a priority queue?
A) O(n^2)
B) O(n log n)
C) O(n)
D) O(log n)
What is the time complexity of searching for an element in a balanced binary search tree (BST)?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
Which of the following algorithms is based on the divide-and-conquer technique?
A) Quick Sort
B) Insertion Sort
C) Merge Sort
D) Selection Sort
Which of the following is the primary advantage of using a hash table for storing data?
A) It guarantees sorted order of data
B) It provides constant time average complexity for searching, insertion, and deletion
C) It is memory-efficient for large datasets
D) It provides an efficient way to store hierarchical data
Which of the following is the correct order of the following sorting algorithms from the best to the worst in terms of time complexity in the average case?
A) Merge Sort, Quick Sort, Bubble Sort, Insertion Sort
B) Bubble Sort, Insertion Sort, Merge Sort, Quick Sort
C) Quick Sort, Merge Sort, Insertion Sort, Bubble Sort
D) Insertion Sort, Bubble Sort, Quick Sort, Merge Sort
In a binary search tree (BST), what is the worst-case time complexity of inserting a node?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
What is the time complexity of the breadth-first search (BFS) algorithm in terms of the number of vertices (V) and edges (E) in a graph?
A) O(V)
B) O(V + E)
C) O(E)
D) O(V^2)
In which scenario would you most likely use a trie (prefix tree)?
A) For storing and efficiently searching large datasets of numeric data
B) For implementing an auto-complete system
C) For finding the shortest path in a graph
D) For sorting a large array of integers
Which data structure is used by the depth-first search (DFS) algorithm to keep track of the vertices visited?
A) Queue
B) Stack
C) Array
D) Linked List
Which of the following operations can be performed in constant time O(1) in a doubly linked list?
A) Insertion at the beginning
B) Searching for an element
C) Deletion of an element
D) Insertion at the middle
What is the space complexity of an algorithm that uses a recursive approach to solve a problem and has a recursion depth of O(n)?
A) O(1)
B) O(n)
C) O(log n)
D) O(n log n)
Which of the following data structures allows you to insert elements at both ends efficiently?
A) Queue
B) Stack
C) Linked List
D) Deque
What is the worst-case time complexity of searching for an element in an unsorted array?
A) O(1)
B) O(log n)
C) O(n)
D) O(n^2)
In which of the following scenarios would you use a priority queue?
A) To implement a depth-first search
B) To keep track of elements with the highest or lowest priority
C) To store elements in sorted order
D) To implement a recursive algorithm
What is the time complexity of deleting the last node in a doubly linked list?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
Which of the following is the primary advantage of using the merge sort algorithm?
A) It is an in-place sorting algorithm
B) It is a stable sorting algorithm
C) It has better worst-case time complexity than other sorting algorithms
D) It works well for small datasets
What is the main disadvantage of using a recursive approach to solve problems?
A) It may lead to stack overflow if the recursion depth is too large
B) It requires additional space for an explicit stack
C) It always has a higher time complexity
D) It cannot be used for divide-and-conquer algorithms
Which data structure is used in the implementation of Dijkstra’s algorithm?
A) Stack
B) Queue
C) Priority Queue
D) Linked List
What is the time complexity of inserting an element in an AVL tree (balanced binary search tree)?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
Which of the following traversal methods is used to find the topological sort of a directed acyclic graph (DAG)?
A) Depth-first search (DFS)
B) Breadth-first search (BFS)
C) Preorder traversal
D) Inorder traversal
What is the time complexity of the Floyd-Warshall algorithm for finding the shortest paths between all pairs of vertices in a graph?
A) O(V)
B) O(V^2)
C) O(V^3)
D) O(V^2 + E)
Which of the following is true about a red-black tree?
A) It is a type of self-balancing binary search tree
B) It guarantees that all leaf nodes are at the same level
C) It requires less space than an AVL tree
D) It is always balanced by rotating nodes
Which of the following is the best choice for representing a sparse graph?
A) Adjacency Matrix
B) Adjacency List
C) Binary Search Tree
D) Hash Table
Which of the following operations does a deque support efficiently?
A) Only insertion at the front
B) Only insertion at the back
C) Insertion and deletion at both ends
D) Random access
What is the time complexity of performing a binary search on a sorted array of n elements?
A) O(n)
B) O(log n)
C) O(n log n)
D) O(1)
Which of the following is true about a stack data structure?
A) Elements can be accessed in a random order
B) It follows the Last In First Out (LIFO) principle
C) It allows insertion and deletion from both ends
D) It uses a queue internally
Which of the following algorithms is used to find the shortest path in a weighted graph with non-negative edge weights?
A) Bellman-Ford Algorithm
B) Dijkstra’s Algorithm
C) Floyd-Warshall Algorithm
D) Kruskal’s Algorithm
In a quicksort algorithm, what is the expected time complexity for a randomly chosen pivot?
A) O(n^2)
B) O(n log n)
C) O(log n)
D) O(n)
Which data structure is best suited for implementing a priority queue?
A) Array
B) Binary Heap
C) Linked List
D) Hash Table
What is the space complexity of a recursive depth-first search (DFS) algorithm in a graph with V vertices and E edges?
A) O(V + E)
B) O(V)
C) O(E)
D) O(log V)
What is the main difference between a binary search tree (BST) and a balanced binary search tree like an AVL tree?
A) A BST is always balanced, while an AVL tree is not
B) An AVL tree maintains a strict balance, ensuring O(log n) height
C) A BST allows duplicate values, while an AVL tree does not
D) An AVL tree has a higher space complexity than a BST
In the context of algorithms, what does the term “divide and conquer” refer to?
A) Breaking a problem into smaller, non-overlapping subproblems
B) Combining multiple algorithms to solve a problem
C) Solving problems by trying every possible solution
D) Dividing a problem into equal parts and solving each part concurrently
Which of the following sorting algorithms is NOT stable?
A) Bubble Sort
B) Merge Sort
C) Quick Sort
D) Insertion Sort
What is the time complexity of the insertion sort algorithm in the worst case?
A) O(n)
B) O(n log n)
C) O(n^2)
D) O(log n)
Which algorithm is used to find the minimum spanning tree in an undirected, weighted graph?
A) Dijkstra’s Algorithm
B) Bellman-Ford Algorithm
C) Prim’s Algorithm
D) Kruskal’s Algorithm
In a graph, what is the time complexity of checking whether an edge exists between two vertices in an adjacency matrix?
A) O(1)
B) O(log n)
C) O(n)
D) O(n^2)
What is the worst-case time complexity of the selection sort algorithm?
A) O(n log n)
B) O(n^2)
C) O(n)
D) O(1)
Which of the following is an application of dynamic programming?
A) Sorting an array of integers
B) Finding the shortest path in an unweighted graph
C) Solving the traveling salesman problem
D) Finding the maximum subarray sum in a sequence
In a graph represented by an adjacency list, what is the time complexity of checking if an edge exists between two vertices?
A) O(1)
B) O(n)
C) O(log n)
D) O(V)
What is the time complexity of accessing an element in a hash table, assuming no collisions?
A) O(1)
B) O(n)
C) O(log n)
D) O(n^2)
Which of the following is a characteristic of a greedy algorithm?
A) It considers the entire problem space before making decisions
B) It guarantees an optimal solution for all problems
C) It makes locally optimal choices at each step in the hope of finding a global optimum
D) It always solves problems using a recursive approach
What is the space complexity of an algorithm that uses a dynamic programming approach to solve a problem with n subproblems, each requiring O(n) space?
A) O(1)
B) O(n)
C) O(n^2)
D) O(n^3)
Which of the following is the primary advantage of a hash table over a binary search tree (BST)?
A) It allows faster searching and retrieval operations
B) It provides better memory efficiency
C) It guarantees that the data is stored in sorted order
D) It requires less space for storage
Which of the following is true for an undirected graph?
A) It always has a cycle
B) The degree of each vertex is always even
C) The edges have no direction and are bidirectional
D) It cannot contain any self-loops
In which of the following scenarios is a min-heap most commonly used?
A) Finding the shortest path in a graph
B) Sorting an array of integers
C) Implementing a priority queue
D) Searching for an element in a list
Which of the following algorithms guarantees the optimal solution for the Knapsack Problem?
A) Dynamic Programming
B) Greedy Algorithm
C) Divide and Conquer
D) Backtracking
Which of the following is true for a red-black tree?
A) It is a binary search tree where each node contains a color and follows specific balancing rules
B) It is a type of AVL tree
C) It guarantees that the root node is always black
D) It does not allow duplicate values
What is the time complexity of performing a union operation in a disjoint set (union-find) data structure, using path compression and union by rank?
A) O(1)
B) O(log n)
C) O(n)
D) O(α(n)) (where α is the inverse Ackermann function)
What is the worst-case time complexity of the merge sort algorithm?
A) O(n)
B) O(n log n)
C) O(n^2)
D) O(log n)
In a directed acyclic graph (DAG), which of the following traversal algorithms is used to perform topological sorting?
A) Depth-first search (DFS)
B) Breadth-first search (BFS)
C) Preorder traversal
D) Postorder traversal
Which of the following is the space complexity of the recursive solution for the Fibonacci sequence, where each call makes two recursive calls?
A) O(1)
B) O(log n)
C) O(n)
D) O(2^n)
Which of the following is the best time complexity for an algorithm that finds the maximum element in an unsorted array?
A) O(n)
B) O(n log n)
C) O(log n)
D) O(1)
Which of the following is a property of a topological sort in a directed graph?
A) It can be performed only on a tree
B) It arranges vertices such that for every directed edge (u, v), u comes before v
C) It produces a cycle
D) It is not possible for graphs with multiple components
Which of the following algorithms is used to find the shortest path between all pairs of vertices in a weighted graph?
A) Dijkstra’s Algorithm
B) Bellman-Ford Algorithm
C) Floyd-Warshall Algorithm
D) Prim’s Algorithm
What is the time complexity of finding the minimum element in a max-heap?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
Which of the following is true about the quicksort algorithm in the average case?
A) It has O(n^2) time complexity
B) It is not a comparison-based sorting algorithm
C) It has O(n log n) time complexity
D) It guarantees that the data will be sorted in ascending order
Which of the following is an example of a divide-and-conquer algorithm?
A) Merge Sort
B) Bubble Sort
C) Selection Sort
D) Quick Sort
Which of the following sorting algorithms is considered to be the most efficient in practice for large datasets?
A) Merge Sort
B) Quick Sort
C) Insertion Sort
D) Selection Sort
In which of the following data structures is the “peek” operation performed efficiently?
A) Queue
B) Stack
C) Linked List
D) Hash Table
What is the main idea behind the Bellman-Ford algorithm?
A) It computes the shortest paths from a source vertex to all other vertices in a graph with positive edge weights
B) It computes the shortest paths in a graph with negative edge weights
C) It finds the minimum spanning tree in a weighted graph
D) It computes the longest path between two vertices in a graph
Which of the following traversal techniques can be used to find a cycle in an undirected graph?
A) Depth-first search (DFS)
B) Breadth-first search (BFS)
C) Preorder traversal
D) Inorder traversal
Which of the following is true about a breadth-first search (BFS) algorithm?
A) It starts at the root node and explores as far as possible along each branch before backtracking
B) It uses a queue to explore the graph level by level
C) It cannot be used to find the shortest path in an unweighted graph
D) It requires more memory than depth-first search (DFS)