Questão nº 27
Questão de Tecnologia da Informação · FCC TRF4 2019 (nº 27)
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. (alternativa correta)
- Clista linear duplamente encadeada circular.
- Dárvore rubro-negra.
- Eárvore binária de busca não balanceada.
Resposta comentada
Gabarito Alternativa B
A questão descreve uma estrutura de dados hierárquica otimizada para o armazenamento e recuperação de informações em memória secundária (como discos rígidos), onde o acesso é lento. Para minimizar o tempo de busca, ela reduz a altura da árvore (número de níveis), permitindo que cada nó tenha um grande número de filhos (alto grau de ramificação) e armazene múltiplos registros de dados.
(A) Incorreta: Árvores digitais (tries) são estruturas especializadas para busca de strings por prefixo e não são projetadas primariamente para minimizar acessos a disco através de um alto grau de ramificação e múltiplos registros por nó.
(B) Correta: A árvore B (B-tree) é a estrutura de dados que se encaixa perfeitamente na descrição. Ela foi criada para ser eficiente em memória secundária, minimizando operações de I/O (leitura/escrita em disco) ao ter um alto grau de ramificação (muitos filhos) e armazenar múltiplos registros (chaves) em cada nó, o que mantém a árvore "baixa" (com pouca altura) mesmo com um grande volume de dados. É a base de muitos sistemas de banco de dados e sistemas de arquivos.
(C) Incorreta: Uma lista linear duplamente encadeada circular é uma estrutura de dados linear, não hierárquica, e não possui as características de grau de ramificação ou otimização de altura para acesso a disco.
(D) Incorreta: A árvore rubro-negra é uma árvore binária de busca balanceada, otimizada para operações em memória principal. Embora seja balanceada (mantendo a altura logarítmica), ela é binária (grau de ramificação 2) e cada nó armazena apenas um registro, o que a torna ineficiente para o cenário de memória secundária descrito. A armadilha aqui é focar apenas em "altura inferior" e esquecer as características cruciais de alto grau de ramificação e múltiplos registros por nó, que são essenciais para a otimização de disco.
(E) Incorreta: Uma árvore binária de busca não balanceada pode ter uma altura muito grande (degenerar para uma lista encadeada) no pior caso, o que seria extremamente ineficiente para acessos à memória secundária, e não possui alto grau de ramificação ou múltiplos registros por nó.
Fonte: FCC TRF4 2019 Técnico Judiciário - Área Apoio Especializado - Especialidade Tecnologia da Informação (Caderno Tipo 001). Reproduzida para fins de estudo.