Программирование (семестр 2)
Экзаменационные вопросы (10 баллов)
Тип данных и переменная. Базовые и производные типы данных. Иерархия определений типов данных и вложенности компонент переменных. Контекстный способ определения типа данных в Си. Абстрактный тип данных. Спецификация typedef .
Модульная организация программы. Время жизни и область действия переменных. Классификация. Определение и объявление переменных. Внешние, автоматические и статические переменные. Область действия функций. Внешние и статические функции.
Модульное программирование. Статическое связывание. Библиотеки. Заголовочные файлы, их назначение и содержание. Файл проекта в классическом программировании.
Указатели. Указатель как элемент архитектуры компьютера. Синтаксис указателя в Си. Указатель и ссылка. Передача формальных параметров и результата по значению и по ссылке.
Адресная арифметика. Указатели и массивы. Способы работы через указатель с массивом.
Динамическая память. Динамические переменные и массивы. Операторы и функции управления динамической памятью.
Массивы указателей. Способы формирования массивов указателей - статические, динамические, смешанные. Работа с массивами указателей.
Списки. Определение элемента списка. Способы формирования списков. Односвязные списки. Двусвязные (циклические) списки.
Рекурсия. Рекурсивная структура данных и функция. Реализация рекурсивных функций, роль стека. Инвариант рекурсивной функции. Особенности разработки рекурсивных алгоритмов. Смысл локальных и глобальных переменных, формальных и фактических параметров в рекурсивной функции. Способы накопления результата.
Рекурсивные алгоритмы сортировки, трудоемкость.
Рекурсивные алгоритмы комбинаторного перебора.
Рекурсивные поисковые алгоритмы. Сокращение пространства перебора. Жадные алгоритмы. На примере алгоритма раскраски карты.
Деревья. Способы представления деревьев. Полный рекурсивный обход дерева (для всех способов представления).Алгоритмы, основанные на полном рекурсивном обходе дерева.
Двоичное дерево. Основные характеристики и алгоритмы. Балансировка дерева.
Дерево, упорядоченное по вертикали. Пирамидальная сортировка.
Указатель на функцию. Его определение в языке и назначение. Указатель на функцию - формальный параметр. Динамическое связывание. Пример - численное интегрирование.
Файл. Двоичный и текстовый файл. Запись. Последовательный и произвольный доступ. Текстовый файл. Позиционирование в текстовом файле. Пример - создание "закладок" в файле.
Двоичный файл (ДФ). Физическая модель двоичного файла. Шестнадцатеричный дамп. Функции работы с ДФ, чтение, запись, позиционирование.
Последовательный двоичный файл. Понятие формата. Пример: сохранение и загрузка дерева в последовательный ДФ.
ДФ произвольного доступа. Распределение памяти в двоичном файле. Файлы записей фиксированной и переменной длины.
Указатель в ДФ (абсолютный адрес и смещение). Использование указателей в ДФ на примере массива файловых указателей.
Экзаменационные задачи (25 баллов)
Задачу реализовать в виде функции, получающей все данные через параметры. Все структуры данных - динамические.
Замечания по выполняемым операциям. Объединение - результат содержит элементы из двух исходных структур данных (СД), элемент, присутствующий в обеих СД, включается в одном экземпляре. Пересечение - результат содержит элементы, одновременно присутствующие в обеих структурах данных. Разность - результат содержит элементы из первой СД, которые отсутствуют во второй.
Объединение двух динамических массивов указателей (ДМУ).
Пересечение двух динамических массивов указателей.
Разность двух динамических массивов указателей.
Объединение двух односвязных списков.
Пересечение двух односвязных списков.
Разность двух односвязных списков.
Объединение двух двусвязных списков.
Пересечение двух двусвязных списков.
Разность двух двусвязных списков.
Объединение двух циклических списков.
Пересечение двух циклических списков.
Разность двух циклических списков.
Сортировка односвязного списка выбором.
Сортировка односвязного списка вставками.
Сортировка двусвязного списка выбором.
Сортировка двусвязного списка вставками.
Сортировка циклического списка выбором.
Сортировка циклического списка вставками.
Элемент односвязного списка содержит массив указателей на строки. Функция создает структуру данных, читает из файла строки и заполняет ее, пока файл не кончится. (В конце последнего МУ записывается NULL-указатель).
Элемент двусвязного списка содержит массив указателей на строки. Функция создает структуру данных, читает из файла строки и заполняет ее, пока файл не кончится.(В конце последнего МУ записывается NULL-указатель).
Элемент циклического списка содержит массив указателей на строки. Функция создает структуру данных, читает из файла строки и заполняет ее, пока файл не кончится.(В конце последнего МУ записывается NULL-указатель).
Элемент односвязного списка содержит заголовок односвязного списка (двухуровневый список). Функция создает структуру данных, читает из файла строки и заполняет ее, пока файл не кончится. (длина списка нижнего уровня задана параметром).
Двухуровневый массив указателей на строки. Функция создает структуру данных, читает из файла строки и заполняет ее, пока файл не кончится. В конце каждого неполного МУ записывается NULL-указатель в качестве ограничителя.
Дерево со списком потомков. Вершина дерева содержит указатель на строку. Полный рекурсивный обход дерева с сохранением адресов строк в динамическом массиве указателей.
Дерево со списком потомков. Поиск вершины с максимальным количеством прямых потомков (результат - указатель на вершину).
Дерево с массивом указателей на потомков. Вершина дерева содержит указатель на строку. Полный рекурсивный обход дерева с сохранением строк в динамическом массиве указателей.
Дерево с массивом указателей на потомков. Поиск вершины с максимальным количеством прямых потомков (результат - указатель на вершину).
Дерево с массивом указателей на потомков. Поиск ближайшей вершины со свободным местом (в МУ потомков есть свободное место) (результат - указатель на вершину).
Дерево с массивом указателей на потомков. Поиск вершины, наиболее удаленной от корня (результат - указатель на вершину).
Двоичное дерево в массиве с вычисляемыми адресами потомков. Включение значения в двоичное дерево.
Тестовые задания (по 3 балла за тест, но не более 10)
Содержательно сформулировать результат теста, прокомментировать отдельные действия, записать пример вызова функции на статических данных и ожидаемый результат.
