2.Функции библиотеки dos. Прерывания. Обработка прерываний.?????

Билет № 17.

1.Связные компоненты графа. Деревья. Бинарное дерево как связный граф без циклов.????

2. Сортировка вставками

Метод простых вставок. Согласно методу простых вставок элементы последовательности, начиная со второго, вставляются в уже упорядоченную подпоследовательность. Для того, чтобы не проверять сложное условие в цикле пока, очередной вставляемый элемент ставится на место нулевого и служит барьером, когда вставляемый элемент оказывается меньшим элементом подпоследовательности. Одновременно с поиском места вставки большие элементы сдвигаются на одну позицию к концу подпоследовательности. Одним из лучших методов сортировки является метод Шелла, который основан на методе простых вставок. Этот метод подобен методу Бэтчера, только подмассивы сортируются не методом обмена, а методом простых вставок.

Билет № 18.

1.Поиск в глубину в графе

Поиск в глубину (англ. Depth-first search, DFS) — один из методов обхода графа. Алгоритм поиска описывается следующим образом: для каждой непройденной вершины необходимо найти все не пройденные смежные вершины и повторить поиск для них. Используется в качестве подпрограммы в алгоритмах поиска одно- и двусвязных компонент, топологической сортировки.

2. Итерационные циклы

Если число повторений заранее не известно и решение о завершении цикла принимается на основе анализа некоторого условия, то такой повторяющийся вычислительный процесс называется итерационным циклом.

В Паскале для организации итерационных циклов предусмотрено две алгоритмические структуры. Первая структура называется «цикл с предусловием» и использует оператор WHILE ... DO (рисунок 10. а). Вторая структура носит название «цикл с постусловием» и реализуется оператором REPEAT... UNTIL (рисунок 10. б).

Цикл с предусловием. Оператор while ... Do.

Синтаксическая структура оператора цикла с предусловием имеет вид:

WHILE < Логическое выражение, или переменная > DO < Оператор >;

Как видно из блок-схемы (рисунок 10.а), перед каждым выполнением цикла анализируется логическое выражение или переменная. При значении TRUE выполняется оператор, составляющий тело цикла. При значении FALSE управление передается следующему за циклом оператору. Если условие ложно с самого начала, то оператор не выполняется ни разу.

Цикл с постусловием. Оператор repeat... Until.

Недостатком оператора WHILE является то, что в цикле можно выполнить только один оператор, поэтому приходится в большинстве случаев использовать операторные скобки BEGIN...END. Этого недостатка лишен оператор цикла с постусловием (иногда его называют оператором «повтора», рисунок 10. б), имеющим следующий вид: REPEAT <Оператор 1>; <Оператор 2>; … < Оператор К> UNTIL   <Условие>; Ключевые слова REPEAT и UNTIL этого оператора играют роль операторных скобок BEGIN ... END. Поэтому эта конструкция тоже один оператор.

Break, Continue.

В циклах FOR, REPEAT, WHILE можно использовать процедуры BREAK и CONTINUE. Первая процедура позволяет досрочно выйти из цикла, не дожидаясь выполнения условий выхода. Вторая процедура позволяет начать новую итерацию цикла даже в том случае, если предыдущая итерация не завершена. Использование этих процедур ускоряет работу программы в рамках принципа структурного программирования.