Открытые практические задачи
Содержание
Открытые задачи на «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»
Всего страниц найдено: 12.
----
Вопрос: Q21-alg4-31d68c
Рассмотрим следующие выражения:
- I
- Подсчет медианы из n элементов занимает
\Omega(n \log n) времени для любого алгоритма, основанного на сравнении элементов. - II
- Пусть T является минимальным остовным деревом для графа G. Тогда для любой пары вершин a и b кратчайший путь между ними в G является кратчайшим путем между ними в T.
Какие утверждения верные, а какие нет?
Ответы
- I-TRUE, II-False
- I-TRUE, II-TRUE
- I-False, II-TRUE
- Правильный ответ: I-False, II-False
Объяснение
- Вычисление медианы из n элементов занимает
\Theta(n) времени в алгоритме Median of Medians. - Минимальных остовных деревьев может быть несколько, и кратчайшие пути могут не совпадать.
Исходники — вопрос 21 на 239 странице книги «2019-gate-computer-science-and-it-practice.pdf»
Вопрос: Q02-alg4-31d68c
Рассмотрим массив из n элементов. Какую временную сложность имеет алгоритм поиска максимальной суммы трех элементов в массиве?
Ответы
-
O(n) -
O(n^2) - Правильный ответ:
O(n \log n) -
O(\log n)
Объяснение
Отсортируем массив за
Исходники — вопрос 2 на 238 странице книги «2019-gate-computer-science-and-it-practice.pdf»
Вопрос: Верные утверждения о сортировках
Рассмотрим следующие утверждения:
- Пусть n — это число элементов в массиве
- В процессе сортировки массива происходит порядка
O(\log n) уровней - На каждом уровне происходит порядка
O(n) действий
Для какого алгоритма сортировки все утверждения являются верными?
Ответы
- Сортировка кучей
- Правильный ответ: Сортировка слиянием
- Сортировка выбором
- Сортировка пузырьком
Объяснение
Сортировка слиянием является устойчивой, в любом случае происходит порядка
Исходники — вопрос 10 на 233 странице книги «2019-gate-computer-science-and-it-practice.pdf»
Вопрос: Q05-alg3-31d68c
Что из перечисленного не может быть временной сложностью алгоритма быстрой сортировки ни в одном из средних, наилучших или наихудших случаев?
Ответы
-
O(n\log n) -
O(n^2) -
O(n^3) - Правильный ответ:
O(\log n)
Объяснение
Средний и лучший случай быстрой сортировки
Исходники — вопрос 5 на 233 странице книги «2019-gate-computer-science-and-it-practice.pdf»
Вопрос: Q03-alg2-31d68c
Пусть дана последовательность n случайных чисел. Какая будет временная сложность для вычисления медианы данного массива?
Ответы
-
O(\log n) - Правильный ответ:
O(n \log n) -
O(n^2) -
O(n^2 \log n)
Объяснение
Прежде всего, массив необходимо отсортировать за
Исходники — вопрос 3 на 226 странице книги «2019-gate-computer-science-and-it-practice.pdf»
Вопрос: Q04-alg2-31d68c
Пусть дана последовательность n случайных чисел.
Какая будет временная сложность (в наихудшем случае) для нахождения элемента, который встречается больше, чем n/2 раз (если такой элемент существует)?
Ответы
-
O(n/2) -
O(n \log n) -
O(\log n) - Правильный ответ:
O(n^2)
Объяснение
Официальный ответ у них: Решение состоит в том, чтобы завести два цикла и отслеживать максимальное количество для всех различных элементов. Если максимальное количество становится больше n/2, то циклы завершаются и возвращается элемент с максимальным количеством. Если в конце максимальное количество не превышает n/2, то такой элемент не существует.
Мысли Стаса: Фиг знает, вроде же легко
- пиромидально или слиянием отсортировать (
O(n \log n) ), - потом пробежаться по отсортированному списку, посчитывая в одном счетчике последовательное число элементов (
O(n) ) - уложимся в
O(n \log n) - WTF?
Исходники — вопрос 4 на 226 странице книги «2019-gate-computer-science-and-it-practice.pdf»
Вопрос: Q32-alg1-31d68c
Какое из следующих рекуррентных соотношений не может быть использовано в оценке времени работы алгоритма быстрой сортировки?
Ответы
-
T(n)=T\left(\frac{6n}{10}\right) + T\left(\frac{4n}{10}\right) + \Theta(n) -
T(n)=T\left(\frac{4n}{5}\right) + T\left(\frac{n}{5}\right) + \Theta(n) -
T(n)=T\left(n-1\right) + T\left(1\right) + \Theta(n) - Правильный ответ:
T(n)=T\left(\frac{4n}{5}\right) + T\left(\frac{4n}{5}\right) + \Theta(n)
Объяснение
Данный массив разбивается на два непустых подмассива.
В правильном ответе разбиение означает, что в первой части массива находится 80 процентов чисел, значит во второй части массива должно быть 20 процентов. Таким образом вместо
Исходники — вопрос 32 на 225 странице книги «2019-gate-computer-science-and-it-practice.pdf»
Вопрос: Q15-alg1-31d68c
Пусть имеется два отсортированных списка размера K и L соответственно.
Сколько потребуется сравнений элементов, для того чтобы получить отсортированный список размера K + L, состоящий из элементов этих списков?
Ответы
-
O(K) -
O(L) - Правильный ответ:
O(K + L) -
O(K * L)
Объяснение
Для сравнения используется два указателя, каждый из которых проходится по своему списку.
Исходники — вопрос 15 на 223 странице книги «2019-gate-computer-science-and-it-practice.pdf»
Вопрос: Q42-08c765
Реальный коэффициент готовности алгоритма к работе в реальном времени (real-time readiness ratio, RTR) можно определить, как отношение среднего времени выполнения алгоритма к худшему времени выполнения.
Какой из следующих алгоритмов имеет коэффициент RTR, наиболее близкий к 0?
Ответы
- Правильный ответ: Быстрая сортировка
- Сортировка слиянием
- Сортировка вставками
- Пирамидальная сортировка
- Сортировка пузырьком
Объяснение
1. Сортировка пузырьком (Bubble Sort):
- Среднее время:O(n^2) - Худшее время:O(n^2) - Коэффициент RTR:\frac{n^2}{n^2} = 1
2. Пирамидальная сортировка (Heap Sort):
- Среднее время:O(n \log n) - Худшее время:O(n \log n) - Коэффициент RTR:\frac{n \log n}{n \log n} = 1
3. Сортировка вставкой (Insertion Sort):
- Среднее время:O(n^2) - Худшее время:O(n^2) - Коэффициент RTR:\frac{n^2}{n^2} = 1
4. Слияние-сортировка (Merge Sort):
- Среднее время:O(n \log n) - Худшее время:O(n \log n) - Коэффициент RTR:\frac{n \log n}{n \log n} = 1
5. Быстрая сортировка (Quick Sort):
- Среднее время:O(n \log n) - Худшее время:O(n^2) - Коэффициент RTR:\frac{n \log n}{n^2}
Исходники — вопрос 42 на 36 странице книги «2011-gre-cs-practice-book.pdf»
StasFomin: Вообще для алгоритмов такой термин почти не используется (концептуально оно странненькое), ну максимум можно нагуглить какие-то редкие упоминания, ну раз мы тут сами его определили, то можно этот вопрос и оставить.
Вопрос: Q35-08c765
Рассмотрим следующий алгоритм, сортирующий массив из n ≥ 2 целых чисел:
- Если в массиве всего 2 элемента, сравнить их и поменять местами если они в неправильном порядке
- Иначе, делать следующие шаги по порядку:
- Рекурсивно отсортировать первые n-1 элементов массива
- Рекурсивно отсортировать последние n-1 элементов массива
- Рекурсивно отсортировать первые 2 элемента массива
Какова асимптотическая временная сложность этого алгоритма, измеряемая количеством проведенных сравнений?
Ответы
-
\Theta(n\log{n}) -
\Theta(n^2) -
\Theta(n^3) - Правильный ответ:
\Theta(2^n) -
\Theta(3^n)
Объяснение
Исходники — вопрос 35 на 31 странице книги «2011-gre-cs-practice-book.pdf»
Напишем реализацию алгоритма на C:
if (sz == 2)
{
// сравнить и свапнуть если надо
return;
}
sort(ar, sz-1); sort(ar+1, sz-1); sort(ar, 2);
}
Заметим, что каждый вызов функции sort (за исключением случая когда sz == 2) создает еще 2 вызова той же функции sort всегда с одинаковым sz. При этом каждый вызов функции sort в конце концов приводит к вызову операции сравнения. Следовательно получаем следующую цепочку вызовов функции: f(n) - 2*f(n-1) - 4*f(n-2) - ... - 2^n-2*f(2), следовательно в итоге получается 2^n вызовов операции сравнения и правильный ответ --
Вопрос: 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»
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.