Qual é a característica essencial que diferencia uma árvore de um grafo?
Resposta correta: C) Não pode haver ciclos; há uma raiz única ou raiz vazia
Observação: árvores não possuem ciclos e, exceto pela raiz, cada nó tem exatamente um pai. O grafo pode possuir ciclos e várias raízes.
Qual é a definição correta de uma árvore binária de busca (ABB)?
Resposta correta: C) É uma árvore binária onde, para cada nó, todas as chaves da subárvore esquerda são menores que a chave do nó e todas as chaves da subárvore direita são maiores
Essa é a definição fundamental de ABB, que facilita buscas eficientes ao manter a ordem entre esquerdo e direito.
Em uma ABB balanceada, qual é o número máximo de comparações necessárias para encontrar um elemento, dado que a altura é h?
Resposta correta: B) h
Em ABB balanceadas, a busca requer no máximo uma quantidade de comparações igual à altura h, pois cada passo desce para uma metade (esquerda ou direita) da árvore.
Considere as afirmações sobre árvores binárias de busca balanceadas. Assinale a alternativa que descreve corretamente por que os algoritmos de balanceamento mantêm a eficiência de busca e mencione dois métodos comuns de balanceamento.
Resposta correta: B) Balanceamento reduz a altura para manter buscas em O(log n); métodos comuns: AVL e árvores rubro-negras
Explicação: manter a altura logarítmica garante que o pior caso de busca permaneça eficiente. AVL e RB-tree são técnicas populares de balanceamento automático.