Questão 1562254

• Banca: Marinha
• Órgão: Quadro Técnico
• Ano: 2013
• Provas: Marinha - 2013 - Quadro Técnico - Primeiro Tenente - Informática
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Algoritmos de Busca

Segundo Szwarcifiter e Markenzon (2010), um aspecto fundamental no estudo das árvores de busca é, naturalmente, o custo de acesso a uma chave desejada.

Sendo assim, assinale a opção que apresenta o tipo de árvore cuja organização visa a minimizar o número de comparações efetuadas no pior caso para uma busca com chaves de probabilidades de ocorrência idênticas.

• A. Completa.
• B. Incompleta.
• C. Difusa.
• D. Assimétrica.
• E. Simétrica.

Gabarito: A

Comentários

• Segundo Szwarcfiter, a complexidade de uma busca para uma árvore T é igual, no pior caso, à sua altura, por isso é melhor tentar uma construção da árvore T com altura mínima possível. A árvore que possui essa propriedade para um conjunto de n chaves é a completa. Nesse caso, a complexidade do algoritmo é O(log n).

• Complementando:

  Árvore completa
  - se algum nó tem uma subárvore vazia, então esse nó pertence ao último ou penúltimo nível;
  - toda árvore cheia é uma árvore completa;

  Árvore cheia
  - todos os nós, exceto as folhas, tem o número máximo de filhos;
  - todas as folhas estão na mesma altura;