Design And Analysis Of Algorithms Set 3

Computer Science Engineering (CSE)

Practice Mode Previous Next
On This Page

This set of Design and Analysis of Algorithms Multiple Choice Questions & Answers (MCQs) focuses on Design And Analysis Of Algorithms Set 3

Q1 | What is the time complexity of the program to reverse stack when linked list is used for its implementation?
  • o(n)
  • o(n log n)
  • o(n2)
  • o(log n)
Answer: o(n)
Explaination:
as a linked list takes o(n) time for getting reversed thus linked list version of stack will also take the same time.
Q2 | Which of the following takes O(n) time in worst case in array implementation of stack?
  • pop
  • push
  • isempty
  • pop, push and isempty takes constant time
Answer: pop, push and isempty takes constant time
Explaination:
functions pop, push and isempty all are implemented in constant time in worst case.
Q3 | What will be the time complexity of the code to reverse stack recursively?
  • o(n)
  • o(n log n)
  • o(log n)
  • o(n2)
Answer: o(n2)
Explaination:
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).
Q4 | Which of the following sorting algorithm has best case time complexity of O(n2)?
  • bubble sort
  • selection sort
  • insertion sort
  • stupid sort
Answer: selection sort
Explaination:
selection sort is not an adaptive sorting algorithm. it finds the index of minimum element in each iteration even if the
Q5 | Which of the following is the biggest advantage of selection sort?
  • its has low time complexity
  • it has low space complexity
  • it is easy to implement
  • it requires only n swaps under any condition
Answer: it requires only n swaps under any condition
Explaination:
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.
Q6 | What will be the recurrence relation of the code of recursive selection sort?
  • t(n) = 2t(n/2) + n
  • t(n) = 2t(n/2) + c
  • t(n) = t(n-1) + n
  • t(n) = t(n-1) + c
Answer: t(n) = t(n-1) + n
Explaination:
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.
Q7 | Which of the following sorting algorithm is NOT stable?
  • selection sort
  • brick sort
  • bubble sort
  • merge sort
Answer: selection sort
Explaination:
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.
Q8 | What will be the best case time complexity of recursive selection sort?
  • o(n)
  • o(n2)
  • o(log n)
  • o(n log n)
Answer: o(n2)
Explaination:
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).
Q9 | Recursive selection sort is a comparison based sort.
  • true
  • false
Answer: true
Explaination:
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.
Q10 | What is the average case time complexity of recursive selection sort?
  • o(n)
  • o(n log n)
  • o(n2)
  • o(log n)
Answer: o(n2)
Explaination:
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.
Q11 | What is the bidirectional variant of selection sort?
  • cocktail sort
  • bogo sort
  • gnome sort
  • bubble sort
Answer: cocktail sort
Explaination:
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.
Q12 | Which of the following methods can be used to find the largest and smallest element in an array?
  • recursion
  • iteration
  • both recursion and iteration
  • no method is suitable
Answer: both recursion and iteration
Explaination:
both recursion and iteration can be used to find the largest and smallest element in an array.
Q13 | What is the number of swaps required to sort the array arr={5,3,2,4,1} using recursive selection sort?
  • 0
  • 1
  • 2
  • 3
Answer: 2
Explaination:
the first swap takes place between 1 and 5. the second swap takes place between 3 and 2 which sorts our array.
Q14 | Which of the following methods can be used to find the largest and smallest number in a linked list?
  • recursion
  • iteration
  • both recursion and iteration
  • impossible to find the largest and smallest numbers
Answer: both recursion and iteration
Explaination:
both recursion and iteration can be used to find the largest and smallest
Q15 | Which of the following techniques can be used to search an element in an unsorted array?
  • iterative linear search
  • recursive binary search
  • iterative binary search
  • normal binary search
Answer: iterative linear search
Explaination:
iterative linear search can be used to search an element in an unsorted array.
Q16 | Consider the array {1,1,1,1,1}. Select the wrong option?
  • iterative linear search can be used to search for the elements in the given array
  • recursive linear search can be used to search for the elements in the given array
  • recursive binary search can be used to search for the elements in the given array
  • no method is defined to search for an element in the given array
Answer: no method is defined to search for an element in the given array
Explaination:
iterative linear search, recursive linear search and recursive binary search can be applied to search for an element in the above given array.
Q17 | What is the time complexity of the above recursive implementation of binary search?
  • o(n)
  • o(2n)
  • o(logn)
  • o(n!)
Answer: o(logn)
Explaination:
the time complexity of the above recursive implementation of binary search is o(logn).
Q18 | Which of the following methods can be used to search an element in a linked list?
  • iterative linear search
  • iterative binary search
  • recursive binary search
  • normal binary search
Answer: iterative linear search
Explaination:
iterative linear search can be used to search an element in a linked list.
Q19 | Can binary search be applied on a sorted linked list in O(Logn) time?
  • no
  • yes
Answer: no
Explaination:
since linked list doesn’t allow random access, binary search cannot be applied on a sorted linked list in o(logn)
Q20 | Recursive program to raise an integer x to power y uses which of the following algorithm?
  • dynamic programming
  • backtracking
  • divide and conquer
  • greedy algorithm
Answer: divide and conquer
Explaination:
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.
Q21 | What is the least time in which we can raise a number x to power y?
  • o(x)
  • o(y)
  • o(log x)
  • o(log y)
Answer: o(log y)
Explaination:
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.
Q22 | What is the advantage of iterative code for finding power of number over recursive code?
  • iterative code requires less time
  • iterative code requires less space
  • iterative code is more compiler friendly
  • it has no advantage
Answer: iterative code requires less space
Explaination:
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.
Q23 | Recursive approach to find power of a number is preferred over iterative approach.
  • true
  • false
Answer: false
Explaination:
the recursive code requires memory in call stack which makes it less preferable as compared to iterative approach.
Q24 | What is the objective of tower of hanoi puzzle?
  • to move all disks to some other rod by following rules
  • to divide the disks equally among the three rods by following rules
  • to move all disks to some other rod in random order
  • to divide the disks equally among three rods in random order
Answer: to move all disks to some other rod by following rules
Explaination:
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
Q25 | Recurrence equation formed for the tower of hanoi problem is given by                    
  • t(n) = 2t(n-1)+n
  • t(n) = 2t(n/2)+c
  • t(n) = 2t(n-1)+c
  • t(n) = 2t(n/2)+n
Answer: t(n) = 2t(n-1)+c
Explaination:
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)
Previous Next