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
- Na inscrição para uma oficina de robótica, a escola registra: nome completo, idade, turno escolhido e autorização da…
- — A estação da Praça das Mangueiras está aberta, mas só restam 3 bicicletas — avisou uma moradora ao serviço municipal…
- — Onde estão as peças ásperas em forma de estrela? — perguntou uma criança durante a montagem de um jogo tátil. O…
- — O caminhão só consegue visitar vinte contêineres por noite — avisou a coordenadora da coleta seletiva. Durante a…
- — A tela do empréstimo mostra primeiro a cor e depois a figura — explicou Nora, responsável pela brinquedoteca…
- — A linha 206 passou com a rampa disponível hoje? — perguntou uma usuária no ponto de ônibus. Durante um teste fictício…
🔎 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