Рубрики

ВОРОТА | GATE-CS-2004 | Вопрос 37

Элементы 32, 15, 20, 30, 12, 25, 16 вставляются один за другим в указанном порядке в Max Heap. Результирующая Max Heap есть.

(А)
(Б) б
(С) с
(D) d

Ответ: (А)
Объяснение: Максимальная куча — это полное двоичное дерево, в котором значение каждого неконечного узла больше или равно значениям его дочерних элементов.

Для данного случая сначала вставьте все значения в полное двоичное дерево. Затем мы применяем сдвиг. То, что мы делаем, мы начинаем с самого нижнего неконечного узла. Если он меньше, чем любой (или оба) из дочерних узлов, мы заменяем его на самый большой дочерний узел. Таким же образом мы продолжаем перемещаться вверх по дереву, пока все неконечные узлы не удовлетворят свойствам максимальной кучи.

Итак, в первый раз, когда мы делаем полное двоичное дерево, мы имеем


             32

       /            \

     15              20

   /    \          /     \

 30      12       25      16

 

Теперь нам нужно поменять местами 15 с 30 и 20 на 25.


             32

       /            \

     30              25

   /    \          /     \

 15      12       20      16

 

Это необходимая максимальная куча, которая соответствует опции А.

Итак, А — правильный выбор.

Пожалуйста, прокомментируйте ниже, если вы найдете что-то не так в вышеуказанном посте.

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

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

ВОРОТА | GATE-CS-2004 | Вопрос 37

0.00 (0%) 0 votes