Вопрос 39 Способы обхода дерева

Обход дерева-последовательное обращение ко всем его узлам. Виды:1)В глубину (прямой, симметричный, обратный)2)В ширину. Прямой(сверху - вниз): 1) Выполняется действие над узлом начиная с корня, 2)Выполняется рекурсивный прямой обход левого поддерева, 3)Выполняется рекурсивный прямой обход правого поддерева. Симметричный(слева - направо): 1)Выполняется рекурсивный симметричный обход левого поддерева, 2)Операция с узлом, 3) Выполняется рекурсивный симметричный обход правого поддерева. Обратный(снизу – вверх): 1)Выполняется рекурсивный обратный обход левого поддерева, 2) Выполняется рекурсивный обратный обход правого поддерева, 3)Операция с узлом. (Примеры)

Вопрос 3 Жизненный цикл программного продукта

Ж.ц.-период от момента появления идеи создания некоторого ПО, до момента завершения его поддержки фирмой-разработчиком. Стандарт ISO/IEC 12207:1995

Вопрос 32 Стек

Частный случай линейного однонаправленного списка, для которого разрешено добавление и удаление элементов только в вершину стека. Для работы со стеком необходимо иметь указатель на текущий элемент и на вершину стека. Создани естека из целых чисел:

Type TStek=^TElement;

TElement=record

inf:byte;

link:TStek;

end; Удаление элемента из

С оздание первого элемента Добавление нового и списка

переустановка указателей

Top:=nil; New(P);

New(P); p^.inf:=5;

p^.inf:=7; p^.link:=Top; P:Top; Top:=P^.link;

p^.link:=nil; Top:=p; Dispose(P);

Top:=p;

Вопрос 37 Деревья

Это нелинейные структуры данных, каждый элемент которых ссылается на нижележащие элементы, при этом количество указателей, используемых при описании типа данных, зависит от количества нижележащих элементов. Корень - узел в который не входит ни одна ветвь. Лист-узел из которого не выходят ветви. Внутренний узел - не корень и не лист. Родительский узел-узел который находится непосредственно над данным узлом. Дочерний узел- узел который находится непосредственно под данным узлом. Предки узла - все узлы на пути вверх от данного узла до корня. Потомки узла – все узлы расположенные ниже данного. Степень узла - количество его дочерних узлов. Степень дерева - максимальная степень его узлов. По степени различают деревья бинарные и сильно ветвящиеся (3-й и более степени). Описание дерева степени n: Type TTRee=^TElement; TElement=record inf:базовый тип данных; link1,link2,…,linkn:TTree;end;

Глубина узлов-количество предков узла +1. Глубина дерева-макс. глубина всех узлов. Бинарное дерево-нелинейная структура данных степени 2. Пример бинарного дерева, его корень..-..потомки Type TTree=^TElement; TElement=Record

inf:byte; left,right:TTree; end;

В опрос 33 Линейный однонаправленный список

Обеспечивает связь элемента только со следующим элементом. Для такой структуры разрешается удалять любой элемент и добавлять элементы между любыми другими элементами, а также в начало и конец списка. Для линейного однонаправленного списка необходимо иметь указатель на начало списка и текущий указатель для добавления или удаления элементов. Частными случаями линейного однонап- равленного списка являются стек и очередь. Общий вид: Type TSpisok=^TElement; TElement=Record inf: тип дан.; link:TSpisok;end;. Чаще всего лин. однонапр. списки используются, как отсортированные. Если список не является отсортированным, то для добавления элемента указывают перед и после какого элемента он должен быть добавлен.

Добавление элемента в Добавление элементата в

с ортированный список произвольное место списка