Вопросы к экзамену-2013
Рабочая программа
по курсу «Информационные технологии»
Этапы трансляции программы. Препроцессор, компилятор, компоновщик.
Типы данных в языке C, преобразование типов. Арифметические и логические операции, операции присвоения, сравнения.
Операторы ветвления if и switch: синтаксис, блок-схемы, примеры использования.
Циклы for, while и do-while: синтаксис, блок-схемы, примеры использования.
Массивы: виды массивов (числовые, символьные и массивы структур), объявление, инициализация, примеры использования.
Указатели: назначение, синтаксис, операции с указателями, примеры использования.
Строки в языке C, библиотечные функции для работы со строками (string.h).
Структура программы на языке C. Функции: синтаксис, передача и возврат параметров, примеры использования.
Организация памяти в программе на языке C. Виды памяти данных: стек, статическая и динамическая память.
Структуры и объединения: назначение, синтаксис, примеры использования.
Средства ввода-вывода в языке C. Стандартные потоки stdin, stdout, stderr.
Линейные структуры данных: одно- и двусвязный список, стек, очередь, дек, ассоциативный массив.
Деревья: назначение и виды. Способы обхода деревьев.
Двоичные деревья поиска: назначение, основные свойства. Процедуры добавления, удаления, поиска узлов и обхода в порядке неубывания ключей в двоичном дереве поиска.
Двоичные деревья поиска: назначение, основные свойства. Балансировка деревьев с помощью алгоритмов Адельсон-Вельского и Ландиса (АВЛ).
Красно-черные деревья: назначение, основные свойства. Добавление новых узлов в красно-черное дерево.
Графы: структура, способы задания, способы обхода, примеры использования.
Волновой алгоритм Ли.
Основные задачи теории графов. Теоремы Эйлера.
Задача о минимальном остовном дереве. Алгоритм Прима.
Задача поиска кратчайших расстояний. Алгоритм Дейкстры.
Задача о максимальном потоке. Модифицированный алгоритм Форда-Фалкерсона.
Планарность графов. Теорема Понтрягина-Куратовского.