Рубрики

ВОРОТА | GATE-CS-2016 (набор 2) | Вопрос 44

Полная двоичная минимальная куча получается путем включения каждого целого числа в [1, 1023] ровно один раз. Глубина узла в куче — это длина пути от корня кучи до этого узла. Таким образом, корень находится на глубине 0. Максимальная глубина, на которой может появляться целое число 9, составляет _____________

[Этот вопрос изначально задавался как вопрос «Заполнить бланки»]
(А) 6
(Б) 7
(С) 8
(D) 9

Ответ: (с)
Объяснение: здесь узел с целым числом 1 должен находиться только в корне. Теперь для максимальной глубины дерева можно принять следующее расположение. Укорениться как уровень 1.

сделать узел 2 на уровне 2 как дочерний узел узла 1.
сделать узел 3 на уровне 3 как дочерний узел узла 2.
..
.. и так далее для узлов 4,5,6,7
..
сделать узел 8 на уровне 8 как дочерний узел узла 7.
сделать узел 9 на уровне 9 как дочерний узел узла 8.

Рекомендуемые посты:

ВОРОТА | GATE-CS-2016 (набор 2) | Вопрос 44

0.00 (0%) 0 votes