Topic MCQs — Algorithms & DAA

25 questions · DSSSB TGT CS style · Original

---

Q1. Which is a required property of an algorithm?

• A) Infinite loops by definition
• B) Finiteness (must terminate)
• C) Ambiguous steps
• D) No output allowed Answer: B
  Algorithms must be finite, definite, effective, with I/O.

Q2. Big-O notation describes:

• A) Only exact runtime constants
• B) An asymptotic upper bound
• C) Only memory brand
• D) Only best case always Answer: B
  O gives upper bound growth rate.

Q3. Θ (Theta) notation means:

• A) Only lower bound
• B) Tight bound (upper and lower)
• C) Unrelated to n
• D) Only NP-hard Answer: B
  Θ is asymptotically tight.

Q4. Worst-case analysis considers:

• A) Minimum time over inputs
• B) Maximum time over inputs of size n
• C) Only average of constants
• D) Compilation time only Answer: B
  Worst case = hardest input for that size.

Q5. Divide and Conquer typically:

• A) Never combines subresults
• B) Divides problem, solves parts, combines
• C) Uses only greedy choice
• D) Ignores recursion Answer: B
  Classic pattern: split–conquer–merge.

Q6. Greedy method:

• A) Always backtracks over all subsets
• B) Makes locally optimal choices hoping for global optimum
• C) Stores all overlapping subproblems always like DP
• D) Is identical to thrashing Answer: B
  Local best at each step.

Q7. Dynamic programming is suitable when there is:

• A) No optimal substructure
• B) Overlapping subproblems + optimal substructure
• C) Only negative cycle requirement
• D) Only UI design Answer: B
  DP caches subproblem answers.

Q8. Merge sort worst-case time is:

• A) O(n)
• B) O(n log n)
• C) O(n²)
• D) O(1) Answer: B
  Merge sort is O(n log n) in all cases.

Q9. Quicksort worst-case time is:

• A) O(n log n)
• B) O(n²)
• C) O(log n)
• D) O(n!) Answer: B
  Unbalanced partitions → O(n²).

Q10. Heap sort worst-case time is:

• A) O(n²)
• B) O(n log n)
• C) O(n)
• D) O(2ⁿ) Answer: B
  Heap sort guarantees O(n log n).

Q11. Binary search requires:

• A) Unsorted linked list only
• B) Sorted array (ordered data)
• C) Graph with negative weights
• D) Hash collisions Answer: B
  Halving works on ordered sequences.

Q12. BFS uses:

• A) Stack only
• B) Queue
• C) Only priority queue of Dijkstra always
• D) No data structure Answer: B
  Breadth-first exploration with a queue.

Q13. DFS uses:

• A) Queue only
• B) Stack (or recursion)
• C) Only arrays of size 1
• D) Round Robin quantum Answer: B
  Depth-first via explicit/implicit stack.

Q14. Dijkstra’s algorithm assumes:

• A) Negative edge weights are fine
• B) Non-negative edge weights
• C) Only unweighted graphs can be used
• D) No source vertex Answer: B
  Negative weights invalidate classic Dijkstra.

Q15. Kruskal’s MST algorithm:

• A) Grows from one vertex only like Prim always
• B) Sorts edges and adds if they don’t form a cycle
• C) Is a page replacement policy
• D) Needs negative cycles Answer: B
  Edge-sorted Union-Find approach.

Q16. Prim’s algorithm:

• A) Builds MST by growing a tree from a start vertex
• B) Only sorts all edges globally like insertion sort
• C) Searches text with grep
• D) Normalizes databases Answer: A
  Vertex-growing MST construction.

Q17. Linear search worst-case complexity is:

• A) O(1)
• B) O(log n)
• C) O(n)
• D) O(n log n) Answer: C
  May scan all elements.

Q18. Space–time tradeoff means:

• A) Time and space are always equal
• B) Extra memory can reduce computation time (or vice versa)
• C) Only NP = P
• D) Algorithms need no memory Answer: B
  Classic engineering tradeoff (tables, DP, caches).

Q19. Ω notation gives:

• A) Upper bound only
• B) Lower bound
• C) Exact milliseconds
• D) Only average case constants Answer: B
  Omega = asymptotic lower bound.

Q20. Insertion sort best-case time (already sorted) is:

• A) O(n²)
• B) O(n)
• C) O(n log n)
• D) O(1) Answer: B
  Only linear pass with constant shifts.

Q21. Comparison-based sorting lower bound (general) is:

• A) O(n)
• B) Ω(n log n)
• C) O(1)
• D) O(n!) Answer: B
  Decision-tree lower bound for comparisons.

Q22. NP-hard problems are loosely described in exams as:

• A) Always solvable in O(1)
• B) Computationally hard; no known efficient poly-time algorithm in general
• C) Only HTML rendering
• D) Identical to FCFS Answer: B
  Light exam-level meaning — hardness class.

Q23. Which is typically stable?

• A) Quicksort (typical in-place)
• B) Merge sort
• C) Heap sort
• D) Selection sort Answer: B
  Merge sort preserves equal-key order.

Q24. Shortest path in an unweighted graph is efficiently found by:

• A) Dijkstra only always
• B) BFS
• C) Kruskal
• D) Binary search on edges Answer: B
  BFS levels = hop distances.

Q25. Average-case time of quicksort (typical) is:

• A) O(n²)
• B) O(n log n)
• C) O(n)
• D) O(log n) Answer: B
  With reasonable pivots, average O(n log n).