Questão FC266047
Considere uma estrutura de dados de uma Lista Encadeada Simples que é composta por uma cabeça e uma cauda, onde a cabeça aponta para o primeiro nó e a cauda aponta para o último nó
Algoritmos e Lógica de Programação
IDECAN · 2024
Considere uma estrutura de dados de uma Lista Encadeada Simples que é composta por uma cabeça e uma cauda, onde a cabeça aponta para o primeiro nó e a cauda aponta para o último nó da lista. Nessa estrutura, cada nó é composto por um valor inteiro e apenas um ponteiro para o próximo nó da lista. Marque a alternativa verdadeira sobre as características dessa estrutura de dados.
- Para alterar o tamanho dessa lista é necessário copiar todos seus elementos para uma nova lista.
- Como não possui um nó seguinte para indicar, o último elemento da lista deve apontar para si.
- As operações de remoção da cabeça e remoção da cauda possuem o mesmo custo computacional para uma lista com mais de um nó.
- A inserção de novos elementos no início ou no final da lista é realizada com custo computacional constante.
Mostrar resposta e comentário
Gabarito
D
Comentário do professor
A afirmação é verdadeira porque, numa lista encadeada que mantém ponteiros para a cabeça e para a cauda, inserir no início ou no fim exige um número fixo de operações independentemente do tamanho da lista.
Para inserir no início: aloca-se um novo nó, define-se novo->prox = cabeça e atualiza-se cabeça = novo. Para inserir no fim: aloca-se o nó, faz-se cauda->prox = novo e atualiza-se cauda = novo. Em lista vazia, ambos os ponteiros recebem o novo nó.
Essas ações envolvem apenas algumas atribuições de ponteiro e, portanto, têm custo computacional constante, representado por \(O(1)\).
Conteúdo do catálogo FC Concursos · Atualizado em