Para um algoritmo que exige acesso direto ao elemento de índice i em tempo O(1), qual estrutura de dados é…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Construir soluções computacionais de problemas de diferentes áreas do conhecimento, de forma individual e colaborativa, selecionando as estruturas de dados e técnicas adequadas, aperfeiçoando e articulando saberes escolares.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Para um algoritmo que exige acesso direto ao elemento de índice i em tempo O(1), qual estrutura de dados é mais indicada: vetor (array) ou lista ligada?
- A) Vetor só permite acesso em tempo O(n) devido à sua estrutura.
- B) Acesso a elementos vetoriais é restrito a índices pares apenas.
- C) Vetor (array).
- D) Ambas estruturas têm acesso à posição i em tempo O(1) com a mesma eficiência.
- E) Lista ligada é a escolha ideal para acesso O(1) a elementos.
✅ Resposta correta: alternativa C
Resolução passo a passo
- A questão pede a estrutura adequada para acesso direto ao elemento de índice i em tempo O(1), ou seja, em tempo constante, independentemente do tamanho da estrutura.
- Em um vetor (array), os elementos ficam armazenados em posições contíguas da memória. O endereço do elemento de índice i é calculado diretamente a partir do endereço base mais i vezes o tamanho de cada elemento, por isso o acesso é O(1).
- Em uma lista ligada, os elementos não ocupam posições contíguas e cada nó só conhece o próximo (ou anterior). Para chegar ao i-ésimo elemento é preciso percorrer a lista desde o início, o que custa O(n).
- Portanto, a estrutura mais indicada é o vetor, alternativa C, que coincide com o gabarito oficial.
- A alternativa A está errada porque afirma que o vetor acessa em O(n), o que é justamente o comportamento da lista ligada. A alternativa B está errada porque índices pares não têm qualquer papel especial no acesso a vetores. A alternativa D está errada porque as duas estruturas não têm a mesma eficiência nesse acesso. A alternativa E está errada porque a lista ligada é justamente a estrutura que não oferece acesso O(1) por índice.
💡 Dica: Considere as características de acesso das estruturas de dados.
Alternativa por alternativa
O aluno confunde o comportamento do vetor com o da lista ligada, achando que o acesso por índice no vetor exige percorrer os elementos um a um.
O aluno acredita que o vetor só consegue acessar posições pares, provavelmente por confundir indexação com alguma regra de paridade inexistente.
Vetores armazenam elementos em memória contígua permitindo cálculo do endereço por aritmética de índice, provendo acesso direto O(1); lista ligada requer percorrer nós O(n).
O aluno supõe que vetor e lista ligada são equivalentes em qualquer operação, ignorando que a lista exige percorrer nós até o índice desejado.
Por que engana: Confundir o tempo de acesso em listas ligadas, acreditando que elas oferecem acesso direto em O(1) como os vetores.
O aluno associa a lista ligada à ideia de acesso rápido, talvez por confundir a facilidade de inserir e remover nós com a facilidade de acessar um elemento pela posição.
Raio-X da questão
estruturas de dados
avaliacao
acesso a estruturas de dados · complexidade de algoritmos
Revisar as diferenças entre vetor e lista ligada.
Confundir o tempo de acesso em listas ligadas, acreditando que elas oferecem acesso direto em O(1) como os vetores.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Entre uma lista ligada e um vetor (array), qual estrutura permite acesso direto ao elemento de índice i em tempo O(1) e…
- Em um algoritmo que insere frequentemente novos elementos no meio de uma sequência, qual estrutura de dados é mais…
- Qual estrutura de dados é mais adequada para armazenar uma lista de elementos que precisam ser acessados por sua…
- Identifique a estrutura de dados que permite armazenar uma lista de itens de forma sequencial, onde cada item pode ser…
- Qual estrutura de dados é mais adequada para armazenar uma lista de itens em que a ordem é importante e pode ser…
- Em um algoritmo que percorre um vetor, qual tipo de dado é mais adequado para armazenar o índice de acesso e por quê?
🔎 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