Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — CIAAR 2026
Algoritmos e Estrutura de Dados›Estrutura de Dados
Código
gp019095
Banca
CIAAR
Órgão
CIAAR
Ano
2026
Cargo
Oficial de Apoio - Análise de Sistemas
Sobre as estruturas de listas ligadas, informe verdadeiro (V) ou falso (F) para as assertivas abaixo e, em seguida, marque a opção que apresenta a sequência correta.( ) Em uma lista duplamente ligada, cada nó possui um objeto, uma chave e dois ponteiros: next e prev.( ) Para buscar um elemento com uma chave k em uma lista ligada de n elementos, o tempo de execução no pior caso é O(1).( ) Em uma lista circular, o ponteiro next do último elemento aponta para o primeiro elemento da lista.( ) A inserção de um novo elemento no início de uma lista ligada com sentinela consome tempo constante O(1).
A(V); (F); (V); (V).
B(V); (V); (F); (F).
C(F); (F); (V); (V).
D(V); (F); (F); (V).
Revelar gabarito e comentário▾
GabaritoA — (V); (F); (V); (V).
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”.
Listas ligadas – assertivas sobre conceitos fundamentais
Gabarito: alternativa A — sequência V, F, V, V. Apenas a segunda assertiva está incorreta: a busca em lista ligada é O(n), não O(1). As demais descrevem corretamente as estruturas.
A banca testa conceitos básicos de listas ligadas: tipos (simples, dupla, circular) e complexidade de operações. Analisemos cada assertiva:
1ª assertiva — ✅ Verdadeira
Em uma lista duplamente ligada, cada nó possui um objeto, uma chave e dois ponteiros: next e prev.
Descrição padrão de um nó de lista duplamente ligada. Cada nó armazena um dado (objeto/chave) e dois ponteiros que ligam ao nó anterior (prev) e ao próximo (next). Assertiva correta.
2ª assertiva — ❌ Falsa
Para buscar um elemento com uma chave k em uma lista ligada de n elementos, o tempo de execução no pior caso é O(1).
Em uma lista ligada simples ou dupla, não há acesso aleatório. Para encontrar um elemento, é necessário percorrer os nós sequencialmente. No pior caso (elemento não existe ou está no fim), todos os n nós são visitados, resultando em complexidade O(n). Tempo constante O(1) é típico de acesso direto por índice (como em vetores), não de busca em listas ligadas.
Assertiva
V/F
Justificativa
Em uma lista duplamente ligada, cada nó possui um objeto, uma chave e dois ponteiros: next e prev.
V
Descrição padrão de nó de lista duplamente ligada: dado + ponteiros para anterior e próximo.
Para buscar um elemento com uma chave k em uma lista ligada de n elementos, o tempo de execução no pior caso é O(1).
F
Busca em lista ligada requer percurso sequencial; pior caso é O(n), não O(1).
Em uma lista circular, o ponteiro next do último elemento aponta para o primeiro elemento da lista.
V
Característica definidora de lista circular: último nó aponta para o primeiro, formando ciclo.
A inserção de um novo elemento no início de uma lista ligada com sentinela consome tempo constante O(1).
V
Com sentinela, inserir no início requer apenas ajuste de ponteiros, independente do tamanho da lista.
1Lista duplamente ligada
2Busca O(1)
3Lista circular
4Inserção com sentinela
LEVEL · soulevel.com.br
NÃO CAIA NESSA!
A banca troca a complexidade da busca em lista ligada (O(n)) por O(1). Cuidado: confundir com acesso por índice de vetor é o erro mais comum. Na lista, a busca sempre requer percorrer os nós.
3ª assertiva — ✅ Verdadeira
Em uma lista circular, o ponteiro next do último elemento aponta para o primeiro elemento da lista.
Exato. Essa é a característica que define uma lista circular: o último nó não aponta para NULL, mas sim para o primeiro, formando um ciclo. Assertiva correta.
4ª assertiva — ✅ Verdadeira
A inserção de um novo elemento no início de uma lista ligada com sentinela consome tempo constante O(1).
Uma lista com sentinela (nó cabeça fictício) simplifica as operações. Para inserir no início, basta criar um novo nó, ajustar seu next para o primeiro elemento real e atualizar o next da sentinela para o novo nó – tudo em O(1), independentemente do tamanho da lista. Assertiva correta.
💡 Dica: Decore as complexidades típicas das listas ligadas: busca e remoção por valor = O(n); inserção/remoção no início (com sentinela) = O(1); inserção/remoção no fim (sem referência) = O(n). Compare com arrays: acesso por índice = O(1); inserção/remoção no meio = O(n).
Conclusão: Sequência correta: V – F – V – V, correspondente à alternativa A.