Открытые практические задачи
Материал из DISCOPAL
Содержание
Открытые задачи на «Dynamic Programming»
Открытые задачи на «Greedy»
Открытые задачи на «Random»
Открытые задачи на «Sorting»
Всего страниц найдено: 2.
----
Вопрос: Q29-4c9f66
Сортировка слиянием выполняется путем разделения списка из n чисел пополам, рекурсивной сортировки каждой половины и объединения двух половин.
Какая из следующих структур данных позволит выполнить сортировку слиянием за
- Односвязный список
- Двусвязный список
- Массив
Ответы
- Нет правильного ответа
- Только 3
- 1 и 2
- 2 и 3
- Правильный ответ: 1, 2, 3
Объяснение
Исходники — вопрос 29 на 24 странице книги «2004-gre-cs-practice-book.pdf»
Ну тут требуется каждый раз односторонний проход
- разделение
- слияние половинок
так что покатит даже односвязный список, не говоря уже о двухсвязном и массиве.
Вопрос: Q03-4c9f66
Какой из следующих алгоритмов имеет время выполнения O(n²) в наихудшем случае, но O(n×log(n)) в среднем?
Ответы
- Пузырьковая сортировка
- Сортировка слиянием
- Пирамидальная сортировка (сортировка кучей)
- Правильный ответ: Быстрая сортировка
- Турнирная (Tournament) сортировка
Объяснение
Исходники — вопрос 3 на 13 странице книги «2004-gre-cs-practice-book.pdf»
- Quicksort да, в худшем — квадрат, в среднем — O(n×log(n))
- Сортировка слиянием — имеет O(n log n) в худшем и среднем (но помните, ест O(n) памяти)
- Пирамидальная сортировка — в среднем и худшем O(n log n) (но есть другие проблемы).
- Пузырьковая — квадрат в худшем и среднем.
- Турнирная сортировка — имеет O(n log n) в худшем и среднем.
Открытые задачи на «Numbers»
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.