Q31. The selection sort algorithm repeatedly moves the smallest element from the
ID: 3847584 • Letter: Q
Question
Q31. The selection sort algorithm repeatedly moves the smallest element from the unsorted list to the beginning of the unsorted list.
a. true
b. false
Q32. Heap sort, for array-based lists, is of the order ____ even in the worst case.
a. O(log n)
b. O(n log n)
c. O(log2n)
d. O(n log2n)
Q33. In quick sort, the list is partitioned into two sublists by selecting a(n) ____, and the two sublists are then sorted and combined into one list in such a way so that the combined list is sorted.
a. marker
b. pivot
c. midpoint
d. average
Q34. Quick sort uses ____ for implementation.
a. recursion
b. traversal
c. heaps
d. queues
Q35. The selection sort algorithm sorts a list by selecting the smallest element in the (unsorted portion of the) list, and then moving this smallest element to the top of the (unsorted) list.
a. true
b. false
Q36. It can be shown that the average number of key comparisons for insertion sort is ____.
a. O(n)
b. O(n2)
c. O(n log n)
d. O(n2 log n)
Q37. Merge sort divides the list into ____ sublists of nearly equal size.
a. two
b. three
c. four
d. five
Q38. In quick sort, the average case for the number of swaps is O(n log2n).
a. true
b. false
Q39. Selection sort always starts with the middle element of the list.
a. true
b. false
Q40. Suppose that L is a list of n elements, where n > 0. Let W(n) denote the number of key comparisons in the worse case of merge sort. Which of the following is true?
a. W(n) = O(n log n)
b. W(n) = O(n log2n)
c. W(n) = O(n2 log2n)
d. W(n) = O(log n)
Explanation / Answer
Q31)Answer:True
Explanation:
The selection sort algorithm repeatedly moves the smallest element from the unsorted list to the beginning of the unsorted list.
The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning. The algorithm maintains two subarrays in a given array.
1) The subarray which is already sorted.
2) Remaining subarray which is unsorted.
In every iteration of selection sort, the minimum element (considering ascending order) from the unsorted subarray is picked and moved to the sorted subarray.
Example:
Q32.Answer: d. O(n log2n)
Explanation:
Heap sort, for array-based lists, is of the order O(n log2n) even in the worst case.
Q33.Answer:b. pivot
Explanation:
Q34.Answer: a. recursion
Explanation:
Quick sort uses recursion for implementation.
Q35.Answer:a. true
Explanation:
The selection sort algorithm sorts a list by selecting the smallest element in the (unsorted portion of the) list, and then moving this smallest element to the top of the (unsorted) list.
Q36.Answer:b. O(n2)
Explanation:
Insertion Sort is in worst case, O(N2)
Q37.Answer:a.two
Explanation:
Merge sort is another comparison-based sorting algorithm. The unsorted list is first divided into two sublists of approximately half the size. Each list is then sorted recursively by re-applying the merge sort. Lastly, the two sublists are merged together back into one sorted list.
39)Answer:b. false
Explanation:
The selection sort algorithm sorts a list of values by successively putting values in their final, sorted positions. • Consider a list of numeric values that should be in ascending (increasing) order:
1. Scan the entire list and find the smallest value.
2. Exchange that value with the value in the first position of the list.
3. Scan the list, omitting the first value, and find the smallest value.
4. Exchange that value with the value in the second position of the list.
5. Scan the list, omitting the first two values, and find the smallest value.
6. Exchange that value with the value in the third position of the list.
7. Continue this process for all but the last position in the list, which will contain the largest value
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.