Entre uma lista ligada e um vetor (array), qual estrutura permite acesso direto ao elemento de índice i em…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Criar soluções de problemas para os quais seja adequado o uso de registros e matrizes unidimensionais para descrever suas informações e automatizá-las usando uma linguagem de programação.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Entre uma lista ligada e um vetor (array), qual estrutura permite acesso direto ao elemento de índice i em tempo O(1) e por que a outra exige tempo O(i) para acessar o mesmo índice?
- A) Vetor (array): acesso direto por índice em O(1).
- B) Lista ligada acessa índice i em O(1); array exige O(i) por realocação.
- C) Lista ligada acessa índice i em O(log n) usando ponteiros binários.
- D) Ambas acessam índice i em O(i) porque mesmo arrays precisam iterar elementos.
- E) Ambas estruturas acessam índice i em O(1) sempre.
✅ Resposta correta: alternativa A
Resolução passo a passo
- Em um vetor (array), os elementos ficam armazenados em posições de memória contíguas e de tamanho fixo. Assim, o endereço do elemento de índice i é calculado diretamente pela fórmula endereço_base + i * tamanho_do_elemento, o que leva tempo constante O(1), independentemente de i.
- Em uma lista ligada, cada nó guarda o dado e um ponteiro para o próximo nó, e não há cálculo de endereço por posição. Para chegar ao índice i é preciso começar pelo primeiro nó e seguir i ponteiros, um de cada vez. Por isso o acesso exige tempo O(i), que no pior caso é O(n).
- Conclusão: a alternativa correta é a A, pois ela afirma exatamente que o vetor acessa diretamente por índice em O(1). O enunciado pergunta qual estrutura permite acesso direto e por que a outra exige O(i); a alternativa A responde a primeira parte corretamente, e a segunda parte é o contraste implícito com a lista ligada descrito no Passo 2.
- Por que as outras estão erradas:
- B) Inverte as estruturas: é a lista ligada que exige percorrer nós, e o array não precisa de realocação para acessar um índice.
- C) Não existe busca binária por ponteiros na lista ligada comum; o acesso continua linear, O(i).
- D) Está errada porque arrays não precisam iterar elementos para acessar um índice, pois o endereço é calculado diretamente.
- E) Está errada porque a lista ligada não acessa índice em O(1); esse acesso exige percorrer os nós.
- Observação: o gabarito oficial (A) coincide com a resolução feita por conta própria.
💡 Dica: Compare as características de acesso das duas estruturas.
Alternativa por alternativa
Arrays armazenam elementos em memória contígua e o endereço do índice i é calculado diretamente; listas ligadas armazenam nós encadeados exigindo percorrer i ponteiros até o nó desejado, o que leva O(i).
O aluno inverteu o comportamento das estruturas, achando que a lista ligada acessa por índice em tempo constante e que o array depende de realocação para isso. Realocação ocorre na inserção de elementos em arrays dinâmicos, não no acesso por índice.
Por que engana: Confundir o tempo de acesso de uma lista ligada com o de um vetor, acreditando que ambos têm acesso O(1).
O aluno supôs que a lista ligada poderia usar uma estrutura de busca binária baseada em ponteiros, o que confunde a lista ligada com árvores binárias. A lista ligada simples não permite busca logarítmica, pois só há acesso sequencial.
O aluno imaginou que o array também precisa percorrer elementos até o índice, aplicando à estrutura contígua a lógica sequencial da lista. Não percebeu que o endereço do índice i é calculado diretamente pela aritmética de endereços.
O aluno assumiu que qualquer estrutura de dados acessa qualquer índice em tempo constante, sem distinguir armazenamento contíguo de armazenamento encadeado. Esquece que na lista ligada é preciso seguir os ponteiros de nó em nó.
Raio-X da questão
acesso a elementos em estruturas
avaliacao
estruturas de dados · complexidade de algoritmos
Revisar as diferenças entre listas ligadas e vetores.
Confundir o tempo de acesso de uma lista ligada com o de um vetor, acreditando que ambos têm acesso O(1).
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Para um algoritmo que exige acesso direto ao elemento de índice i em tempo O(1), qual estrutura de dados é mais…
- Qual estrutura de dados é mais adequada para armazenar uma lista de elementos que precisam ser acessados por sua…
- Em um algoritmo que insere frequentemente novos elementos no meio de uma sequência, qual estrutura de dados é mais…
- Identifique a estrutura de dados que permite armazenar uma lista de itens de forma sequencial, onde cada item pode ser…
- Na indústria, compare duas implementações para gerenciar uma fila de pedidos: usar uma lista encadeada versus um vetor…
- Qual estrutura de dados é mais adequada para armazenar uma lista de itens em que a ordem é importante e pode ser…
Todas as questões de Programação - Programação usando registros e matrizes
🔎 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