Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — FGV 2024
Algoritmos e Estrutura de Dados›Estrutura de Dados
Código
fg089766
Banca
FGV
Órgão
Prefeitura de Caraguatatuba - SP
Ano
2024
Nível
Médio
Cargo
Técnico em Processamento de Dados
Considere as seguintes afirmativas sobre árvores binárias, árvores binárias ordenadas e árvores binárias ordenadas balanceadas (AVL), assinale V para a afirmativa verdadeira e F para a falsa.( ) Uma árvore binária é uma estrutura de dados que consiste em nós, onde cada nó tem no máximo dois filhos.( ) Uma árvore binária ordenada é uma árvore binária em que os valores dos nós são ordenados de forma crescente ou decrescente.( ) Uma árvore binária ordenada balanceada (AVL) é uma árvore binária ordenada em que a altura de qualquer subárvore não difere da altura de sua subárvore oposta em mais de um.As afirmativas são, respectivamente,
AV – V – V.
BV – F – V.
CV – V – F.
DF – V – V.
EV – F – F.
Revelar gabarito e comentário▾
GabaritoB — V – F – V.
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 binárias, BST e AVL
Gabarito: letra B (V – F – V). A primeira afirmativa está correta (definição de árvore binária); a segunda é falsa, pois a ordenação em uma BST é recursiva por nó, não global; a terceira está correta (condição de balanceamento AVL).
A questão testa as definições fundamentais dessas estruturas. A pegadinha está na segunda afirmativa, que sugere uma ordenação linear inexistente.
NÃO CAIA NESSA!
A banca explora a confusão entre "ordenada" e "ordem global". Em uma árvore binária ordenada (BST), a propriedade é recursiva: para cada nó, a subárvore esquerda contém valores menores e a direita valores maiores. Isso não significa que a árvore como um todo esteja em ordem crescente ou decrescente – uma travessia em ordem pode produzi-la, mas a estrutura não é uma lista ordenada.
Afirmativa
Descrição
V/F
Justificativa
1ª
Uma árvore binária é uma estrutura de dados que consiste em nós, onde cada nó tem no máximo dois filhos.
V
Definição clássica de árvore binária: cada nó possui no máximo duas subárvores (esquerda e direita).
2ª
Uma árvore binária ordenada é uma árvore binária em que os valores dos nós são ordenados de forma crescente ou decrescente.
F
A ordenação em uma BST é recursiva por nó (esquerda < nó < direita), não global/linear. A árvore não é uma lista ordenada.
3ª
Uma árvore binária ordenada balanceada (AVL) é uma árvore binária ordenada em que a altura de qualquer subárvore não difere da altura de sua subárvore oposta em mais de um.
V
Condição de balanceamento AVL:
altura(esq) – altura(dir)
≤ 1 para todo nó.
1ª afirmativa — ✅ Verdadeira
Uma árvore binária é definida como uma estrutura de dados hierárquica em que cada nó possui, no máximo, dois filhos (subárvores esquerda e direita). Essa é a propriedade que a distingue de árvores gerais.
2ª afirmativa — ❌ Falsa
Uma árvore binária ordenada (BST) não armazena os valores em ordem global crescente ou decrescente. A propriedade de ordenação é local: para cada nó, todos os valores da subárvore esquerda são menores (ou maiores, dependendo da convenção) que o valor do nó, e todos os valores da subárvore direita são maiores (ou menores). Essa relação recursiva não impõe uma sequência linear ordenada sobre todos os nós; a árvore não é uma lista. A afirmativa confunde ordenação com a estrutura de dados.
3ª afirmativa — ✅ Verdadeira
Uma árvore AVL (Adelson-Velsky e Landis) é uma árvore binária ordenada balanceada. A condição de balanceamento é que, para qualquer nó, a altura de suas duas subárvores (esquerda e direita) difere em no máximo 1 (|altura(esq) – altura(dir)| ≤ 1). Isso garante que a altura seja O(log n) e as operações eficientes. A afirmativa descreve exatamente essa condição.
Alternativa A (V – V – V) — ❌ Incorreta
A segunda afirmativa é falsa, portanto a sequência V-V-V está errada.
Alternativa B (V – F – V) — ✅ Correta ⟵ GABARITO
Única combinação que coincide com a análise: primeira verdadeira, segunda falsa, terceira verdadeira.
Alternativa C (V – V – F) — ❌ Incorreta
Erra na segunda (deveria ser F) e na terceira (deveria ser V).
Alternativa D (F – V – V) — ❌ Incorreta
Erra na primeira (deveria ser V) e na segunda (deveria ser F).