Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — IBADE 2025
Algoritmos e Estrutura de Dados›Estrutura de Dados
Código
qg511947
Banca
IBADE
Órgão
SES-MG
Ano
2025
Nível
Superior
Cargo
Especialista em Políticas e Gestão da Saúde D01 (Área de TI)
Julgue as sentenças acima como VERDADEIRAS (V) ou FALSAS (F).I. As pilhas (stacks) operam segundo o princípio LIFO, permitindo inserções e remoções no topo com excelente desempenho, sendo úteis em chamadas de função.II. Árvores binárias de busca garantem tempo constante O(1) para inserção e busca em qualquer cenário, independentemente da ordem de inserção dos dados.III. Filas (queues) seguem o princípio FIFO, sendo amplamente utilizadas em sistemas de agendamento, buffers e comunicação assíncrona.A sequência correta é:
AF – V – V
BV – V – V
CF – F – V
DV – F – V
EV – V – F
Revelar gabarito e comentário▾
GabaritoD — V – 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”.
Estruturas de Dados: Pilhas, Filas e Árvores Binárias de Busca
Gabarito: D (V – F – V). Apenas a afirmativa II está incorreta, pois árvores binárias de busca (BST) não garantem tempo constante O(1) em qualquer cenário; no pior caso (árvore degenerada) a complexidade é O(n). As definições de pilha (LIFO) e fila (FIFO) estão corretas e são amplamente utilizadas conforme descrito.
A questão testa o conhecimento das características fundamentais de três estruturas de dados clássicas. A afirmativa II é uma generalização falsa, pois ignora a possibilidade de degeneração da árvore.
Item
Afirmação
V/F
Justificativa
I
Pilhas (stacks) operam segundo o princípio LIFO, permitindo inserções e remoções no topo com excelente desempenho, sendo úteis em chamadas de função.
V
Pilhas seguem LIFO; operações push/pop no topo têm complexidade O(1); usadas em pilha de execução, undo, etc.
II
Árvores binárias de busca garantem tempo constante O(1) para inserção e busca em qualquer cenário, independentemente da ordem de inserção dos dados.
F
BST não garante O(1); no pior caso (árvore degenerada) a complexidade é O(n); em árvores balanceadas é O(log n).
III
Filas (queues) seguem o princípio FIFO, sendo amplamente utilizadas em sistemas de agendamento, buffers e comunicação assíncrona.
V
Filas seguem FIFO; operações enqueue/dequeue; usadas em agendamento, buffers, filas de impressão, etc.
Estruturas de dados
1Pilha (stack)
LIFO
Inserção/remoção no topo
O(1)
2Fila (queue)
FIFO
Inserção no final, remoção no início
O(1)
3Árvore binária de busca (BST)
Balanceada
O(log n)
Degenerada
O(n)
LEVEL · soulevel.com.br
Item I — ✅ Verdadeiro
Pilhas (stacks) operam pelo princípio LIFO (Last In, First Out), ou seja, o último elemento inserido é o primeiro a ser removido. As operações de inserção (push) e remoção (pop) ocorrem no topo da pilha e, em implementações típicas (vetor ou lista ligada), têm complexidade O(1). São amplamente utilizadas em chamadas de função (pilha de execução), análise de expressões, desfazimento de operações (undo), entre outros. O enunciado está perfeitamente correto.
Item II — ❌ Falso
Árvores binárias de busca (BST) não garantem tempo constante O(1) para inserção e busca em qualquer cenário. A complexidade dessas operações depende da altura da árvore:
Em uma árvore balanceada (ex.: árvore AVL ou rubro-negra), a altura é O(log n), e as operações são O(log n).
Se os dados forem inseridos em ordem crescente ou decrescente, a BST degenera em uma lista ligada, com altura O(n) e operações O(n).
Portanto, a afirmação de que "garantem tempo constante O(1) para inserção e busca em qualquer cenário, independentemente da ordem de inserção" é falsa. A banca explora essa generalização indevida, que desconsidera o pior caso.
Item III — ✅ Verdadeiro
Filas (queues) seguem o princípio FIFO (First In, First Out): o primeiro elemento inserido é o primeiro a ser removido. As operações básicas são enqueue (inserir no final) e dequeue (remover do início). Essa estrutura é amplamente empregada em sistemas de agendamento de tarefas, buffers de comunicação, filas de impressão, processamento assíncrono e algoritmos de escalonamento. O enunciado está correto.
Conclusão: A sequência correta é V – F – V, correspondente à alternativa D.
NÃO CAIA NESSA!
Ao encontrar afirmações sobre complexidade de estruturas de dados, desconfie de generalizações absolutas como "sempre O(1)" ou "garantido em qualquer cenário". Lembre-se de que o desempenho de BSTs depende da ordem de inserção, e a degenerescência é um ponto frequente de pegadinha em concursos.