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

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

Номер 1

Алгоритм сортировки называется стабильным, если он
сохраняет относительный порядок равных элементов.
Среди перечисленных ниже алгоритмов сортировки
(имеются в виду их классические варианты) отметьте все стабильные.

Ответ:

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

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

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

Номер 2

Алгоритм сортировки называется стабильным, если он
сохраняет относительный порядок равных элементов.
Среди перечисленных ниже алгоритмов сортировки
(имеются в виду их классические варианты) отметьте все стабильные.

Ответ:

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

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

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

Номер 3

Алгоритм сортировки называется стабильным, если он
сохраняет относительный порядок равных элементов.
Среди перечисленных ниже алгоритмов сортировки
(имеются в виду их классические варианты) отметьте все стабильные.

Ответ:

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

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

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

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

Номер 1

К трехзначным десятичным числам (строкам длины 3 из десятичных
цифр) применяется алгоритм RADIX-сортировки сначала по младшей цифре,
затем по средней и в конце по старшей. Исходный массив содержит следующие
числа:

122, 232, 171, 198, 401, 035, 077, 201, 199, 400.

Каким будет содержимое массива после выполнения первых двух шагов
сортировки (т.е. после сортировки по младшей и средней цифрам)?

Ответ:

(1) 400, 201, 401, 122, 232, 035, 171, 077, 198, 199

(2) 400, 401, 201, 122, 035, 232, 171, 077, 198, 199

(3) 400, 401, 201, 122, 232, 035, 171, 077, 198, 199

(4) 400, 401, 201, 122, 171, 232, 035, 077, 198, 199

(5) 400, 401, 201, 122, 232, 035, 171, 077, 198, 199

Номер 2

К трехзначным десятичным числам (строкам длины 3 из десятичных
цифр) применяется алгоритм RADIX-сортировки сначала по младшей цифре,
затем по средней и в конце по старшей. Исходный массив содержит следующие
числа:

232, 102, 307, 901, 835, 215, 105, 301, 323, 811.

Каким будет содержимое массива после выполнения первых двух шагов
сортировки (т.е. после сортировки по младшей и средней цифрам)?

Ответ:

(1) 301, 901, 102, 105, 307, 811, 215, 323, 232, 835

(2) 901, 301, 102, 105, 307, 811, 215, 323, 232, 835

(3) 901, 301, 102, 105, 307, 811, 215, 232, 323, 835

(4) 901, 301, 102, 105, 307, 215, 811, 323, 232, 835

(5) 901, 301, 102, 307, 105, 811, 215, 323, 232, 835

Номер 3

К трехзначным десятичным числам (строкам длины 3 из десятичных
цифр) применяется алгоритм RADIX-сортировки сначала по младшей цифре,
затем по средней и в конце по старшей. Исходный массив содержит следующие
числа:

102, 232, 307, 901, 835, 215, 105, 301, 335, 811.

Каким будет содержимое массива после выполнения первых двух шагов
сортировки (т.е. после сортировки по младшей и средней цифрам)?

Ответ:

(1) 901, 301, 102, 105, 307, 811, 215, 232, 835, 335

(2) 301, 901, 102, 105, 307, 811, 215, 232, 835, 335

(3) 102, 301, 901, 105, 307, 811, 215, 232, 335, 835

(4) 901, 301, 102, 105, 307, 811, 215, 232, 335, 835

(5) 301, 901, 105, 102, 307, 811, 215, 232, 335, 835

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

Номер 1

RADIX-сортировка применяется к составным ключам длины k,
длина сортируемого массива равна n. Какова асимптотическая
оценка времени работы алгоритма?

Ответ:

(1) t = O(k*n)

(2) t = O(k*log₂n)

(3) t = O(k²*n)

(4) t = O(k*n²)

(5) t = O(n)

Номер 2

Сортируемый массив содержит составные ключи из 20
десятичных цифр (например, идентификаторы банковских счетов).
Массив имеет длину 1000. Надо выбрать один из двух алгоритмов
сортировки: сортировку кучей HeapSort или RADIX-сортировку.
Какой из двух алгоритмов будет в среднем работать быстрее
в данной ситуации?

Ответ:

(1) RADIX-сортировка.

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

Номер 3

Сортируемый массив содержит составные ключи из 10
десятичных цифр.
Массив имеет длину 1000000 (миллион). Надо выбрать один из двух алгоритмов
сортировки: сортировку кучей HeapSort или RADIX-сортировку.
Какой из двух алгоритмов будет в среднем работать быстрее
в данной ситуации?

Ответ:

(1) RADIX-сортировка.

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

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

Номер 1

Функция merge слияния двух упорядоченных массивов
применяется к двум массивам длины 10 и 20.
Может ли в процессе ее выполнения быть сделано ровно 28 сравнений?

Ответ:

(1) Может.

(2) Не может.

Номер 2

Функция merge слияния двух упорядоченных массивов
применяется к двум массивам длины 100 и 1000. Какое максимальное
число сравнений может быть сделано при выполнении этой функции?

Ответ:

(1) 100

(2) 1000

(3) 1099

(4) 1100

Номер 3

Функция merge слияния двух упорядоченных массивов
применяется к двум массивам длины 100 и 1000. Какое минимальное
число сравнений может быть сделано при выполнении этой функции?

Ответ:

(1) 99

(2) 100

(3) 999

(4) 1000

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

Номер 1

Рассмотрим алгоритм сортировки слиянием с использованием
дополнительной памяти. Используется нисходящая (рекурсивная)
схема реализации алгоритма. Алгоритм применяется к массиву
длины 1000000 (миллион). Какова максимально возможная
глубина рекурсии? Дайте наиболее точную оценку.

Ответ:

(1) Не больше 10

(2) Не больше 20

(3) Не больше 50

(4) Не больше 100

Номер 2

Рассмотрим алгоритм сортировки слиянием с использованием
дополнительной памяти. Используется восходящая
схема реализации алгоритма. Алгоритм применяется к массиву
длины 100. На каждом шаге сливаются пары
соседних упорядоченных подмассивов длины
не больше k и получаются упорядоченные подмассивы
длины не больше 2k; первый шаг выполняется при
k=1.
Сколько всего шагов будет выполнено?

Ответ:

(1) 5

(2) 6

(3) 7

(4) 8

Номер 3

Рассмотрим алгоритм сортировки слиянием с использованием
дополнительной памяти. Используется нисходящая (рекурсивная)
схема реализации алгоритма. Алгоритм применяется к массиву
длины 1000. Какова максимально возможная
глубина рекурсии? Дайте наиболее точную оценку среди приведенных ниже.

Ответ:

(1) Не больше 8.

(2) Не больше 10.

(3) Не больше 12.

(4) Не больше 20.

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