Qual estrutura de dados é mais adequada para implementar buscas eficientes por prefixo em um dicionário de…
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
Qual estrutura de dados é mais adequada para implementar buscas eficientes por prefixo em um dicionário de palavras (por exemplo, sugestão de auto-completar), usando cada caractere como nível de navegação?
- A) Trie (árvore de prefixos), onde cada nível corresponde a um caractere, permitindo buscas por prefixo em tempo proporcional ao comprimento do prefixo.
- B) Usar uma árvore binária de busca para implementações de prefixo.
- C) Empregar um vetor dinâmico para armazenar palavras.
- D) Adotar um dicionário de palavras com busca linear.
- E) Utilizar uma lista ligada para armazenar palavras.
✅ Resposta correta: alternativa A
Resolução passo a passo
- A questão pede a estrutura de dados mais adequada para buscas por prefixo (como auto-completar) em que cada caractere representa um nível de navegação.
- Resolvendo por conta própria, a estrutura que organiza as palavras caractere a caractere, com um nível por letra, é a trie (árvore de prefixos). Para encontrar todas as palavras que começam com um prefixo de tamanho k, basta descer k níveis a partir da raiz, o que custa tempo proporcional a k, e depois coletar as palavras da subárvore alcançada.
- Comparando com o gabarito oficial (letra A), a resposta coincide com a conclusão obtida.
- Por que as outras estão erradas:
- B) Uma árvore binária de busca compara palavras inteiras por ordem alfabética e não navega caractere a caractere, então não é a estrutura natural para prefixos.
- C) Um vetor dinâmico guarda as palavras sem organização por prefixo, exigindo varredura para encontrar as que começam com um determinado prefixo.
- D) Busca linear percorre todas as palavras a cada consulta, sendo ineficiente para sugestões em tempo real; além disso, não é uma estrutura de dados e sim uma forma de busca.
- E) Uma lista ligada também exige percorrer os elementos um a um para encontrar palavras com um prefixo, sem aproveitar a estrutura dos caracteres.
💡 Dica: Considere as características das estruturas de dados para buscas.
Alternativa por alternativa
A trie organiza palavras por prefixos; ao buscar um prefixo percorre apenas os nós desse prefixo em vez de comparar todas as palavras, tornando consultas e sugestões rápidas.
O aluno associa busca eficiente à árvore binária de busca, achando que ordenar as palavras basta para localizar prefixos rapidamente. Não percebe que a BST compara palavras inteiras e não aproveita a navegação caractere a caractere.
Por que engana: Confundir a eficiência de busca em uma árvore binária de busca com a de uma trie, subestimando a complexidade das operações de prefixo.
O aluno pensa que armazenar as palavras em um vetor dinâmico, que permite acesso rápido por índice, já resolve a busca por prefixo. Não percebe que o vetor não organiza as palavras por prefixo e exige varredura.
O aluno confunde a estrutura de armazenamento com o método de busca e considera a busca linear uma opção válida de eficiência. Ignora que percorrer todo o dicionário a cada consulta é justamente o que a questão quer evitar.
O aluno imagina que a lista ligada, por ser dinâmica e fácil de inserir elementos, serve para buscas eficientes. Não percebe que, sem organização, a lista exige percorrer as palavras uma a uma.
Raio-X da questão
buscas por prefixo
avaliacao
estruturas de dados · buscas em dicionários
Revisar estruturas de dados como tries e suas aplicações.
Confundir a eficiência de busca em uma árvore binária de busca com a de uma trie, subestimando a complexidade das operações de prefixo.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Para implementar em um algoritmo uma tabela de símbolos com busca rápida por chaves alfanuméricas (por exemplo nomes)…
- Ao projetar um algoritmo que conta ocorrências de palavras em um texto grande, qual estrutura de dados é mais eficiente…
- Qual estrutura de dados é mais adequada para implementar um sistema de navegação por mapas?
- 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…
- Um programador precisa organizar uma lista de nomes em ordem alfabética. Qual estrutura de dados é mais adequada para…
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