# Recursion in Data Structure and Algorithms MCQs

Q1. Recursion is similar to which of the following?.

A.  Switch Case.

B.  Loop.

C.  If-else.

D.  None of the mentioned.

Q2. In recursion, the condition for which the function will stop calling itself is ____________.

A.  Best case.

B.  Worst case.

C.  Base case.

D.  There is no such condition.

Q3. Which of the following methods can be used to find the factorial of a number?.

A.  Recursion.

B.  Iteration.

C.  Dynamic programming.

D.  All of the mentioned.

Q4. Which of the following recursive formula can be used to find the factorial of a number?.

A.  fact(n) = n * fact(n).

B.  fact(n) = n * fact(n+1).

C.  fact(n) = n * fact(n-1).

D.  fact(n) = n * fact(1).

Answer=  fact(n) = n * fact(n-1)

Q5. Suppose the first fibonnaci number is 0 and the second is 1. What is the sixth fibonnaci number?.

A. 5.

B. 6.

C. 7.

D. 8.

Q6. Which of the following is not a fibonnaci number?.

A. 8.

B. 21.

C. 55.

D. 14.

Q7. Which of the following methods can be used to find the nth fibonnaci number?.

A.  Dynamic programming.

B.  Recursion.

C.  Iteration.

D.  All of the mentioned.

Q8. Which of the following recurrence relations can be used to find the nth fibonacci number?.

A.  F(n) = F(n) + F(n – 1).

B.  F(n) = F(n) + F(n + 1).

C.  F(n) = F(n – 1).

D.  F(n) = F(n – 1) + F(n – 2).

Answer=  F(n) = F(n – 1) + F(n – 2)

Q9. Which of the following methods can be used to find the sum of first n natural numbers?.

A.  Iteration.

B.  Recursion.

C.  Binomial coefficient.

D.  All of the mentioned.

Q10. Which of the following gives the sum of the first n natural numbers?.

A.  nC2.

B.  (n-1)C2.

C.  (n+1)C2.

D.  none of the mentioned.

Q11. Which of the following methods used to find the sum of first n natural numbers has the least time complexity?.

A.  Recursion.

B.  Iteration.

C.  Binomial coefficient.

D.  All of the mentioned.

Q12. Which of the following is not an alias for GCD?.

A.  LCM.

B.  GCM.

C.  GCF.

D.  HCF.

Q13. What is the GCD of 8 and 12?.

A. 8.

B. 12.

C. 2.

D. 4.

Q14. If GCD of two number is 8 and LCM is 144, then what is the second number if first number is 72?.

A. 24.

B. 2.

C. 3.

D. 16.

Q15. Which of the following is also known as GCD?.

A.  Highest Common Divisor.

B.  Highest Common Multiple.

C.  Highest Common Measure.

D.  Lowest Common Multiple.

Q16. Which of the following is coprime number?.

A.  54 and 24.

B.  4 and 8.

C.  6 and 12.

D.  9 and 28.

Q17. In terms of Venn Diagram, which of the following expression gives GCD (Given A ? B ? Ã˜)?.

A.  Multiplication of A U B terms.

B.  Multiplication of A ? B terms.

C.  Multiplication of A*B terms.

D.  Multiplication of A-B terms.

Answer=  Multiplication of A ? B terms

Q18. What is the GCD of a and b?.

A.  a + b.

B.  gcd (a-b, b) if a>b.

C.  gcd (a+b, a-b).

D.  a – b.

Answer=  gcd (a-b, b) if a>b

Q19. What is the GCD of 48, 18, 0?.

A. 24.

B. 2.

C. 3.

D. 6.

Q20. Is 9 and 28 coprime number?.

A. TRUE.

B. FALSE.

C. Nothing Can be Said.

D. None of the mentioned.

Q21. If gcd (a, b) is defined by the expression, d=a*p + b*q where d, p, q are positive integers and a, b is both not zero, then what is the expression called?.

A.  Bezout’s Identity.

B.  Multiplicative Identity.

C.  Sum of Product.

D.  Product of Sum.

Q22. Is gcd an associative function..

A. TRUE.

B. FALSE.

C. Nothing Can be Said.

D. None of the mentioned.

Q23. Which is the correct term of the given relation, gcd (a, b) * lcm (a, b) =?.

A. a*b.

B.  a + b.

C.  a – b.

D.  a / b.

Q24. Who gave the expression for the probability and expected value of gcd?.

A.  James E. Nymann.

B.  Riemann.

C.  a – b.

D.  Euler.

Q25. What is the computational complexity of Binary GCD algorithm where a and b are integers?.

A.  O (log a + log b)2).

B.  O (log (a + b)).

C.  O (log ab).

D.  O (log a-b).

Answer=  O (log a + log b)2)

Q26. Which of the following is an alias for LCM?.

A.  GCD.

B.  SCM.

C.  GCF.

D.  HCF.

Q27. What is the LCM of 8 and 13?.

A. 8.

B. 12.

C. 20.

D. 104.

Q28. Which is the smallest number of 3 digits that is divisible by 2, 4, 8?.

A. 100.

B. 102.

C. 116.

D. 104.

Q29. Which of the following is also known as LCM?.

A.  Lowest Common Divisor.

B.  Least Common Multiple.

C.  Lowest Common Measure.

D.  Highest Common Multiple.

Q30. What is the LCM of two coprime numbers?.

A. 1.

B. 0.

C.  Addition of two coprime numbers.

D.  Multiplication of two coprime numbers.

Answer=  Multiplication of two coprime numbers

Q31. In terms of Venn Diagram, which of the following expression gives LCM (Given A ? B ? Ã˜)?.

A.  Multiplication of A U B terms.

B.  Multiplication of A ? B terms.

C.  Multiplication of A*B terms.

D.  Multiplication of A-B terms.

Answer=  Multiplication of A U B terms

Q32. What is the lcm (a, b)?.

A.  a + b.

B.  gcd (a-b, b) if a>b.

C.  lcm (b, a).

D.  a – b.

Q33. What is the LCM of 48, 18, 6?.

A. 122.

B.  12*2.

C. 3.

D. 6.

Q34. Is 9 and 28 coprime number..

A. TRUE.

B. FALSE.

C. Nothing Can be Said.

D. None of the mentioned.

Q35. What is the following expression, lcm (a, lcm (b, c) equal to?.

A.  lcm (a, b, c).

B.  a*b*c.

C.  a + b + c.

D.  lcm (lcm (a, b), c).

Answer=  lcm (lcm (a, b), c)

Q36. Is lcm an associative function..

A. TRUE.

B. FALSE.

C. Nothing Can be Said.

D. None of the mentioned.

Q37. Which is the correct term of the given relation, lcm (a, b) * gcd (a, b) =?.

A. a*b.

B.  a + b.

C.  a – b.

D.  a / b.

Q38. What is the following expression, lcm (a, gcd (a, b)) equal to?.

A.  "a".

B.  "b".

C.  a*b.

D.  a + b.

Q39. Which algorithm is the most efficient numerical algorithm to obtain lcm?.

A.  Euler’s Algorithm.

B.  Euclid’s Algorithm.

C.  Chebyshev Function.

D.  Partial Division Algorithm.

Q40. Which of the following methods can be used to find the sum of digits of a number?.

A.  Recursion.

B.  Iteration.

C.  Greedy algorithm.

D.  Both recursion and iteration.

Q41. What can be the maximum sum of digits for a 4 digit number?.

A. 1.

B. 16.

C. 36.

D.  none of the mentioned.

Q42. What can be the minimum sum of digits for a 4 digit number?.

A. 0.

B. 1.

C. 16.

D. 36.

Q43. For which of the following cases will the reversal of a string be equal to the original string?.

A.  Palindromic strings.

B.  Strings of length 1.

C.  Empty String.

D.  All of the mentioned.

Q44. Which of the following is the binary representation of 100?.

A. 1010010.

B. 1110000.

C. 1100100.

D. 1010101.

Q45. What is the time complexity of the recursive implementation used to convert a decimal number to its binary equivalent?.

A.  O(1).

B.  O(n).

C.  O(n^2).

D.  O(logn).

Q46. What is the space complexity of the recursive implementation used to convert a decimal number to its binary equivalent?.

A.  O(1).

B.  O(n).

C.  O(n^2).

D.  O(logn).

Q47. Which of the following can be the base case for the recursive implementation used to find the length of linked list?.

A.  if(current_node == 0) return 1.

B.  if(current_node->next == 0) return 1.

C.  if(current_node->next == 0) return 0.

D.  if(current_node == 0) return 0.

Answer=  if(current_node == 0) return 0

Q48. If Matrix A is of order X*Y and Matrix B is of order M*N, then what is the order of the Matrix A*B given that Y=M?.

A.  Y*N.

B.  X*M.

C.  X*N.

D.  Y*M.

Q49. How many recursive calls are there in Recursive matrix multiplication through Simple Divide and Conquer Method?.

A. 2.

B. 6.

C. 9.

D. 8.

Q50. What is the time complexity of matrix multiplied recursively by Divide and Conquer Method?.

A.  O(n).

B.  O(n^2).

C.  O(n3).

D.  O(n!).

Q51. What is the time complexity of matrix multiplied recursively by Strassen’s Method?.

A.  O(nlog7).

B.  O(n^2).

C.  O(n3).

D.  O(n!).

Q52. How many recursive calls are there in Recursive matrix multiplication by Strassen’s Method?.

A. 5.

B. 7.

C. 8.

D. 4.

Q53. Matrix A is of order 3*4 and Matrix B is of order 4*5. How many elements will be there in a matrix A*B multiplied recursively..

A. 12.

B. 15.

C. 16.

D. 20.

Q54. Which of the following statement is true about stack?.

A.  Pop operation removes the top most element.

B.  Pop operation removes the bottom most element.

C.  Push operation adds new element at the bottom.

D.  Push operation removes the top most element.

Answer=  Pop operation removes the top most element

Q55. What is the space complexity of program to reverse stack recursively?.

A.  O(1).

B.  O(log n).

C.  O(n).

D.  O(n log n).

Q56. Stack can be reversed without using extra space by _____________.

A.  using recursion.

B.  using linked list to implement stack.

C.  using an extra stack.

D.  it is not possible.

Q57. Which of the following is considered as the top of the stack in the linked list implementation of the stack?.

A.  Last node.

B.  First node.

C.  Random node.

D.  Middle node.

Q58. Which of the following takes O(n) time in worst case in array implementation of stack?.

A.  pop.

B.  push.

C.  isEmpty.

D.  none.

Q59. What will be the time complexity of the code to reverse stack recursively?.

A.  O(n).

B.  O(n log n).

C.  O(log n).

D.  O(n^2).

Q60. Which of the following sorting algorithm has best case time complexity of O(n^2)?.

A.  bubble sort.

B.  selection sort.

C.  insertion sort.

D.  stupid sort.

Q61. Which of the following is the biggest advantage of selection sort?.

A.  its has low time complexity.

B.  it has low space complexity.

C.  it is easy to implement.

D.  it requires only n swaps under any condition.

Answer=  it requires only n swaps under any condition

Q62. What will be the recurrence relation of the code of recursive selection sort?.

A.  T(n) = 2T(n/2) + n.

B.  T(n) = 2T(n/2) + c.

C.  T(n) = T(n-1) + n.

D.  T(n) = T(n-1) + c.

Answer=  T(n) = T(n-1) + n

Q63. Which of the following sorting algorithm is NOT stable?.

A.  Selection sort.

B.  Brick sort.

C.  Bubble sort.

D.  Merge sort.

Q64. What will be the best case time complexity of recursive selection sort?.

A.  O(n).

B.  O(n^2).

C.  O(log n).

D.  O(n log n).

Q65. Recursive selection sort is a comparison based sort..

A.  true.

B.  false.

C. Nothing Can be Said.

D. None of the mentioned.

Q66. What is the average case time complexity of recursive selection sort?.

A.  O(n).

B.  O(n log n).

C.  O(n^2).

D.  O(log n).

Q67. What is the bidirectional variant of selection sort?.

A.  cocktail sort.

B.  bogo sort.

C.  gnome sort.

D.  bubble sort.

Q68. Which of the following methods can be used to find the largest and smallest element in an array?.

A.  Recursion.

B.  Iteration.

C.  Both recursion and iteration.

D.  None of the mentioned.

Q69. Which of the following methods can be used to find the largest and smallest number in a linked list?.

A.  Recursion.

B.  Iteration.

C.  Both Recursion and iteration.

D.  None of the mentioned.

Q70. Which of the following techniques can be used to search an element in an unsorted array?.

A.  Iterative linear search.

B.  Recursive binary search.

C.  Iterative binary search.

D.  All of the mentioned.

Q71. Consider the array {1,1,1,1,1}:Which of the following techniques can be used to search an element in the above array?.

A.  Iterative linear search.

B.  Recursive linear search.

C.  Recursive binary search.

D.  All of the mentioned.

Q72. Which of the following methods can be used to search an element in a linked list?.

A.  Iterative linear search.

B.  Iterative binary search.

C.  Recursive binary search.

D.  All of the mentioned.

Q73. What is the objective of tower of hanoi puzzle?.

A.  To move all disks to some other rod by following rules.

B.  To divide the disks equally among the three rods by following rules.

C.  To move all disks to some other rod in random order.

D.  To divide the disks equally among three rods in random order.

Answer=  To move all disks to some other rod by following rules

Q74. Which of the following is NOT a rule of tower of hanoi puzzle?.

A.  No disk should be placed over a smaller disk.

B.  Disk can only be moved if it is the uppermost disk of the stack.

C.  No disk should be placed over a larger disk.

D.  Only one disk can be moved at a time.

Answer=  No disk should be placed over a larger disk

Q75. The time complexity of the solution tower of hanoi problem using recursion is _________.

A.  O(n^2).

B.  O(2n).

C.  O(n log n).

D.  O(n).

Q76. Recurrence equation formed for the tower of hanoi problem is given by _________.

A.  T(n) = 2T(n-1)+n.

B.  T(n) = 2T(n/2)+c.

C.  T(n) = 2T(n-1)+c.

D.  T(n) = 2T(n/2)+n.

Q77. Minimum number of moves required to solve a tower of hanoi problem with n disks is __________.

A.  2n.

B.  2n-1.

C.  n^2.

D.  n^2-1.

Q78. Space complexity of recursive solution of tower of hanoi puzzle is ________.

A.  O(1).

B.  O(n).

C.  O(log n).

D.  O(n log n).

Q79. Recursive solution of tower of hanoi problem is an example of which of the following algorithm?.

A.  Dynamic programming.

B.  Backtracking.

C.  Greedy algorithm.

D.  Divide and conquer.

Q80. Tower of hanoi problem can be solved iteratively..

A. TRUE.

B. FALSE.

C. Nothing Can be Said.

D. None of the mentioned.