Рубрики

ВОРОТА | GATE-CS-2009 | Вопрос 60

GATE

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

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

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

Let us delete the two nodes one by one:
1) Deletion of 25:
Replace 25 with 12

          12
        /    \
      /       \
    14        16
   / \         /
 /     \      /
13     10    8
Since heap property is violated for root (16 is greater than 12),
make 16 as root of the tree.

           16
        /     \
      /        \
    14         12
   / \         /
  /   \       /
13     10    8
2) Deletion of 16:
Replace 16 with 8

           8
        /    \
       /      \
    14         12
   / \
  /   \
 13     10
Heapify from root to bottom.

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

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

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

ВОРОТА | GATE-CS-2009 | Вопрос 60

0.00 (0%) 0 votes