— 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
- No centro comunitario do bairro, um grupo de jovens montou um sistema simples para registrar os arquivos enviados para a…
- Pesquisas recentes indicam que 23% dos usuários de um fórum online relatam ter visto comentários abusivos diariamente…
- No fim da tarde, monitores de um parque costeiro passaram a registrar, em um tablet, as aves vistas em cada trilha. O…
- Ao final de uma feira de ciências, um grupo de estudantes criou um aplicativo simples para registrar pedidos de…
- Dados levantados por um grupo de jovens voluntários apontam que eles catalogaram cerca de 1.200 artefatos em um acervo…
- Em uma atividade de Computação, uma turma está desenvolvendo um aplicativo para acompanhar a coleta seletiva no bairro…
🔎 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