Questão de Algoritmos e Estrutura de Dados — Árvores — FGV 2023
Algoritmos e Estrutura de Dados›Árvores
Código
fg065337
Banca
FGV
Órgão
PGM - Niterói
Ano
2023
Nível
Superior
Cargo
Analista de Tecnologia da Informação
No contexto das estruturas de índices do tipo árvores balanceadas (B-Trees), analise as afirmativas a seguir.I. Qualquer operação de inserção de uma nova chave implica uma divisão (split) de algum nó.II. Qualquer operação de remoção de uma chave implica uma divisão (split) de algum nó.III. Qualquer operação de remoção de uma chave implica uma concatenação de dois ou mais nós em um.Está correto o que se afirma em:
Anenhuma;
Bsomente I;
Csomente II;
Dsomente III;
Esomente I e III.
Revelar gabarito e comentário▾
GabaritoA — nenhuma;
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”.
B-Trees: operações de inserção e remoção
Gabarito: letra A (nenhuma). Nenhuma das afirmativas é verdadeira para B-Trees: inserções nem sempre geram split; remoções nunca geram split e nem sempre geram concatenação.
A questão testa o conhecimento do funcionamento de árvores B (B-Trees), estrutura balanceada utilizada em índices de bancos de dados e sistemas de arquivos. Ao contrário de árvores binárias balanceadas (como AVL), as B-Trees possuem grau mínimo e máximo definidos (ordem). As operações de inserção e remoção possuem regras específicas de rebalanceamento.
B-Tree: operações
1Inserção
Nó com espaço → insere sem split
Nó cheio → split (overflow)
2Remoção
Irmão com chaves → redistribuição
Irmão sem chaves → merge (concatenação)
Nunca gera split
LEVEL · soulevel.com.br
Afirmativa I — ❌ Falsa
"Qualquer operação de inserção de uma nova chave implica uma divisão (split) de algum nó."
Em B-Trees, a inserção começa pela busca da posição correta no nó folha. Se o nó folha tiver espaço (menos chaves que o máximo), a chave é simplesmente adicionada, sem split. O split só ocorre quando o nó está cheio (já contém o número máximo de chaves). Portanto, nem toda inserção provoca split.
Afirmativa II — ❌ Falsa
"Qualquer operação de remoção de uma chave implica uma divisão (split) de algum nó."
Split é operação exclusiva de inserção (para tratar overflow). Na remoção, quando um nó fica com menos chaves que o mínimo (underflow), as operações são redistribuição (pegar chave de um nó irmão) ou concatenação/merge (fundir com um irmão). Nunca ocorre split na remoção.
Afirmativa III — ❌ Falsa
"Qualquer operação de remoção de uma chave implica uma concatenação de dois ou mais nós em um."
A concatenação (merge) não é obrigatória. Se o nó irmão tiver chaves sobrando, a remoção pode ser resolvida por redistribuição, sem fundir nós. Merge só ocorre quando ambos os nós (o que perdeu a chave e seu irmão) ficam abaixo do mínimo. Assim, nem toda remoção gera concatenação.
PEGA ESSA DICA!
Para B-Trees, lembre-se: inserção → pode causar split (apenas quando nó cheio); remoção → pode causar redistribuição ou merge (quando nó fica com menos do mínimo). Nenhuma operação é "sempre" split ou merge.
Gabarito: letra A — nenhuma afirmativa está correta.