Подготовка к ЕГЭ и олимпиадам по информатике 2019 / Тренировочные варианты ЕГЭ

Профильная информатика:
подготовка к ЕГЭ и олимпиадам

Вариант № EGE_INF_1803

Добавлен 05 мая 2018 в 0:44. Изменён 18 ноября 2018 в 15:19.Скачать PDF

Задание

Для эффективного поиска целочисленных ключей часто используют двоичное дерево поиска (BST). Любое поддерево BST также является BST, причём все ключи узлов левого поддерева меньше, а ключи узлов правого поддерева, соответственно, больше ключа текущего узла.

В Таблице 1 содержится информация об узлах некоторого двоичного дерева поиска и их ключах. Знак "—" обозначает отсутствие соответствующего сына. На основании представленных данных определите наибольшее количество операций сравнения ключей, которые могут потребоваться для поиска произвольного целочисленного ключа в данном дереве.

Таблица 1
IDID_левого_сынаID_правого_сына
1
21
324
4
536
67
79
8
98

Ответ

5

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