Você precisa armazenar uma coleção onde testar a existência de um elemento seja muito rápido e a ordem dos…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Construir soluções computacionais de problemas de diferentes áreas do conhecimento, de forma individual e colaborativa, selecionando as estruturas de dados e técnicas adequadas, aperfeiçoando e articulando saberes escolares.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Você precisa armazenar uma coleção onde testar a existência de um elemento seja muito rápido e a ordem dos elementos não importe. Qual estrutura técnica atende melhor esse requisito?
- A) Lista ordenada para armazenar os elementos.
- B) Conjunto implementado por tabela hash (hash set).
- C) Vector com ordenação periódica dos elementos.
- D) Fila para gerenciar a coleção e sua presença.
- E) Árvore binária de busca para consolidar os elementos.
✅ Resposta correta: alternativa B
Resolução passo a passo
- O enunciado pede uma coleção em que testar a existência de um elemento seja muito rápido e em que a ordem não importe. Ou seja, a estrutura precisa responder à pergunta 'este elemento está na coleção?' com custo baixo e sem se preocupar com posições.
- Um conjunto implementado por tabela hash (hash set) calcula a posição do elemento a partir de uma função de dispersão (hash). Assim, a verificação de pertinência tem custo médio constante, O(1), independentemente do número de elementos. Como conjuntos não garantem ordem, o requisito de ordem irrelevante também é atendido.
- A alternativa A está errada porque uma lista ordenada exige busca linear ou binária, que é mais lenta que O(1) e ainda impõe uma ordem que o problema dispensa.
- A alternativa C está errada porque um vector com ordenação periódica ainda depende de busca (linear ou binária) entre as ordenações, além de gastar tempo reordenando, sem vantagem sobre a tabela hash.
- A alternativa D está errada porque uma fila é uma estrutura de acesso FIFO, feita para inserir no fim e remover no início; não serve para testar pertinência de forma eficiente sem percorrer seus elementos.
- A alternativa E está errada porque uma árvore binária de busca oferece busca em tempo médio O(log n), que é eficiente, mas inferior ao custo constante de uma tabela hash, e ainda mantém os elementos ordenados, o que não é necessário.
- Conclusão: o gabarito B está correto. A tabela hash é a melhor escolha porque combina pertinência muito rápida com a dispensa de ordenação.
💡 Dica: Considere as características das estruturas de dados em computação.
Alternativa por alternativa
O aluno acredita que manter os elementos ordenados sempre acelera a busca, sem considerar que a lista ainda exige percorrer ou dividir a sequência para achar o elemento.
Por que engana: Confundir a eficiência de busca em listas ou árvores com a de conjuntos, subestimando a rapidez do acesso em tabelas hash.
Tabelas hash oferecem verificação de existência em média O(1) e eliminam duplicatas; como não preservam ordem, atendem coleções onde apenas a presença importa.
O aluno associa vector a acesso indexado rápido e acha que ordenar de tempos em tempos resolve a busca, sem perceber que a pertinência continua dependendo de pesquisa e que a reordenação custa caro.
O aluno confunde o nome 'fila' com uma estrutura de consulta geral, imaginando que gerenciar a coleção envolve automaticamente testar presença, quando a fila serve apenas para inserir no fim e remover no início.
O aluno lembra que árvores binárias de busca são eficientes e conclui que são a melhor opção, sem comparar com o custo constante médio da tabela hash nem notar que a ordenação oferecida não é exigida.
Raio-X da questão
estruturas de dados
avaliacao
estruturas de dados · tabela hash
Revisar as características das estruturas de dados, especialmente conjuntos e listas.
Confundir a eficiência de busca em listas ou árvores com a de conjuntos, subestimando a rapidez do acesso em tabelas hash.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Num fluxo contínuo de dados com memória limitada, deseja-se testar rapidamente se um dado já apareceu, aceitando alguns…
- Um programa guarda muitos números, precisa inserir e remover números com frequência e fazer buscas rápidas, sem…
- Qual estrutura de dados é mais adequada para armazenar uma lista de itens em que a ordem é importante e pode ser…
- Em um algoritmo que deve verificar rapidamente se um código de estudante já existe em uma grande coleção de dados, qual…
- Em um programa que simula um caixa eletrônico, é preciso consultar se um número de conta está cadastrado e impedir que…
- Qual estrutura de dados é mais adequada para armazenar uma lista de elementos que precisam ser acessados por sua…
🔎 Procurar outra questão
Procure no banco do GeraProva pelo tema ou por um trecho do enunciado. Cada questão já vem com resolução comentada e a análise de cada alternativa.
Professor: monte a prova com questões como esta, com gabarito e folha de respostas, em 30 segundos. Ver planos · Blog