Q.1 Which of the following best describes the time complexity of binary search on a sorted array?
O(n)
O(log n)
O(n^2)
O(1)
Explanation - Binary search divides the search space in half at each step, resulting in a logarithmic time complexity O(log n).
Correct answer is: O(log n)
Q.2 What is the main purpose of a greedy algorithm?
To find all possible solutions
To find an approximate solution quickly
To backtrack and try different paths
To sort data efficiently
Explanation - Greedy algorithms make locally optimal choices at each step to achieve a solution that is often close to the global optimum.
Correct answer is: To find an approximate solution quickly
Q.3 Which of the following sorting algorithms has the best average-case time complexity?
Bubble Sort
Insertion Sort
Merge Sort
Selection Sort
Explanation - Merge Sort consistently has O(n log n) time complexity in the average case, which is better than the O(n^2) of Bubble, Insertion, and Selection Sort.
Correct answer is: Merge Sort
Q.4 What is the primary difference between dynamic programming and divide-and-conquer algorithms?
Dynamic programming solves subproblems independently; divide-and-conquer reuses solutions
Dynamic programming reuses solutions; divide-and-conquer solves subproblems independently
Dynamic programming is always recursive; divide-and-conquer is iterative
There is no difference
Explanation - Dynamic programming stores solutions of subproblems to avoid recomputation, while divide-and-conquer solves each subproblem separately and combines results.
Correct answer is: Dynamic programming reuses solutions; divide-and-conquer solves subproblems independently
Q.5 In a graph, the shortest path from a single source to all other vertices can be found using which algorithm?
Prim's Algorithm
Dijkstra's Algorithm
Kruskal's Algorithm
Bellman-Ford Algorithm
Explanation - Dijkstra's Algorithm computes shortest paths from a single source to all vertices in a weighted graph with non-negative edges.
Correct answer is: Dijkstra's Algorithm
Q.6 What is the worst-case time complexity of quicksort?
O(n)
O(n log n)
O(n^2)
O(log n)
Explanation - Quicksort has a worst-case time complexity of O(n^2) when the pivot selection is poor, such as always choosing the smallest or largest element.
Correct answer is: O(n^2)
Q.7 Which algorithmic technique is used in the Knapsack problem to improve efficiency?
Divide and Conquer
Greedy Approach
Dynamic Programming
Backtracking
Explanation - Dynamic programming is used in the 0/1 Knapsack problem to store solutions of subproblems and avoid recomputation, improving efficiency.
Correct answer is: Dynamic Programming
Q.8 Which of the following data structures is most suitable for implementing a priority queue?
Array
Stack
Heap
Queue
Explanation - A heap allows efficient insertion and extraction of the maximum (or minimum) element, making it ideal for a priority queue.
Correct answer is: Heap
Q.9 In a recursive algorithm, what is the base case?
The simplest subproblem that can be solved directly
The first recursive call
The most complex problem
A case where recursion is avoided
Explanation - The base case defines when recursion should stop, usually for the simplest possible input that can be solved without further recursion.
Correct answer is: The simplest subproblem that can be solved directly
Q.10 What is the time complexity of inserting an element at the beginning of a singly linked list?
O(1)
O(n)
O(log n)
O(n log n)
Explanation - Insertion at the beginning of a singly linked list only requires updating pointers, which takes constant time O(1).
Correct answer is: O(1)
Q.11 Which of the following statements is true for a minimum spanning tree (MST)?
It contains all edges of the graph
It contains all vertices with minimal total edge weight
It may contain cycles
It maximizes the total edge weight
Explanation - An MST connects all vertices with the minimum possible sum of edge weights without forming cycles.
Correct answer is: It contains all vertices with minimal total edge weight
Q.12 What is the main advantage of using memoization in an algorithm?
It reduces space complexity
It avoids recomputation of subproblems
It ensures the algorithm is iterative
It guarantees optimality
Explanation - Memoization stores previously computed results, preventing repeated computation and improving performance in recursive algorithms.
Correct answer is: It avoids recomputation of subproblems
Q.13 Which of the following is an example of a divide-and-conquer algorithm?
Merge Sort
Dijkstra's Algorithm
Linear Search
Prim's Algorithm
Explanation - Merge Sort splits the array into halves, recursively sorts them, and then merges the sorted halves, following divide-and-conquer.
Correct answer is: Merge Sort
Q.14 In Big-O notation, what does O(n log n) indicate?
The algorithm's time increases linearly with input size
The algorithm's time increases logarithmically with input size
The algorithm's time increases slightly faster than linear but less than quadratic
The algorithm's time increases quadratically
Explanation - O(n log n) grows faster than linear O(n) but slower than quadratic O(n^2), typical for efficient sorting algorithms like Merge Sort.
Correct answer is: The algorithm's time increases slightly faster than linear but less than quadratic
Q.15 Which graph traversal technique uses a queue?
Depth-First Search
Breadth-First Search
Dijkstra's Algorithm
Prim's Algorithm
Explanation - Breadth-First Search (BFS) explores neighbors level by level using a queue to keep track of vertices to visit next.
Correct answer is: Breadth-First Search
Q.16 In algorithm analysis, which case represents the performance on typical input?
Best Case
Average Case
Worst Case
Extreme Case
Explanation - The average case represents the expected performance over all possible inputs of a given size.
Correct answer is: Average Case
Q.17 Which of the following is true about backtracking algorithms?
They always guarantee polynomial time
They explore all possible solutions systematically
They only work for numeric problems
They avoid recursion
Explanation - Backtracking algorithms systematically explore all possible candidate solutions, pruning invalid paths along the way.
Correct answer is: They explore all possible solutions systematically
Q.18 What is the space complexity of storing an adjacency matrix for a graph with n vertices?
O(n)
O(n log n)
O(n^2)
O(1)
Explanation - An adjacency matrix requires n x n entries to represent all possible edges between n vertices, resulting in O(n^2) space complexity.
Correct answer is: O(n^2)
Q.19 Which algorithm finds the longest common subsequence (LCS) between two sequences?
Greedy Algorithm
Dynamic Programming
Divide and Conquer
Backtracking
Explanation - The LCS problem is solved efficiently using dynamic programming by building a table of solutions for subproblems.
Correct answer is: Dynamic Programming
Q.20 In which scenario is a brute-force algorithm acceptable?
When input size is very large
When input size is small and correctness is critical
When efficiency is the primary concern
Never
Explanation - Brute-force algorithms are simple and guarantee correctness, but they are only feasible for small input sizes due to inefficiency.
Correct answer is: When input size is small and correctness is critical
Q.21 Which of the following problems is typically solved using the greedy method?
Traveling Salesman Problem
Minimum Spanning Tree
Longest Common Subsequence
0/1 Knapsack
Explanation - Algorithms like Prim's and Kruskal's use the greedy approach to build a minimum spanning tree by choosing the smallest edges incrementally.
Correct answer is: Minimum Spanning Tree
Q.22 What is the primary goal of algorithm analysis?
To determine correctness only
To estimate efficiency in terms of time and space
To implement the algorithm in code
To compare programming languages
Explanation - Algorithm analysis focuses on understanding how an algorithm performs, particularly its time and space requirements, as input size grows.
Correct answer is: To estimate efficiency in terms of time and space
Q.23 Which of the following statements about NP-complete problems is true?
They can be solved in polynomial time
Their solutions can be verified in polynomial time
They always have a unique solution
They cannot be solved by any algorithm
Explanation - NP-complete problems may not have known polynomial-time solutions, but any proposed solution can be verified in polynomial time.
Correct answer is: Their solutions can be verified in polynomial time
Q.24 Which algorithmic approach uses recursion and combines solutions of subproblems without overlapping subproblems?
Dynamic Programming
Divide and Conquer
Greedy
Backtracking
Explanation - Divide and Conquer splits the problem into independent subproblems, solves them recursively, and combines the results.
Correct answer is: Divide and Conquer
Q.25 Which of the following is an in-place sorting algorithm?
Merge Sort
Heap Sort
Quick Sort
Counting Sort
Explanation - Quick Sort sorts the array in place without requiring additional arrays, unlike Merge Sort or Counting Sort.
Correct answer is: Quick Sort