Sobre o algoritmo de pilha utilizando listas encadeadas, é incorreto afirmar que:
c) percorrer a lista tem complexidade
.
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.
d) a inserção é sempre no início.