Sail E0 Webinar

MCQs

Total Questions : 10
Question 1. In a computational complexity theory, a problem with decision making is said to be NP-complete when it is both in NP and NP-hard. What does NP mean?
  1.    Non Polynomial time
  2.    Non-deterministic Probabilistic
  3.    Non-deterministic Polynomial time
  4.    Non Probabilistic time
 Discuss Question
Answer: Option C. -> Non-deterministic Polynomial time


Although any given solution to an NP-complete problem can be validated quickly in polynomial time; there is no way to efficiently locate a solution to begin with. The unique characteristic of NP-complete problems is that no fast solution to them is known and hence NP-complete problems are said to be non-deterministic polynomial time.


Question 2. What is the worst case complexity of selection sort?
  1.    O(nlogn)
  2.    O(logn)
  3.    O(n)
  4.    O(n2)
 Discuss Question
Answer: Option D. -> O(n2)


Selection sort creates a sub-list, LHS of the 'min' element is already sorted and RHS is yet to be sorted. Starting with the first element the 'min' element moves towards the final element.


Question 3. What is the average case complexity of selection sort?
  1.    O(nlogn)
  2.    O(logn)
  3.    O(n)
  4.    O(n2)
 Discuss Question
Answer: Option D. -> O(n2)


In the average case, even if the input is partially sorted, selection sort behaves as if the entire array is not sorted. Selection sort is insensitive to input.


Question 4. What is the worst case complexity of bubble sort?
  1.    O(nlogn)
  2.    O(logn)
  3.    O(n)
  4.    O(n2)
 Discuss Question
Answer: Option D. -> O(n2)


Bubble sort works by starting from the first element and swapping the elements if required in each iteration.


Question 5. What is the disadvantage of selection sort?
  1.    It requires auxiliary memory
  2.    It is not scalable
  3.    It can be used for small keys
  4.    None of the mentioned
 Discuss Question
Answer: Option B. -> It is not scalable


As the input size increases, the performance of selection sort decreases.


Question 6. The given array is arr = {1,2,4,3}. Bubble sort is used to sort the array elements. How many iterations will be done to sort the array?
  1.    4
  2.    2
  3.    1
  4.    0
 Discuss Question
Answer: Option A. -> 4


Even though the first two elements are already sorted, bubble sort needs 4 iterations to sort the given array.


Question 7. What is the best case complexity of QuickSort?
  1.    O(nlogn)
  2.    O(logn)
  3.    O(n)
  4.    O(n2)
 Discuss Question
Answer: Option A. -> O(nlogn)


The array is partitioned into equal halves, using the Divide and Conquer master theorem, the complexity is found to be O(nlogn).


Question 8. What is the advantage of bubble sort over other sorting techniques?
  1.    It is faster
  2.    Consumes less memory
  3.    Detects whether the input is already sorted
  4.    All of the mentioned
 Discuss Question
Answer: Option C. -> Detects whether the input is already sorted


Bubble sort is one of the simplest sorting techniques and perhaps the only advantage it has over other techniques is that it can detect whether the input is already sorted.


Question 9. The given array is arr = {2,3,4,1,6}. What are the pivots that are returned as a result of subsequent partitioning?
  1.    1 and 3
  2.    3 and 1
  3.    2 and 6
  4.    6 and 2
 Discuss Question
Answer: Option A. -> 1 and 3


The call to partition returns 1 and 3 as the pivot elements.


Question 10. In addition to the pancake sorting problem, there is the case of the burnt pancake problem in which we are dealing with pancakes (discs) that are burnt on one side only. In this case it is taken that the burnt side must always end up _______
  1.    Faced down
  2.    Faced up
  3.    It doesn't matter
  4.    Both sides are burnt
 Discuss Question
Answer: Option A. -> Faced down


A varation of this pancake is with burnt pancakes. Here each pancake has a burnt side and all pancakes must, in addition, end up with the burnt side on bottom. It is a more difficult version of the regular pancake problem.


Latest Videos

Latest Test Papers