Вопрос 2. Нелинейные структуры: обходы деревьев

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

При выборе способа машинного представления дерева используется понятие “прошивания” дерева. Этот способ обладает эффективностью как с точки зрения уменьшения объема памяти, так и с точки зрения увеличения быстродействия.

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

Нисходящий обход: (префиксная запись) сверху - вниз

- обработка корневой вершины;

- нисходящий обход левого поддерева;

- нисходящий обход правого поддерева.

Смешанывй обход : (инфиксная запись ) слева- направо

- смешаный обход левого поддерева;

- обработка корневой вершины ;

- смешаный обход правого поддерева.

Восходящий обход (постфиксная запись) снизу вверх

- восходящий обход левого поддерева;

- восходящий обход правого поддерева;

- обработка корневой вершины.

Например:

нисходящий обход ABCDEFG

cмешаный CBAEFDG

восходящий CBFEGDA

Дерево “прошивается” с учетом определенного способа обхода. В этом случае легко разработать алгоритмы обработки дерева и обход осуществляется быстрее, т. к. вместо стека имеется прошивка.

Однако включение новой вершины в прошитое дерево занимает больше времени,чем включение ее в непрошитое дерево.

Еще одно необходимое понятие

Два дерева называются подобными, если они имеют одинаковую структуру (форму).

Два дерева называются эквивалентными, если они подобны и вершины у них содержат одинаковую информацию.

Вопрос 3. Качество по. Критерии качества: сложность, корректность, надежность, трудоемкость. Методика оценки качества по. Метрические особенности объектно-ориентированных пс. Сертификация по

Метрические оценки. Задаются по стандарту (как сказала Стриженок) где много цифр. Для оценки формируется фактор, который складывается из критериев –> метрики -> оценки.

Система рассчитывается снизу вверх через весовые коэффициенты.

Как говорилось фактор состоит из критериев :

- надежность

- эффективность

- удобство

- корректность

- сопровождаемость

- работоспособность

Оценка является субъективной. Весовые критерии берутся из графичекой структуры.

Билет 13.