McqMate
These multiple-choice questions (MCQs) are designed to enhance your knowledge and understanding in the following areas: Computer Science Engineering (CSE) .
| 51. |
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(n2) |
| Answer» D. o(n2) | |
| Explanation: the recurrence relation for the recursive code to reverse stack will be given by-t(n)=t(n-1)+n.this is calculated to be equal to o(n2). | |
| 52. |
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» D. it requires only n swaps under any condition | |
| Explanation: selection sort works by obtaining least value element in each iteration and then swapping it with the current index. so it will take n swaps under any condition which will be useful when memory write operation is expensive. | |
| 53. |
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» C. t(n) = t(n-1) + n | |
| Explanation: function to find the minimum element index takes n time.the recursive call is made to one less element than in the previous call so the overall recurrence relation becomes t(n) = t(n-1) + n. | |
| 54. |
Which of the following sorting algorithm is NOT stable? |
| A. | selection sort |
| B. | brick sort |
| C. | bubble sort |
| D. | merge sort |
| Answer» A. selection sort | |
| Explanation: out of the given options selection sort is the only algorithm which is not stable. it is because the order of identical elements in sorted output may be different from input array. | |
| 55. |
What will be the best case time complexity of recursive selection sort? |
| A. | o(n) |
| B. | o(n2) |
| C. | o(log n) |
| D. | o(n log n) |
| Answer» B. o(n2) | |
| Explanation: selection sort’s algorithm is such that it finds the index of minimum element in each iteration even if the given array is already sorted. thus its best case time complexity becomes o(n2). | |
| 56. |
Recursive selection sort is a comparison based sort. |
| A. | true |
| B. | false |
| Answer» A. true | |
| Explanation: in selection sort we need to compare elements in order to find the minimum element in each iteration. so we can say that it uses comparisons in order to sort the array. thus it qualifies as a comparison based sort. | |
| 57. |
What is the average case time complexity of recursive selection sort? |
| A. | o(n) |
| B. | o(n log n) |
| C. | o(n2) |
| D. | o(log n) |
| Answer» C. o(n2) | |
| Explanation: the overall recurrence relation of recursive selection sort is given by t(n) = t(n-1) + n. it is found to be equal to o(n2). it is unvaried throughout the three cases. | |
| 58. |
What is the bidirectional variant of selection sort? |
| A. | cocktail sort |
| B. | bogo sort |
| C. | gnome sort |
| D. | bubble sort |
| Answer» A. cocktail sort | |
| Explanation: a bidirectional variant of selection sort is called cocktail sort. it’s an algorithm which finds both the minimum and maximum values in the array in every pass. | |
| 59. |
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. | no method is suitable |
| Answer» C. both recursion and iteration | |
| Explanation: both recursion and iteration can be used to find the largest and smallest element in an array. | |
| 60. |
What is the number of swaps required to sort the array arr={5,3,2,4,1} using recursive selection sort? |
| A. | 0 |
| B. | 1 |
| C. | 2 |
| D. | 3 |
| Answer» C. 2 | |
| Explanation: the first swap takes place between 1 and 5. the second swap takes place between 3 and 2 which sorts our array. | |
| 61. |
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. | impossible to find the largest and smallest numbers |
| Answer» C. both recursion and iteration | |
| Explanation: both recursion and iteration can be used to find the largest and smallest | |
| 62. |
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. | normal binary search |
| Answer» A. iterative linear search | |
| Explanation: iterative linear search can be used to search an element in an unsorted array. | |
| 63. |
Consider the array {1,1,1,1,1}. Select the wrong option? |
| A. | iterative linear search can be used to search for the elements in the given array |
| B. | recursive linear search can be used to search for the elements in the given array |
| C. | recursive binary search can be used to search for the elements in the given array |
| D. | no method is defined to search for an element in the given array |
| Answer» D. no method is defined to search for an element in the given array | |
| Explanation: iterative linear search, recursive linear search and recursive binary search can be applied to search for an element in the above given array. | |
| 64. |
What is the time complexity of the above recursive implementation of binary search? |
| A. | o(n) |
| B. | o(2n) |
| C. | o(logn) |
| D. | o(n!) |
| Answer» C. o(logn) | |
| Explanation: the time complexity of the above recursive implementation of binary search is o(logn). | |
| 65. |
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. | normal binary search |
| Answer» A. iterative linear search | |
| Explanation: iterative linear search can be used to search an element in a linked list. | |
| 66. |
Can binary search be applied on a sorted linked list in O(Logn) time? |
| A. | no |
| B. | yes |
| Answer» A. no | |
| Explanation: since linked list doesn’t allow random access, binary search cannot be applied on a sorted linked list in o(logn) | |
| 67. |
Recursive program to raise an integer x to power y uses which of the following algorithm? |
| A. | dynamic programming |
| B. | backtracking |
| C. | divide and conquer |
| D. | greedy algorithm |
| Answer» C. divide and conquer | |
| Explanation: the recursive approach uses divide and conquer algorithm as we break the problem into smaller parts and then solve the smaller parts and finally combine their results to get the overall solution. | |
| 68. |
What is the least time in which we can raise a number x to power y? |
| A. | o(x) |
| B. | o(y) |
| C. | o(log x) |
| D. | o(log y) |
| Answer» D. o(log y) | |
| Explanation: we can optimize the code for finding power of a number by calculating x raised to power y/2 only once and using it depending on whether y is even or odd. | |
| 69. |
What is the advantage of iterative code for finding power of number over recursive code? |
| A. | iterative code requires less time |
| B. | iterative code requires less space |
| C. | iterative code is more compiler friendly |
| D. | it has no advantage |
| Answer» B. iterative code requires less space | |
| Explanation: both iterative and recursive approach can be implemented in log n time but the recursive code requires memory in call stack which makes it less preferable. | |
| 70. |
Recursive approach to find power of a number is preferred over iterative approach. |
| A. | true |
| B. | false |
| Answer» B. false | |
| Explanation: the recursive code requires memory in call stack which makes it less preferable as compared to iterative approach. | |
| 71. |
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» A. to move all disks to some other rod by following rules | |
| Explanation: objective of tower of hanoi problem is to move all disks to some other rod by following the following rules-1) only one disk can be moved at a time. 2) disk can | |
| 72. |
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 |
| Answer» C. t(n) = 2t(n-1)+c | |
| Explanation: as there are 2 recursive calls to n-1 disks and one constant time operation so the recurrence relation will be given by t(n) | |
| 73. |
Tower of hanoi problem can be solved iteratively. |
| A. | true |
| B. | false |
| Answer» A. true | |
| Explanation: iterative solution to tower of hanoi puzzle also exists. its approach depends on whether the total numbers of disks are even or odd. | |
| 74. |
Minimum time required to solve tower of hanoi puzzle with 4 disks assuming one move takes 2 seconds, will be |
| A. | 15 seconds |
| B. | 30 seconds |
| C. | 16 seconds |
| D. | 32 seconds |
| Answer» B. 30 seconds | |
| Explanation: number of moves = 24-1=16- 1=15 | |
| 75. |
Master’s theorem is used for? |
| A. | solving recurrences |
| B. | solving iterative relations |
| C. | analysing loops |
| D. | calculating the time complexity of any code |
| Answer» A. solving recurrences | |
| Explanation: master’s theorem is a direct method for solving recurrences. we can solve any recurrence that falls under any one of the three cases of master’s theorem. | |
| 76. |
How many cases are there under Master’s theorem? |
| A. | 2 |
| B. | 3 |
| C. | 4 |
| D. | 5 |
| Answer» B. 3 | |
| Explanation: there are primarily 3 cases under master’s theorem. we can solve any recurrence that falls under any one of these three cases. | |
| 77. |
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? |
| A. | none of the below |
| B. | t(n) = o(nc log n) |
| C. | t(n) = o(f(n)) |
| D. | t(n) = o(n2) |
| Answer» B. t(n) = o(nc log n) | |
| Explanation: in second case of master’s theorem the necessary condition is that c = logba. if this condition is true then t(n) = o(nc log n) | |
| 78. |
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? |
| A. | none of the below |
| B. | t(n) = o(nc log n) |
| C. | t(n) = o(f(n)) |
| D. | t(n) = o(n2) |
| Answer» C. t(n) = o(f(n)) | |
| Explanation: in third case of master’s theorem the necessary condition is that c > logba. if this condition is true then t(n) = o(f(n)). | |
| 79. |
We can solve any recurrence by using Master’s theorem. |
| A. | true |
| B. | false |
| Answer» B. false | |
| Explanation: no we cannot solve all the recurrences by only using master’s theorem. we can solve only those which fall under the three cases prescribed in the theorem. | |
| 80. |
Under what case of Master’s theorem will the recurrence relation of merge sort fall? |
| A. | 1 |
| B. | 2 |
| C. | 3 |
| D. | it cannot be solved using master’s theorem |
| Answer» B. 2 | |
| Explanation: the recurrence relation of merge sort is given by t(n) = 2t(n/2) + o(n). so we can observe that c = logba so it will fall under case 2 of master’s theorem. | |
| 81. |
Under what case of Master’s theorem will the recurrence relation of stooge sort fall? |
| A. | 1 |
| B. | 2 |
| C. | 3 |
| D. | it cannot be solved using master’s theorem |
| Answer» A. 1 | |
| Explanation: the recurrence relation of stooge sort is given as t(n) = 3t(2/3n) + o(1). it is found too be equal to o(n2.7) using master’s theorem first case. | |
| 82. |
Which case of master’s theorem can be extended further? |
| A. | 1 |
| B. | 2 |
| C. | 3 |
| D. | no case can be extended |
| Answer» B. 2 | |
| Explanation: the second case of master’s theorem can be extended for a case where f(n) | |
| 83. |
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? |
| A. | none of the below |
| B. | t(n) = o(nc log n) |
| C. | t(n)= o(nc (log n)k+1 |
| D. | t(n) = o(n2) |
| Answer» C. t(n)= o(nc (log n)k+1 | |
| Explanation: in the extended second case of master’s theorem the necessary condition is that c = logba. if this condition is true then t(n)= o(nc(log n))k+1. | |
| 84. |
Under what case of Master’s theorem will the recurrence relation of binary search fall? |
| A. | 1 |
| B. | 2 |
| C. | 3 |
| D. | it cannot be solved using master’s theorem |
| Answer» B. 2 | |
| Explanation: the recurrence relation of binary search is given by t(n) = t(n/2) + o(1). so we can observe that c = logba so it will fall under case 2 of master’s theorem. | |
| 85. |
7 T (n/2) + 1/n |
| A. | t(n) = o(n) |
| B. | t(n) = o(log n) |
| C. | t(n) = o(n2log n) |
| D. | cannot be solved using master’s theorem |
| Answer» D. cannot be solved using master’s theorem | |
| Explanation: the given recurrence cannot be solved by using the master’s theorem. it is because in this recurrence relation a < 1 so master’s theorem cannot be applied. | |
| 86. |
Which of the following sorting algorithms is the fastest? |
| A. | merge sort |
| B. | quick sort |
| C. | insertion sort |
| D. | shell sort |
| Answer» B. quick sort | |
| Explanation: quick sort is the fastest known sorting algorithm because of its highly optimized inner loop. | |
| 87. |
Quick sort follows Divide-and-Conquer strategy. |
| A. | true |
| B. | false |
| Answer» A. true | |
| Explanation: in quick sort, the array is divided into sub-arrays and then it is sorted (divide-and-conquer strategy). | |
| 88. |
Which of the following methods is the most effective for picking the pivot element? |
| A. | first element |
| B. | last element |
| C. | median-of-three partitioning |
| D. | random element |
| Answer» C. median-of-three partitioning | |
| Explanation: median-of-three partitioning is the best method for choosing an appropriate pivot element. picking a first, last or random element as a pivot is not much effective. | |
| 89. |
Which is the safest method to choose a pivot element? |
| A. | choosing a random element as pivot |
| B. | choosing the first element as pivot |
| C. | choosing the last element as pivot |
| D. | median-of-three partitioning method |
| Answer» A. choosing a random element as pivot | |
| Explanation: this is the safest method to choose the pivot element since it is very unlikely that a random pivot would consistently provide a poor partition. | |
| 90. |
What is the average running time of a quick sort algorithm? |
| A. | o(n2) |
| B. | o(n) |
| C. | o(n log n) |
| D. | o(log n) |
| Answer» C. o(n log n) | |
| Explanation: the best case and average case analysis of a quick sort algorithm are mathematically found to be o(n log n). | |
| 91. |
Which of the following sorting algorithms is used along with quick sort to sort the sub arrays? |
| A. | merge sort |
| B. | shell sort |
| C. | insertion sort |
| D. | bubble sort |
| Answer» C. insertion sort | |
| Explanation: insertion sort is used along with quick sort to sort the sub arrays. | |
| 92. |
Quick sort uses join operation rather than merge operation. |
| A. | true |
| B. | false |
| Answer» A. true | |
| Explanation: quick sort uses join operation since join is a faster operation than merge. | |
| 93. |
How many sub arrays does the quick sort algorithm divide the entire array into? |
| A. | one |
| B. | two |
| C. | three |
| D. | four |
| Answer» B. two | |
| Explanation: the entire array is divided into two partitions, 1st sub array containing elements less than the pivot element and 2nd sub array containing elements greater than the pivot element. | |
| 94. |
The shortest distance between a line and a point is achieved when? |
| A. | a line is drawn at 90 degrees to the given line from the given point |
| B. | a line is drawn at 180 degrees to the given line from the given point |
| C. | a line is drawn at 60 degrees to the given line from the given point |
| D. | a line is drawn at 270 degrees to the given line from the given point |
| Answer» A. a line is drawn at 90 degrees to the given line from the given point | |
| Explanation: the shortest distance between a line and a point is achieved when a line is drawn at 90 degrees to the given line from the given point. | |
| 95. |
What is the shortest distance between the line given by -2x + 3y + 4 = 0 and the point (5,6)? |
| A. | 4.5 units |
| B. | 5.4 units |
| C. | 4.3 units |
| D. | 3.3 units |
| Answer» D. 3.3 units | |
| Explanation: the shortest distance between a line and a point is given by the formula (ax1+by1+c)/(√a2+b2). using this formula we get the answer 3.3 units. | |
| 96. |
What is the distance between the lines 3x- 4y+7=0 and 3x-4y+5=0? |
| A. | 1 unit |
| B. | 0.5 unit |
| C. | 0.8 unit |
| D. | 0.4 unit |
| Answer» D. 0.4 unit | |
| Explanation: as the given lines are parallel so the distance between them can be calculated by using the formula (c1- c2)/(√a2+b2). so we get the distance as 0.4 unit. | |
| 97. |
What will be the slope of the line given by ax + by + c = 0? |
| A. | -a/b |
| B. | -b/a |
| C. | -c/a |
| D. | a/c |
| Answer» A. -a/b | |
| Explanation: the slope of a line given by the equation ax + by + c=0 has the slope of -a/b. so two lines having the same ratio of the coefficient of x and y will be parallel to each other. | |
| 98. |
What will be the slope of the line given by 10x + 5y + 8=0? |
| A. | -5 |
| B. | -2 |
| C. | -1.25 |
| D. | 5 |
| Answer» B. -2 | |
| Explanation: the slope of a line given by the equation ax + by + c=0 has the slope of -a/b. so the slope of the given line will be -2. | |
| 99. |
Which of the following areas do closest pair problem arise? |
| A. | computational geometry |
| B. | graph colouring problems |
| C. | numerical problems |
| D. | string matching |
| Answer» A. computational geometry | |
| Explanation: closest pair problem arises in two most important areas- computational geometry and operational research. | |
| 100. |
What is the runtime efficiency of using brute force technique for the closest pair problem? |
| A. | o(n) |
| B. | o(n log n) |
| C. | o(n2) |
| D. | o(n3 log n) |
| Answer» C. o(n2) | |
| Explanation: the efficiency of closest pair algorithm by brute force technique is mathematically found to be o(n2). | |
Done Studing? Take A Test.
Great job completing your study session! Now it's time to put your knowledge to the test. Challenge yourself, see how much you've learned, and identify areas for improvement. Don’t worry, this is all part of the journey to mastery. Ready for the next step? Take a quiz to solidify what you've just studied.