Ao projetar um algoritmo que conta ocorrências de palavras em um texto grande, qual estrutura de dados é mais…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Identificar as principais formas de organizar e representar a informação de maneira estruturada (matrizes, registros, listas e grafos) ou não estruturada (números, palavras, valores verdade).
Fonte: Base Nacional Comum Curricular (MEC).Questão
Ao projetar um algoritmo que conta ocorrências de palavras em um texto grande, qual estrutura de dados é mais eficiente para armazenar pares (palavra, contagem) permitindo busca e atualização rápidas?
- A) Conjunto (Set)
- B) Dicionário (tabela de hash) — mapeia cada palavra à sua contagem.
- C) Matriz bidimensional
- D) Lista ligada ordenada
- E) Fila circular
✅ Resposta correta: alternativa B
Resolução passo a passo
- A tarefa exige armazenar pares (palavra, contagem) e, para cada palavra lida no texto, localizar rapidamente a entrada correspondente para somar 1 à contagem. Ou seja, é preciso uma estrutura que associe uma chave (a palavra) a um valor (a contagem), com busca e atualização rápidas.
- Um dicionário implementado com tabela de hash faz exatamente isso. Calculando o hash da palavra, o algoritmo acessa diretamente a posição onde ela está guardada, com custo médio constante, O(1), para buscar e atualizar. Por isso a alternativa B é a correta, e coincide com o gabarito oficial.
- A alternativa A está errada porque um conjunto (Set) guarda apenas elementos sem valor associado; ele diz se a palavra existe, mas não guarda quantas vezes ela apareceu.
- A alternativa C está errada porque uma matriz bidimensional é indexada por posições numéricas e não por palavras, e seria inadequada para um conjunto de chaves textuais de tamanho variável.
- A alternativa D está errada porque uma lista ligada ordenada exige percorrer os nós até achar a palavra, com custo linear no pior caso, o que é lento para textos grandes.
- A alternativa E está errada porque uma fila circular é uma estrutura de acesso sequencial (entra por um lado, sai pelo outro), sem suporte a busca por chave.
💡 Dica: Considere as características das estruturas de dados disponíveis.
Alternativa por alternativa
O aluno acredita que um conjunto basta para contar ocorrências, pois ele registra as palavras já vistas. Não percebe que o conjunto não armazena um valor associado à contagem.
Por que engana: Escolher uma estrutura de dados que não permite busca eficiente, como uma lista ligada, ao invés de um dicionário.
Tabelas de hash oferecem, em média, busca e atualização em tempo constante O(1), permitindo inserir ou incrementar a contagem de uma palavra sem percorre r listas. Outras opções (lista ou vetor) exigiriam busca linear.
O aluno pensa que uma matriz pode servir como tabela de consulta por qualquer dado, sem perceber que ela só acessa posições numéricas e não chaves textuais.
O aluno supõe que manter a lista ordenada garante busca rápida, sem considerar que ainda é preciso percorrer os nós linearmente para achar a palavra e atualizar sua contagem.
O aluno associa a palavra 'circular' ou 'fila' a algum tipo de acesso rápido, confundindo o modelo de acesso sequencial da fila com a busca por chave.
Raio-X da questão
estruturas de dados
avaliacao
estruturas de dados · algoritmos de busca
Revisar as principais estruturas de dados e suas aplicações.
Escolher uma estrutura de dados que não permite busca eficiente, como uma lista ligada, ao invés de um dicionário.
ciencia_tecnologia
tomada_decisao
cientifico
Questões parecidas com resolução
- Em um programa que conta a frequência de palavras em um texto, qual estrutura de dados é mais adequada para associar…
- Dado um algoritmo que conta a frequência de palavras em redações escolares, qual estrutura de dados é mais adequada para…
- Ao projetar um algoritmo que detecta padrões em uma sequência de eventos, qual estrutura de dados facilita buscas e…
- Qual estrutura de dados é mais adequada para implementar buscas eficientes por prefixo em um dicionário de palavras (por…
- Desenvolva um algoritmo que conte quantas vezes uma determinada palavra aparece em um texto. Apresente a lógica…
- Para implementar em um algoritmo uma tabela de símbolos com busca rápida por chaves alfanuméricas (por exemplo nomes)…
Todas as questões de Organização e representação da informação
🔎 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