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

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

Вариант № EGE_INF_1802

Добавлен 16 декабря 2017 в 0:45. Изменён 17 июня 2018 в 17:03.Скачать PDF

Задание

Для реализации интерфейса ассоциативного массива, ключами которого являются строки, обычно используют сжатое префиксное дерево (trie). Каждая дуга префиксного дерева помечена строковой, а каждая вершина — бинарной меткой. Значение ключа можно получить соединением символов, написанных на дугах на пути от корня до соответствующего выделенного узла, имеющего метку 1.

В Таблице 1 содержится информация о дугах некоторого префискного дерева и их метках, а в Таблице 2 хранятся соответствующие метки вершин. На основании представленных данных определите количество ключей, имеющих префикс «КОД».

Таблица 1
ID_началоID_конецМетка дуги
01К
12А
13Т
14О
45РА
56БЛЬ
57Л
98ЕК
49Д
810С
1211АНИЕ
912ИРОВ
1213КА
314ИРОВКА
315ЁЛ
1816А
1817ИНА
218РТ
1819ОН
220ДЕТ
Таблица 2
IDМетка вершины
00
10
20
31
40
50
61
71
81
91
101
111
120
131
141
151
161
171
180
191
201

Ответ

5

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