Алгоритмы поиска, деревья поиска и хеш-таблицы — тест для ИТ-класса

Найти нужную запись среди миллиона можно перебором, а можно за двадцать шагов — если данные заранее правильно организованы. Разделы курса «Программирование» о поиске, деревьях поиска и хешировании объясняют, как устроены структуры, на которых держатся словари, индексы баз данных и автодополнение. Работа проверяет понимание этих структур и умение проследить их работу вручную.

Темы

Последовательный поиск и его оценка; двоичный поиск в отсортированном массиве и число шагов в худшем случае. Двоичное дерево поиска: свойство «слева меньше, справа больше», поиск, минимум и максимум, вставка элемента, три случая удаления узла, прямой, симметричный и обратный обходы. Почему вырожденное дерево превращается в список и зачем нужны сбалансированные деревья — АВЛ-деревья и splay-деревья. Хеширование: хеш-функция, хеш-таблица, коллизии, метод цепочек и открытая адресация, коэффициент заполнения.

Как построены задания

Пятнадцать заданий: посчитать шаги двоичного поиска, построить дерево по последовательности вставок и назвать его высоту, выписать симметричный обход, найти ячейку хеш-таблицы по остатку от деления, сопоставить структуру и сложность операций, упорядочить шаги удаления узла с двумя потомками. На выполнение — тридцать минут.

Что даёт разбор

Пояснения показывают, почему симметричный обход дерева поиска выдаёт ключи по возрастанию, почему двоичный поиск бесполезен на неотсортированном массиве и почему даже хорошая хеш-таблица в худшем случае работает за линейное время.

Где применить

Работу удобно провести после разделов о поиске и деревьях в десятом классе или как повторение перед олимпиадным блоком программы, где эти структуры используются без пояснений.

Как проходит работа

Задания открываются в браузере на компьютере, планшете или мобильном телефоне, поэтому подойдёт любое устройство под рукой. Поскольку для работы можно указать окно выполнения, ученики вправе проходить её дистанционно, из дома. Для защиты от подсказок отслеживается, покидал ли ученик вкладку с тестом ради других вкладок или приложений.