- Быстрая сортировка
-
- Базовый алгоритм
- Оцените сложность алгоритма в среднем и худшем случае
- Доказательство сложности алгоритма
- Быстрая сортировка для строк
- Какие оптимизации алгоритма существуют (выбор медианы, использование стека, сортировка вставками, разделение на 3 блока)?
- Сортировка вставками
- «Двусвязный список»
-
- Расскажите о реализации двусвязного списка
- Какие структуры для этого требуются?
- Модифицируйте его для реализации закольцованности.
- Задача сортировки N объектов.
-
- Базовый алгоритм быстрой сортировки. Его производительность в худшем случае.
- Что такое стабильная сортировка? Какие сортировки стабильны?
- Алгоритм бинарного поиска и его модификация для строк.
- Назовите стандартные реализации сортировок в языке и STL.
- Предложите алгоритм нахождения k-й порядковой статистики, основанный на идее алгоритма Quick Sort. Напишите иллюстрирующий код.
- Оцените среднее и худшее время работы этого алгоритма.
- Heap Sort
-
- На основе какой структуры данных реализуется данный алгоритм?
- Расскажите сам алгоритм.
- Какова сложность алгоритма в среднем? А в худшем случае?
- Напишите код для бинарного поиска.
- Binary Search Tree
-
- Что такое граф, дерево?
- Что такое бинарное дерево?
- Опишите Binary Search Tree. В чем его отличие от кучи?
- Как его можно реализовать?
- Поразрядная сортировка
-
- Какие предположения о типе данных требуются?
- Какие виды поразрядной сортировки известны?
- Расскажите алгоритм.
- Какова его сложность?
- Сортировка слиянием
-
- Какова сложность этого алгоритма? Каковы затраты памяти?
- Напишите код слияния отсортированных подмассивов.
- Сортировка Шелла.
-
- Идея сортировки.
- Лемма об h-сортировке k-упорядоченного файла.
- Популярные последовательности.
- Список, стек, очередь
-
- Что такое стек?
- Что такое очередь?
- Как эти типы данных можно реализовать?
- Жадные алгоритмы и динамическое программирование.
-
- Примеры задач
- Задача о расписании.
- Варианты задачи о рюкзаке
- LCS, нахождение длины и восстановление самой последовательности
- Расстояние Левенштейна и его вариации
- Алгоритм Хиршберга для LCS
- ООП
-
- Что такое класс? Чем класс в С++ отличается от структуры? В чем отличие класса от объекта?
- Основные понятия ООП.
- Конструкторы/деструкторы.
- Перегрузка методов. Сокрытие методов. Перегрузка стандартных операторов. Какие способы перегрузки операторов Вы знаете? Какие методы и операторы необходимы для использования типа в качестве параметра стандартного шаблонного контейнера?
- Ключевые слова virtual и const.
- Что такое срезка?
- Множественное наследование.
- Исключения.
-
- Какие методы сообщения об ошибках есть в языке?
- Генерирование и перехват исключений.
- throw-списки. Их изменение в переопределенных методах.
- Обработка ошибок в конструкторах и деструкторах.
- Шаблоны.
- АТД «Очередь с приоритетом»
-
- Чем отличаются понятия «абстрактный тип данных (АТД)» и «структура данных»
- Опишите абстрактный тип данных «Очередь с приоритетом»
- Опишите структуру данных «Двоичная куча»
- Оцените среднее и худшее время выполнения операций
- Приведите примеры задач, в которых естественно использовать АТД «Очередь с приоритетом»
- Можно ли реализовать АТД «Очередь с приоритетом» на базе реализации сбалансированного дерева поиска?
- Расскажите о стандартных реализациях кучи и очереди с приоритетом в STL.
- Последовательные контейнеры STL и адаптеры.
-
- [code] Опишите список и приведите примерную реализацию операций ins ert и push_back.
- Какие последовательные контейнеры Вы знаете? В чем их отличие? Как они устроены?
- Что такое адаптер над контейнером STL? Зачем они нужны? Приведите известные Вам.
- В чем отличие vector<bool> от bitset?
- STL: итераторы
-
- Что такое итератор?
- Какие бывают итераторы?
- Чем принципиально отличаются итератор по элементам контейнера set и по элементам контейнера vector?
- Какие функции и операторы должны быть определены для итератора по элементам двусвязного списка?
- Что такое итератор с произвольным доступом?
- Устройство, основные операции и их стоимость, особенности использования vector.
- Устройство, основные операции и их стоимость, особенности использования list.
- Устройство, основные операции и их стоимость, особенности использования deque.
- Устройство, основные операции и их стоимость, особенности использования stack и queue.
- Устройство, основные операции и их стоимость, особенности использования map, se t.
- Устройство, основные операции и их стоимость, особенности использования bitset и vector<bool>.
- Устройство, основные операции и их стоимость, особенности использования unordered_map.
- Устройство, основные операции и их стоимость, особенности использования priority_queue.
- Сортировка и поиск в STL. В каких контейнерах элементы хранятся упорядоченно?
- Куча в STL. Алгоритмы STL.
- Длинная арифметика. Способы реализации. Алгоритм Карацубы.
- Матрицы и работа с ними.
- Геометрия на плоскости.
-
- Определение расстояния до прямой, угла между прямыми, проверка пересечения отрезков
- Построение выпуклой оболочки точек (алгоритмы Джарвиса, Грэхема).
- Метод заметающей прямой и его применения.
- Триангуляция Делоне.
- Диаграмма Вороного.
- Графы. Деревья. Представление графов. Поиск в глубину и в ширину.
- Топологическая сортировка
- Сильно-связные компоненты. Алгоритм Косарайю.
- Ассоциативный массив. Интерфейс, варианты реализации.
- Хеш-таблицы.
-
- Хеш-функции.
- Способы разрешения коллизий – цепочки, открытое хеширование, кукушка.
- Красно-черные деревья. Основные операции.
- B-деревья. Основные операции. Применение на практике.
- Задачи кодирования. Коды Хаффмана.
