Рубрики

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

Поиск в ширину (BFS) запускается в двоичном дереве, начиная с корневой вершины. На расстоянии четырех от корня есть вершина t. Если t является n-й вершиной в этом обходе BFS, то максимально возможное значение n равно ________

[Этот Вопрос изначально был Вопросом Заполнить Пробелы]

(А) 15
(Б) 16
(С) 31
(D) 32

Ответ: (с)
Пояснение: Это будет узел № 31 для данного расстояния 4.

Например, если мы рассмотрим на расстоянии 2, ниже выделенный узел G может быть самым дальним узлом в позиции 7.

            A
         /    \
        B       C
       / \     / \
      D   E   F   G

Альтернативное решение :
t — это n-я вершина в этом обходе BFS на расстоянии четыре от корня. Итак, высота дерева 4.
Максимальное количество узлов = 2 ^ {h + 1} — 1 = 2 ^ {5} — 1 = 31
На расстоянии четыре последний узел равен 31. option (C)
Тест на этот вопрос

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

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

0.00 (0%) 0 votes