Открытые практические задачи
Содержание
Открытые задачи на «Dynamic Programming»
Открытые задачи на «Greedy»
Всего страниц найдено: 1.
----
Вопрос: Q37-4c9f66
Какая из следующих задач может быть решена с помощью стандартного жадного алгоритма?
- Нахождение минимального остовного дерева в неориентированном графе с целыми положительными весами ребер.
- Нахождение максимальной клики в неориентированном графе.
- Нахождение максимального потока от узла-источника к узлу-приемнику в ориентированном графе с целыми положительными значениями пропускной способности ребер.
Ответы
- Правильный ответ: Только 1
- Только 2
- Только 3
- 1 и 2
- 1, 2, 3
Объяснение
- MST ищется жадно, да.
- клика — NPC
- максимальный поток — полиномиальна, форд=фалкерсон (жадных эвристик неизвестно, интересный вопрос — как доказать, что их не может быть? Класс
NC_0 ?).
Исходники — вопрос 37 на 28 странице книги «2004-gre-cs-practice-book.pdf»
Открытые задачи на «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»
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.