Sample Questions and Answers
Which of the following sorting algorithms is NOT stable?
A) Bubble Sort
B) Merge Sort
C) Quick Sort
D) Insertion Sort
Answer: C
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)
Answer: C
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
Answer: D
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)
Answer: A
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)
Answer: B
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
Answer: C
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)
Answer: B
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)
Answer: A
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
Answer: C
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)
Answer: C
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
Answer: A
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
Answer: C
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
Answer: C
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
Answer: A
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
Answer: A
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)
Answer: D
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)
Answer: B
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
Answer: A
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)
Answer: D
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)
Answer: A
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
Answer: B
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
Answer: C
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)
Answer: C
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
Answer: C
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
Answer: A
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
Answer: B
In which of the following data structures is the “peek” operation performed efficiently?
A) Queue
B) Stack
C) Linked List
D) Hash Table
Answer: B
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
Answer: B
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
Answer: A
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)
Answer: B
Reviews
There are no reviews yet.