Рубрики

ВОРОТА | GATE-CS-2006 | Вопрос 77

GATE

3-х максимальная куча похожа на бинарную максимальную кучу, но вместо 2 дочерних узлов узлы имеют 3 дочерних. 3-арная куча может быть представлена в виде массива следующим образом: корень хранится в первом месте, a [0], узлы на следующем уровне, слева направо, сохраняются от [1] до [3 ]. Узлы со второго уровня дерева слева направо сохраняются с позиции [4] и далее. Элемент x можно вставить в трехкомпонентную кучу, содержащую n элементов, поместив x в местоположение a [n] и вытолкнув его вверх по дереву, чтобы удовлетворить свойство кучи.

Предположим, что элементы 7, 2, 10 и 4 вставлены в указанном порядке в допустимую максимальную кучу 3, найденную в приведенном выше вопросе. Какая из следующих последовательностей представляет собой последовательность элементов в массиве, представляющую результирующую кучу?

(А) 10, 7, 9, 8, 3, 1, 5, 2, 6, 4
(В) 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
(С) 10, 9, 4, 5, 7, 6, 8, 2, 1, 3
(D) 10, 8, 6, 9, 7, 2, 3, 4, 1, 5

Ответ: (А)
Пояснение: после вставки 7

                                          9
                                      /   |   \
                                    /     |     \
                                  7       6       8
                               / | \
                             /   |  \
                            3    1    5

После вставки 2

                                           9
                                      /    |   \
                                    /      |     \
                                  7        6       8
                               / | \       /
                             /   |  \     /
                            3    1    5  2

После вставки 10

                                 10
                             /    |   \
                           /      |     \
                        7         9       8
                    / | \       / |
                  /   |  \     /  |
                3    1    5  2    6

После вставки 4

                                 10
                             /   |   \
                           /     |     \
                         7        9       8
                      / | \      / | \
                    /   |  \    /  |   \
                  3    1    5  2   6    4

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

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

ВОРОТА | GATE-CS-2006 | Вопрос 77

0.00 (0%) 0 votes