Questão de Algoritmos e Estrutura de Dados — Árvores — FEPESE 2022
Algoritmos e Estrutura de Dados›Árvores
Código
qq723526
Banca
FEPESE
Órgão
UDESC
Ano
2022
Nível
Superior
Cargo
Analista de Sistemas
Assinale a alternativa correta com relação à estrutura de arquivos.
AUma árvore é considerada balanceada se, e somente se, para qualquer nó, a altura de suas duas sub-árvores difere de no máximo uma unidade. Exemplos de árvores balanceadas são as árvores AVL.
BUma árvore é considerada desbalanceada se, e somente se, para qualquer nó, a altura de suas duas sub-árvores difere de, no máximo, uma unidade. Exemplos de árvores balanceadas são as árvores AVL.
CUma árvore é considerada degenerarda se, e somente se, para qualquer nó, a altura de suas duas sub-árvores difere de, no máximo, uma unidade. Exemplos de árvores balanceadas são as árvores AVL.
DUma árvore AVL é uma árvore na qual as alturas das sub-árvores esquerda e direita de cada nó diferem no mínimo por uma unidade.
ENa inserção em uma árvore AVL utiliza-se um processo de balanceamento que pode ser de 2 tipos gerais: Rotação simples ou Rotação complexa.
Revelar gabarito e comentário▾
GabaritoA — Uma árvore é considerada balanceada se, e somente se, para qualquer nó, a altura de suas duas sub-árvores difere de no máximo uma unidade. Exemplos de árvores balanceadas são as árvores AVL.
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”.
Árvores Balanceadas e AVL
Gabarito: letra A. A definição correta de árvore AVL (e de árvore balanceada no contexto de AVL) é que, para cada nó, a diferença entre as alturas das duas subárvores é no máximo 1. Essa definição consta da literatura de estruturas de dados, como no artigo sobre Árvore AVL (fonte: Wikipédia).
Wikipédia – Árvore AVL: "Uma árvore binária T é denominada AVL quando, para qualquer nó de T, as alturas de suas duas subárvores, esquerda e direita, diferem em módulo de até uma unidade."
As demais alternativas distorcem esse conceito, trocando termos essenciais como "mínimo" por "máximo" ou definindo o contrário.
Alternativa
Definição de árvore balanceada/AVL
Diferença de alturas das subárvores
Exemplo de árvore balanceada
Correção
A
Balanceada (no sentido AVL)
No máximo 1 unidade
Árvores AVL
✅ Correta
B
Desbalanceada
No máximo 1 unidade
Árvores AVL
❌ Incorreta (inverte o conceito)
C
Degenerada
No máximo 1 unidade
Árvores AVL
❌ Incorreta (degenerada é o oposto)
D
AVL
No mínimo 1 unidade
—
❌ Incorreta (troca "máximo" por "mínimo")
E
—
—
—
❌ Incorreta (tipos de rotação: 4, não 2)
Árvore AVL
1Definição
Diferença de alturas ≤ 1
Fator de balanceamento: -1, 0 ou 1
2Tipos de rotação
Simples
À direita
À esquerda
Dupla
À direita
À esquerda
LEVEL · soulevel.com.br
Alternativa A — ✅ Correta ⟵ GABARITO
Define corretamente uma árvore balanceada (no sentido AVL) como aquela em que as alturas das subárvores diferem em no máximo 1 unidade, e cita as árvores AVL como exemplo. A definição é exata e corresponde ao fator de balanceamento FB = -1, 0 ou 1.
Alternativa B — ❌ Incorreta
Afirma que uma árvore é desbalanceada quando as alturas diferem em no máximo 1, o que é justamente a definição de balanceada. Erro de conceito: inverte o significado.
Alternativa C — ❌ Incorreta
Afirma que uma árvore é degenerada quando as alturas diferem em no máximo 1. Uma árvore degenerada (ou em formato de lista) tem diferenças de altura maiores que 1, sendo o oposto do balanceamento. A palavra "degenerarda" provavelmente é um erro de digitação para "degenerada".
Alternativa D — ❌ Incorreta
Afirma que, na AVL, as alturas das subárvores diferem no mínimo por 1 unidade. O correto é no máximo 1 unidade. A banca troca o operador, induzindo ao erro.
NÃO CAIA NESSA!
A banca inverte a condição: a definição da AVL exige diferença máxima de 1 (FB = -1, 0 ou 1), mas a alternativa D usa mínima de 1 (FB ≥ 1). Memorize: AVL = diferença de alturas ≤ 1.
Alternativa E — ❌ Incorreta
Afirma que o balanceamento na inserção usa apenas 2 tipos: rotação simples ou complexa. Na verdade, existem quatro tipos de rotação: simples à direita, simples à esquerda, dupla à direita e dupla à esquerda. O termo "rotação complexa" não é padrão; o correto é "rotação dupla". Além disso, o balanceamento pode envolver mais de uma rotação, especialmente na remoção. A afirmação é imprecisa e incompleta.
Conclusão: A definição clássica de árvore AVL (balanceada) é a apresentada na alternativa A, corroborada pela literatura. Gabarito: letra A.