Showing posts with label Divide and Merge operation. Show all posts
Showing posts with label Divide and Merge operation. Show all posts

Friday, October 09, 2020

Algorithms Multiple choice questions

 1.Algorithm is a ________________.
 Processing of problem
 Step by Step method to solve a problem
 Graphical method
 None of the above

2.Algorithm should have _______________ or more output.
 Zero
 One
 Two
 Three

3.Which is correct according to increasing order of growth rate
 n, n! , nlogn , n^2 , n^3 , n^5 , 2^n
 nlogn , n^2 , n^3 , n^5 , 2^n , n!
 n , nlogn , n^2 , n^3 , n^5 , 2^n , n!
 n , nlogn , n^2 , n^3 , n^5 ,  n!, 2^n

4.Big Oh! notation looks for____________ value.
 Maximum
 Minimum
 Average
 Mean

5.Omega (Ω) notation looks for ___________ value.
 Maximum
 Minimum
 Average
 Mean

6.A function which calls itself is called __________ function.
 Null
 Default
 Recursive
 Non recursive

7. _____________ method is used to solve recurrence.
 Main
 Major
 Divide
 Master

8.Time complexity of binary search is _____________.
 O(n)
 O(logn)
 O(nlogn)
 None of the above

9.The condition for applying binary search is _______________.
 Elements should be sorted
 Elements should be unsorted
 Elements should have priority
 None of the above

10.best case of binary search, the searching element is at _______________ position.
 First
 Second
 Last
 Middle

11.The __________________of an algorithm is the amount of computer time it needs to run to completion.
 Time complexity
 Space complexity
 Time period
 None of the above

12.The minimum number of comparisons required finding the minimum and maximum of 100 numbers is ________
 99
 100
 101
 None of the above

13.Divide and Merge operation is done in ____________.
 Binary search
 Merge sort
 Quicksort
 Heap sort

14.Which sort takes an extra array.
 Binary search
 Merge sort
 Quicksort
 Heap sort

15.Recurrence equation of merge sort is _______________.
 T(n) = T(n/2) + O(n)
 T(n) = 2T(n/2) + O(n)
 T(n) = 3T(n/2) + O(n)
 None of the above

16.Pivot element is used in ___________ sort.
 Binary search
 Mergesort
 Quick sort
 Heap sort

17.Partition operation is done in _____________ sort.
 Binary search
 Mergesort
 Quick sort
 Heap sort

18.Quick sort algorithm is an example of
 Greedy
 Improved search
 Dynamic Programming
 Divide and Conquer

19.Time complexity of merge sort is ___________.
 O(n)
 O(logn)
 O(nlogn)
 None of the above

20.Time complexity of quick sort is depends on _____________.
 O(n)
 O(logn)
 O(nlogn)
 None of the above

21.Merge sort uses which of the following technique to implement sorting?
 Backtracking
 Greedy algorithm
 Divide and conquer
 Dynamic programming

22.What is the average case time complexity of merge sort ?
 O(n log n)
 O(n^2)
 O(n^2log n)
 O(n log n2)

23.What is the auxiliary space complexity of merge sort?
 O(1)
 O(log n)
 O(n)
 O(n log n)

24.Merge sort can be implemented using O(1) auxiliary space.
 True
 False

25.What is the worst case time complexity of merge sort?
 O(n log n)
 O(n^2)
 O(n^2 log n)
 O(n logn2 )

26.Which of the following method is used for sorting in merge sort?
 Merging
 Partitioning
 Selection
 Exchanging

27.What will be the best case time complexity of merge sort ?
 O(n log n)
 O(n2)
 O(n2 logn)
 O(n logn2)

28. Which of the following is not a variant of merge sort ?
 In-place merge sort
 Bottom up merge sort
 Top down merge sort
 Linear merge sort

29.Choose the incorrect statement about merge sort from the following?
 It is a comparison based sort
 It is an adaptive algorithm
 It is not an in place algorithm
 It is stable algorithm

30.Which of the following is not in place sorting algorithm?
 Merge sort
 Quick sort
 Heap sort
 Insertion sort

31.Which of the following is not a stable sorting algorithm?
 Quick sort
 Cocktail sort
 Bubble sort
 Merge sort

32.Which of the following stable sorting algorithm takes the least time when applied to an almost sorted array?
 Quick sort
 Insertion sort
 Selection sort
 Merge sort

33.Merge sort is preferred for arrays over linked lists.
 True
 False

34.Which of the following sorting algorithm makes use of merge sort?
 Tim sort
 Intro sort
 Bogo sort
 Quick sort

35.Choose the correct code for merge sort.
 void merge_sort(int arr[], int left, int right) { if (left > right) { int mid = (right-left)/2; merge_sort(arr, left, mid); merge_sort(arr, mid+1, right); merge(arr, left, mid, right); //function to merge sorted arrays } }
 void merge_sort(int arr[], int left, int right) { if (left < right) { int mid = left+(right-left)/2; merge_sort(arr, left, mid); merge_sort(arr, mid+1, right); merge(arr, left, mid, right); //function to merge sorted arrays } }
 void merge_sort(int arr[], int left, int right) { if (left < right) { int mid = left+(right-left)/2; merge(arr, left, mid, right); //function to merge sorted arrays merge_sort(arr, left, mid); merge_sort(arr, mid+1, right); } }
 void merge_sort(int arr[], int left, int right) { if (left < right) { int mid = (right-left)/2; merge(arr, left, mid, right); //function to merge sorted arrays merge_sort(arr, left, mid); merge_sort(arr, mid+1, right); } }

36. Which of the following sorting algorithm does not use recursion?
 Quick sort
 Merge sort
 Heap sort
 Bottom up merge sort

37.Which of the following sorting algorithms is the fastest ?
 Merge sort
 Quick sort
 Insertion sort
 Shell sort

38.Quick sort follows Divide-and-Conquer strategy.
 True
 False

39.What is the worst case time complexity of a quick sort algorithm?
 O(N)
 O(N log N)
 O(N^2 )
 O(log N)

40.Which of the following methods is the most effective for picking the pivot element ?
 First element
 Last element
 Median-of-three partitioning
 Random element

41.Find the pivot element from the given input using median-of-three partitioning method. 8, 1, 4, 9, 6, 3, 5, 2, 7, 0.
 8
 7
 9
 6

42.Which is the safest method to choose a pivot element ?
 Choosing a random element as pivot
 Choosing the first element as pivot
 Choosing the last element as pivot
 Median-of-three partitioning method

43.What is the average running time of a quick sort algorithm ?
 O(N^2 )
 O(N)
 O(N log N)
 O(log N)

44.Which of the following sorting algorithms is used along with quick sort to sort the sub arrays?
 Merge sort
 Shell sort
 Insertion sort
 Bubble sort

45.Quick sort uses join operation rather than merge operation.
 True
 False

46.How many sub arrays does the quick sort algorithm divide the entire array into?
 One
 Two
 Three
 Four

47.Which is the worst method of choosing a pivot element ?
 First element as pivot
 Last element as pivot
 Median-of-three partitioning
 Random element as pivot

48.Which among the following is the best cut-off range to perform insertion sort within a quick sort ?
 N=0-5
 N=5-20
 N=20-30
 N>30

49.Recursion is a method in which the solution of a problem depends on ____________
 Larger instances of different problems
 Larger instances of the same problem
 Smaller instances of the same problem
 Smaller instances of different problems

50.Which of the following problems can’t be solved using recursion?
 Factorial of a number
 Nth fibonacci number
 Length of a string
 Problems without base case

Search Aptipedia