- •1.Рекурсия: прямая и косвенная.
- •2. Объект. Способы описания. Инкапсуляция. Полиморфизм. Наследование.
- •1.Процедуры и функции.
- •2. Способы представления графов.
- •1.Структура Unit-a.
- •2.Введение в Delphi. Главное окно: пиктографические кнопки, палитра компонентов. Окна: формы, инспектора объектов, кода программы. Основы визуального программирования.
- •1.Организация библиотек. Стандартные библиотечные модули и модули пользователя.
- •1.Файлы в Паскале: текстовые файлы, типизированные файлы, нетипизированные файлы, их назначение и использование.
- •2. Построение остовного дерева поиском в глубину (нерекурсивный вариант).
- •1.Создание удобного пользовательского интерфейса: системы меню, окна для ввода, корректировки, просмотра информации. Модуль Crt.
- •2.Сортировка подсчетом
- •1.Стандартные процедуры и функции Unit Graph. Методы создания анимации.
- •2.Основы визуального программирования. Пустая форма и ее модификация. Компоненты страницы Standard. Размещение нового компонента.
- •1.Сортировка обменом
- •2.Объект. Конструктор и деструктор. Виртуальные функции.
- •1.Переменные действительного типа, их объявление и использование.
- •2. Сортировка выбором
- •1.Статическое и динамическое распределение памяти. Понятие указателя.
- •2.Процедуры и функции модуля graph.
- •1.Доступ к системным ресурсам. Определение переменной как absolute.
- •2.Процедуры и функции модуля crt, их использование.
- •1.Динамические структуры данных и их организация с помощью указателей.
- •2.Файлы без типа, их применение.
- •1.Введение в комбинаторику. Генерация k–элементного подмножества данного множества. Размещения. Сочетания.
- •2. Законы алгебры логики. Таблицы истинности.?????
- •1.Генерация всех перестановок n–элементного множества в антилексикографическом порядке.
- •2. Создание и обработка типизированных файлов.?????
- •1.Алгоритм генерирования перестановок с минимальным числом транспозиций.
- •2. Объявление массивов????
- •1.Введение в теорию графов. Способы представления графов: матрицы смежности и инцидентности, списки инцидентностей.
- •2.Функции библиотеки dos. Прерывания. Обработка прерываний.?????
- •1.Связные компоненты графа. Деревья. Бинарное дерево как связный граф без циклов.????
- •2. Сортировка вставками
- •1.Поиск в глубину в графе
- •2. Итерационные циклы
- •Цикл с предусловием. Оператор while ... Do.
- •Цикл с постусловием. Оператор repeat... Until.
- •Обозначение циклов на блок-схемах согласно госТу.
- •1.Поиск в ширину в графе
- •2. Оператор выбора case
- •1.Эйлеровы пути в графе.
- •2. Ввод-вывод с помощью текстовых файлов.
- •1.Алгоритмы с возвратом, их реализация с помощью рекурсий и с использованием стека. Гамильтоновы циклы.
- •2. Объект. Инициализация и разрушение объекта.
- •1.Кратчайшие пути. Алгоритмы Дейкстры, Флойда.
- •2.Процедурные типы. Передача функций как параметров.
- •1.Передача параметров вызываемым программам.?????
- •2. Объект. Свойства объектов.
- •1.Очереди и операции над ними.
- •2. Сортировка слиянием
- •1.Структурированные типы данных: массивы, символьные переменные и строки, множества.
- •1. Массивы.
- •2. Строковый тип данных.
- •3. Множества.
- •4. Записи.
- •2. Условный оператор.
- •1.Создание и обработка одномерных динамических массивов.
- •2. Операторы цикла.
- •1.Стеки и операции над ними.
- •2. Поразрядная сортировка
- •1.Процедуры и функции.
- •2. Бинарные деревья, их создание. Способы обхода дерева.
- •1.Односвязные линейные списки и операции над ними.
- •2. Записи. Организация, размещение. Записи с вариантами.??????
- •1.Двухсвязные линейные списки и кольца, операции над ними.
- •2. Затем создаём два указателя:
- •1.Обход списка в прямом направлении и его вывод на экран монитора:
- •2.Обход списка в обратном направлении и его вывод на экран монитора:
- •2. Сортировка и поиск информации. Методы внутренней сортировки.
Обозначение циклов на блок-схемах согласно госТу.
ГОСТом предусмотрен единый блок для обозначения различных циклов (Рисунок 11). В блоке, соответствующем началу цикла указывается имя цикла (Как правило, это одна буква латинского алфавита) и начальное значение переменной цикла. В зависимости от оператора цикла, условие окончания записывается либо в блоке, соответствующем началу цикла (для операторов FOR…DO и WHILE…DO), либо в блоке, соответствующем концу цикла (для оператора REPEAT…UNTIL). Аналогично записывается и шаг изменения переменной цикла.
Билет № 19.
1.Поиск в ширину в графе
Поиск в ширину — метод обхода и разметки вершин графа. Поиск в ширину выполняется в следующем порядке: началу обхода s приписывается метка 0, смежным с ней вершинам — метка 1. Затем поочередно рассматривается окружение всех вершин с метками 1, и каждой из входящих в эти окружения вершин приписываем метку 2 и т. д.Если исходный граф связный, то поиск в ширину пометит все его вершины. Дуги вида (i, i+1) порождают остовный бесконтурный орграф, содержащий в качестве своей части остовное ордерево, называемое поисковым деревом. Легко увидеть, что с помощью поиска в ширину можно также занумеровать вершины, нумеруя вначале вершины с меткой 1, затем с меткой 2 и т. д. Поиск в ширину реализуется с помощью структуры очередь. Для этого занесем в очередь исходную вершину. Затем будем работать, пока очередь не опустеет, таким образом: выберем элемент из очереди и добавим все смежные ему элементы, которые еще не использованы.
2. Оператор выбора case
Оператор case используется для выбора одного из нескольких направлений дальнейшего хода программы. Этот оператор имеет вид: case p of a: s1; b: s2; . . n: sn; else sn+1; end; При выполнении оператора case сначала вычисляется выражение p, называемое селектором выбора. Выражение p должно принадлежать типу данных, имеющему конечное число значений (например: integer). Затем, в зависимости от полученного значения (если оно равно одной из констант a, b, …, n, которые называются константами выбора), выполняется один из операторов s1, s2, …, sn, помеченный соответствующей константой. Каждый из этих операторов может быть составным. Затем управление передается следующему (после case) оператору в программе.Если значение выражения p не совпадает ни с одной из констант выбора, выполняется оператор sn+1, содержащийся после ключевого слова else, причем ветвь else в операторе case необязательна.Зарезервированные слова case, of, else и end имеют смысл вариант, из, иначе и конец.Кроме одиночных констант в вариантах оператора case могут использоваться диапазоны значений и списки (представленные через запятую). Оператор case работает следующим образом. Сначала вычисляется значение выражения-селектора, затем в последовательности операторов отыскивается такой, которому предшествует константа, равная вычисленному значению. Если ни одна из констант не равна вычисленному значению, выполняется оператор, стоящий за словом else. Если слово else отсутствует, выполняется оператор, находящийся за словом end, т. е. первый оператор за границей case. Селектор должен относиться к одному из целочисленных типов (находящихся в диапазоне — 32768..32767): булевскому, литерному или пользовательскому. При использовании оператора выбора case должны .выполняться следующие правила: 1. Значения выражения "переключателя", записанного после служебного слова case, должны принадлежать дискретному типу (лат. discretus — прерывистый, дробный, состоящий из отдельных частей); для целого типа они должны лежать в диапазоне integer. 2. Все константы, предшествующие операторам альтернатив, должны иметь тип, совместимый с типом выражения. 3. Все константы в альтернативах должны быть уникальны в пределах оператора варианта (т. е. повторения констант в альтернативах не допускаются); диапазоны не должны пересекаться и не должны содержать констант, указанных в данной или других альтернативах.
Билет № 20