1. Recursion is similar to which of the following?
Correct : B. loop
2. Recursion is a method in which the solution of a problem depends on
Correct : C. smaller instances of the same problem
3. Which of the following problems can’t be solved using recursion?
Correct : D. problems without base case
4. In general, which of the following methods isn’t used to find the factorial of a number?
Correct : A. recursion
5. Which of the following recursive formula can be used to find the factorial of a number?
Correct : C. fact(n) = n * fact(n-1)
6. Suppose the first fibonnaci number is 0 and the second is 1. What is the sixth fibonnaci number?
Correct : A. 5
7. Which of the following is not a fibonnaci number?
Correct : D. 14
8. Which of the following option is wrong?
Correct : D. no method is defined to calculate fibonacci number
9. Which of the following recurrence relations can be used to find the nth fibonacci number?
Correct : D. f(n) = f(n – 1) + f(n – 2)
10. Which of the following gives the sum of the first n natural numbers?
Correct : C. (n+1)c2
11. If GCD of two number is 8 and LCM is 144, then what is the second number if first number is 72?
Correct : D. 16
12. Which of the following is also known as GCD?
Correct : A. highest common divisor
13. Which of the following is coprime number?
Correct : D. 9 and 28
14. In terms of Venn Diagram, which of the following expression gives GCD (Given A ꓵ B ≠ Ø)?
Correct : B. multiplication of a ꓵ b terms
15. What is the GCD according to the given Venn Diagram?
Correct : C. 5
16. What is the GCD of a and b?
Correct : B. gcd (a-b, b) if a>b
17. What is the GCD of 48, 18, 0?
Correct : D. 6
18. Is 9 and 28 coprime number?
Correct : A. true
19. 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?
Correct : A. bezout’s identity
20. Is gcd an associative function.
Correct : A. true
21. Who gave the expression for the probability and expected value of gcd?
Correct : A. james e. nymann
22. What is the computational complexity of Binary GCD algorithm where a and b are integers?
Correct : A. o (log a + log b)2)
23. LCM is also called as
Correct : B. scm
24. What is the LCM of 8 and 13?
Correct : D. 104
25. Which is the smallest number of 3 digits that is divisible by 2, 4, 8?
Correct : D. 104
26. Which of the following is also known as LCM?
Correct : A. lowest common divisor
27. What is the LCM of two coprime numbers?
Correct : D. multiplication of two coprime numbers
28. In terms of Venn Diagram, which of the following expression gives LCM (Given A ꓵ B ≠ Ø)?
Correct : A. multiplication of a u b terms
29. What is the LCM according to the given Venn Diagram?
Correct : C. 180
30. What is the lcm (a, b)?
Correct : C. lcm (b, a)
31. Is 9 and 28 coprime number.
Correct : A. true
32. What is the following expression, lcm (a, lcm (b, c) equal to?
Correct : D. lcm (lcm (a, b), c)
33. Is lcm an associative function.
Correct : A. true
34. What is the following expression, lcm (a, gcd (a, b)) equal to?
Correct : A. a
35. Which algorithm is the most efficient numerical algorithm to obtain lcm?
Correct : B. euclid’s algorithm
36. Which of the following methods can be used to find the sum of digits of a number?
Correct : D. both recursion and iteration
37. What can be the maximum sum of digits for a 4 digit number?
Correct : C. 36
38. What can be the minimum sum of digits for a 4 digit number?
Correct : B. 1
39. What is the time complexity of the above code used to reverse a string?
Correct : D. checks if a string is a palindrome
40. Which of the following is the binary representation of 100?
Correct : C. 1100100
41. What is the time complexity of the above recursive implementation used to reverse a string?
Correct : B. o(n)
42. What is the time complexity of matrix multiplied recursively by Divide and Conquer Method?
Correct : C. o(n3)
43. How many recursive calls are there in Recursive matrix multiplication by Strassen’s Method?
Correct : B. 7
44. 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.
Correct : B. 15
45. If Matrix X is of order A*B and Matrix Y is of order C*D, and B=C then the order of the Matrix X*Y is A*D?
Correct : A. true
46. Is Coppersmith-Winograd algorithm better than Strassen’s algorithm in terms of time complexity?
Correct : A. true
47. Which of the following statement is true about stack?
Correct : A. pop operation removes the top most element
48. What is the space complexity of program to reverse stack recursively?
Correct : C. o(n)
49. Stack can be reversed without using extra space by
Correct : B. using linked list to implement stack
50. Which of the following is considered as the top of the stack in the linked list implementation of the stack?
Correct : B. first node
51. What is the time complexity of the program to reverse stack when linked list is used for its implementation?
Correct : A. o(n)
52. Which of the following takes O(n) time in worst case in array implementation of stack?
Correct : D. pop, push and isempty takes constant time
53. What will be the time complexity of the code to reverse stack recursively?
Correct : D. o(n2)
54. Which of the following sorting algorithm has best case time complexity of O(n2)?
Correct : B. selection sort
55. Which of the following is the biggest advantage of selection sort?
Correct : D. it requires only n swaps under any condition
56. What will be the recurrence relation of the code of recursive selection sort?
Correct : C. t(n) = t(n-1) + n
57. Which of the following sorting algorithm is NOT stable?
Correct : A. selection sort
58. What will be the best case time complexity of recursive selection sort?
Correct : B. o(n2)
59. Recursive selection sort is a comparison based sort.
Correct : A. true
60. What is the average case time complexity of recursive selection sort?
Correct : C. o(n2)
61. What is the bidirectional variant of selection sort?
Correct : A. cocktail sort
62. Which of the following methods can be used to find the largest and smallest element in an array?
Correct : C. both recursion and iteration
63. What is the number of swaps required to sort the array arr={5,3,2,4,1} using recursive selection sort?
Correct : C. 2
64. Which of the following methods can be used to find the largest and smallest number in a linked list?
Correct : C. both recursion and iteration
65. Which of the following techniques can be used to search an element in an unsorted array?
Correct : A. iterative linear search
66. Consider the array {1,1,1,1,1}. Select the wrong option?
Correct : D. no method is defined to search for an element in the given array
67. What is the time complexity of the above recursive implementation of binary search?
Correct : C. o(logn)
68. Which of the following methods can be used to search an element in a linked list?
Correct : A. iterative linear search
69. Can binary search be applied on a sorted linked list in O(Logn) time?
Correct : A. no
70. Recursive program to raise an integer x to power y uses which of the following algorithm?
Correct : C. divide and conquer
71. What is the least time in which we can raise a number x to power y?
Correct : D. o(log y)
72. What is the advantage of iterative code for finding power of number over recursive code?
Correct : B. iterative code requires less space
73. Recursive approach to find power of a number is preferred over iterative approach.
Correct : B. false
74. What is the objective of tower of hanoi puzzle?
Correct : A. to move all disks to some other rod by following rules
75. Recurrence equation formed for the tower of hanoi problem is given by
Correct : C. t(n) = 2t(n-1)+c
76. Tower of hanoi problem can be solved iteratively.
Correct : A. true
77. Minimum time required to solve tower of hanoi puzzle with 4 disks assuming one move takes 2 seconds, will be
Correct : B. 30 seconds
78. Master’s theorem is used for?
Correct : A. solving recurrences
79. How many cases are there under Master’s theorem?
Correct : B. 3
80. What is the result of the recurrences which fall under second case of Master’s theorem (let the recurrence be given by T(n)=aT(n/b)+f(n) and f(n)=nc?
Correct : B. t(n) = o(nc log n)
81. What is the result of the recurrences which fall under third case of Master’s theorem (let the recurrence be given by T(n)=aT(n/b)+f(n) and f(n)=nc?
Correct : C. t(n) = o(f(n))
82. We can solve any recurrence by using Master’s theorem.
Correct : B. false
83. Under what case of Master’s theorem will the recurrence relation of merge sort fall?
Correct : B. 2
84. Under what case of Master’s theorem will the recurrence relation of stooge sort fall?
Correct : A. 1
85. Which case of master’s theorem can be extended further?
Correct : B. 2
86. What is the result of the recurrences which fall under the extended second case of Master’s theorem (let the recurrence be given by T(n)=aT(n/b)+f(n) and f(n)=nc(log n)k?
Correct : C. t(n)= o(nc (log n)k+1
87. Under what case of Master’s theorem will the recurrence relation of binary search fall?
Correct : B. 2
88. 7 T (n/2) + 1/n
Correct : D. cannot be solved using master’s theorem
89. What is the worst case time complexity of KMP algorithm for pattern searching (m = length of text, n = length of pattern)?
Correct : C. o(m)
90. What is the time complexity of Z algorithm for pattern searching (m = length of text, n = length of pattern)?
Correct : A. o(n + m)
91. What is the auxiliary space complexity of Z algorithm for pattern searching (m = length of text, n = length of pattern)?
Correct : B. o(m)
92. The naive pattern searching algorithm is an in place algorithm.
Correct : A. true
93. Rabin Karp algorithm and naive pattern searching algorithm have the same worst case time complexity.
Correct : A. true
94. Which of the following sorting algorithms is the fastest?