 |
Теория языков программирования и методы трансляции
|
|
|
|
Примерный перечень вопросов к государственному экзамену
По специальности ПОВТ
(2012-2013уч.год)
Структуры и алгоритмы обработки данных
1. Линейные списки – стеки, очереди, деки. Набор процедур для работы со связанным стеком, очередью.
2. Кольцевые списки. Многосвязные списки, примеры применения.
3. Древовидная структура, основные понятия. Способы обхода бинарного дерева.
4. Дерево поиска. Включение элементов. Удаление элементов из дерева поиска.
5. В-деревья, их свойства, построение. Индексирование массивов данных. Индексные деревья.
6. Применение бинарных деревьев. Кодирование и сжатие данных. Кодовые деревья, дерево Хаффмена.
7. Сортировка. Методы вставок и обмена. Метод Шелла. Быстрая сортировка. Обменная поразрядная сортировка.
8. Сортировка. Методы выбора и слияния. Простой, квадратичный выбор. Выбор из дерева. Двухпутевое слияние. Метод слияния списков.
9. Алгоритмы поиска данных. Последовательный, двоичный, блочный, интерполяционный, Фибоначчиев поиск.
10. Хеширование, хеш-функции. Способы разрешения коллизий.
Функциональное и логическое программирование
1. Структура программы на языке Пролог и ее разделы. Основная терминология. Стандартные домены. Способы описания параметров предикатов.
2. Способы реализации повторяющихся действий в языке Пролог. Использование повторения. Отсечение и откат. Метод повторения, определяемый пользователем. Рекурсия. Примеры реализации.
3. Списки в языке Пролог. Описание, установление связи между различными списками, доступ к элементам списка. Сортировка списков. Слияние и разделение списков.
|
|
|
4. Обработка строк в языке Пролог. Работа с файлами в Прологе. Пример управления потоками ввода-вывода.
5. Составные объекты в языке Пролог. Способы описания и использования.
6. Структуры данных ядра Лиспа. Базовые функции языка Лисп. Способ создания пользовательских функций. Примеры функций удаления элементов из списка по заданному правилу. Примеры функций проверки принадлежности элемента списку и эквивалентности списков.
7. Управляющие структуры в языке Лисп. Разветвление вычислительного процесса. Работа с контекстом и организация циклических процедур. Операторные скобки и передача управления. Примеры реализации.
8. Прямой доступ к элементам списка в языке Лисп. Возможные способы реализации прямого доступа. Функции, используемые для формирования списков в Лиспе. Сравнительные возможности этих функций.
9. Обработка строк в языке Лисп. Пример удаления всех вхождений заданной подстроки из заданной строки.
10. Внутреннее представление объектов языка Лисп. Структура символа. Списки, физическая и логическая структура.
Объектно-ориентированное программирование
1. Перечислить и дать характеристику основным причинам сложности программного обеспечения. Общие признаки любой сложной системы; приемы борьбы со сложностью ПО.
2. Перечислить и дать характеристику основным разновидностям стилей (парадигм) программирования. Роль объектно-ориентированной парадигмы. Основные и дополнительные элементы объектной модели.
3. Ссылки в языке С++, использование ссылок. Отличие ссылок от указателей. Передача аргументов функций по ссылке. Перегрузка функций; правила перегрузки.
4. Общее понятие класса языка С++. Классы как абстрактные типы данных. Синтаксис описания класса. Виды членов класса. Управление доступом к членам класса. Инкапсуляция. Интерфейс и реализация класса. Объекты (экземпляры) класса и способы их создания.
|
|
|
5. Конструкторы и деструкторы класса. Виды конструкторов класса: конструктор по умолчанию, копирующий конструктор, конструкторы преобразования типа, прочие конструкторы. Правила вызова конструкторов различных видов. Вызов деструктора.
6. Перегрузка операций для классов. Назначение и способы перегрузки. Принципы и правила перегрузки операций. Пример перегрузки операции «=». Рекомендации по перегрузке операций; правильные форматы перегруженных операций.
7. Перечислить и дать характеристику видов отношений между классами. Привести примеры для каждого вида отношений.
8. Отношение между классами типа «наследование». Отличия наследования от агрегации. Иерархия наследования. Синтаксис наследования. Открытое и закрытое наследование. Назначение «защищенных» (protected) членов базового класса. Виртуальные функции и их назначение. Полиморфизм. Виртуальные деструкторы и правила их использования. Чисто виртуальные функции и абстрактные классы. Наследование интерфейса и наследование реализации.
9. Концепция параметризуемых типов (шаблонов) в языке С++. Шаблоны классов. Различия между шаблонами и классами. Синтаксис описания шаблона. Создание объекта шаблонного класса (инстанцирование шаблона). Шаблоны функций. Связь между шаблонами функций и перегрузкой.
10. Понятие исключения (особой ситуации). Механизм обработки исключений. Синтаксические конструкции языка для обработки исключений. Различение особых ситуаций. Имена особых ситуаций. Группирование исключений. Повторная генерация исключений; перехват всех исключений.
Теория языков программирования и методы трансляции
1. Языки программирования и формальные языки. Понятие транслятора и компилятора. Фазы компиляции. Инструменты и технологии разработки и реализации языков программирования.
2. Способы задания формальных языков (перечислить). Задание языка при помощи грамматики (основные определения), классификация
грамматик и языков (привести примеры грамматик и выводов цепочек).
3. Способы задания формальных языков (перечислить). Задание языка при помощи распознавателей. Модели распознавателей: конечные автоматы и автоматы с магазинной памятью (основные определения, привести примеры распознавателей).
|
|
|
4. Способы задания формальных языков(перечислить). Праволинейные и регулярные языки. Задание языка при помощи регулярных выражений и синтаксических диаграмм (применение в языках программирования).
5. Классификация языков и грамматик. Соответствия между способами задания языков. Соответствия между КС-грамматиками и МП-автоматами. Построение МП-автомата, моделирующего левые выводы по заданной КС-грамматике (построить МП-автомат для конкретной КС-грамматики).
6. Общая характеристика процесса сканирования. Методики конструирования сканеров (характеристика каждого этапа построения сканера и применяемые методы). Представление результатов сканирования.
7. Определение синтаксического разбора. Модели анализаторов. Построение левого анализатора по заданной КС-грамматике (привести пример).
8. Свойства КС-языков и грамматик. Эквивалентные преобразования КС-
грамматик (перечислить виды преобразований) и их применение в разработке трансляторов. Устранение левой рекурсии и факторизация (привести пример и пояснить на каком этапе разработки языка применяются эти преобразования).
9. Классы лево- и право- анализируемых грамматик (определение). Левые и правые анализаторы. LL(k) – грамматики и их место в разработке языков программирования. Модель LL(k) – анализатора.
10. Основные функции семантического анализа. Способы представления промежуточной программы. Применение моделей синтаксически управляемой трансляции (СУ-перевода) в разработке анализаторов.
|
|
|
