DSA Miscellaneous : MCQs & PYQs with Explanation

Option D

A Divide and Conquer algorithm are a problem-solving technique where a big problem is broken into smaller ones, solved individually, and then combined to produce the final answer. This method is used in algorithms like Merge Sort, Quick Sort, and Binary Search. The Divide and Conquer approach follow three main steps:

• Divide: Break the original problem into smaller subproblems.
• Conquer: Solve each subproblem either directly if small enough or by applying recursion.
• Combine: Merge subproblem solutions to solve the original problem.

Option C

Spatial Locality is a principle of memory access that states if a memory location is accessed, nearby memory locations are likely to be accessed soon. Since arrays store data in contiguous memory locations, accessing elements sequentially benefits heavily from spatial locality. Thus, arrays highly utilize this concept.

Option A

Memorization is a key technique used in dynamic programming to improve efficiency by:

• Saving the results of expensive function calls.
• Reusing those saved results when the same sub-problem occurs again.

In  other word, instead of recalculating the result every time, we "memorize" (store) it — typically using an array, map, or hash table.
 

Option D

A data structure is indeed a particular way of organizing and storing data so that it can be accessed and modified efficiently. This is true.
Subtraction of two pointers gives the difference in terms of number of elements (blocks) between them, not bytes. This is true.
A function is a block of statements used to perform a specific task. This is true.
Since all the given statements (A), (B), and (C) are true, there is no false statement among them.

Option C

NP-Complete problems are a class of computational problems that are considered difficult because, while a proposed solution can be verified quickly (in polynomial time), there is no known algorithm that can solve all instances of the problem efficiently. Examples include the Traveling Salesman Problem (TSP), which involves finding the shortest possible route visiting all cities, and the Boolean Satisfiability Problem (SAT), which asks whether a boolean formula can be satisfied.
The Shortest Path Problem, which finds the minimum path between nodes in a graph, is not NP-Complete, because it can be solved efficiently in polynomial time using algorithms like Dijkstra’s or Bellman-Ford.

Option D

The process of converting a high-level program into machine code is done in multiple phases of a compiler. Each phase performs a specific task to transform the source code step by step into machine code.
1)  Lexical Analysis.
2)  Syntax Analysis or Parsing.
3)  Semantic Analysis.
4)  Intermediate Code Generation.
5)  Code Optimization.
6)  Code Generation.
In the compilation process, Lexical Analysis is the first phase of a compiler. It takes the source code as input and breaks it into smaller units called tokens such as keywords, identifiers, operators, and constants.
The output of lexical analysis is therefore a stream or set of tokens, which is then passed to the next phase Syntax Analysis.

Option B

A Greedy Algorithm is a problem-solving technique in which the algorithm makes the best possible choice at the current step, without considering future consequences.
The main idea is to select the locally optimal solution at each stage with the hope that these choices will lead to a globally optimal solution.
Instead of exploring all possible solutions, the greedy approach selects the best immediate option according to a specific criterion such as minimum cost, maximum profit, or shortest distance.
This behavior distinguishes greedy algorithms from Dynamic Programming and Backtracking.

• Dynamic Programming examines overlapping subproblems and stores results to ensure the global optimum.
• Backtracking or Exhaustive Search checks all possible solutions before selecting the best one.

Option D

A Stack follows the LIFO (Last In First Out) principle. The element inserted last is removed first. Typical operations are Push and Pop.
A Queue follows the FIFO (First In First Out) principle. The element inserted first is removed first. Typical operations are Enqueue and Dequeue.

Option D

NP-Complete problems are computational problems that are difficult to solve efficiently.
Clique Problem, Hamiltonian Cycle Problem, and Travelling Salesman Problem are NP-Complete problems.
The Shortest Path Problem is not NP-Complete because efficient algorithms like Dijkstra’s Algorithm can solve it in Polynomial Time.

Option C

The Divide and Conquer Approach solves problems by dividing them into smaller independent subproblems and combining their solutions, which is exactly how Strassen Matrix Multiplication reduces matrix multiplication complexity.
Strassen’s Algorithm divides matrices into smaller sub-matrices, solves them recursively, and then combines the results.
Dynamic Programming is used when a problem has overlapping subproblems and optimal substructure. Dynamic programming stores intermediate results to avoid repeated computation. The 0/1 Knapsack problem has overlapping subproblems and optimal substructure.
The Greedy Approach works by making locally optimal choices, and Huffman Encoding uses this idea by repeatedly choosing the least frequent symbols to build an optimal coding tree.
The Backtracking is used to explore all possible solutions by trying choices and undoing them if they lead to failure. Graph Coloring tries different color assignments and backtracks whenever a conflict occurs, making backtracking the suitable approach.

Option D

The 0/1 Knapsack problem is a classic combinatorial optimization problem where each item must be either included or excluded from the knapsack. In this version, the objective is to minimize the profit (or cost), rather than maximize it. Simple greedy methods are not suitable here because they do not always guarantee an optimal solution for 0/1 decisions.

To handle minimization effectively, the Branch & Bound (0/1) technique is used. This method systematically explores all possible combinations of items while using bounds to prune suboptimal branches, which reduces unnecessary computations. While dynamic programming or backtracking can also solve the problem.