Рубрики

Структуры данных | Куча | Вопрос 6

Каково содержимое массива после двух операций удаления при правильном ответе на предыдущий вопрос?
(А) 14,13,12,10,8
(В) 14,12,13,8,10
(С) 14,13,8,12,10
(D) 14,13,12,8,10

Ответ: (Д)
Объяснение: Для деревьев кучи удаление узла включает в себя следующие две операции.

1) Замените корень последним элементом на последнем уровне.
2) Начиная с корня, сложите целое дерево сверху вниз.

Давайте удалим два узла один за другим:
1) Удаление 25:
Заменить 25 на 12

          12
        /    \
      /       \
    14        16
   / \         /
 /     \      /
13     10    8

Так как свойство кучи нарушено для корня (16 больше 12), сделайте 16 корнем дерева.

           16
        /     \
      /        \
    14         12
   / \         /
  /   \       /
13     10    8

2) Удаление 16:
Заменить 16 на 8

           8
        /    \
       /      \
    14         12
   / \
  /   \
 13     10

Кучи от корня до дна.

           14
         /    \
       /       \
     8         12
    / \
   /   \
 13     10
            14
         /     \
        /       \
     13         12
    / \
   /   \
  8    10

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

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

Структуры данных | Куча | Вопрос 6

0.00 (0%) 0 votes