Questão 51 — Listas Encadeadas (Algoritmos e Estruturas de Dados) — Escola de Formação Complementar do Exército (EsFCEx) · Exército Brasileiro 2019

Algoritmos e Estruturas de Dados Listas Encadeadas

Escola de Formação Complementar do Exército (EsFCEx) 2019

Exército Brasileiro · Oficial do Quadro Complementar (CFO/QC) — Informática · Caderno Tipo A

Gabarito disponível

Considere a implementação de uma lista simples encadeada e não ordenada. Suponha que tenha sua representação apenas com um ponteiro na cabeça. Dada a representação, analise os itens a seguir, em relação às operações podem ser implementadas no tempo O(1):

I. inserção no início da lista encadeada;

II. inserção no final da lista encadeada;

III. exclusão do nó inicial da lista encadeada;

IV. exclusão do último nó da lista encadeada.

Assinale

Selecione uma alternativa A) se apenas os itens I e III estiverem corretos. B) se apenas os itens I e II estiverem corretos. C) se apenas os itens I, II e III estiverem corretos. D) se apenas os itens I, II e IV estiverem corretos. E) se apenas os itens II, III e IV estiverem corretos.

Resolução comentada

Só inserção e exclusão no início são O(1) numa lista simples com apenas o ponteiro da cabeça.

Com apenas o ponteiro da cabeça, inserir ou remover no início exige apenas ajustar a cabeça: O(1). Inserir ou excluir no final exige percorrer a lista até o último nó, o que custa O(n).

Análise das alternativas

II) Inserção no final: O(n), pois sem ponteiro para a cauda é preciso percorrer a lista. IV) Exclusão do último nó: O(n), pois é preciso achar o penúltimo. Portanto só I e III estão corretas.

Referência: Cormen et al.; Ziviani – Listas encadeadas.

Resolução comentada do VaiConcursos.