Na indústria, compare duas implementações para gerenciar uma fila de pedidos: usar uma lista encadeada versus…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Identificar as principais formas de organizar e representar a informação de maneira estruturada (matrizes, registros, listas e grafos) ou não estruturada (números, palavras, valores verdade).
Fonte: Base Nacional Comum Curricular (MEC).Questão
Na indústria, compare duas implementações para gerenciar uma fila de pedidos: usar uma lista encadeada versus um vetor. Em um experimento computacional simples com 1000 operações de inserção no início, qual afirmação descreve melhor o comportamento de tempo?
- A) Ambas as implementações têm O(1) para inserção no início.
- B) A lista encadeada oferece inserção no início em tempo constante, enquanto o vetor requer deslocamento de elementos, resultando em O(n).
- C) Ambas precisam de O(log n) para inserção no início.
- D) A lista encadeada é mais lenta para busca do que o vetor, mas mais rápida na inserção no início; ambos têm O(n).
- E) O desempenho depende do compilador e não do tipo de estrutura de dados utilizado.
✅ Resposta correta: alternativa B
Resolução passo a passo
- A questão compara o custo de inserir um elemento no início de uma lista encadeada e de um vetor, em 1000 operações. Passo 2: Na lista encadeada, inserir no início basta criar um nó novo e ajustar o ponteiro da cabeça para ele; o número de passos é fixo, independente de quantos elementos já existem, logo o tempo é constante, O(1). Passo 3: No vetor, os elementos ocupam posições contíguas na memória; para abrir espaço na posição 0, cada um dos n elementos precisa ser deslocado uma posição à direita, o que custa O(n) por inserção. Passo 4: Portanto, a alternativa B descreve corretamente o comportamento: tempo constante na lista e tempo linear no vetor. Passo 5: A alternativa A está errada porque o vetor exige deslocamento de elementos, não sendo O(1) nesse caso. Passo 6: A alternativa C está errada porque O(log n) não corresponde a nenhuma das duas estruturas nessa operação; é típico de busca binária ou heaps. Passo 7: A alternativa D está errada porque, na inserção no início, a lista encadeada é O(1), e não O(n); a parte sobre busca é verdadeira, mas não resolve a comparação pedida. Passo 8: A alternativa E está errada porque a diferença é teórica e vem da estrutura de dados (deslocamento versus ponteiros), não do compilador. Passo 9: Conclusão: o gabarito oficial B está correto.
💡 Dica: Analise as características de listas encadeadas e vetores em relação a inserções.
Alternativa por alternativa
O aluno supõe que qualquer inserção, em qualquer estrutura, é uma operação instantânea, esquecendo que o vetor precisa deslocar os demais elementos para abrir espaço no início.
Por que engana: Confundir o custo de insercao no inicio entre lista encadeada e vetor, assumindo que ambos sao O(1).
Correta: descreve a vantagem da lista encadeada para inserção no início, com O(1); o vetor tem custo O(n).
O aluno associa estruturas de dados a logaritmo por reconhecer O(log n) em busca binária ou heaps e aplica essa complexidade indevidamente à inserção no início de lista ou vetor.
O aluno acerta que a busca é mais lenta na lista encadeada, mas conclui erradamente que a inserção no início também é O(n) na lista, quando nela basta ajustar o ponteiro da cabeça.
O aluno acredita que o desempenho observado em um experimento depende apenas de fatores externos, como o compilador ou o hardware, e não da própria organização dos dados.
Raio-X da questão
gerenciamento de filas
avaliacao
complexidade de algoritmos · estruturas de dados basicas
Revisar as diferenças de desempenho entre listas encadeadas e vetores.
Confundir o custo de insercao no inicio entre lista encadeada e vetor, assumindo que ambos sao O(1).
ciencia_tecnologia
pensamento_critico
cientifico
Questões parecidas com resolução
- Em um algoritmo que insere frequentemente novos elementos no meio de uma sequência, qual estrutura de dados é mais…
- Durante uma prática de laboratório, você vai comparar o desempenho de inserção entre vetor (lista) e lista ligada. Quais…
- Um professor propõe um experimento simples para comparar estruturas de dados. Ele gera 100 registros de estudantes, cada…
- Em um experimento rápido no laboratório de informática, você quer observar como o tempo de execução de um algoritmo de…
- Entre uma lista ligada e um vetor (array), qual estrutura permite acesso direto ao elemento de índice i em tempo O(1) e…
- Interpretando dados de desempenho, suponha que você está avaliando o tempo médio de busca para uma lista de 1000 nomes…
Todas as questões de Organização e representação da informaçã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