As seguintes perguntas foram feitas no exame GATE CS 2009.

1. Considere um heap máximo binário implementado usando uma array. Qual das seguintes arrayes representa um heap máximo binário?

(A) 25,12,16,13,10,8,14
(B) 25,14,13,16,10,8,12
(C) 25,14,16,13,10,8,12
(D ) 25,14,12,13,10,8,16

Resposta (C)

Uma árvore é heap máximo se os dados em cada nó da árvore forem maiores ou iguais aos dados dos filhos.

Na representação de array da árvore heap, um nó no índice i tem seu filho esquerdo no índice 2i + 1 e filho direito no índice 2i + 2.

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

2. Qual é o conteúdo da array após duas operações de exclusão na resposta correta à pergunta anterior?

(A) 14,13,12,10,8
(B) 14,12,13,8,10
(C) 14,13,8,12,10
(D) 14,13,12,8,10

Resposta (D)

Para árvores Heap, a exclusão de um nó inclui as duas operações a seguir.

1) Substitua a raiz pelo último elemento no último nível.
2) Começando da raiz, monte a árvore completa de cima para baixo.

Vamos excluir os dois nós um por um:
1) Exclusão de 25:
Substitua 25 por 12

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

Como a propriedade de heap é violada para a raiz (16 é maior que 12), faça 16 como a raiz da árvore.

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

2) Exclusão de 16:
Substitua 16 por 8

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

Heapify da raiz ao fundo.

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

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

3. Na classificação rápida, para classificar n elementos, o (n / 4) o menor elemento é selecionado como pivô usando um algoritmo de tempo O (n). Qual é o pior caso de complexidade de tempo do tipo rápido?

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

Resposta (B)
A expressão de recursão torna-se:

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

Depois de resolver a recursão acima, obtemos Θ (nLogn).

4. Qual é a altura máxima de qualquer árvore AVL com 7 nós? Suponha que a altura de uma árvore com um único nó seja 0.
(A) 2
(B) 3
(C) 4
(D) 5

Resposta (B) As
árvores AVL são árvores binárias com as seguintes restrições.
1) a diferença de altura das crianças é de no máximo 1.
2) ambas as crianças são árvores AVL

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

Referências:
http://en.wikipedia.org/wiki/AVL_tree

Escreva comentários se encontrar alguma das respostas / explicações incorretas ou se quiser compartilhar mais informações sobre os tópicos discutidos acima.

Aprenda todos os conceitos do GATE CS com aulas gratuitas ao vivo em nosso canal do youtube.