Deck 11: Sorting
سؤال
سؤال
سؤال
سؤال
سؤال
سؤال
سؤال
سؤال
سؤال
سؤال
سؤال
سؤال
سؤال
سؤال
سؤال
سؤال
سؤال
سؤال
سؤال
سؤال
سؤال
سؤال
سؤال
سؤال
سؤال
فتح الحزمة
قم بالتسجيل لفتح البطاقات في هذه المجموعة!
Unlock Deck
Unlock Deck
1/25
العب
ملء الشاشة (f)
Deck 11: Sorting
1
__________ is the process of rearranging the data in an array or container so that the data elements are in increasing (or decreasing) order.
Sorting
2
In a selection sort, there are at most __________ exchanges.
A) 1
B) log n
C) n
D) n - 1
A) 1
B) log n
C) n
D) n - 1
n
3
If the array happens to be sorted before selection sort begins, no exchanges will be required.
True
4
A(n) __________ sort compares adjacent array elements and exchanges their values if they are out of order.
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 25 في هذه المجموعة.
فتح الحزمة
k this deck
5
In the worst case scenario, the number of comparisons performed by a bubble sort is O(__________).
A) n
B) n log n
C) n2
D) n3
A) n
B) n log n
C) n2
D) n3
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 25 في هذه المجموعة.
فتح الحزمة
k this deck
6
If the array bubble sort is applied to a sorted array, the number of exchanges is O(__________).
A) 0
B) 1
C) log n
D) n
A) 0
B) 1
C) log n
D) n
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 25 في هذه المجموعة.
فتح الحزمة
k this deck
7
The __________ sort is a quadratic sorting algorithm based on the technique used by card players to arrange a hand of cards.
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 25 في هذه المجموعة.
فتح الحزمة
k this deck
8
In the best case scenario for insertion sort, the maximum number of comparisons is O(__________).
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 25 في هذه المجموعة.
فتح الحزمة
k this deck
9
A shift in an insertion sort requires the movement of only one item, whereas in a bubble sort or a selection sort an exchange involves a temporary item and requires the movement of __________ items.
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 25 في هذه المجموعة.
فتح الحزمة
k this deck
10
The error written into KW::insert function below can be corrected with the code __________.

A) (next_pos != first || *next_pos < *(next_pos - 1))
B) (next_pos != first && *(next_pos - 1)< *next_pos)
C) std::iter_swap(next_pos - 1, next_pos)
D) --next_post;

A) (next_pos != first || *next_pos < *(next_pos - 1))
B) (next_pos != first && *(next_pos - 1)< *next_pos)
C) std::iter_swap(next_pos - 1, next_pos)
D) --next_post;
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 25 في هذه المجموعة.
فتح الحزمة
k this deck
11
When comparing selection sort, bubble sort, and insertion sort, we can observe that __________ sort gives the best performance for most arrays, because it takes advantage of any partial sorting that is in the array and uses less costly shifts instead of exchanges to rearrange array elements.
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 25 في هذه المجموعة.
فتح الحزمة
k this deck
12
A variation on insertion sort, known as Shell sort, has O(__________) or better performance.
A) 1
B) n3/2
C) n2
D) n3
A) 1
B) n3/2
C) n2
D) n3
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 25 في هذه المجموعة.
فتح الحزمة
k this deck
13
Suppose the growth rate of a sorting routine is O(n log n). If the sorting routine is applied to an array with 1,024 items, we can expect it to perform about __________ operations.
A) 10
B) 1,024
C) 10,240
D) 1,048,576
A) 10
B) 1,024
C) 10,240
D) 1,048,576
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 25 في هذه المجموعة.
فتح الحزمة
k this deck
14
It is known that Shell sort is O(n2) if successive powers of __________ are used for the gap value.
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 25 في هذه المجموعة.
فتح الحزمة
k this deck
15
The time and space requirements for a single merge operation are each O(__________)
A) log n
B) n
C) n log n
D) n3/2
A) log n
B) n
C) n log n
D) n3/2
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 25 في هذه المجموعة.
فتح الحزمة
k this deck
16
The total effort to reconstruct a sorted array through merging is O(__________).
A) log n
B) n
C) n log n
D) n2
A) log n
B) n
C) n log n
D) n2
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 25 في هذه المجموعة.
فتح الحزمة
k this deck
17
Whenever a recursive function is called, a copy of the local variables is saved on the run-time __________.
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 25 في هذه المجموعة.
فتح الحزمة
k this deck
18
The merge sort algorithm requires, at least temporarily, n log n extra storage locations.
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 25 في هذه المجموعة.
فتح الحزمة
k this deck
19
A max heap is a data structure that maintains the largest value at the top.
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 25 في هذه المجموعة.
فتح الحزمة
k this deck
20
For a node at position p in a heap, the right child is at __________.
A) 2p - 1
B) 2p
C) 2p + 1
D) 2p + 2
A) 2p - 1
B) 2p
C) 2p + 1
D) 2p + 2
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 25 في هذه المجموعة.
فتح الحزمة
k this deck
21
Because we have n items to insert and each insert (or remove) is O(log n), building a heap is O(__________).
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 25 في هذه المجموعة.
فتح الحزمة
k this deck
22
The process by which quicksort rearranges an array into two parts around a pivot is called __________.
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 25 في هذه المجموعة.
فتح الحزمة
k this deck
23
If the pivot value generated by quicksort is a random value selected from the current sequence, then statistically it is expected that one-quarter of the items in the sequence will be less than the pivot value and three-quarters will be greater than the pivot value.
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 25 في هذه المجموعة.
فتح الحزمة
k this deck
24
In the best case scenario of quicksort, the partitioning process at each level involves moving every element into its correct partition, so quicksort is O(__________).
A) log n
B) n
C) n log n
D) n2
A) log n
B) n
C) n log n
D) n2
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 25 في هذه المجموعة.
فتح الحزمة
k this deck
25
If the pivot used by quicksort is always the first element of an input array, the worst possible performance occurs when the input array is sorted.
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 25 في هذه المجموعة.
فتح الحزمة
k this deck