---
# System prepended metadata

title: Зачет

---

# Зачет
__Семестр 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.
    - Этапы сборки проекта. Заголовочные файлы.