Вопросы к экзамену по АиП - II (ФИТ, КМБ, ИТС, ИБАС)

Вопросы к экзамену по АиП - II (ФИТ, КМБ, ИТС, ИБАС)

Вопросы к экзамену по АиП - II (ФИТ, КМБ, ИТС, ИБАС)

Понятие структуры, описание структуры в языке С++, инициализация структуры. Доступ к полям структуры, ввод и вывод информации при работе со структурами. Пример использования структур. Битовые поля. Бинарные файлы: отличие бинарных файлов от файлов с последовательным доступом, открытие бинарного файла, чтение и запись в бинарные файлы. Указатели чтения и записи. Пример использования бинарных файлов. Возможность одновременной записи и чтения в бинарные файлы. Перечисления и объединения. Описание и примеры использования Указатели на структуры. Сортировка массивов структур с использованием указателей. Метод перебора с возвратом. Типы задач, требующие для решения перебора с возвратом. Задача о прохождении лабиринта: суть метода, способ организации данных, реализация функции выхода из лабиринта на языке С++ Динамическое программирование: суть метода, задач о черепашке. Динамическое программирование: суть метода, задача о k-ичных числах Динамические структуры данных: причины использования и преимущества. Стек: определение, описание, правило работы со стеком. Функции добавления элемента в стек, отображения стека, удаления стека из памяти Динамические структуры данных: причины использования и преимущества. Очередь: определение, описание, правило работы с очередью. Функции добавления элемента в очередь, отображения очереди, удаления очереди из памяти Основные действия с линейными односвязными списками: проход по списку, поиск узла, добавление узла после и до заданного, удаление узла. Организация циклического списка Двусвязные списки: описание и преимущества работы. Функции работы с двусвязными списками: добавление узла в начало и конец, добавление узла до и после заданного, поиск узла, удаление узла. Организация циклического двусвязного списка. Деревья: основные определения. Понятие бинарного дерева, описание вершины дерева на С++. Виды обходов бинарных деревьев. Построение дерева минимальной высоты: алгоритм решения и функция формирования дерева минимальной высоты на С++. Деревья поиска: понятие дерева поиска, алгоритм построения, поиск по дереву, сортировка данных с помощью дерева поиска Удаление вершины из дерева поиска. Способы вывода дерева на экран («боком» и с помощью скобок) Понятие идеально-сбалансированного дерева и АВЛ-дерева.  Показатель сбалансированности. Варианты нарушения балансировки при добавлении узла в дерево. Одинарные LL и RR-повороты: описание, примеры функции балансировки, формулы деревьев до и после балансировки Двойные LR и RL-повороты: описание, примеры функции балансировки, формулы деревьев до и после балансировки Последовательный контейнер vector: определение, способ выделения памяти, инициализация, основные методы, примеры использования Последовательный контейнер deque: определение, способ выделения памяти, инициализация, основные методы, примеры использования Последовательный контейнер list: определение, способ выделения памяти, инициализация, основные методы, примеры использования. Предикаты Адаптеры последовательных контейнеров stack и queue: определение, инициализация, основные методы, примеры использования Ассоциативные контейнеры map и multimap: определение, инициализация, основные методы, примеры использования Ассоциативные контейнеры set и multiset: определение, инициализация, основные методы, примеры использования Понятие итератора при работе с контейнерами библиотеки STL.  Описание итераторов, примеры использования. Способы перемещения итераторов в разных видах контейнеров. Операция разыменования. Примеры использования Понятие алгоритма в библиотеке STL. Алгоритмы поиска, подсчета и сортировки в библиотеке STL. Понятие алгоритма в библиотеке STL. Алгоритмы удаления и замены в библиотеке STL. Примеры использования Основные понятия теории графов. Способы представления графов в памяти компьютера. Примеры Обход графа в глубину: суть метода, реализация обхода в глубину (рекурсивная функция). Поиск количества компонент связности графа. Примеры Обход графа в глубину: суть метода, реализация обхода в глубину (нерекурсивная функция). Примеры Обход графа в ширину: суть метода, реализация обхода в глубину. Примеры Алгоритм Дейкстры: суть метода, реализация функции на языке С++ Топологическая сортировка графа: описание метода, примеры. Понятие остовного дерева графа и его построение. Алгоритм Прима: описание алгоритма, примеры.