► 3. [24] Измените алгоритм 2 3 2D, используя идею алгоритма F промежуточные производные размещались в стеке, а их адреса не записываются таким необычным способом, который применяется на шаге,D3 (см упр 2 3 2-21) Управление стеком может осуществляться на основе поля RLINK в корне каждой производной

4. [18] Деревья (2) содержат 10 узлов, пять из которых являются концевыми Представление этих деревьев в виде нормальных бинарных деревьев включает 10 полей LLINK и 10 полей RLINK (по одному для каждого узла) Для представления этих деревьев в виде (10), где LLINK и INFO совместно используют одно и то же пространство внутри узла, требуется 5 полей LLINK и 15 полей RLINK В каждом случае имеется по 10 полей INFO

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

5. [16] Трижды связанное дерево, аналогичное показанному на рис 26, содержит в каждом узле поля PARENT, LCHILD и RLINK, причем при отсутствии узла, на который могли бы указать поля PARENT, LCHILD и RLINK, в них применяются связи Л Стоит ли расширять это представление до прошитого дерева, применяя связи-нити вместо пустых связей LCHILD и RLINK, как показано в разделе 2 3 1

► 6. [24] Предположим, что узлы ориентированного леса имеют по три поля связи PARENT, LCHILD и RLINK, но только одна связь PARENT используется для обозначения древовидной структуры Поле LCHILD каждого узла равно Л, а поля RLINK расположены в линейном списке, который просто связывает узлы вместе в некотором порядке Переменная связи FIRST указывает на первый узел, а в последнем узле RLINK = Л

Создайте алгоритм обхода этих узлов и заполнения полей LCHILD и RLINK в соответствии со значениями связей PARENT, чтобы в результате можно было получить представление трижды связанного дерева, подобное показанному на рис 26 Кроме того, установите для FIRST значение которое будет указывать на корень первого дерева в этом представлении

7. [15] Какие классы содержались бы в (12), если бы в (11) отсутствовало отношение 9 = 3?

8. [15] Алгоритм Е задает древовидную структуру, которая представляет заданные пары эквивалентных элементов, но в этом разделе явно не указывается, как можно использовать результат выполнения алгоритма Е Создайте алгоритм, который может установить справедливость выражения "j = к" при условии, что l<j<n, 1<А:<пи алгоритм Е задает таблицу PARENT для некоторого набора пар эквивалентных элементов

9. [20] Предложите таблицу наподобие (15) и схему вида (16), которые изображали оы деревья, полученные после обработки алгоритмом Е всех пар эквивалентных элементов в (11) в направлении слева направо

10. [28] Для обработки п пар эквивалентных элементов с помощью алгоритма Е в худшем случае потребуется выполнить около п шагов Покажите, как можно было бы модифицировать этот алгоритм, чтобы повысить эффективность его работы в данном случае

► 11. [24] (Объявления эквивалентности) В некоторых компилируемых языках программирования, особенно в языке FORTRAN, предусмотрена возможность перекрытия ячеек памяти, которые выделены для таблиц, последовательно размещенных в памяти Программист предлагает компилятору набор отношений вида "X[j] = Y[fr]", который означает, что для переменной X[j -f s] выделяется та же ячейка памяти, что и для переменной У [fc -I- s] при всех s Кроме того, для каждой переменной определен диапазон допустимых индексов Например, ARRAY Х[/ и]" означает, что нужно выделить некоторую область

памяти для элементов таблицы Х[/] , Х[/ + 1] , ..., Х[и] . Для каждого класса эквивалентности переменных компилятор резервирует минимально возможный блок последовательно расположенных ячеек дтамяти, чтобы в нем можно было хранить все элементы таблицы для допустимых значений индексов.

Например, предположим, что имеются таблицы ARRAY Х[0:10], ARRAY Y[3:10], ARRAY А[1:1] и ARRAY Z[-2:0], а также пары эквивалентных элементов Х[7] = Y[3], Z[0] = А[0] и Y[l] = А [8]. Для этих переменных необходимо выделить 20 последовательных ячеек памяти:

Хо Xl Хг Хз Х4 Xs Хб Ху Xg Xg Хю

Z 2Z-i Zo Al y3 y4 -Ys Ye y7 Yg Yg Yio

(Адрес расположенной за элементом А [1] ячейки памяти не соответствует ни одному диапазону допустимых значений индексов для любого массива, но эту ячейку все равно придется зарезервировать.)

Назначение этого упражнения заключается в модификации алгоритма Е таким образом, чтобы его можно было применять в более общем случае, который только что был описан. Допустим, необходимо создать компилятор такого языка, а таблицы внутри самого компилятора имеют по одному узлу в каждом массиве с полями NAME, PARENT, DELTA, LBD и UBD. Допустим также, что компилятор предварительно обработал все объявления ARRAY таким образом, что при наличии объявления "ARRAY X[/:u]" и Р, указывающего на узел X,

NAME(P) = "X", PARENT (?) = Л, DELTA(Р) = О, LBD(P) = /, UBD(P) = и.

Задача заключается в создании алгоритма, который обрабатывал бы объявления эквивалентности так, чтобы после выполнения алгоритма получалось следующее:

PARENT(Р) = Л означает, что ячейки памяти X [LED (Р)] ,..., X [UBD(P)] должны быть зарезервированы в памяти для этого класса эквивалентности;

PARENT (Р) = Q / Л означает, что ячейка памяти Х[А:] эквивалентна ячейке Y[A: + DELTA(Р)], где NAME(Q) = "Y".

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

(Здесь "*" обозначает данные, которые не имеют никакого отношения к рассматриваемой задаче.)

Создайте алгоритм, который выполняет это преобразование. Предположите, что данные из входного потока поступают в виде {P,j,Q,k), а это означает, что "X[j] = Y[A:]", где NAME(P) - "X" и NAME(Q) = "Y". Непременно убедитесь в том, что эти пары эквивалентных

отношений не противоречат одна другой. Например, Х[1] = Y[2] будет противоречить X[2]=Y[1].

12. [21] В начале алгоритма А переменные Р и Q указывают на корни двух деревьев. Пусть Ро и Qo -значения переменных Р и Q до выполнения алгоритма А. (а) Всегда ли по завершении выполнения этого алгоритма Qo будет содержать адрес корня дерева, представляющего результат суммирования двух заданных полиномов? (Ь) Будут ли переменным Р и Q возвращены их исходные значения Ро и Qo по окончании выполнения этого алгоритма?

* 13. [М29] Предложите неформальное доказательство того, что в алгоритме А в начале шага А8 всегда справедливы равенства ЕХР(Р) = EXP(Q) и CV(UP(P)) = CV(UP(Q)). (Это очень важно для понимания принципа работы алгоритма.)

14. [40] Предложите формальное доказательство (или опровержение) справедливости алгоритма А.

15. [40] Создайте алгоритм для вычисления произведения двух полиномов, показанных на рис. 28.

16. Докажите корректность алгоритма F.

► 17. [25] Алгоритм F позволяет вычислить локально определенную функцию по направлению "снизу вверх", которая сначала вычисляется для детей некоторого узла, а затем - и для самого узла, тогда как локально определенной функцией для узла х по направлению "сверху вниз" / называется функция, которая зависит только от узла х и значения функции / для родителя узла х. С помощью вспомогательного стека создайте алгоритм, аналогичный алгоритму F, который оценивает локально определенную функцию по направлению "сверху вниз" / для каждого узла этого дерева. (Подобно алгоритму F данный алгоритм должен эффективно обрабатывать деревья, которые хранятся в обратном порядке со степенями узлов, как в (9).)

► 18. [28] Создайте алгоритм, который на основе двух таблиц INFOlCj] и RLINK [j] для 1 J < ") соответствующих последовательному представлению в прямом порядке обхода, позволяет создать таблицы INF02 [j] и DEGREE [j] для 1 < j < п, соответствующие последовательному представлению в обратном порядке обхода с указанием степеней. Например, согласно (3) и (9) этот алгоритм должен привести таблицы

19. [M27] Вместо использования связей SCOPE в (5) можно было бы просто указать количество наследников для каждого узла в прямом порядке:

DESC 3 0 1 0 5 1 0 1 0 0 INFO ABCKDEHFJG

Пусть d\d2. -dn-последовательность чисел, указывающих количество наследников для узлов одного леса, полученная таким образом.

a) Покажите, что к + dk < п для 1 < А: < п и что из А: < j < k + dk следует j + dj < k + dk.

b) И наоборот, докажите, что если did .. - dn является последовательностью неотрицательных целых чисел, которые удовлетворяют условиям (а), то она является пос (ло-вательностью количеств узлов-наследников для данного леса.