Sobre o algoritmo de pilha utilizando listas encadeadas, é incorreto afirmar que:
c) percorrer a lista tem complexidade .

Passo 1

Então, você está trabalhando com um exercício sobre o algoritmo de pilha usando listas encadeadas. A questão apresenta afirmações e pergunta qual delas está INCORRETA. A afirmação que vamos analisar aqui é a opção c): "percorrer a lista tem complexidade ". Para resolver isso, vamos entender o que significa complexidade e como ela se aplica ao percorrer uma lista encadeada.

Passo 2

Primeiro, vamos falar sobre o que é uma pilha utilizando listas encadeadas. Uma pilha é uma estrutura de dados que segue o princípio LIFO (Last In, First Out), ou seja, o último elemento inserido é o primeiro a ser retirado. Quando implementamos uma pilha com uma lista encadeada, cada elemento aponta para o próximo, formando uma cadeia.

Passo 3

Agora, sobre a complexidade . Em ciência da computação, a notação (grande-O) descreve a complexidade de tempo de um algoritmo em função do tamanho da entrada, . significa que o tempo de execução cresce linearmente com o tamanho da entrada.

Passo 4

Percorrer uma lista encadeada significa visitar cada elemento um por um, desde o início até o fim da lista. Como você precisa acessar cada elemento individualmente, o tempo necessário para percorrer toda a lista cresce proporcionalmente ao número de elementos presentes, ou seja, é linear.

Passo 5

Então, afirmar que "percorrer a lista tem complexidade " está correto, porque realmente leva tempo proporcional ao número de elementos na lista.

Resposta

A afirmação c) está CORRETA, pois percorrer uma lista encadeada realmente possui complexidade .

Exercícios relacionados

Escreva um programa em Python que cria um dicionário a partir de uma string digitada. As chaves do dicionário devem ser as letras da string e os valores de tais chaves a quantidade de ocorrências das mesmas na palavra.
Escreva um programa que a partir de uma lista1 e uma lista2 (ambos de tamanho ) cria um dicionário onde as chaves são os itens da lista1 e os valores são os itens da lista2.
a) Uma empresa aérea quer fazer o controle de reservas de voos de forma automatizada. Há vários voos e cada um deles tem certo número de lugares disponíveis. Os usuários fazem a reserva por telefone, fornecendo seus nomes. As pilhas devem ser usadas para controlar a lista de passageiros de cada voo, ordenados pelo nome.
Sobre o algoritmo de pilha utilizando listas encadeadas, é incorreto afirmar que:
d) a inserção é sempre no início.