DVBogdanov.ru / Тренировочный вариант по информатике, задание 4

Задание №1701/04

Задание

Во фрагменте базы данных сохранено дерево разбора некоторого арифметического выражения. На основании приведённых данных вычислите значение выражения.

IDID_родителяЗначение
148
235
34+
40*
534

Решение

По приведённым в таблице данным восстановим дерево разбора арифметического выражения (рисунок 1). Общим родителем вершин с ID 1 и ID 3 является вершина с ID 4, при этом вершина с ID 3 является родителем для вершин с ID 2 и ID 5. Родителем вершины с ID 4 является вершина с ID 0, отсутствующая в таблице, поэтому можно считать вершину с ID 4 корнем дерева.

Дерево разбора выражения
Рис. 1. Дерево разбора выражения

Вычислим значение арифметического выражения по построенному дереву. Существуют различные способы обхода деревьев, рассмотрим лишь один из них. Так как значение в вершине с ID 4, являющейся корнем, равно *, то значение всего выражения равно произведению значений левого (с корнем, имеющим ID 1) и правого поддерева (с корнем, имеющим ID 3). Отметим, что перестановка поддеревьев местами (левого и правого) на результат не влияет в силу коммутативности операции умножения.

Левое поддерево содержит единственную вершину с ID 1 и числовым значением, равным 8. Рекурсивно применяя рассмотренный выше алгоритм, вычислим значение поддерева, имеющего корень с ID 3, которое равно сумме значений вершин с ID 2 и ID 5, то есть \(5+4=9\).

Таким образом, искомое значение арифметического выражение равно \( 8*(5+4) = 72\).

Подробнее...

Ответ

72

Подробнее...
Добавить комментарий
Комментарии (0)
#Дерево разбора выражения #Основы баз данных #Подготовка к ЕГЭ по информатике