Рубрики

ВОРОТА | Gate IT 2008 | Вопрос 44

Известно, что следующие три последовательности предзаказа, порядка и порядка следования двоичного дерева. Но неизвестно, что есть что.
MBCAFHPYK
KAMCBYPFH
MABCKYFPH
Выберите верное утверждение из следующего.

(A) I и II являются последовательностями предзаказов и порядков соответственно
(B) I и III — последовательности предварительного и пост-заказа соответственно
(C) II — последовательность порядка, но больше ничего нельзя сказать о двух других последовательностях
(D) II и III — последовательности предзаказа и неупорядочения соответственно

Ответ: (D)
Объяснение:

Подход к решению этого вопроса состоит в том, чтобы сначала найти 2 последовательности, первый и последний элементы которых совпадают. Причина в том, что первым элементом в предзаказе любого двоичного дерева является корень, а последним элементом в последующем порядке любого бинарного дерева является корень.
Глядя на данные последовательности,
Предварительный заказ = KAMCBYPFH
Post-order = MBCAFHPYK
Оставшаяся последовательность MABCKYFPH будет в порядке.
Поскольку у нас определены все обходы, давайте попробуем нарисовать двоичное дерево, если это возможно.

I. Почтовый заказ
II. Предварительный заказ
III. Чтобы

Это решение предоставлено Пранджул Ахаджа.
Тест на этот вопрос

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

ВОРОТА | Gate IT 2008 | Вопрос 44

0.00 (0%) 0 votes