Рубрики

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

Число способов, которыми числа 1, 2, 3, 4, 5, 6, 7 могут быть вставлены в пустое двоичное дерево поиска, так что результирующее дерево имеет высоту 6, составляет _____________

Примечание. Высота дерева с одним узлом равна 0.

[Этот вопрос изначально был вопросом Заполнить бланки]
(А) 2
(Б) 4
(С) 64
(D) 32

Ответ: (с)
Объяснение: Чтобы получить высоту 6, нам нужно поставить либо 1, либо 7 в корень.

Таким образом, счет может быть записан как T (n) = 2 * T (n-1) с T (1) = 1


    7
   / 
 [1..6]  

    1
      \
     [2..7] 

Следовательно, количество составляет 2 6 = 64

Другое объяснение:

Рассмотрим эти случаи,
1 2 3 4 5 6 7
1 2 3 4 5 7 6
1 7 6 5 4 3 2
1 7 6 5 4 2 3
7 6 5 4 3 2 1
7 6 5 4 3 1 2
7 1 2 3 4 5 6
7 1 2 3 4 6 5

Для высоты 6 у нас есть 2 варианта. Либо мы выбираем корень как 1 или 7.
Предположим, мы выбрали 7.
Теперь у нас есть 6 узлов и оставшаяся высота = 5.
Итак, теперь у нас есть 2 способа выбрать root для этого поддерева.
Теперь мы продолжаем повторять ту же процедуру, пока оставшаяся высота = 1
Для этого последнего случая также у нас есть 2 способа.

Следовательно, общее количество путей = 2 6 = 64

Тест на этот вопрос

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

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

0.00 (0%) 0 votes