Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — FUNDATEC 2026
Algoritmos e Estrutura de Dados›Estrutura de Dados
Código
qg685520
Banca
FUNDATEC
Órgão
IFC-SC
Ano
2026
Nível
Superior
Cargo
Professor EBTT - Computação
Considere árvores B não vazias, com grau mínimo t ≥ 2. Para árvores B+, adote a convenção usual de sistemas de indexação: todas as chaves de dados permanecem nas folhas, enquanto os nodos (nós) internos armazenam apenas chaves separadoras; todas as folhas estão na mesma profundidade. Nesse contexto, analise as assertivas a seguir:I. Em uma árvore B de grau mínimo t, todo nodo não raiz armazena entre t−1 e 2t−1 chaves; a raiz armazena entre 1 e 2t−1 chaves.II. A altura de uma árvore B aumenta somente quando a raiz é dividida e diminui somente quando, após uma fusão, uma raiz interna fica sem chaves e é substituída por seu único filho.III. Na inserção em uma árvore B+, a divisão de uma folha cheia remove da folha a chave separadora promovida ao pai, exatamente como ocorre na divisão de um nodo em uma árvore B convencional.IV. A altura h de uma árvore B de grau mínimo t, com n chaves, satisfaz h ≤ logt((n+1)/2). Para t=500 e n=10⁹, conclui-se que h ≤ 3; ou seja, o caminho da raiz até uma folha contém no máximo 4 nodos.Assumindo um nodo por página de disco e a raiz residente em memória principal, uma busca exige, no máximo, 3 acessos a disco.Quais estão corretas?
AApenas I e II.
BApenas I e III.
CApenas I, II e IV.
DApenas II, III e IV.
EI, II, III e IV.
Revelar gabarito e comentário▾
GabaritoC — Apenas I, II e IV.
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 B e B+: Propriedades e Análise de Assertivas
Gabarito: letra C — estão corretas apenas as assertivas I, II e IV. A assertiva III está incorreta porque, na árvore B+, ao dividir uma folha, a chave separadora promovida ao pai permanece na folha (não é removida), diferentemente da divisão de um nó interno na árvore B convencional.
A questão testa conhecimentos fundamentais sobre árvores B (de grau mínimo t) e árvores B+ (variante de indexação). Vamos analisar cada assertiva separadamente.
Assertiva
Descrição
Correção
Motivo
I
Em árvore B de grau mínimo t, todo nó não raiz armazena entre t−1 e 2t−1 chaves; a raiz armazena entre 1 e 2t−1 chaves.
✅ Correta
Definição padrão de árvore B com grau mínimo t ≥ 2.
II
A altura de uma árvore B aumenta somente quando a raiz é dividida e diminui somente quando, após fusão, raiz interna fica sem chaves e é substituída por seu único filho.
✅ Correta
Comportamento característico e correto de árvores B.
III
Na inserção em árvore B+, a divisão de folha cheia remove da folha a chave separadora promovida ao pai, exatamente como na B convencional.
❌ Incorreta
Na B+, a chave separadora permanece na folha (é copiada, não removida); na B convencional, a chave mediana é removida e promovida.
IV
A altura h de árvore B de grau mínimo t, com n chaves, satisfaz h ≤ logₜ((n+1)/2). Para t=500 e n=10⁹, h ≤ 3, e busca exige no máximo 3 acessos a disco.
✅ Correta
Cálculo correto: log₅₀₀(5×10⁸) ≈ 3,22 → h ≤ 3; acessos a disco = h (níveis 1 a 3).
Árvore B (grau mínimo t)
1Número de chaves por nó
Raiz: 1 a 2t−1
Não raiz: t−1 a 2t−1
2Altura
Aumenta: divisão da raiz
Diminui: fusão na raiz
3Busca: h ≤ logₜ((n+1)/2)
4Árvore B+ (indexação)
Folhas: todas as chaves de dados
Nós internos: só chaves separadoras
Divisão de folha
Chave separadora permanece na folha
Cópia ao pai (não remoção)
LEVEL · soulevel.com.br
Item I — ✅ Correto
Descreve corretamente o número de chaves por nó em uma árvore B: todo nó não raiz armazena entre t−1 e 2t−1 chaves; a raiz armazena entre 1 e 2t−1 chaves. Essa é a definição padrão de árvore B com grau mínimo t ≥ 2.
Item II — ✅ Correto
A altura de uma árvore B aumenta apenas quando a raiz é dividida (após uma inserção) e diminui apenas quando, após uma fusão (deleção), a raiz interna fica sem chaves e é substituída por seu único filho. Esse comportamento é característico e correto.
Item III — ❌ Incorreto
Afirma que, na inserção em árvore B+, a divisão de uma folha cheia remove da folha a chave separadora promovida ao pai, exatamente como na B convencional. Erro: na B+, todas as chaves de dados permanecem nas folhas; quando uma folha é dividida, a chave separadora (menor chave da nova folha direita) é copiada para o pai, mas permanece na folha. Já na árvore B convencional, a chave mediana é removida do nó que se divide e promovida ao pai. Logo, os processos são diferentes.
Item IV — ✅ Correto
A altura h de uma árvore B de grau mínimo t, com n chaves, satisfaz h ≤ logₜ((n+1)/2). Para t=500 e n=10⁹:
Logo, h ≤ 3 (altura máxima 3), e o caminho da raiz até uma folha contém no máximo 4 nós (raiz no nível 0, folha no nível h). Com a raiz residente em memória principal e um nó por página, uma busca exige no máximo 3 acessos a disco (níveis 1, 2 e 3), conforme afirmado. Portanto, a assertiva está correta.
Conclusão: Corretos I, II e IV → alternativa C.
NÃO CAIA NESSA!
A assertiva III explora a confusão clássica entre árvore B e B+: na B+ a chave promovida de uma folha não é removida dela, enquanto na B convencional o nó interno perde a chave. Fique atento a essa diferença!