Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — FGV 2024
Algoritmos e Estrutura de Dados›Estrutura de Dados
Código
fg086772
Banca
FGV
Órgão
MF
Ano
2024
Nível
Superior
Cargo
Auditor Federal de Finanças e Controle - Área de Tecnologia da Informação (Transformação Digital) - manhã
No contexto de uma Árvore B, estrutura comumente utilizada na indexação de tabelas relacionais, considere as seguintes propriedades numa Árvore B de grau g.1. Todas as folhas estão no mesmo nível de profundidade na árvore.2. Todos os nós podem conter, no máximo, 2g - 1 chaves.3. Exceto pelo nó raiz, todos os demais nós devem conter, no mínimo, g -1 chaves.4. Para uma árvore com N chaves, a complexidade do algoritmo de inserção é O(n).5. Para uma árvore com N chaves, a complexidade do algoritmo de inserção é O(log n).Estão corretas as afirmativas
A2, 3 e 4, apenas.
B1, 2, 3 e 5.
C1, 2, 4 e 5.
D2, 3, 4 e 5.
E1, 3, 4 e 5.
Revelar gabarito e comentário▾
GabaritoB — 1, 2, 3 e 5.
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 B: Propriedades e Complexidade
Gabarito: letra B. Estão corretas as afirmativas 1, 2, 3 e 5. A Árvore B é uma estrutura balanceada: todas as folhas no mesmo nível (1), cada nó tem no máximo 2g-1 chaves (2), e exceto a raiz, cada nó tem no mínimo g-1 chaves (3). A inserção, por ser balanceada, tem complexidade O(log n) (5) e não O(n) (4, falsa).
NÃO CAIA NESSA!
A afirmativa 4 tenta confundir o candidato afirmando que a inserção é O(n) – isso vale para árvores degeneradas (como uma ABB em lista), mas a Árvore B garante altura O(log n) no pior caso, então todas as operações (inserção, busca, remoção) são O(log n).
Afirmativa
Descrição
Correta?
Justificativa
1
Todas as folhas no mesmo nível
✅ Sim
Propriedade essencial de balanceamento da Árvore B
2
Máximo de 2g - 1 chaves por nó
✅ Sim
Decorre da definição de grau g
3
Mínimo de g - 1 chaves (exceto raiz)
✅ Sim
Evita degradação da árvore
4
Inserção O(n)
❌ Não
Árvore B é balanceada, altura O(log n)
5
Inserção O(log n)
✅ Sim
Altura logarítmica garante complexidade
Árvore B (grau g): Propriedades (Folhas no mesmo nível, Máx. 2g-1 chaves por nó, Mín. g-1 chaves (exceto raiz)); Complexidade (N chaves) (Inserção: O(log n), Busca: O(log n), Remoção: O(log n)); Não é O(n) (Árvore degenerada (ABB))
Análise das afirmativas (base para as alternativas)
Afirmativa 1 — ✅ Correta Todas as folhas estão no mesmo nível. Essa é uma propriedade essencial das Árvores B: elas são balanceadas por altura, garantindo que o caminho da raiz até qualquer folha tenha o mesmo comprimento. Isso assegura desempenho previsível.
Afirmativa 2 — ✅ Correta Em uma Árvore B de grau g, cada nó pode conter no máximo 2g - 1 chaves. Esse limite decorre da definição: um nó completo tem exatamente 2g filhos (pois o número de filhos é número de chaves + 1) e, portanto, 2g-1 chaves.
Afirmativa 3 — ✅ Correta Exceto o nó raiz, todo nó (não folha ou folha) deve ter no mínimo g - 1 chaves. A raiz pode ter de 1 a 2g-1 chaves. Essa regra evita que a árvore degrade.
Afirmativa 4 — ❌ Incorreta Afirma que a complexidade de inserção é O(n). Isso é falso: a Árvore B é balanceada, então a altura é O(log n) no pior caso, e a inserção percorre um caminho da raiz até a folha e eventualmente faz splits, tudo com custo O(log n). O(n) seria o custo de uma árvore degenerada, não de uma Árvore B.
Afirmativa 5 — ✅ Correta A complexidade de inserção é O(log n). Correto, pela mesma razão: a altura logarítmica garante que o número de nós visitados seja proporcional a log n.
Análise das alternativas (combinações)
Alternativa A — ❌ Incorreta
Afirma que estão corretas apenas 2, 3 e 4. Inclui a afirmativa 4 (falsa) e exclui a afirmativa 1 (verdadeira). Portanto, errada.
Alternativa B — ✅ Correta ⟵ GABARITO
Afirma que estão corretas 1, 2, 3 e 5. Exatamente as quatro afirmativas verdadeiras, sem incluir a falsa (4). É a alternativa correta.
Alternativa C — ❌ Incorreta
Afirma que estão corretas 1, 2, 4 e 5. Inclui a afirmativa 4 (falsa), logo incorreta.
Alternativa D — ❌ Incorreta
Afirma que estão corretas 2, 3, 4 e 5. Inclui a afirmativa 4 (falsa) e exclui a afirmativa 1 (verdadeira). Incorreta.
Alternativa E — ❌ Incorreta
Afirma que estão corretas 1, 3, 4 e 5. Inclui a afirmativa 4 (falsa) e exclui a afirmativa 2 (verdadeira). Incorreta.
Gabarito: letra B – corretas as afirmativas 1, 2, 3 e 5.