Dado um algoritmo que conta a frequência de palavras em redações escolares, qual estrutura de dados é mais…
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
Dado um algoritmo que conta a frequência de palavras em redações escolares, qual estrutura de dados é mais adequada para associar cada palavra ao seu número de ocorrências?
- A) Árvore binária de busca, que é ineficiente para contagem de palavras.
- B) Mapa (dicionário/hashtable) associando palavra ? contador
- C) Conjunto (set), que não permite armazenar contagem de ocorrências de palavras.
- D) Lista encadeada, que não permite acesso rápido a elementos específicos.
- E) Fila, que apenas permite adicionar e remover elementos em uma ordem específica.
✅ Resposta correta: alternativa B
Resolução passo a passo
- A tarefa é associar cada palavra a um número de ocorrências, ou seja, para cada chave (palavra) guardar um valor (contador) e poder consultar e atualizar esse valor rapidamente enquanto o texto é percorrido.
- Um mapa, também chamado dicionário (em Python) ou hashtable, é justamente a estrutura feita para armazenar pares chave-valor. Ao ler uma palavra, basta buscar a chave; se existir, incrementa o contador; se não existir, cria a entrada com valor 1. Essas operações costumam ser realizadas em tempo médio constante.
- Por que as outras estão erradas: A) a árvore binária de busca também associa chaves a valores, sendo uma solução válida embora menos eficiente que a tabela hash em média, então a justificativa dada na alternativa não a invalida totalmente para a associação; porém não é a estrutura mais adequada. C) o conjunto guarda apenas a presença de elementos, sem associar a eles um contador. D) a lista encadeada exige percorrer os elementos para achar uma palavra, tornando a contagem lenta. E) a fila permite apenas inserir no fim e remover do início, não sendo adequada para buscar e atualizar contadores de palavras específicas.
- Conclusão: a estrutura mais adequada é o mapa (dicionário/hashtable) associando palavra a contador, alternativa B, que coincide com o gabarito oficial.
💡 Dica: Considere as características das estruturas de dados disponíveis.
Alternativa por alternativa
O aluno pode acreditar que a árvore binária de busca é a estrutura padrão para contagem e que sua ineficiência é um impedimento total, sem perceber que ela também associa chaves a valores.
Por que engana: Escolher uma estrutura de dados que não permite contagem eficiente, como uma lista encadeada ou um conjunto, por não entender suas limitações.
Um mapa permite mapear cada palavra a um valor contador com operações de inserção e acesso em tempo médio O(1), facilitando incremento e consulta de frequências.
O aluno confunde conjunto com mapa, achando que, por o conjunto guardar elementos sem repetição, ele também poderia guardar a quantidade de ocorrências de cada palavra.
O aluno supõe que qualquer estrutura sequencial serve para armazenar dados, sem considerar que a busca em lista encadeada percorre elemento por elemento, tornando a contagem lenta.
O aluno associa fila a um simples armazenamento de dados em ordem de chegada, sem perceber que ela não permite localizar e atualizar uma palavra específica.
Raio-X da questão
estruturas de dados
avaliacao
estruturas de dados · algoritmos de contagem
Revisar as principais estruturas de dados e suas aplicações.
Escolher uma estrutura de dados que não permite contagem eficiente, como uma lista encadeada ou um conjunto, por não entender suas limitações.
ciencia_tecnologia
pensamento_critico
abstrato
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