Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — FGV 2024
Algoritmos e Estrutura de Dados›Estrutura de Dados
Código
fg098442
Banca
FGV
Órgão
TJ-MS
Ano
2024
Nível
Superior
Cargo
Técnico de Nível Superior - Analista de Sistemas Computacionais - Analista de Infraestrutura de Redes
Micael, atuando como analista no desenvolvimento de um sistema de gerenciamento de biblioteca, enfrenta o desafio de selecionar uma estrutura de dados que otimize o armazenamento de informações sobre os livros. O sistema requer uma solução que combine a eficiência em realizar buscas rápidas por título, a capacidade de adicionar novos títulos frequentemente e a preservação da ordem alfabética para melhorar a experiência de navegação.Levando em conta os critérios de acesso, busca, inserção e ordenação nas estruturas de dados, Micael identifica que a melhor opção para cumprir esses requisitos é a(o):
Ahash table;
Blista encadeada;
Carray ordenado;
Dfila de prioridade;
Eárvore de busca binária.
Revelar gabarito e comentário▾
GabaritoE — árvore de busca binária.
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”.
Seleção de Estrutura de Dados para Gerenciamento de Biblioteca
Gabarito: letra E. A árvore de busca binária (ABB) atende aos três requisitos simultaneamente: busca rápida (O(log n) em média), inserção eficiente (O(log n)) e manutenção da ordem alfabética (percurso in-order). Nenhuma outra estrutura listada combina essas características.
A questão testa a capacidade de relacionar propriedades de estruturas de dados a requisitos práticos. O ponto central é identificar qual estrutura oferece, ao mesmo tempo, busca eficiente, inserção dinâmica e ordenação intrínseca.
Estrutura de dados para biblioteca
1Requisitos
Busca rápida por título
Inserção frequente
Ordem alfabética mantida
2Alternativas
Hash table
Busca O(1)
Inserção O(1)
Não preserva ordem
Lista encadeada
Busca O(n)
Inserção ordenada O(n)
Array ordenado
Busca O(log n)
Inserção O(n)
Fila de prioridade
Não busca por valor
Ordenação parcial
Árvore de busca binária
Busca O(log n)
Inserção O(log n)
Ordem por percurso in-order
LEVEL · soulevel.com.br
Alternativa A — ❌ Incorreta
A hash table oferece busca e inserção em tempo constante no caso médio (O(1)), mas não preserva a ordem alfabética. Os elementos são armazenados com base no valor da função hash, sem relação com a sequência das chaves. Para obter os livros em ordem alfabética, seria necessário ordenar todos os elementos a cada operação, o que é custoso e anula a vantagem da busca rápida.
Alternativa B — ❌ Incorreta
A lista encadeada permite inserção eficiente no início (O(1)) e para adição ordenada exige percorrer a lista até a posição correta (O(n)). A busca por título é linear (O(n)), inaceitável para um sistema que exige buscas rápidas com muitos dados.
Alternativa C — ❌ Incorreta
O array ordenado permite busca binária eficiente (O(log n)) e mantém a ordem, mas a inserção de novos elementos exige deslocar todos os elementos posteriores (O(n) no pior caso). Adições frequentes tornam essa estrutura inviável.
Alternativa D — ❌ Incorreta
A fila de prioridade (geralmente implementada com heap) garante acesso rápido ao elemento de maior/menor prioridade, mas não oferece busca por um valor específico (como um título) – a única forma de localizar um elemento é percorrer toda a estrutura. Além disso, a ordenação é parcial (apenas o topo é garantido), não a sequência alfabética completa.
Alternativa E — ✅ Correta ⟵ GABARITO
A árvore de busca binária (ABB) ou, idealmente, uma versão balanceada (AVL, rubro-negra) atende a todos os requisitos:
Busca rápida: percorre a árvore comparando chaves, com complexidade O(log n) em média.
Inserção eficiente: localiza a posição correta e insere em O(log n).
Ordem preservada: o percurso in-order (esquerda-raiz-direita) retorna os elementos em ordem alfabética naturalmente.
Dessa forma, a ABB é a estrutura que melhor equilibra os três critérios.