Рубрики

Структуры данных и алгоритмы | Набор 16

На экзамене GATE CS 2009 были заданы следующие вопросы.

1. Рассмотрим двоичную максимальную кучу, реализованную с использованием массива. Какой из следующих массивов представляет двоичную максимальную кучу?

(А) 25,12,16,13,10,8,14
(В) 25,14,13,16,10,8,12
(С) 25,14,16,13,10,8,12
(D) 25,14,12,13,10,8,16

Ответ (С)

Дерево имеет максимальную кучу, если данные в каждом узле дерева больше или равны его дочерним данным.

В представлении массива дерева кучи узел с индексом i имеет левого дочернего элемента с индексом 2i + 1 и правого дочернего элемента с индексом 2i + 2.

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

2. Каково содержимое массива после двух операций удаления при правильном ответе на предыдущий вопрос?

(А) 14,13,12,10,8
(В) 14,12,13,8,10
(С) 14,13,8,12,10
(D) 14,13,12,8,10

Ответ (D)

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

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

3. При быстрой сортировке для сортировки по n элементам (n / 4) -ый наименьший элемент выбирается как сводный, используя алгоритм времени O (n). Какова временная сложность быстрой сортировки в худшем случае?

(A) Θ (n)
(B) Θ (n Log n)
(C) Θ (n ^ 2)
(D) Θ (n 2 log n)

Ответ (B)
Выражение рекурсии становится:

T (n) = T (n / 4) + T (3n / 4) + cn

После решения приведенной выше рекурсии мы получаем Θ (nLogn).


4. Какова максимальная высота любого AVL-дерева с 7 узлами? Предположим, что высота дерева с одним узлом равна 0.

(А) 2
(Б) 3
(С) 4
(D) 5

Ответ (B)
Деревья AVL являются двоичными деревьями со следующими ограничениями.
1) разница в росте у детей не более 1.
2) оба ребенка AVL деревья

                 a
               /   \
             /      \
            b        c
          /  \      /
         /    \    /
        d     e   g
       /
      /
     h

Ссылки:
http://en.wikipedia.org/wiki/AVL_tree

Пожалуйста, пишите комментарии, если вы найдете какие-либо неправильные ответы / объяснения, или вы хотите поделиться дополнительной информацией по темам, обсужденным выше.

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

Структуры данных и алгоритмы | Набор 16

0.00 (0%) 0 votes