# Зачет
__Семестр II, 2021-2022__
__Информатика, С++__

## Формат зачета

- Пять вопросов из списка
- Правильный ответ - 1
- Максимальный балл за ответ на вопросы -- 5 из 5
- Если оценка не удовлетворяет, то можно сбросить прогресс и получить новые 5 вопросов

## Вопросы к зачету

1. Структурное программирование на языке С++ I.
- Что такое блок кода?
- Базовые операторы C++ и их приоритеты. Пример работы `i = 0; i++ + ++i`.
- Последовательность выполнения кода, точка входа программы?
- Этапы компиляции программы? Зачем нужен компилятор?
2. Объявление переменных. Понятие инициализации и деструктурированного присваивания. Литеральные константы. Фундаментальные типы.
- Как объявляется переменная, отличие от Python? Расшифровать несколько объявлений переменных.
- Фундаментальные типы данных, литеральные константы, перечислить.
- Объявление, инициализация, присвоение. В чем отличия, привести примеры.
3. Ключевое слово auto. Ключевое слово const. Область видимости переменной.
- Как работает служебное слова `auto`. Привести примеры.
- Принцип работы служебного слова `const`. Изменяемость переменных с модификатором `const`.
- Область видимости переменных в цикле и функции. Глобальные переменные. Привести пример.
4. Условные конструкции if / else. Циклы for, while, do / while.
- Циклы for, while, do/while. Объявления переменных в цикле. Примеры
- Условные конструкции, короткая логика. Примеры объявления.
5. Структурное программирование на языке С++ II. Функции. Формальные параметры. Локальные и глобальные переменные. Возвращаемые значения.
- Сигнатура функции. Объявление и определение функции. forward-declaration.
- Локальность параметров функции и способы передачи параметров в функции.
- Перегрузка функций. Выбор перегруженной функции.
- Возвращение данных из функции, void функции.
6. Косвенное обращение – ссылки.
- Косвенное обращение - ссылки. Основные свойства, область применения. Привести пример функции `swap`.
7. Автоматические массивы, поиск и сортировка.
- Объявление автоматических массивов, инициализация. Примеры.
8. Объявление массивов. Обращение к элементам массива. Массивы как аргументы функции.
- Объявление массивов заданного типа данных. Инициализация массива. Примеры
- Обращение к элементам массива, выход за границы. Примеры.
- Способы передачи массивов в функции. Примеры.
9. Асимптотическая сложность алгоритма. Линейный и бинарный поиски. «Медленные» сортировки.
- О-большое, определение и свойства. Применение к алгоритмам.
- Массив. Сложность поиска элемента, доступа, удаления и добавления элемента
- Бинарный поиск. Алгоритм, условие применимости. Асимптотическая сложность.
- Медленные сортировки. Алгоритмы и асимптотическая сложность.
10. Рекурсивный вызов по имени. База рекурсии. Прямой и обратный ход рекурсивного вызова. Эквивалентность итераций и рекурсии. Хвостовая рекурсия.
- Рекурсия. Определение, примеры. База рекурсии.
- Рекурсия. Прямой и обратный ход рекурсивного вызова.
- Эквивалентность итерации и рекурсии. Хвостовая рекурсия. Примеры
11. Парадигма «разделяй и властвуй». Рекурсивная «быстрая сортировка» Хоара. Пирамидальная сортировка.
- Парадигма «разделяй и властвуй»
- Быстрая сортировка. Алгоритм, асимптотическая сложность.
- Пирамидальная сортировка. Алгоритм, асимптотическая сложность.
12. Автоматическая, статическая и динамическая память. Ключевое слово static.
- Представление программы в памяти компьютера. Разделы.
- Автоматическая память. Свойства, примеры.
- Статическая память. Ключевое слово `static` Свойства, примеры.
- Динамическая память. Свойства, примеры.
13. Время жизни и область видимости. Адреса и память, указатели. Операторы &, *. Косвенное обращение посредством адресов, отличие указателя от ссылки.
- Время жизни программных объектов. Область видимости. Примеры.
- Адреса переменных. Получение адреса переменной. Примеры.
- Указатели. Принцип работы. Примеры.
- Указатели. Арифметика указателей. Примеры.
- Указатели. Обращение по указателю. Привести пример функции `swap`.
- Указатели. Отличие указателя от ссылки. Примеры.
- Возвращение из функции по указателю. Примеры.
- (\*) Указатели типа void*. `reinterpret_cast<T>`.
14. Выделение и освобождение динамической памяти. Ключевые слова new / delete. Связь массивов и указателей. Арифметика указателей и оператор []. Выражения new[] / delete[].
- Операторы `new` и `delete`. Выделение динамической памяти, освобождение.
- (\*)Перегрузка оператора `operator new`. Примеры.
- Динамические массивы, оператор `[]`. Указательная арифметика. Примеры.
- «Утечка памяти». «Висящие указатели». «Двойное освобождение».
- (\*) Утилиты для разметки памяти и отслеживания ошибок (санитайзеры и valgrind.)
15. Перечисления, enum class. Структуры, struct. Объединения, union. Оператор -> для доступа к данным структуры или объединения посредством указателя.
- `enum / enum class`, область применения, пример.
- `union`, область применения, пример.
- `struct`, область применения, пример.
- Обращение к данным структуры. Операторы доступа.
- Передача структур (`enum, struct, union`) в функции и их возврат.
16. --- Ключевое слово sizeof. Перегрузка операторов для определённых пользователем типов данных.
- Ключевое слово `sizeof`. Размер фундаментальных и пользовательских типов данных.
- Перегрузка операторов пользовательских структур данных. Примеры.
- (\*) Битовые поля в структурах. Примеры.
17. Конструкторы и инициализация структур. Неявные преобразования типов.
- Конструктор для структуры. Обращение к полям структуры.
- Неявное преобразование типов. `static_cast<T>`.
- (\*) *Ключевое слово explicit.*
18. Односвязный список, стек.
- Представление односвязного списка. Алгоритмы на списках (поиск, добавление, удаление).
- Стек. Реализация на односвязном списке.
19. Двусвязный список, очередь.
- Динамические структуры данных - двусвязный список. Алгоритмы на списках (поиск, добавление, удаление).
- Динамические структуры данных - очередь. Алгоритмы на списках (поиск, добавление, удаление).
20. (\*) Двоичная куча (heap). Построение и поддержание двоичной кучи. Построение очереди с приоритетом на основе двоичной кучи.
- (\*) Двоичная куча. Пример использования.
- (\*) Очередь с приоритетом. Пример.
21. Жадные алгоритмы. Общие принципы построения жадных алгоритмов. Задача о расписании занятий в аудитории. Задача о размене момент. Алгоритм Прима с очередью с приоритетом.
- Жадные алгоритмы. Принцип жадного алгоритма. Пример.
- (\*) Алгоритм Прима с очередью с приоритетом.
22. Динамическое программирование. Понятие динамического программирования. Оптимальная подструктура и перекрывающиеся подзадачи. Нисходящее и восходящее динамическое программирование. Уравнение Беллмана. Задача о наибольшей общей подпоследовательности. Задача о редакционном расстоянии.
- Динамические программирование, принципы и основы. Оптимальнальная подструктура и перекрывающиеся подзадачи.
- Примеры задач.
- Динамическое программирование. Нисходщее и восходящее ДП.
- Динамическое программирование. Задача о наибольшей общей подпоследовательности.
- (\*) Задача о редакционном расстоянии.
23. Бинарные деревья поиска. Бинарное дерево поиска как структура быстрого поиска в упорядоченном множестве. Проблема балансировки. Самобалансирующиеся деревья поиска: АВЛ-дерево, красно-чёрное дерево.
- Бинарные деревья поиска. Определение, основные операции на деревьях.
- AVL-деревья. Балансировка. Отличие от бинарных деревьев.
- (\*) Красно-черное дерево
24. (\*) Хеш-таблицы. Понятие о хеш-функции. Хеш-таблица как структура быстрого поиска в неупорядоченном множестве. Проблема коллизий. Разрешение коллизий методом цепочек и открытой адресацией.
25. Числа с плавающей точкой. Числа с плавающей точкой как числа с относительной точностью. Внутреннее представление чисел с плавающей точкой. Машинное эпсилон. Сравнение чисел с плавающей точкой. Проблема накопительной ошибки. Суммирование Кехена. Проблема перемножения двух чисел с плавающей точкой. Fused multiply accumulate.
- Числа в памяти компьютера - целые, с плавающей точкой. Примеры перевода.
- Машинная точность. Сравнение числе с плавающей точкой.
- Проблема суммирования. Суммирование Кехена.
- Проблема перемножения чисел с плавающей точкой. Fused multiply accumulate.
26. Модульные проекты. Сборка модульного проекта на С++. Заголовочные файлы. Детали компоновки. Пространства имён. Ключевые слова namespace и using. Препроцессор: директивы и макорсы. Статические библиотеки и разделяемые объекты (shared objects). Сборка проекта при помощи Makefile и Cmake.
- Этапы сборки проекта. Заголовочные файлы.