Алгоритмы и структуры данных-1. ПЗ-Тест №5. В1

Алгоритм INSERTION SORT больше подходит для

• Линейного двусвязного списка

• Одномерного массива

Асимптотические оценки худших случаев работы алгоритмов QUICK SORT и MERGE SORT совпадают

• Да!

• Нет!

Блок данных, который помещается в оперативную память,
может быть отсортирован с помощью

• QUICK SORT

• MERGE SORT

• INSERTION SORT

• HEAP SORT

Порядковая статистика №K массива А, состоящего из уникальных элементов, - это

• K-ый наименьший элемент в массиве А

• Элемент массива А, индекс которого, - это случайное число в диапазоне [0, ..., K]

• Элемент, стоящий на K-ом месте в массиве А после сортировки

• К-ый элемент в массиве А

Внешняя сортировка применяется в случае, если

• данные помещаются в оперативную память целиком
• данные не требуют сортировки
• эммм....

• данные не помещаются в оперативную память целиком

Средняя ожидаемая сложность алгоритма RANDOMIZED SELECT
для поиска K-ой порядковой статистики ...

• O(n)
• O(n^2)
• совпадает с ожидаемой сложностью
  QUICK SORT

• O(1)