Алгоритмы и сложность: лист заданий с ответами

Какой алгоритм сортировки выбирает опорный элемент и разбивает массив на меньшие и бо́льшие элементы?

1. AСортировка пузырьком
2. BБыстрая сортировка
3. CСортировка слиянием
4. DСортировка вставками

Что такое базовый случай рекурсивной функции?

1. AВызов, использующий больше всего памяти
2. BПервая строка функции
3. CСлучай с наибольшими входными данными, который обрабатывается до любых рекурсивных вызовов
4. DСлучай, ответ на который даётся напрямую, без нового рекурсивного вызова

Чему равен log₂ 1024?

1. A512
2. B10
3. C32
4. D12

Какое утверждение о рекурсивной функции без достижимого базового случая верно?

1. AОна автоматически возвращает 0
2. BОна продолжает вызывать себя, пока не переполнится стек вызовов
3. CКомпилятор всегда превращает её в цикл, который безопасно завершается
4. DОна работает за время O(1)

Почему основание логарифма в O большом обычно не указывают, как в O(log n)?

1. AОснование имеет значение только при малых n
2. BЛогарифмы всегда округляются до целых
3. CВсе логарифмы в информатике имеют основание 10, так что оно подразумевается
4. DЛогарифмы по разным основаниям отличаются лишь постоянным множителем

Сколько памяти стека использует простая рекурсивная функция факториала fact(n) = n × fact(n − 1)?

1. AO(log n)
2. BO(1)
3. CO(n)
4. DO(n²)

Как соотносятся n! и 2ⁿ при больших n?

1. AОни растут с одинаковой скоростью
2. B2ⁿ растёт быстрее n!
3. Cn! есть O(n²)
4. Dn! растёт быстрее 2ⁿ

Для какого варианта задачи о рюкзаке жадное правило «брать предметы в порядке ценности на единицу веса» всегда даёт оптимальный ответ?

1. AНи для одного варианта
2. BДля обоих вариантов
3. CДля непрерывного (дробного) рюкзака, где предметы можно делить
4. DДля рюкзака 0/1, где предметы всегда нужно брать целиком