Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — IDECAN 2025
Algoritmos e Estrutura de Dados›Estrutura de Dados
Código
qg523012
Banca
IDECAN
Órgão
IF-PA
Ano
2025
Nível
Superior
Cargo
Professor - Informática
Durante a implementação de uma estrutura de lista para representar uma fila de impressão com inserções frequentes no final e remoções no início, um professor do EBTT propôs analisar qual tipo de lista e estratégia de alocação ofereceria o melhor desempenho. Considerando os tipos de listas e suas implicações no tempo de execução das operações básicas, é correto afirmar que:
Aa lista circular encadeada com a locação dinâmica é ineficiente para inserção no final, pois requer o reposicionamento de todos os nós.
Bo uso de uma lista encadeada com ponteiro para o último elemento permite inserção no final em tempo constante, otimizando a operação de enfileiramento.
Ca implementação com lista duplamente encadeada e alocação sequencial garante menor uso de memória e maior performance em todas as operações.
Da utilização de uma lista circular com vetor fixo permite remoção eficiente no início, mesmo sem controle de índices de cabeça e cauda.
Eo uso de lista simplesmente encadeada com alocação sequencial reduz o tempo de acesso aleatório a elementos intermediários da lista.
Revelar gabarito e comentário▾
GabaritoB — o uso de uma lista encadeada com ponteiro para o último elemento permite inserção no final em tempo constante, otimizando a operação de enfileiramento.
Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.
Estruturas de dados para filas de impressão
Gabarito: letra B. Uma lista encadeada simples que mantém um ponteiro para o último elemento permite inserir no final da fila em tempo constante O(1), o que otimiza a operação de enfileiramento (enqueue). As demais alternativas misturam conceitos de alocação (sequencial × dinâmica) e características estruturais (simples, dupla, circular) de forma incorreta ou contraditória.
A questão explora o conhecimento sobre implementações de listas e seus impactos no desempenho das operações básicas de uma fila: inserção no final (enqueue) e remoção no início (dequeue).
Alternativa
Afirmação
Análise
Conclusão
A
Lista circular encadeada com alocação dinâmica é ineficiente para inserção no final, pois requer reposicionamento de todos os nós.
Falso. Com ponteiro para o último nó, a inserção é O(1), ajustando apenas ponteiros.
❌ Incorreta
B
Lista encadeada com ponteiro para o último elemento permite inserção no final em tempo constante, otimizando o enfileiramento.
Verdadeiro. Basta atualizar o último nó e o ponteiro de cauda em O(1).
✅ Correta (Gabarito)
C
Lista duplamente encadeada com alocação sequencial garante menor uso de memória e maior performance em todas as operações.
Contraditório: encadeamento usa alocação dinâmica, não sequencial. Duplo encadeamento consome mais memória (2 ponteiros/nó).
❌ Incorreta
D
Lista circular com vetor fixo permite remoção eficiente no início, mesmo sem controle de índices de cabeça e cauda.
Falso. Sem controle de índices, a remoção no início em vetor fixo exige deslocamento de todos os elementos (O(n)).
❌ Incorreta
E
Lista simplesmente encadeada com alocação sequencial reduz o tempo de acesso aleatório a elementos intermediários.
Falso. Alocação sequencial (vetor) permite acesso O(1) a qualquer posição; encadeamento não melhora isso.
❌ Incorreta
Listas para fila (enqueue/dequeue)
1Alocação dinâmica
Simples c/ ponteiro final
Inserção final O(1)
Remoção início O(1)
Duplamente encadeada
Mais memória (2 ponteiros)
Inserção/remoção meio O(n)
Circular c/ ponteiro final
Inserção final O(1)
2Alocação sequencial (vetor)
Circular c/ índices cabeça/cauda
Remoção início O(1)
Sem índices
Remoção início O(n)
LEVEL · soulevel.com.br
Alternativa A — ❌ Incorreta
Afirma que a lista circular encadeada com alocação dinâmica é ineficiente para inserção no final, pois exigiria reposicionar todos os nós. Isso é falso. Em uma lista circular encadeada (alocação dinâmica), se houver um ponteiro para o último nó, a inserção no final é feita em O(1), ajustando apenas os ponteiros do novo nó e do último nó. Não há reposicionamento de nós. O erro está em generalizar uma suposta ineficiência.
Alternativa B — ✅ Correta ⟵ GABARITO
O uso de uma lista encadeada com ponteiro para o último elemento (também chamada de "fila encadeada") permite inserir um novo nó no final em tempo constante O(1). Basta fazer o último nó apontar para o novo nó e atualizar o ponteiro de cauda. É exatamente a estratégia adequada para otimizar o enfileiramento em uma fila.
Alternativa C — ❌ Incorreta
A alternativa menciona "lista duplamente encadeada e alocação sequencial". Há uma contradição: listas encadeadas (simples ou duplas) utilizam alocação dinâmica (nós ligados por ponteiros), enquanto alocação sequencial é característica de vetores (arrays). Além disso, uma lista duplamente encadeada consome mais memória (dois ponteiros por nó) do que uma lista simples, e não garante "maior performance em todas as operações"; por exemplo, inserção/remoção no meio pode ser O(n) mesmo com encadeamento duplo.
Alternativa D — ❌ Incorreta
A afirmação diz que uma lista circular com vetor fixo (alocação sequencial) permite remoção eficiente no início "mesmo sem controle de índices de cabeça e cauda". Sem esses índices, a remoção do primeiro elemento exigiria deslocar todos os demais elementos para a esquerda, resultando em O(n). A implementação eficiente de fila circular com vetor usa exatamente os índices head e tail (ou front e rear) para evitar deslocamentos.
Alternativa E — ❌ Incorreta
Mistura conceitos: "lista simplesmente encadeada com alocação sequencial" é uma contradição (encadeada = alocação dinâmica; sequencial = vetor). Além disso, listas encadeadas não oferecem acesso aleatório eficiente – o acesso a um elemento intermediário requer percorrer a lista desde o início, em O(n). A afirmação de que reduz o tempo de acesso aleatório é falsa; quem reduz é um vetor (acesso O(1)).
PEGA ESSA DICA!
Para provas de estruturas de dados, lembre-se: alocação sequencial = vetor (acesso O(1), inserção/remoção no início O(n)); alocação dinâmica = lista encadeada (inserção/remoção O(1) se posição conhecida, acesso O(n)). Uma fila pode ser implementada com vetor circular (com índices head/tail) ou com lista encadeada simples + ponteiro para o último. Ambas dão operações O(1) para enqueue e dequeue.