Программирование (группы АП, семестр 4)
Экзаменационные вопросы
Тип данных и переменная. Базовые и производные типы данных. Иерархия определений типов данных и вложенности компонент переменных. Контекстный способ определения типа данных в Си. Абстрактный тип данных. Спецификация typedef .
Модульная организация программы. Время жизни и область действия переменных. Классификация. Определение и объявление переменных. Внешние, автоматические и статические переменные. Область действия функций. Внешние и статические функции.
Модульное программирование. Статическое связывание. Библиотеки. Заголовочные файлы, их назначение и содержание. Файл проекта в классическом программировании.
Указатели. Указатель как элемент архитектуры компьютера. Синтаксис указателя в Си. Указатель и ссылка. Передача формальных параметров и результата по значению и по ссылке. Адресная арифметика. Указатели и массивы. Способы работы через указатель с массивом. Динамическая память. Динамические переменные и массивы. Операторы и функции управления динамической памятью.
Трудоемкость алгоритмов. Определение трудоемкости. O-нотация. Способы оценки трудоемкости простейших программ.
Сортировка и поиск. Понятие записи и ключа. Линейный и двоичный поиск. Трудоемкость алгоритмов сортировки и поиска. Классификация сортировок: выбор, вставка, обмен, подсчет, разделение, слияние.
Структура данных как система взаимосвязанных переменных и значений. Статические и динамические структуры данных. Последовательность. Стек и очередь. Свойства. Представление стека и очереди в массиве и списке. Использование стека при вызове функции.
Массивы указателей. Способы формирования массивов указателей - статические, динамические, смешанные. Работа с массивами указателей.
Списки. Определение элемента списка. Способы формирования списков. Односвязные списки. Двусвязные (циклические) списки.
Рекурсия. Рекурсивная структура данных и функция. Реализация рекурсивных функций, роль стека. Инвариант рекурсивной функции. Особенности разработки рекурсивных алгоритмов. Смысл локальных и глобальных переменных, формальных и фактических параметров в рекурсивной функции. Способы накопления результата.
Рекурсивные алгоритмы сортировки, трудоемкость. Рекурсивные алгоритмы комбинаторного перебора.
Рекурсивные поисковые алгоритмы. Сокращение пространства перебора. Жадные алгоритмы.
Деревья. Способы представления деревьев. Полный рекурсивный обход, ветвление. Алгоритмы, основанные на полном рекурсивном обходе дерева. Эффективность алгоритмов на деревьях.
Двоичное дерево. Основные характеристики и алгоритмы. Балансировка дерева.
Указатель на функцию. Его определение в языке и назначение. Указатель на функцию - формальный параметр. Динамическое связывание. Использование массивов указателей при реализации виртуальных функций.
Файл. Двоичный и текстовый файл. Запись. Последовательный и произвольный доступ. Текстовый файл. Особенности представления и преобразования строки текста. Функции для работы с текстовым файлом. Позиционирование в текстовом файле.
Двоичный файл. Способы распределения памяти в двоичном файле. Классификация форматов представления данных в двоичных файлах. Файлы записей фиксированной и переменной длины. Параметризованный файл записей фиксированной длины. Представление таблицы с произвольными типами полей в файле.
Указатель в файле. Связанные записи в файле. Сохранение и загрузка дерева и массива указателей в файле. Способы работы со связанными записями в файле: загрузка всей структуры данных, поэлементная загрузка, кэширование.
Определение класса и объекта. Свойства и методы (функции) класса. Синтаксическое и технологическое определение класса. Технология ООП. Программирование от функции к функции и от класса к классу. "Эпизодическое" и "тотальное" ООП.
Синтаксис определения класса и объекта в Си++. Функция, встраиваемые в структуру. Указатель this. Определение функции (метода) в заголовке класса и вне его.
Закрытая и общая части класса. Назначение закрытых и открытых данных и методов. Дружественность. Конструктор и деструктор. Глобальные, локальные и динамические объекты.
Переопределение операций. Синтаксис. Операнды, результат. Переопределение операций внутри и вне класса. Особенности переопределения некоторых операций (сравнение, присваивание, вывод в поток, [], (), приведение типа).
Конструктор копирования, принципы передачи объектов по ссылке и по значению. Способы передачи параметров (операндов) в методы. Конвейер ссылок и конвейер значений.
Основные технологические при принципы определения класса. Представление данных переменной размерности в объектах. Классы типов данных: cтроки переменной длины, матрицы, полиномы.
Представление структур данных в виде классов. Классы динамического массива указателей и списка и дерева.
Наследование. Иерархия объектов. Базовый и производный классы. Наследование данных и методов. Наследование как основа программирования "от класса к классу". Объектно-ориентированные библиотеки, работа с ними с использованием наследования. Наследование. Способы наследования методов: полное наследование, перекрытие, частичное (условное) наследование. Конструирование объектов вложенных классов.
Ограничения доступа при наследовании: личная (закрытая), общая и защищенная области класса. Обычное и публичное наследование.
Преобразование указателей на базовый и производный класс. "Расширение" и "сужение". Полиморфизм. Виртуальная функция. Определение и механизм реализации.
Внешний и внутренний полиморфизм. Виртуальная функция как основа для создания интерфейсов. Абстрактные базовые классы. Виртуальная функция как элемент "отложенного" программирования.
Статические элементы класса и методы класса и их использование. Множественное наследование. Виртуальные базовые классы.
Технология модульного проектирования ООП-программ. Статическое связывание и компоновка. Заголовочный файл и файл тела класса. Структура проекта ООП-программы.
Шаблон как макроопределение класса. Параметры шаблонов. Примеры шаблонов структур данных: стек, очередь, список. Требования к объектам - параметрам шаблонов.
Модульное программирование на "классическом Си". Статическое связывание: внешняя ссылка и точка входа. Заголовочные файлы, объектные модули, библиотека. Компоновка. Структура проекта на "классическом" Си
Модульное программирование на Си++. Файл описания класса и файл тела класса. Inline-методы. Структура проекта на Си++.
Экзаменационные задачи
Разработать указанный метод для заданного класса. Задача должна включать определение внутренних структур данных класса, разработку заголовка класса, конструктора и деструктора, указанного метода (функции или переопределенной операции с заданным способом передачи параметров или операндов), а также вспомогательных элементов класса, необходимых для реализации указанного метода (конструктор копирования, управление динамической памятью).
Содержание разрабатываемого класса.
Матрица переменной размерности, представленная динамическим массивом указателей на строки.
Матрица переменной размерности, представленная линейным динамическим массивом коэффициентов (двумерный массив разложен по строкам в линейный).
Разреженная матрица переменной размерности, представленная списком ненулевых коэффициентов (элемент списка содержит координаты коэффициента и его значение).
Разреженная матрица переменной размерности, представленная динамическим массивом описателей коэффициентов (описатель содержит координаты коэффициента и его значение).
Степенной полином произвольной степени.
Шаблон структуры данных – динамический массив указателей
Шаблон структуры данных – односвязный список, элемент списка содержит указатель на объект.
Шаблон структуры данных – односвязный список, элемент списка содержит непосредственно объект.
Шаблон структуры данных – двусвязный список, элемент списка содержит указатель на объект.
Шаблон структуры данных – двусвязный список, элемент списка содержит непосредственно объект.
Шаблон структуры данных – двусвязный циклический список, элемент списка содержит указатель на объект.
Шаблон структуры данных – двусвязный циклический список, элемент списка содержит непосредственно объект.
Шаблон структуры данных – двоичное дерево. Для операции извлечения по логическому номеру каждая вершина содержит счетчик вершин в поддереве.
Шаблон структуры данных – дерево, хранящее данные в концевых вершинах. Для операции извлечения по логическому номеру каждая вершина содержит счетчик вершин в поддереве.
Шаблон структуры данных – стек, представленный динамическим массивом объектов. При переполнении производится перераспределение памяти.
Шаблон структуры данных – стек, представленный односвязным списком.
Шаблон структуры данных – циклическая очередь, представленная динамическим массивом объектов. При переполнении производится перераспределение памяти.
Шаблон структуры данных – очередь, представленная циклическим списком.
Шаблон структуры данных – упорядоченная последовательность, представленная динамическим массивом объектов. При переполнении производится перераспределение памяти
Метод разрабатываемого класса.
Вставка по логическому номеру (переопределение операции объект(T,int)).
Вставка с сохранением порядка (переопределение операции объект << T).
Удаление по логическому номеру, переопределение операции объект[int].
Получение объекта по логическому номеру, переопределение операции объект[int].
Добавление объекта (переопределение операции объект << T).
Переопределение операции вывода в текстовый поток (переопределение операции ostream << объект).
Переопределение операции ввода из текстового потока (переопределение операции istream >> объект).
Сохранение в двоичный файловый поток.
Загрузка из двоичного файлового потока.
Сортировка выбором.
Сортировка вставками.
Сложение двух объектов. Переопределение операции "+". Результат – новый объект (копия).
Умножение двух объектов. Переопределение операции "*". Результат – новый объект (копия).
Конструктор объекта из массива параметров (коэффициентов).
Конструктор копирования.
Тестовые задания
Тестовые задания из глав 10-11 электронного учебника.
