Considere uma fila (FIFO) implementada com lista ligada que mantém ponteiros para cabeça e cauda. Qual é a…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Identificar o comportamento dos algoritmos no que diz respeito ao consumo de recursos como tempo de execução, espaço de memória e energia, entre outros.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Considere uma fila (FIFO) implementada com lista ligada que mantém ponteiros para cabeça e cauda. Qual é a complexidade temporal das operações enqueue e dequeue, em notação assintótica?
- A) enqueue: O(1); dequeue: O(1).
- B) enqueue: O(log n); dequeue: O(log n).
- C) enqueue: O(n); dequeue: O(n).
- D) enqueue: O(1); dequeue: O(n).
- E) enqueue: O(n); dequeue: O(1).
✅ Resposta correta: alternativa A
Resolução passo a passo
- A fila (FIFO) é implementada com lista ligada que mantém ponteiros para a cabeça (head) e para a cauda (tail).
- No enqueue, o novo nó é inserido após a cauda. Como já temos o ponteiro para a cauda, basta ligar o novo nó ao final, atualizar o ponteiro da cauda e, se a fila estava vazia, ajustar a cabeça. Isso são poucas operações de ponteiro, independentes do número n de elementos: O(1).
- No dequeue, removemos o nó apontado pela cabeça e avançamos a cabeça para o próximo nó. Não é preciso percorrer a lista, pois o elemento a sair já está na cabeça: O(1).
- Logo, a alternativa correta é a A, com enqueue O(1) e dequeue O(1). O gabarito oficial está correto.
- Por que as outras estão erradas: B supõe busca em árvore balanceada, o que não ocorre em lista ligada com ponteiros de cabeça e cauda; C e D e E atribuem O(n) a uma operação que, com os ponteiros mantidos, não exige percorrer a lista.
💡 Dica: Relacione os ponteiros de cabeça e cauda às operações de inserção e remoção na fila.
Alternativa por alternativa
Com ponteiros para cabeça e cauda, inserir no fim (enqueue) e remover no início (dequeue) exigem atualizações constantes nos ponteiros, sem percorrer a lista.
Assume que filas precisam de estrutura ordenada ou balanceada, como em árvores, e aplica o custo logarítmico de busca a operações que não fazem busca.
Imagina que inserir e remover exigem percorrer a lista até a posição final ou inicial, ignorando que os ponteiros de cabeça e cauda evitam essa travessia.
Acredita que enqueue é rápido por acessar a cauda diretamente, mas que dequeue precisa percorrer a lista para achar o penúltimo nó ou o nó anterior, o que não acontece na remoção pela cabeça.
Por que engana: Confundir a fila com uma lista ligada sem ponteiro para a cauda e concluir que inserir no fim exige percorrer todos os elementos.
Pensa que adicionar ao fim exige percorrer toda a lista para encontrar a cauda, esquecendo que o ponteiro de cauda já está mantido.
Raio-X da questão
Complexidade de operações em filas
avaliacao
Estruturas de dados listas ligadas · Notação assintótica Big O
Revise como os ponteiros de cabeça e cauda permitem inserir no fim e remover do início em tempo constante.
Confundir a fila com uma lista ligada sem ponteiro para a cauda e concluir que inserir no fim exige percorrer todos os elementos.
ciencia_tecnologia
tomada_decisao
abstrato
Questões parecidas com resolução
- Em um projeto de monitoramento de rios, uma boia computacional organiza leituras de sensores antes de enviá-las por…
- Uma biblioteca escolar recebeu caixas de livros doados para uma feira de troca. Para registrar os exemplares, a equipe…
- Um centro cultural público oferece inscrições on-line para atividades com critérios variados. Na oficina de teatro…
- Uma escola está testando dois protótipos de aplicativo para que estudantes consultem mudanças de sala, horários e…
- Uma secretaria municipal de educação está digitalizando pedidos de transporte escolar e de atendimento em contraturno…
- — O cartaz não pode sair duas vezes, pois a feira começa em uma hora — alertou a coordenadora do centro cultural. No…
🔎 Procurar outra questão
Procure no banco do GeraProva pelo tema ou por um trecho do enunciado. Cada questão já vem com resolução comentada e a análise de cada alternativa.
Professor: monte a prova com questões como esta, com gabarito e folha de respostas, em 30 segundos. Ver planos · Blog