Вопросы для теоретической части зачета весной 2021 г.
- Цели и задачи программирования. Парадигмы программирования.
- Языки программирования низкого и высокого уровня. Трансляторы.
- Быстродействие алгоритмов.
- Метод «пузырька», сортировка выбором и вставками.
- Рекурсивные и нерекурсивные алгоритмы. Принцип «разделяй и властвуй». Алгоритмы поиска элементов в массиве.
- Быстрая сортировка Хоара (Quicksort). Пирамидальная сортировка (Heapsort).
- Сортировка слиянием. Сортировка подсчетом. Поразрядная сортировка.
- Алгоритмы поиска подстроки в строке: метод грубой силы, алгоритм Боуэра-Мура, алгоритм Рабина-Карпа.
- Модули. Реализация модулей в Python.
- Составные типы данных, два основных вида.
- Понятие об абстрактном типе данных. Стеки и очереди. Связанные списки.
- Дерево как структура данных. N-арные и двоичные деревья.
- Деревья поиска. Реализация операций над ними.
- Балансировка деревьев поиска. АВЛ-деревья. 2-3-4 деревья. Красно-черные деревья.
- Очередь с приоритетом, двоичная куча.
- Хеш-таблицы: идея и интерфейс. Хеш-функции и требования к ним. Решение проблемы конфликтов с помощью динамического массива списков.
- Открытая адресация в хеш-таблице. Кукушиное хеширование. Сходства и отличия между хеш-таблицей и деревом поиска. Криптографические хеш-функции.
Действия