Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — COPESE - UFPI 2024
Algoritmos e Estrutura de Dados›Estrutura de Dados
Código
qg107582
Banca
COPESE - UFPI
Órgão
UFPI
Ano
2024
Nível
Superior
Cargo
COPESE - - Analista de Tecnologia da Informação: Infraestrutura
Julgue cada afirmativa abaixo sobre listas ordenadas, listas encadeadas, pilhas e filas como verdadeira (V) ou falsa (F). Em seguida, assinale a opção que corresponde à sequência CORRETA:( ) Em uma lista encadeada simples, a inserção de um novo elemento no final da lista sempre requer tempo constante O(1).( ) Em uma pilha, a operação de remoção de um elemento segue o princípio FIFO (First In, First Out).( ) Em uma fila, a operação de inserção e remoção de elementos pode ser realizada em qualquer posição da estrutura, desde que seja mantida a ordenação.( ) Em uma lista ordenada, a inserção de um novo elemento sempre ocorre em tempo O(1), independentemente de sua posição.( ) Em uma fila, a operação de inserção ocorre no final da estrutura, enquanto a remoção ocorre no início, seguindo o princípio FIFO.
AV – F – V – F – F
BF – F – V – V – F
CF – F – F – F – V
DF – V – F – F – V
EV – V – F – V – F
Revelar gabarito e comentário▾
GabaritoC — F – F – F – F – 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, Pilhas e Filas: conceitos fundamentais
Gabarito: letra C (F–F–F–F–V). A única afirmativa verdadeira é a quinta, que descreve corretamente o funcionamento de uma fila (inserção ao final, remoção no início, princípio FIFO). As demais são falsas por confundirem conceitos essenciais: inserção no final de lista encadeada simples é O(n) sem referência à cauda; pilha segue LIFO, não FIFO; fila não permite inserção/remoção em qualquer posição; lista ordenada requer busca para inserção, resultando em O(n).
Afirmativa
V/F
Justificativa
1ª: Inserção no final de lista encadeada simples é sempre O(1)
F
Sem ponteiro para o último nó (tail), é necessário percorrer toda a lista (O(n)). Mesmo com tail, o termo "sempre" torna a afirmação incorreta, pois há implementações sem tail.
2ª: Pilha segue princípio FIFO
F
Pilhas operam pelo princípio LIFO (Last In, First Out). FIFO é princípio de filas.
3ª: Fila permite inserção/remoção em qualquer posição
F
Filas são estruturas FIFO restritas: inserções apenas no final (enqueue) e remoções apenas no início (dequeue).
4ª: Inserção em lista ordenada é sempre O(1)
F
Para manter a ordem, é necessário encontrar o local correto de inserção, exigindo percorrer a lista (O(n) no pior caso).
5ª: Fila insere no final e remove no início (FIFO)
V
Definição clássica de fila: inserção ao final, remoção no início, seguindo o princípio FIFO.
1ª afirmativa — ❌ Falsa
"Em uma lista encadeada simples, a inserção de um novo elemento no final da lista sempre requer tempo constante O(1)." Em uma lista encadeada simples sem um ponteiro para o último nó (tail), é necessário percorrer toda a lista para encontrar o final, resultando em O(n). Mesmo com tail, o uso do termo "sempre" torna a afirmação incorreta, pois há implementações sem tail. Portanto, falsa.
2ª afirmativa — ❌ Falsa
"Em uma pilha, a operação de remoção de um elemento segue o princípio FIFO (First In, First Out)." Pilhas operam pelo princípio LIFO (Last In, First Out). A remoção retira o elemento inserido mais recentemente. FIFO é o princípio de filas. Afirmação troca os conceitos.
3ª afirmativa — ❌ Falsa
"Em uma fila, a operação de inserção e remoção de elementos pode ser realizada em qualquer posição da estrutura, desde que seja mantida a ordenação." Filas são estruturas FIFO restritas: inserções ocorrem apenas no final (enqueue) e remoções apenas no início (dequeue). Não é permitido inserir ou remover em posições arbitrárias, independentemente de ordenação.
4ª afirmativa — ❌ Falsa
"Em uma lista ordenada, a inserção de um novo elemento sempre ocorre em tempo O(1), independentemente de sua posição." Para manter a ordem, é necessário encontrar o local correto de inserção, o que exige percorrer a lista (ou usar busca binária em um array, mas não é o caso típico de lista ordenada). A complexidade no pior caso é O(n), não O(1).
5ª afirmativa — ✅ Verdadeira
"Em uma fila, a operação de inserção ocorre no final da estrutura, enquanto a remoção ocorre no início, seguindo o princípio FIFO." Essa é a definição clássica de fila: enqueue ao final, dequeue no início, comportamento FIFO. Afirmativa correta.
Conclusão: Sequência correta: F, F, F, F, V → alternativa C.
NÃO CAIA NESSA!
A banca explora as confusões clássicas entre FIFO e LIFO (afirmativas 2 e 5) e a generalização de complexidades (afirmativas 1 e 4). Lembre-se: pilha = LIFO; fila = FIFO; inserção no final de lista encadeada simples é O(n) sem tail; lista ordenada exige busca para inserir.