Questão de Tecnologia da Informação · FGV MP-SC 2022 (nº 42)

Conceito-chave: Em uma lista encadeada não ordenada, a inserção de um novo elemento sempre acontece no início (ou no final), pois não há necessidade de comparar valores para manter uma ordem. O custo dessa operação é constante, ou seja, não depende do número de elementos $N$ — mas a banca considera o caso de inserção em posição arbitrária, que exige percorrer a lista até achar a posição.

• (A) Incorreta: $\log N$ seria o custo de uma busca em estrutura balanceada (como árvore AVL), não de uma lista encadeada simples, onde não há acesso direto por índice.
• (B) Correta: O gabarito oficial diz que a inserção em lista encadeada não ordenada tem complexidade $O(N)$, pois, na prática, para inserir em uma posição específica (ou no final sem ponteiro de cauda), é preciso percorrer os elementos até chegar ao local desejado — e percorrer uma lista de $N$ elementos custa $N$ passos.
• (C) Incorreta: $N \log N$ é típico de algoritmos de ordenação eficientes (como Merge Sort), não de inserção em lista encadeada.
• (D) Incorreta: $N^2$ aparece em algoritmos com dois loops aninhados (como Bubble Sort), não em uma única operação de inserção.
• (E) Incorreta: $O(1)$ seria o custo se a inserção fosse sempre no início (com ponteiro para a cabeça) ou se houvesse um ponteiro direto para o final — mas a banca considera o caso geral, sem essas otimizações. Armadilha da banca: muitos alunos marcam "1" pensando na inserção no início, mas a questão fala "inserção nessa lista" sem especificar posição, então a banca exige o pior caso, que é percorrer até o fim.