— Recebemos dezenas de links de eventos comunitários todo dia, diz Mariana ao grupo de voluntários online. —…
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
— Recebemos dezenas de links de eventos comunitários todo dia, diz Mariana ao grupo de voluntários online. — Como garantir que cada site é confiável antes de compartilhar? propõe Leo. No debate, sugerem armazenar os domínios das fontes aprovadas em alguma estrutura de dados. A secretária digital, Carla, lista algumas: vetor ordenado, lista ligada, árvore binária de busca, fila ou tabela de hash. Ela lembra que as verificações devem ser rápidas, já que chegam cerca de 5 000 requisições por turno. Analise o relato e identifique qual estrutura de dados permite, em média, verificar rapidamente se um domínio de fonte está na lista confiável antes de compartilhar um link.
- A) Tabela de hash
- B) Lista ligada
- C) Fila
- D) Vetor ordenado
- E) Árvore binária de busca
✅ Resposta correta: alternativa A
Resolução passo a passo
- O problema pede uma estrutura que permita verificar, em média, se um domínio está na lista de fontes aprovadas de forma rápida, com cerca de 5 000 consultas por turno. O que importa é o tempo médio da operação de busca.
- Em uma tabela de hash, a chave (o domínio) é transformada por uma função de espalhamento em um índice, e a busca ocorre em tempo médio constante, O(1). Por isso, a tabela de hash é a resposta correta, coincidindo com o gabarito oficial.
- Por que as outras estão erradas:
- B) Lista ligada: a busca precisa percorrer os nós um a um, custando O(n) no pior e no caso médio.
- C) Fila: foi feita para inserção no fim e remoção no início (FIFO), e não para buscar um elemento específico; a busca também é linear.
- D) Vetor ordenado: a busca binária é O(log n), que é rápida, mas não é a opção de tempo médio constante; com muitos domínios a tabela de hash tende a ser mais rápida.
- E) Árvore binária de busca: a busca é O(log n) em média quando balanceada, mas pode degenerar para O(n) se desbalanceada; é menos vantajosa que a tabela de hash para apenas verificar pertinência.
- Conclusão: para verificar pertinência com o menor tempo médio possível, a tabela de hash é a estrutura mais adequada.
💡 Dica: Considere a eficiência média das estruturas para busca de elementos.
Alternativa por alternativa
Tabela de hash oferece tempo médio de pesquisa O(1), ideal para verificar domínios rapidamente antes de compartilhar.
Considera que a lista ligada serve para consultas rápidas porque armazena os elementos em sequência. Na prática, para achar um domínio é preciso percorrer nó por nó, o que é lento com milhares de consultas.
Confunde a fila, que organiza a ordem de atendimento (primeiro a entrar, primeiro a sair), com uma estrutura de busca. A fila não foi feita para localizar um elemento específico.
Acredita que, por ser ordenado, o vetor já resolve a busca de forma ideal. Embora a busca binária seja rápida (O(log n)), ela não é a de menor tempo médio, e a tabela de hash é superior para pertinência.
Por que engana: Confundir estruturas que permitem busca rápida com as que têm busca sequencial lenta.
Assume que a árvore binária de busca sempre oferece a melhor busca. Ela é O(log n) apenas quando balanceada e pode degenerar para O(n), além de ser menos eficiente que a tabela de hash para apenas verificar pertinência.
Raio-X da questão
estruturas de dados para busca
avaliacao
estruturas de dados básicas · complexidade de algoritmos
estude as características e eficiência das estruturas de dados para busca
Confundir estruturas que permitem busca rápida com as que têm busca sequencial lenta.
ciencia_tecnologia
pensamento_critico
cotidiano
Questões parecidas com resolução
- Um sistema de irrigação segue o esquema: leia a umidade do solo; se umidade < 30, ligue a água; caso contrário…
- Em um laboratório de análise de sementes, dois programas escritos na mesma linguagem processam registros. O programa P…
- Em uma incubadora usada em pesquisas científicas, um sensor mede a temperatura. A equipe considera adequada uma leitura…
- Em uma barraca de feira, cada suco custa R$ 5. Uma cliente escolhe uma quantidade de sucos, representada pela variável…
- Quatro colegas vão planejar um aplicativo simples para organizar os estudos do grupo. O aplicativo deve mostrar as…
- — A ponte do rio ficou interditada; a lancha terá de mudar o trajeto — informou a central de defesa civil. Para levar…
🔎 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