Методы сортировки массивов (стр. 4 из 4)
15.1. на каждом шаге просмотру подвергается несортированная правая часть массива. В ней ищется очередной максимальный элемент. Если он найден, то производится его перемещение на место крайнего левого элемента несортированной правой части массива.
15.2. на каждом шаге просмотру подвергается несортированная правая часть массива. В ней ищется очередной минимальный элемент. Если он не найден, то производится его перемещение на место крайнего левого элемента несортированной правой части массива.
15.3. на каждом шаге просмотру подвергается несортированная правая часть массива. В ней ищется очередной минимальный элемент. Если он найден, то производится его перемещение на место крайнего правого элемента несортированной левой части массива.
15.4. на каждом шаге просмотру подвергается несортированная правая часть массива. В ней ищется очередной минимальный элемент. Если он найден, то производится его перемещение на место крайнего левого элемента несортированной правой части массива.
16. Если сортировку выбором применить для массива "bdac", то будут получены следующие проходы
16.1. первый проход: c d b a; второй проход: a b b c; третий проход: a b c d.
16.2. первый проход: a d b c; второй проход: a b d c; третий проход: a b c d.
16.3. первый проход: a d b c; второй проход: a cdb; третий проход: a b c d.
16.4. первый проход: a d b c; второй проход: a b d c; третий проход: d b c a.
17. Как и в сортировке массива пузырьковым методом в сортировке массива прямым выбором внешний цикл
17.1. выполняется n раз, а внутренний цикл выполняется n/2 раз.
17.2. выполняется n-1 раз, а внутренний цикл выполняется n раз.
17.3. выполняется n-1 раз, а внутренний цикл выполняется n/2 раз.
17.4. выполняется n раз, а внутренний цикл выполняется n раз.
18. Вставить во фрагмент кода сортировки массива прямым выбором, вместо знака «вопроса», верное неравенство:
for i := 1 to n - 1 dobegin min := i; for j := i + 1 to n do if ? then min := j; t := a[i]; a[i] := a[min]; a[min] := t end;18.1. a[min] > a[j].
18.2. a[min] = a[j].
18.3. a[min] < a[j].
18.4. a[min] <>a[j].
19. При сортировке массива методом прямого выбора в лучшем случае (когда исходный массив уже упорядочен) потребуется поменять местами только ?, а каждая операция обмена требует три операции пересылки.
Вставьте вместо знака «вопрос» верный вариант.
19.1. n-элементов.
19.2. (n-1)-элементов.
19.3. n/2-элементов.
19.4. 2*n-элементов.
20. Алгоритм сортировки массива методом пирамидального выбора предназначен для сортировки последовательности чисел, которые
20.1. являются отображением в памяти дерева специальной структуры — пирамиды.
20.2. являются отображением в памяти дерева специальной структуры — дерева.
20.3. являются отображением в памяти пирамиды специальной структуры — пирамиды.
20.4. являются отображением в памяти куста специальной структуры — дерева.
21. На рисунке изображено несколько деревьев, из которых лишь одноявляется пирамидой.
21.1. Т3.
21.2. Т1.
21.3. Т4.
21.4. Т2.
22. Пирамида, показанная на рисунке (одна из четырех), в памяти будет представлена следующим массивом:
22.1. 3, 2, 7, 11, 5, 8, 14, 9, 27.
22.2. 2, 3, 5, 7, 8, 9, 11, 14, 27.
22.3. 27, 14, 11, 9, 8, 7, 5, 3, 2.
22.4. 27, 9, 14, 8, 5, 11, 7, 2, 3.
23. На каждом из n шагов, требуемых для сортировки массива методом пирамидального выбора, нужно
23.1. n*log n (двоичных) сравнений.
23.2. (log n)/2 (двоичных) сравнений.
23.3. log n (двоичных) сравнений.
23.4. 2 * log n (двоичных) сравнений.
24. Идея алгоритма сортировки массива прямым обменом заключается в том, что
24.1. если номер позиции большего из элементов больше номера позиции меньшего элемента, то меняем их местами.
24.2. если номер позиции меньшего из элементов больше номера позиции большего элемента, то не меняем их местами.
24.3. если номер позиции меньшего из элементов больше номера позиции большего элемента, то оставляем их на месте.
24.4. если номер позиции меньшего из элементов больше номера позиции большего элемента, то меняем их местами.
25. При использовании метода пузырьковой сортировки массива требуется самое большее
25.1. n проходов.
25.2. (n-1) проходов.
25.3. n/2 проходов.
25.4. 2*n проходов.
26. При сортировке массива методом прямого обмена или методом пузырьковой сортировки после каждого прохода через таблицу может быть сделана проверка, были ли совершены перестановки в течение данного прохода. Если перестановок не было, то это означает, что
26.1. таблица не отсортирована и требует дальнейших проходов.
26.2. таблица уже отсортирована и требует дальнейших проходов.
26.3. таблица уже отсортирована и дальнейших проходов не требуется.
26.4. таблица не отсортирована и дальнейших проходов не требуется.
27. Сортировка массива пузырьковым методом обладает одной особенностью: расположенный не на своем месте в конце массива элемент
27.1. достигает своего места за один проход.
27.2. достигает своего места за два прохода.
27.3. достигает своего места за три прохода.
27.4. достигает своего места за N проходов.
28. Сортировка массива пузырьковым методом обладает одной особенностью: элемент, расположенный в начале массива
28.1. очень быстро достигает своего места.
28.2. очень медленно достигает своего места.
28.3. не достигает своего места.
28.4. достигает середины массива.
29. В основе метода внутренней сортировки массива лежит процедура слияния
29.1. двух упорядоченных таблиц.
29.2. одной упорядоченной таблицы.
29.3. трех упорядоченных таблиц.
29.4. двух неупорядоченных таблиц.
30. Сущность сортировки массива слиянием состоит в том, что упорядочиваемая таблица разделяется на равные группы элементов. Группы упорядочиваются, а затем
30.1. попарно сливаются, образуя три новые группы, содержащие втрое больше элементов.
30.2. попарно сливаются, образуя две новые группы, содержащие вдвое больше элементов.
30.3. попарно сливаются, образуя новые группы, содержащие втрое больше элементов.
30.4. попарно сливаются, образуя новые группы, содержащие вдвое больше элементов.
В предложенных тестах правильные ответы выделены курсивом.
Заключение.
В данной курсовой работе рассматриваются задачи сортировки, постановка задачи сортировки массивов. А также основная часть отведена рассмотрению методов: а именно, простые методы сортировки (сортировка с помощью прямого включения, сортировка с помощью прямого выбора, сортировка с помощью прямого обмена) и улученные методы сортировки массивов (метод Шелла, сортировка с помощью дерева, сортировка с помощью разделения). Предложен анализ к каждому из методов сортировки массивов. Разработаны тестовые задания по сортировкам массивов (30 заданий).
1. http://www.books.everonit.ru
2. http://ru.wikipedia.org
3. http://khpi-iip.mipk.kharkiv.edu/library/
4. http://www.mgopu.ru/
5. http://www.compdoc.ru/prog/pascal/
6. http://www.cyberguru.ru/programming/