Questão de Algoritmos e Estrutura de Dados — Algoritmos — PR-4 UFRJ 2023
Algoritmos e Estrutura de Dados›Algoritmos
Código
qg019542
Banca
PR-4 UFRJ
Órgão
UFRJ
Ano
2023
Nível
Superior
Cargo
PR-4 - - Analista de Tecnologia da Informação-Desenvolvimento
Dentro do conceito de modelo matemático, ao se empregar uma estrutura de dados, um algoritmo é um processo sistemático para a resolução de um problema, sob essa perspectiva, as árvores constituem estruturas não sequenciais com maior aplicação em computação, logo, toda árvore com n nós que possui exatamente n + 1 subárvores vazias entre suas subárvores esquerdas e direitas é denominada:
Aárvore unária.
Bárvore balanceada.
Cárvore recursiva.
Destrutura em pilhas e filas.
Eárvore binária.
Revelar gabarito e comentário▾
GabaritoE — árvore binária.
Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.
Árvore binária e a propriedade do número de subárvores vazias
Gabarito: alternativa E. Toda árvore com n nós que possui exatamente n + 1 subárvores vazias entre as subárvores esquerda e direita é uma árvore binária. Essa é uma propriedade fundamental: em uma árvore binária com n nós, o número total de apontadores nulos (subárvores vazias) é sempre n + 1, pois cada nó tem 2 filhos (total 2n apontadores), e como há n - 1 arestas, sobram 2n - (n - 1) = n + 1 apontadores nulos.
A questão cobra esse conceito clássico de estruturas de dados. Vejamos cada alternativa:
Árvore unária (ou monária) é aquela em que cada nó tem no máximo um filho. Nesse caso, o número de subárvores vazias não é n + 1, mas sim n + 1? Na verdade, em uma árvore unária (uma lista), o número de subárvores vazias também é n + 1? Não, pois cada nó tem apenas um filho (direito ou esquerdo), totalizando n apontadores, dos quais n - 1 são arestas e 1 é nulo no final, mas o cálculo muda. A propriedade n + 1 é específica da árvore binária.
Alternativa B — ❌ Incorreta
Árvore balanceada é um tipo especial de árvore binária (como AVL, Rubro-Negra) que mantém alturas aproximadamente iguais, mas a propriedade de n + 1 subárvores vazias não é o que a define. Qualquer árvore binária, balanceada ou não, tem exatamente n + 1 subárvores vazias.
Alternativa C — ❌ Incorreta
Árvore recursiva não é uma classificação formal de estrutura de dados. O termo refere-se a algoritmos recursivos aplicados a árvores, não a um tipo específico de árvore.
Alternativa D — ❌ Incorreta
Estrutura em pilhas e filas são estruturas lineares (listas), não árvores. Não se aplicam ao conceito de subárvores esquerda/direita.
Alternativa E — ✅ Correta ⟵ GABARITO
Árvore binária é exatamente a estrutura em que cada nó possui no máximo dois filhos (esquerdo e direito) e, consequentemente, o número de subárvores vazias (apontadores nulos) é igual a n + 1. Essa é uma propriedade matemática elementar e frequentemente cobrada em concursos.
PEGA ESSA DICA!
Lembre-se sempre: em qualquer árvore binária com n nós, o número de subárvores vazias = n + 1. Isso é útil para provas de indução e para entender a complexidade de algoritmos.