Questão Q803074

Sobre o algoritmo de pilha utilizando listas encadeadas, é incorreto afirmar que:

Alternativas

a remoção é sempre no final da lista.

a complexidade para inserir no final é O(1).

percorrer a lista tem complexidade O(n).

a inserção é sempre no início.

Comentários

O gabarito é a letra D.

No conceito de pilha, a inserção é sempre no final da lista, assim como a remoção.
Numa lista com n itens, temos as seguintes complexidades de tempo no pior caso:

Inserção:

início O(1)

Meio O(n)

fim O(n) (O(1) quando se tem uma referência pro fim da lista)

remoção:

início O(1)

Meio O(n)

fim O(n) (O(1) quando se tem uma referência pro fim da lista)

https://pt.wikipedia.org/wiki/Lista_ligada#N.C3.ADveis_de_complexidade
Gabarito: D.

Quando se fala em pilha, normalmente se utiliza o termo topo, em vez de início ou fim, como em fila.

De qualquer forma, o topo é considerado o final da pilha, que é onde ocorrem as operações de inserção (PUSH) e retirada (POP), assim como leitura (TOP) e substituição (PULL).
Força Guerreiro!!!!!!

SóProvas