Программирование

Упражнение 1:

Номер 1

Назовем алгоритм сортировки оптимальным, если он
работает за время O(n log₂ n) даже при
самом плохом входе. Среди перечисленных ниже алгоритмов
сортировки отметьте оптимальные.

Ответ:

(1) Пузырьковая сортировка.

(2) Сортировка прямым выбором.

(3) Быстрая сортировка QuickSort.

(4) Сортировка кучей HeapSort.

Номер 2

Какие из перечисленных ниже алгоритмов сортировки
работают в среднем
за время O(n log₂ n)?
Отметьте все правильные ответы.

Ответ:

(1) Пузырьковая сортировка.

(2) Сортировка прямым выбором.

(3) Быстрая сортировка QuickSort.

(4) Сортировка кучей HeapSort.

Номер 3

Пусть мы имеем набор из n элементов,
которые можно сравнивать
между собой. Их медианой называется такое
значение m, что число элементов набора,
меньших либо равных m,
равно числу элементов, больших либо равных m.
Существует ли алгоритм выбора медианы, который
работает за время O(n) (т.е. за время,
линейно зависящее от n)?

Ответ:

(1) Да.

(2) Нет.

Упражнение 2:

Номер 1

Целочисленный массив содержит элементы
25, 10, 20, 5, 9, 15, 19, 1, 3, 8, 7, 12
в указанном порядке. Образуют ли они бинарную кучу (пирамиду)?

Ответ:

(1) Да.

(2) Нет.

Номер 2

Целочисленный массив содержит элементы
20, 18, 10, 15, 7, 7, 9, 8, 10, 6, 4, 5
в указанном порядке. Образуют ли они бинарную кучу (пирамиду)?

Ответ:

(1) Да.

(2) Нет.

Номер 3

Целочисленный массив содержит элементы
30, 25, 23, 15, 10, 20, 16, 7, 12, 5, 11, 9
в указанном порядке. Образуют ли они бинарную кучу (пирамиду)?

Ответ:

(1) Да.

(2) Нет.

Упражнение 3:

Номер 1

Пусть целочисленный массив содержит элементы
11, 18, 10, 7, 15, 9, 8
в указанном порядке. Услове пирамиды нарушается
только для элемента 11, стоящего в вершине пирамиды.
Для исправления пирамиды выполняется процедура просеивания,
при которой элемент 11 опускается на свое место.
Каким будет содержимое массива после окончания этой процедуры?

Ответ:

(1) 18, 15, 10, 11, 7, 9, 8.

(2) 18, 15, 11, 7, 10, 9, 8.

(3) 18, 15, 10, 7, 11, 9, 8.

(4) 18, 15, 10, 11, 8, 9, 7.

(5) 11, 18, 15, 7, 10, 9, 8.

Номер 2

Пусть целочисленный массив содержит элементы
14, 20, 25, 15, 12, 22, 18
в указанном порядке. Услове пирамиды нарушается
только для элемента 14, стоящего в вершине пирамиды.
Для исправления пирамиды выполняется процедура просеивания,
при которой элемент 14 опускается на свое место.
Каким будет содержимое массива после окончания этой процедуры?

Ответ:

(1) 25, 20, 14, 15, 12, 22, 18.

(2) 25, 20, 22, 15, 12, 14, 18.

(3) 25, 15, 22, 14, 12, 20, 18.

(4) 25, 20, 14, 14, 15, 22, 18.

(5) 25, 15, 20, 14, 12, 22, 18.

Номер 3

Пусть целочисленный массив содержит элементы
10, 16, 12, 8, 11, 7, 5
в указанном порядке. Услове пирамиды нарушается
только для элемента 10, стоящего в вершине пирамиды.
Для исправления пирамиды выполняется процедура просеивания,
при которой элемент 10 опускается на свое место.
Каким будет содержимое массива после окончания этой процедуры?

Ответ:

(1) 16, 10, 12, 8, 11, 7, 5.

(2) 16, 11, 12, 8, 7, 10, 5.

(3) 16, 11, 12, 8, 10, 7, 5.

(4) 16, 12, 11, 8, 10, 7, 5.

(5) 16, 11, 12, 8, 10, 5, 7.

Упражнение 4:

Номер 1

К целочисленному массиву применяется алгоритм сортировки
кучей. Пусть после первого этапа алгоритма пирамида
(бинарная куча) уже построена и массив содержит элементы
16, 12, 11, 8, 7, 10, 6
в указанном порядке. Затем выполняется второй этап сортировки.
На его первом шаге начальный и конечный элементы массива
меняются местами, от пирамиды отрезается правая нижняя ветка
(т.е. последний элемент массива), затем элемент в вершине
пирамиды просеивается, благодаря чему восстанавливается
условие пирамиды. Каким будет содержимое массива по
окончании этого шага?

Ответ:

(1) 12, 7, 11, 8, 6, 10, 16.

(2) 12, 8, 11, 6, 7, 10, 16.

(3) 12, 8, 11, 7, 6, 10, 16.

Номер 2

К целочисленному массиву применяется алгоритм сортировки
кучей. Пусть после первого этапа алгоритма пирамида
(бинарная куча) уже построена и массив содержит элементы
20, 17, 12, 2, 10, 4, 8
в указанном порядке. Затем выполняется второй этап сортировки.
На его первом шаге начальный и конечный элементы массива
меняются местами, от пирамиды отрезается правая нижняя ветка
(т.е. последний элемент массива), затем элемент в вершине
пирамиды просеивается, благодаря чему восстанавливается
условие пирамиды. Каким будет содержимое массива по
окончании этого шага?

Ответ:

(1) 17, 10, 12, 2, 4, 8, 20.

(2) 17, 12, 10, 2, 8, 4, 20.

(3) 17, 10, 12, 2, 8, 4, 20.

(4) 17, 2, 10, 12, 8, 4, 20.

(5) 17, 10, 12, 20, 8, 4, 2.

Номер 3

К целочисленному массиву применяется алгоритм сортировки
кучей. Пусть после первого этапа алгоритма пирамида
(бинарная куча) уже построена и массив содержит элементы
30, 20, 25, 10, 7, 19, 5
в указанном порядке. Затем выполняется второй этап сортировки.
На его первом шаге начальный и конечный элементы массива
меняются местами, от пирамиды отрезается правая нижняя ветка
(т.е. последний элемент массива), затем элемент в вершине
пирамиды просеивается, благодаря чему восстанавливается
условие пирамиды. Каким будет содержимое массива по
окончании этого шага?

Ответ:

(1) 25, 20, 19, 10, 7, 5, 30.

(2) 25, 20, 19, 10, 5, 7, 30.

(3) 25, 19, 20, 10, 7, 5, 30.

(4) 25, 10, 19, 20, 5, 7, 30.

(5) 25, 30, 19, 10, 5, 7, 20.

Упражнение 5:

Номер 1

К целочисленному массиву применяется алгоритм сортировки
кучей. На первом этапе из элементов массива строится
пирамида (бинарная куча) путем просеивания элементов
по бинарному дереву в порядке справа налево и снизу вверх.
Пусть вначале массив содержал элементы
1, 2, 3, 4, 5, 6, 7
в указанном порядке.
Каким будет содержимое массива
после построения пирамиды?

Ответ:

(1) 7, 5, 6, 2, 4, 1, 3.

(2) 7, 5, 6, 4, 2, 1, 3.

(3) 7, 5, 6, 4, 2, 3, 1.

(4) 7, 5, 4, 6, 2, 3, 1.

(5) 7, 5, 6, 4, 3, 2, 1.

Номер 2

К целочисленному массиву применяется алгоритм сортировки
кучей. На первом этапе из элементов массива строится
пирамида (бинарная куча) путем просеивания элементов
по бинарному дереву в порядке справа налево и снизу вверх.
Пусть вначале массив содержал элементы
4, 5, 6, 7, 1, 2, 3
в указанном порядке.
Каким будет содержимое массива
после построения пирамиды?

Ответ:

(1) 7, 6, 4, 5, 1, 2, 3.

(2) 7, 6, 5, 4, 1, 2, 3.

(3) 7, 5, 6, 4, 1, 2, 3.

(4) 7, 6, 5, 4, 3, 2, 1.

(5) 7, 5, 6, 4, 3, 2, 1.

Номер 3

К целочисленному массиву применяется алгоритм сортировки
кучей. На первом этапе из элементов массива строится
пирамида (бинарная куча) путем просеивания элементов
по бинарному дереву в порядке справа налево и снизу вверх.
Пусть вначале массив содержал элементы
1, 2, 3, 4, 7, 6, 5
в указанном порядке.
Каким будет содержимое массива
после построения пирамиды?

Ответ:

(1) 7, 4, 6, 1, 2, 3, 5.

(2) 7, 4, 5, 1, 2, 6, 3.

(3) 7, 6, 5, 4, 2, 3, 1.

(4) 7, 4, 6, 5, 2, 3, 1.

(5) 7, 6, 4, 5, 2, 3, 1.

Программирование - тест 97