экзамен_вопросы.txt

Алгоритм Беллмана-Форда построения кратчайшего пути в графе. Оценка сложности.
Алгоритм Бойера-Мура поиска подстроки в строке без суффиксной эвристики. Оценка сложности.
Алгоритм Рабина-Карпа поиска подстроки в строке. Оценка сложности.
Алгоритм топологической сортировки. Оценка сложности.
Алгоритм построения записи в позиционной системе счисления для целых чисел. 
Алгоритм построения записи в позиционной системе счисления для дробной части вещественных чисел.
Алгоритм обхода графа в глубину. Оценки сложности.
Алгоритм обхода графа в ширину с использованием очереди. Оценки сложности.
Алгоритмы обхода деревьев (в ширину, в глубину: в пре/пост/инфиксном порядке).
Алгоритмы с возвратом на примере расстановки ферзей.
Алгоритмы сортировки массива простым включением, простым выбором, «пузырьком». Оценка сложности.
Алгоритм быстрой сортировки Хоара. Оценка сложности.
Алгоритм пирамидальной сортировки. Оценка сложности.
Алгоритм Краскала построения каркаса графа (без СНМ). Оценка сложности.
Алгоритм Прима построения каркаса графа. Оценка сложности.
Алгоритм Флойда-Уоршелла вычисления длин кратчайших путей между всеми парами вершин. Оценка сложности.
Алгоритм Дейкстры поиска кратчайших путей в графе. Оценка сложности.
Алгоритм вставки элемента в АВЛ-дерево. Длинный и короткий повороты. Оценка сложности.
Алгоритмы поиска в массиве: линейный поиск, бинарный поиск, оценки сложности. 
Алгоритм Хаффмана построения оптимального префиксного двоичного кода.
Алгоритм преобразование инфиксной формы записи выражения в постфиксную и вычисление значения полученного выражения.

Язык Си. Вещественные типы. Двоичное представление значений (мантисса, порядок, знак; inf, nan, +0, -0). Преобразования «по умолчанию». Особенности арифметики (распределение на числовой прямой, потеря точности).
Язык Си. Целочисленные типы. Двоичное представление значений (знаковый разряд, дополнительный код и др. представления значений < 0). Преобразования «по умолчанию». Особенности арифметики и сдвигов (учет знаковости, переполнение, перенос, implementation-defined поведение).
Язык Си. Выражения. Порядок вычисления выражения в языке Си. Понятие приоритета и ассоциативности операции. Понятие побочного эффекта и точки следования.
Язык Си. Стандартные функции языка Си для работы с динамической памятью (кучей). Основные принципы устройства кучи на примере dlmalloc. Основные ошибки при работе с кучей.
Язык Си. Понятие времени жизни и способа хранения переменной. Их виды. Ключевые слова для задания способа хранения.
Язык Си. Понятие области видимости переменной. Виды областей видимости. Ключевые слова для задания области видимости.
Язык Си. Понятие указателя в языке Си. Операции над указателями. 
Язык Си. Понятие функции. Описание функций (тип результата, формальные параметры, тело). Передача фактических параметров через стек вызовов.
Язык Си. Препроцессор. Макроопределения.
Язык Си. Препроцессор. Включаемые файлы. Условная компиляция.
Язык Си. Массивы. Многомерные массивы. Индексация многомерных массивов. Распределение памяти в многомерных массивах. Связь понятия указателя и массива. Инициализаторы массивов.
Язык Си. Строки. Длина строки. Строковые литералы (синтаксис, хранение в памяти, использования в качестве инициализаторов массивов).
Язык Си. Структуры. Синтаксис описания структур. Обращение к полям структур для объектов и к полям по указателю на объект типа структура. Инициализатор структур. 


Граф. Представление через матрицу смежности, список дуг, упакованный список дуг.
Дерево двоичного поиска, алгоритмы включения и удаления без балансировки, сравнение их сложности с известными алгоритмами на массивах.
Дерево, как частный вид графа. Способы представления деревьев в ЭВМ: левая и правая скобочная запись, список предков, указатели.
Динамическое программирование на примере конкретной задачи. Обратный ход.
Стек. Реализация стека через массив. Реализация стека через структуры с указателем.
Очередь. Реализация очереди через кольцевой буфер. Реализация очереди через структуры с указателем. Реализация очереди через два стека.
Система непересекающихся множеств. Реализация СНМ через дерево с рангом и сжатием путей.
Список. Реализации списка через структуры с одним указателем (односвязный список). Реализации списка через структуры с двумя указателями (двухсвязный список).