Задания ЕГЭВариант № EGE_INF_1701
Добавлен 18 мая 2017 г. в 0:11. Изменён 24 декабря 2017 г. в 22:53.
Скачать PDFЗадание
Во фрагменте базы данных сохранено дерево разбора некоторого арифметического выражения. На основании приведённых данных вычислите значение выражения.
| ID | ID_родителя | Значение |
|---|---|---|
| 1 | 4 | 8 |
| 2 | 3 | 5 |
| 3 | 4 | + |
| 4 | 0 | * |
| 5 | 3 | 4 |
Решение
По приведённым в таблице данным восстановим дерево разбора арифметического выражения (рисунок 1). Общим родителем вершин с ID 1 и ID 3 является вершина с ID 4, при этом вершина с ID 3 является родителем для вершин с ID 2 и ID 5. Родителем вершины с ID 4 является вершина с ID 0, отсутствующая в таблице, поэтому можно считать вершину с ID 4 корнем дерева.
Вычислим значение арифметического выражения по построенному дереву. Существуют различные способы обхода деревьев, рассмотрим лишь один из них. Так как значение в вершине с ID 4, являющейся корнем, равно *, то значение всего выражения равно произведению значений левого (с корнем, имеющим ID 1) и правого поддерева (с корнем, имеющим ID 3). Отметим, что перестановка поддеревьев местами (левого и правого) на результат не влияет в силу коммутативности операции умножения.
Левое поддерево содержит единственную вершину с ID 1 и числовым значением, равным 8. Рекурсивно применяя рассмотренный выше алгоритм, вычислим значение поддерева, имеющего корень с ID 3, которое равно сумме значений вершин с ID 2 и ID 5, то есть \(5+4=9\).
Таким образом, искомое значение арифметического выражение равно \( 8*(5+4) = 72\).
Подробнее...Ответ
72
Подробнее...