Para implementar em um algoritmo uma tabela de símbolos com busca rápida por chaves alfanuméricas (por exemplo…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Classificar informações, agrupando-as em coleções (conjuntos) e associando cada coleção a um ‘tipo de dados’
Fonte: Base Nacional Comum Curricular (MEC).Questão
Para implementar em um algoritmo uma tabela de símbolos com busca rápida por chaves alfanuméricas (por exemplo nomes), qual estrutura de dados oferece buscas com tempo médio O(1) e é mais adequada?
- A) Array (vetor)
- B) Conjunto (set)
- C) Lista encadeada
- D) Tabela hash (dicionário/hashtable).
- E) Pilha (stack)
✅ Resposta correta: alternativa D
Resolução passo a passo
- A questão pede uma estrutura que faça buscas com tempo médio O(1) para chaves alfanuméricas, como nomes, em uma tabela de símbolos. Passo 2: Uma tabela hash calcula uma função de espalhamento sobre a chave, obtendo diretamente a posição onde o valor deve estar. Com poucas colisões, a busca, a inserção e a remoção ocorrem em tempo médio constante, O(1). Passo 3: A alternativa A está errada, pois um array só oferece acesso O(1) quando se conhece o índice numérico; buscar um nome exige percorrer os elementos (O(n)) ou usar ordenação com busca binária (O(log n)). Passo 4: A alternativa B está errada em parte, pois um conjunto (set) costuma ser implementado com tabela hash ou árvore balanceada; o conceito de conjunto trata de pertinência, não de associação chave-valor, e na tradicional comparação de estruturas a tabela hash é a resposta mais direta. Passo 5: A alternativa C está errada, pois em uma lista encadeada a busca percorre os nós um a um, com tempo O(n). Passo 6: A alternativa E está errada, pois a pilha só permite acesso ao topo (LIFO) e não oferece busca por chave. Passo 7: Portanto, a resposta correta é a D, tabela hash (dicionário/hashtable), que é a estrutura padrão para tabelas de símbolos com busca rápida por chave.
💡 Dica: Considere as características das estruturas de dados para busca.
Alternativa por alternativa
O aluno acredita que o acesso em vetor é sempre O(1), mesmo quando a busca é feita pelo conteúdo (nome) e não pelo índice numérico.
O aluno associa conjunto apenas à ideia de elementos não repetidos e não percebe que a busca eficiente depende da implementação subjacente, nem considera a estrutura de chave-valor pedida no contexto de tabela de símbolos.
Por que engana: Confundir a tabela hash com listas encadeadas, acreditando que ambas oferecem buscas rápidas.
O aluno imagina que a lista encadeada, por ser dinâmica, também oferece busca rápida, esquecendo que é necessário percorrer os nós sequencialmente.
Tabelas hash mapeiam chaves a índices via função de dispersão, oferecendo busca, inserção e remoção com tempo médio constante; apenas é necessário tratar colisões.
O aluno confunde a pilha com uma estrutura de consulta, pensando que é possível localizar qualquer elemento diretamente, quando na pilha só o topo é acessível.
Raio-X da questão
estruturas de dados
avaliacao
estruturas de dados · complexidade de algoritmos
Revisar as estruturas de dados e suas complexidades de busca.
Confundir a tabela hash com listas encadeadas, acreditando que ambas oferecem buscas rápidas.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Qual estrutura de dados é mais adequada para implementar buscas eficientes por prefixo em um dicionário de palavras (por…
- Num algoritmo que precisa localizar rapidamente o registro de um aluno a partir da matrícula, qual estrutura de dados é…
- Um programador precisa organizar uma lista de nomes em ordem alfabética. Qual estrutura de dados é mais adequada para…
- Em um algoritmo que deve verificar rapidamente se um código de estudante já existe em uma grande coleção de dados, qual…
- Em um programa escolar, cada aluno terá seu nome ligado à sua nota. O professor deverá informar um nome e encontrar…
- Você precisa armazenar uma coleção onde testar a existência de um elemento seja muito rápido e a ordem dos elementos nã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