Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — FCC 2019
Algoritmos e Estrutura de Dados›Estrutura de Dados
Código
fc058044
Banca
FCC
Órgão
TRF - 4ª REGIÃO
Ano
2019
Cargo
Técnico Judiciário - Tecnologia da Informação
Determinada estrutura de dados foi projetada para minimizar o número de acessos à memória secundária. Como o número de acessos à memória secundária depende diretamente da altura da estrutura, esta foi concebida para ter uma altura inferior às estruturas hierarquizadas similares, para um dado número de registros. Para manter o número de registros armazenados e, ao mesmo tempo, diminuir a altura, uma solução é aumentar o grau de ramificação da estrutura (o número máximo de filhos que um nó pode ter). Assim, esta estrutura possui um grau de ramificação geralmente muito maior que 2. Além disso, a cada nó são associados mais de um registro de dados: se o grau de ramificação de um nó for g, este pode armazenar até g-1 registros.Esta estrutura de dados é utilizada em banco de dados e sistema de arquivos, sendo denominada
Aárvore digital ou trie.
Bárvore B.
Clista linear duplamente encadeada circular.
Dárvore rubro-negra.
Eárvore binária de busca não balanceada.
Revelar gabarito e comentário▾
GabaritoB — árvore B.
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”.
Estrutura de dados: Árvore B
Gabarito: letra B. A descrição corresponde exatamente a uma árvore B: estrutura balanceada de múltiplos caminhos (grau de ramificação muito maior que 2), que armazena múltiplas chaves por nó (até g-1) e é projetada para minimizar acessos a disco em bancos de dados e sistemas de arquivos.
A banca testa o reconhecimento das características fundamentais das árvores B. Diferentemente de árvores binárias (rubro-negra, busca não balanceada) ou estruturas lineares, a árvore B tem alto fator de ramificação e nós com múltiplos registros, reduzindo a altura e consequentemente o número de acessos à memória secundária.
Característica
Árvore B (✅ Correta)
Árvore Digital/Trie (❌ Incorreta)
Lista Linear Duplamente Encadeada Circular (❌ Incorreta)
Árvore Rubro-Negra (❌ Incorreta)
Árvore Binária de Busca Não Balanceada (❌ Incorreta)
Grau de ramificação
Muito maior que 2 (centenas/milhares)
Variável (baseado em alfabeto)
Fixo em 2 (anterior/próximo)
Fixo em 2 (binária)
Fixo em 2 (binária)
Registros por nó
Até g-1 registros (múltiplos)
Geralmente 1 caractere/chave
1 registro
1 registro
1 registro
Altura para grande volume
Baixa (reduz acessos a disco)
Pode ser alta (depende do prefixo)
Linear (alta)
Logarítmica (maior que árvore B)
Pode ser linear (alta)
Uso principal
Bancos de dados e sistemas de arquivos (minimizar acessos a disco)
Armazenamento eficiente de strings (prefixos)
Estrutura linear genérica
Memória principal (balanceamento)
Memória principal (sem balanceamento)
Alternativa A — ❌ Incorreta
A árvore digital (trie) é usada para armazenamento eficiente de strings com base em prefixos, mas não possui as características descritas: geralmente cada nó representa um caractere e não armazena múltiplos registros por nó com grau de ramificação variável. Não é a estrutura típica para minimizar acessos a disco em bancos de dados.
Alternativa B — ✅ Correta ⟵ GABARITO
A árvore B é uma árvore balanceada de múltiplos caminhos. Suas principais propriedades casam exatamente com o enunciado:
Grau de ramificação g geralmente muito maior que 2 (centenas ou milhares).
Cada nó armazena até g-1 registros (chaves).
Altura reduzida para um dado número de registros, minimizando acessos à memória secundária.
Amplamente utilizada em sistemas de gerenciamento de banco de dados e sistemas de arquivos (ex.: índices de tabelas, sistemas de diretórios).
Alternativa C — ❌ Incorreta
A lista linear duplamente encadeada circular é uma estrutura linear (cada nó tem um único predecessor e sucessor), não hierárquica. Não possui grau de ramificação (cada nó tem no máximo dois ponteiros) nem armazena múltiplos registros por nó com a finalidade de reduzir altura. É inadequada para minimizar acessos a disco em grandes volumes.
Alternativa D — ❌ Incorreta
A árvore rubro-negra é uma árvore binária de busca balanceada: cada nó tem grau de ramificação 2 e armazena uma única chave. Embora seja balanceada e útil em memória principal, sua altura é maior que a de uma árvore B para o mesmo número de elementos, e não é projetada para minimizar acessos a disco. Não atende aos requisitos de alto grau de ramificação e múltiplas chaves por nó.
Alternativa E — ❌ Incorreta
A árvore binária de busca não balanceada tem grau fixo 2 e armazena uma chave por nó. Sua altura pode chegar a O(n) no pior caso, resultando em muitos acessos a disco. Não possui as características de alto fator de ramificação e balanceamento que a descrição exige.
PEGA ESSA DICA!
Em questões sobre estruturas de dados para banco de dados, lembre-se: árvores B são as únicas que combinam alto grau de ramificação, múltiplas chaves por nó e balanceamento. Quando o enunciado mencionar "minimizar acessos à memória secundária", "altura reduzida" e "grau de ramificação maior que 2", a resposta quase sempre é árvore B.