Em uma base grande de registros de alunos, qual estrutura (termo técnico) permite buscar um registro por…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Identificar o comportamento dos algoritmos no que diz respeito ao consumo de recursos como tempo de execução, espaço de memória e energia, entre outros.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Em uma base grande de registros de alunos, qual estrutura (termo técnico) permite buscar um registro por matrícula em tempo médio O(1)?
- A) Árvore balanceada.
- B) Vetor ordenado.
- C) Lista encadeada.
- D) Matriz bidimensional.
- E) Tabela hash (hashtable/dicionário).
✅ Resposta correta: alternativa E
Resolução passo a passo
- A questão pede a estrutura de dados que permite buscar um registro por chave (matrícula) em tempo médio constante, O(1).
- Em uma tabela hash, uma função de dispersão (hash) converte a chave, como a matrícula, em um índice de um vetor. Assim, a busca calcula o índice diretamente e acessa o registro com custo médio constante, independentemente do número de registros, desde que a função distribua bem as chaves e as colisões sejam tratadas adequadamente.
- Por que as outras estão erradas:
- A) Árvore balanceada: a busca custa O(log n), pois percorre um caminho proporcional à altura da árvore, que cresce logaritmicamente com o número de registros.
- B) Vetor ordenado: a busca binária custa O(log n), e a busca sequencial custa O(n).
- C) Lista encadeada: a busca percorre os nós um a um, com custo O(n) no pior e no caso médio.
- D) Matriz bidimensional: é uma estrutura de acesso direto por dois índices de posição, mas não localiza um registro pelo valor da matrícula sem percorrer os dados, então não resolve a busca por chave.
- Conclusão: a alternativa correta é a E, que coincide com o gabarito oficial. A letra E corresponde à tabela hash, estrutura clássica para dicionários com busca em tempo médio O(1).
💡 Dica: Relacione a complexidade O(1) à busca por chave em uma estrutura de dados.
Alternativa por alternativa
O aluno sabe que a árvore balanceada é eficiente, mas acredita que ela alcança tempo constante, confundindo O(log n) com O(1) por ser 'muito rápida'.
Por que engana: Confundir a busca em uma estrutura ordenada, como vetor ou árvore balanceada, com acesso médio O(1); essas estruturas normalmente exigem mais operações do que uma tabela hash.
O aluno associa a ordenação a uma busca instantânea, sem perceber que mesmo com o vetor ordenado é preciso comparar chaves, o que leva a O(log n) na busca binária.
O aluno imagina que, por ser uma estrutura dinâmica e de fácil inserção, a lista encadeada também facilita a busca, ignorando que é preciso percorrer nó a nó até encontrar a matrícula.
O aluno confunde acesso direto por índices de linha e coluna com busca por conteúdo, achando que a matriz localiza a matrícula diretamente sem saber qual posição procurar.
Tabela hash distribui chaves em buckets permitindo acesso médio O(1); colisões são tratadas por encadeamento ou endereçamento aberto.
Raio-X da questão
Tabela hash e busca O(1)
avaliacao
Noções de estruturas de dados · Notação de complexidade algorítmica
Revise tabelas hash, acesso por chave e complexidade de busca nas principais estruturas de dados.
Confundir a busca em uma estrutura ordenada, como vetor ou árvore balanceada, com acesso médio O(1); essas estruturas normalmente exigem mais operações do que uma tabela hash.
ciencia_tecnologia
tomada_decisao
cientifico
Questões parecidas com resolução
- Num algoritmo que precisa localizar rapidamente o registro de um aluno a partir da matrícula, qual estrutura de dados é…
- 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…
- Na escola, um aplicativo guarda o nome de cada aluno junto com suas notas em várias matérias. A professora quer…
- Identifique a estrutura de dados que melhor organiza informações em uma tabela, permitindo acesso rápido e fácil a cada…
- Em um algoritmo que processa uma lista de alunos como dados e precisa evitar registros duplicados, qual estrutura de…
🔎 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