Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — IDCAP 2023
Algoritmos e Estrutura de Dados›Estrutura de Dados
Código
qq939428
Banca
IDCAP
Órgão
CREA-ES
Ano
2023
Nível
Superior
Cargo
Analista de Sistemas
As estruturas de dados do tipo árvore são não lineares, e apresentam, dentre outras, a seguinte propriedade:
AA profundidade de um nó refere-se à sua distância do nó raiz.
BTodos os nós de uma sub-árvore direita são menores que o nó raiz.
CCada árvore-binária é também uma sub-árvore.
DNó folha refere-se ao nós que não possuem filhos.
EA expressão que representa o número de nós de uma árvore estritamente binária é 2n-1, onde n é o número de nós folha.
Revelar gabarito e comentário▾
GabaritoE — A expressão que representa o número de nós de uma árvore estritamente binária é 2n-1, onde n é o número de nós folha.
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”.
Propriedades de Árvores em Estruturas de Dados
Gabarito: letra E. A expressão que relaciona o número total de nós ao número de folhas em uma árvore estritamente binária é 2n-1 (onde n é o número de folhas). Essa é a única alternativa que apresenta uma propriedade matemática específica desse tipo de árvore. As demais alternativas (A e D) são definições corretas, mas não são propriedades no sentido exigido pelo enunciado; B e C são falsas.
Alternativa A — ✅ Correta (definição, não propriedade)
A profundidade de um nó é a distância (número de arestas) do nó raiz até ele. É um conceito básico e correto, mas o enunciado pede uma propriedade (relação matemática), não uma definição.
Alternativa B — ❌ Incorreta
A afirmação de que todos os nós da subárvore direita são menores que a raiz é falsa. Isso vale apenas para árvores binárias de busca (BST), onde os valores da subárvore direita são maiores. Em uma árvore genérica, não há essa ordenação.
Alternativa C — ❌ Incorreta
"Cada árvore-binária é também uma sub-árvore" é uma afirmação vaga e falsa. Uma árvore binária é uma estrutura isolada; ela pode ser subárvore de outra, mas não o é por definição.
Alternativa D — ✅ Correta (definição, não propriedade)
Nó folha (ou nó externo) é aquele que não possui filhos. Definição correta, mas novamente é uma definição, não uma propriedade relacional.
Alternativa E — ✅ Correta ⟵ GABARITO
Em uma árvore estritamente binária (cada nó tem 0 ou 2 filhos), vale a relação:
Essa é uma propriedade matemática importante, decorrente do fato de que o número de nós internos é igual ao número de folhas menos 1.
PEGA ESSA DICA!
Lembre-se: para qualquer árvore estritamente binária, nós internos = folhas - 1. Portanto, total = folhas + (folhas - 1) = 2*folhas - 1. Essa fórmula é frequentemente cobrada em concursos.
Conclusão: A única alternativa que expressa uma propriedade (relação numérica) correta é a letra E. As definições de profundidade e nó folha (A e D) são verdadeiras, mas não são o foco da questão.