Викторина
Алгоритмы и структуры данных
25 вопросов для олимпиадников: сортировки, бинарный поиск, графы, стек и очередь, сложность O(n). Пригодится перед контестом. Фото: Wikimedia Commons, свободные лицензии (авторы указаны в пояснениях).
Провести игру
Войдите, чтобы провести игру для класса.
Играть одному
Рекордов пока нет.
Вопросы
- Один вариант Разминка без очков: что такое алгоритм?
-
Один вариант
Что обязательно нужно для бинарного поиска?
Фото: AlwaysAngry, CC BY-SA 4.0, Wikimedia Commons - Ползунок Сколько максимум сравнений нужно бинарному поиску в отсортированном массиве из 1 000 000 чисел?
-
Один вариант
Какая сложность у сортировки пузырьком в худшем случае?
Фото: Pmdumuid, CC0, Wikimedia Commons - Один вариант Какая сложность у сортировки слиянием?
-
Один вариант
Стек работает по принципу…
Фото: Foto: Jonn Leffmann, CC BY 3.0, Wikimedia Commons - Один вариант А очередь — по принципу…
- Один вариант Какую структуру данных использует обход графа в ширину (BFS)?
- Один вариант Ловушка: в графе есть рёбра с отрицательным весом. Какой алгоритм ищет кратчайшие пути правильно?
-
Один вариант
Что находит алгоритм Евклида?
Фото: Jusepe de Ribera (Spanish / Italian, 1591 - 1652) (1591 - 1652) – artist (Spanish / Italian) Details on Google Art Proje, Public domain, Wikimedia Commons - Введи ответ Чему равен НОД(48, 18)?
-
Один вариант
Что находит решето Эратосфена?
Фото: SKopp at German Wikipedia, CC BY-SA 3.0, Wikimedia Commons - Один вариант Почему простая рекурсия для чисел Фибоначчи такая медленная?
- Расставь по порядку Расставьте сложности от самой быстрой к самой медленной.
- Верно / Неверно Есть монеты 1, 3 и 4 сома. Жадный алгоритм («каждый раз бери самую большую монету») всегда даст 6 сомов наиме…
- Один вариант Что будет, если у рекурсии нет базового случая?
- Один вариант Какая средняя сложность поиска в хеш-таблице?
- Один вариант Передышка без очков: какой фигурой в блок-схеме обозначают условие?
-
Один вариант
Сколько рёбер в дереве из n вершин?
Фото: автор неизвестен, Public domain, Wikimedia Commons - Ползунок Чему равно 2¹⁰?
- Один вариант Чему равно двоичное число 1011 в десятичной системе?
- Несколько верных Какие из этих алгоритмов — сортировки?
-
Один вариант
Какой алгоритм строит минимальное остовное дерево графа?
Фото: No machine-readable author provided. Dcoetzee assumed (based on copyright claims)., Public domain, Wikimedia Commons - Собери слово Соберите слово: когда функция вызывает саму себя.
-
Один вариант
Финал на двойные очки! Сколько минимум ходов нужно, чтобы перенести 5 дисков в «Ханойской башне»?
Фото: автор неизвестен, CC BY-SA 3.0, Wikimedia Commons