Оператор1, оператор2, ... , операторN

UNTIL условие;

где оператор1, оператор2,..., операторN - операторы тела цикла;

условие - логическое выражение, диктующее завершение повторов.

Оператор цикла с постусловием начинается с выполнения операторов внутри цикла. Затем проверяется истинность логического условия, стоящего после слова UNTIL. Если это условие справедливо (True), то осуществляется выход из цикла. Если же значение логического выражения ложно (False), то выполнение операторов тела цикла повторяется, после чего снова проверяется истинность логического условия.

12. Дайте определение массива. Перечислите способы объявления массива.

МАССИВ - упорядоченная группа фиксированного количества переменных одного типа, имеющая общее имя.

Массив описывается в разделе переменных посредством указания типа его элементов и максимального их количества. Тип элементов может быть любым. При задании максимального числа элементов массива (числа ячеек таблицы) обычно употребляют диапазон целых чисел. Общий вид описания массива следующий:

Возможны два способа описания массивов:

Typeимя типа = Array[t,t₁,...,t_n ] Of тип элементов;

Varимя массива: имя типа;

или

Var имя массива:Array[t,t₁,...,t_n ] Of тип элементов;

здесь t, t₁,...,t_n - типы индексов массива (любой скалярный тип, кроме real) или размерность.

К имени массива предъявляются те же требования, что и к имени переменной.

Размерность - это диапазон целых чисел, каждое из которых является порядковым номером (индексом) одной из ячеек массива. Обычно диапазон индексов задают, начиная от единицы: [1..100]. Это удобно, но не обязательно. Важно лишь, чтобы правая граница диапазона была больше или равна левой границе.

13. Дайте определение понятию «подпрограмма». Назовите основное отличие процедур от функций. Опишите структуру процедуры и функции.

Подпрограммой называется именованная логически законченная группа операторов, которую можно многократно вызвать для выполнения по имени из различных мест программы.

Отличие функции от процедуры заключается в том, что результатом исполнения операторов, образующих тело функции, всегда является некоторое единственное значение или указатель, поэтому обращение к функции можно использовать в соответствующих выражениях наряду с переменными и константами.

Описание процедуры имеет вид:

Procedure имя (формальные параметры);

раздел описаний

Begin

раздел операторов

End;

и помещается в разделе описаний основной программы (глобальном блоке).

Подпрограмма-функция аналогична процедуре, но имеет следующие отличия.

1. Заголовок функции имеет вид

Function имя (формальные параметры): тип функции;

2. Функция имеет только один результат выполнения.

3. Результат обозначается именем функции, поэтому в разделе операторов функции обязательно должен присутствовать оператор присваивания, в левой части которого стоит имя этой функции.

4. Вызов функции в основной программе осуществляется непосредственно внутри выражения по ее имени с указанием фактических параметров.

14. Опишите структуру Unit-модуля. Ключевые слова Unit, Interface, Implementation. Описание каждого раздела.

Структура модуля имеет вид:

ЗАГОЛОВОК МОДУЛЯ

Unit < имя модуля >;

ИНТЕРФЕЙСНАЯ ЧАСТЬ

Interfaсe

Uses < список используемых модулей >

Type{ открытые объявления переменных, которые будут доступны в основной программе}

Var

Procedure

Function

РЕАЛИЗАЦИОННАЯ ЧАСТЬ или ИСПОЛНЯЕМАЯ ЧАСТЬ

Implementation {выполнение}

Uses < список используемых модулей >

{ собственные объявления, доступны только внутри данной реализации подпрограмм}

Type

Var

{ процедуры и функции }

Procedure

Function

ИНИЦИИРУЮЩАЯ ЧАСТЬ

Begin

… {Основной блок модуля}

End.

15. Дайте определение понятию «строка». Опишите формат строки.

Строка - это последовательность символов кодовой таблицы персональной ЭВМ. При использовании в выражениях строка-константа заключается в апострофы. Длина строки равняется количеству символов в этой строке и может изменяться от 0 до 255.

Форма описания строковых данных:

Type имя типа = String [максимальная длина строки];

Var имя строковой переменной: имя типа;

или

Var имя строковой переменной: String [максимальная длина строки];

16. Дайте определение понятия «запись». Опишите формат объявления структуры типа запись.

Запись - это структурированный тип данных, состоящий из фиксированного числа компонентов одного или нескольких типов, называемых полями записи. Определение типа записи начинается идентификатором Record и заканчивается зарезервированным словом end. Между ними заключен список компонентов, называемых полями, с указанием имен полей и типа каждого поля. Структура объявления типа записи такова:

Type <имя типа> = Record

<имя поля1>: <тип компонентов>;

…

<имя поляN>: <тип компонентов>;

End;

VAR <имя переменной>: <имя типа>;

17. Дайте определение понятия «множество». Перечислите операции, производимые над множествами. Опишите формат множества.

Множество – это структурированный тип данных, представляющий собой набор взаимосвязанных по какому-либо признаку или группе признаков объектов, которые можно рассматривать как единое целое. Каждый объект во множестве называется элементом множества.

Все элементы множества должны принадлежать одному из скалярных типов, кромевещественного. При работе с множествами допускается использование операций отношения, “=”, “<>”, “>=”, “<=”, объединения, пересечения, разности множеств и операции in. Результатом выражения с применением этих операций является значение True или False.

Формат записи множественных типов:

Type <имя типа> = set of <элемент 1,…., элементN>;

Var <идентификатор, ….>: <имя типа>;

Можно задать множественный тип и без предварительного описания:

Var <идентификатор, …>: set of <элемент1, …>;

18. Раскройте суть понятия «сортировка». Перечислите типы сортировок с краткой их характеристикой.

Под сортировкой понимают процесс переупорядочивания некоторого множества объектов с целью их размещения в заданном порядке. Существует три категории прямых методов внутренней сортировки (сортировка включением, сортировка выбором, обменная сортировка).

Сортировка прямым включением.

Допустим, что массив a[1..n] разбит на две части a_1..i-1, a_i..n – в первой части элементы упорядочены, во второй – нет. При i=2 такое разбиение получается автоматически, т.к. массив из одного элемента тривиально упорядочен. На каждом шаге i=2..n выполняем элементарный алгоритм: берем очередной элемент r из неупорядоченной части и включаем его в «нужное» место упорядоченной части. Для поиска нужного места в нижеприведенном алгоритме используется барьер a[0]:=x. Элементы, начиная от i-1 до нужного j сдвигаются на одну позицию: a[j]:=a[j-1]. На каждом проходе происходит перемещение i -того элемента в готовую последовательность, а некоторое число элементов сдвигается вправо. Данный процесс перемещения называется просачиванием элемента.

Сортировка бинарными включениями.

Алгоритм сортировки прямыми включениями можно легко улучшить, пользуясь тем, что готовая последовательность a[1],...,a[i-1], в которую нужно включить новый элемент, уже упорядочена. Поэтому место включения можно найти значительно быстрее, применив бинарный поиск, который исследует средний элемент готовой последовательности и продолжает деление пополам, пока не будет найдено место включения. Модифицированный алгоритм сортировки называется сортировкой бинарными включениями.

Прямой выбор.

Для i=1..n-1 выполняется следующий элементарный алгоритм: среди элементов a_i..n выбираем минимальный a_m и переставляем местами элементы i -й и m -й. В результате на первое место станет самый минимальный, на второе – следующий минимальный и т.д.

Сортировка прямого обмена (пузырьковая).

Это метод, в котором обмен двух элементов является основной характеристикой процесса. Алгоритм сортировки простым обменом основан на принципе сравнения и обмена пары соседних элементов до тех пор, пока не будут рассортированы все элементы. Для i=1..n-1 выполняется следующий элементарный алгоритм: начиная от n до i последовательно проверяем упорядоченность двух соседних элементов a[j] и a[j-1], и если они не упорядочены, то меняем их местами. В результате такого обмена минимальный элемент перемещается на место i.

Шейкерная сортировка.

Улучшение алгоритма - это запоминать, производится ли на данном проходе какой-либо обмен. Если нет, то это означает, что алгоритм может закончить работу. Этот процесс улучшения можно продолжить, если запомнить не только сам факт обмена, но и место (индекс) последнего обмена.

Однако внимательный программист заметит здесь странную асимметрию: один неправильно расположенный "пузырек" в "тяжелом" конце рассортированного массива всплывет на место за один проход, а неправильно расположенный элемент в "легком" конце будет опускаться на правильное место только на один шаг на каждом проходе. Изменение направления сортировки в каждом из проходов алгоритма поиска называют шейкерной сортировкой.

Для того чтобы тяжелые элементы сразу попадали вниз, пузырьковую сортировку выполняют так, чтобы направление прохода было снизу вверх, следующий проход - сверху вниз и так далее.

Пирамидальная сортировка.

Предположим, что дана пирамида с элементами h_l+1,..., h_r для некоторых значений l и r и нужно добавить новый элемент x для того, чтобы сформировать расширенную пирамиду h_l,..., h_r. Новый элемент x сначала помещается в вершину дерева, а затем “просеивается” по пути, на котором находятся меньшие по сравнению с ним элементы, которые одновременно поднимаются вверх; таким образом, формируется новая пирамида.

Обменная сортировка разделением (быстрая сортировка).

Выбирается любой произвольный элемент массива, далее массив просматривается слева направо до тех пор пока не будет найден элемент больший выбранного; а затем просмотрим его справа налево, пока не найдем элемент меньший выбранного. Найденные элементы поменяем местами. Затем продолжим процесс “просмотра с обменом”, пока два просмотра не встретятся где-то в середине массива. В результате массив разделится на две части: левую - с ключами меньшими выбранного элемента; и правую - с большими ключами. Описанный алгоритм применяется к обоим этим частям, в результате чего последовательность разбивается на 4 части. Алгоритм применяется к каждой четвертинке и т.д. Разделение заканчивается, когда в каждой части остается 1 элемент.

19. Дайте определение «Рекурсия», «Условие завершения рекурсии», «Косвенная рекурсия».

Рекурсия – процедура (функция), которая обращается к самой себе или вызывает саму себя. Содержание и мощность рекурсивного определения, а также главное назначение, состоит в том, что оно позволяет с помощью конечного выражения определить бесконечное множество объектов. Максимальное число рекурсивных вызовов процедуры без возвратов, которое происходит во время выполнения программы, называется глубиной рекурсии. Число рекурсивных вызовов в каждый конкретный момент времени, называется текущим уровнем рекурсии. Главное требование к рекурсивным процедурам заключается в том, что вызов рекурсивной процедуры должен выполняться по условию, которое на каком-то уровне рекурсии станет ложным. Косвенной или взаимной рекурсией называется организация вызовов нескольких процедур и функций по кругу (первая процедура вызывает вторую, вторая - третью,..., n-я процедура вызывает первую).

20. Дайте понятие «текстовый файл». Опишите формат объявления текстового файла.

Текстовые файлы состоят из последовательности символов, разделенных на строки. Каждый текстовый файл разделяется на строки неопределенной длины, которые заканчиваются символом конец строки. Каждый символ представлен во внутреннем коде ASCII и занимает 1 байт. Текстовый файл отличается от символьного не только делением на строки. В текстовый файл можно записать и из него прочитать информацию любого типа. Если эта информация не символьная, то в процессе чтения или записи происходит ее преобразование из символьной формы во внутреннюю и обратно.

К текстовым файлам возможен только последовательный доступ. С текстовыми файлами работают различные редакторы текстов. Текстовые файлы имеют стандартный тип TEXT.

Формат описания