2011-gre-cs-practice-book.pdf/Q21 — различия между версиями

Текущая версия на 21:43, 18 декабря 2024

Вопрос: Q21-08c765

Начиная с пустого двоичного дерева поиска, вставка какой из следующих последовательностей целочисленных ключей может создать двоичное дерево выше?

Ответы

• 5, 9, 1, 7, 3, 4
• 5, 7, 4, 9, 3, 1
• 5, 4, 7, 3, 9, 1
• Правильный ответ: 5, 3, 4, 9, 1, 7
• 5, 3, 1, 7, 9, 4

Объяснение

Исходники — вопрос 21 на 25 странице книги «2011-gre-cs-practice-book.pdf»

Дерево строится так, что все потомки левее предка меньше него, и все потомки правее предка больше него по значению.

• Начинаем с 5.
• Далее подойдет 3 или 9. Поэтому варианты «5, 7, 4, 9, 3, 1» и «5, 4, 7, 3, 9, 1» отпадают.
• Вариант «5, 9, 1, 7, 3, 4» не подходит, так как 1 была бы прямым потомком 5.
• Вариант «5, 9, 1, 7, 3, 4» тоже отпал. после 5-3-1 не может быть 7, ведь она тоже была бы прямым потомком 5.
• Вариант «5, 3, 4, 9, 1, 7» подходит идеально.