Questão de Algoritmos e Estrutura de Dados — Algoritmos — CIAAR 2026
Algoritmos e Estrutura de Dados›Algoritmos
Código
gp019096
Banca
CIAAR
Órgão
CIAAR
Ano
2026
Cargo
Oficial de Apoio - Análise de Sistemas
Analise as afirmativas abaixo sobre as propriedades de uma Árvore Binária de Busca (BST). Para qualquer nó x, se y é um nó na subárvore esquerda de x, então a chave de y é maior ou igual à chave de x. O percurso em ordem (in-order tree walk) de uma árvore binária de busca imprime as chaves em ordem crescente. O tempo de execução das operações básicas, como inserção e busca em uma BST, é proporcional à altura da árvore. No pior caso, a altura de uma árvore binária de busca com n nós é Θ(n). Estão corretas apenas as afirmativas
AI e II.
BII e III.
CI, III e IV.
DII, III e IV.
Revelar gabarito e comentário▾
GabaritoD — II, III e IV.
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”.
Árvore Binária de Busca (BST) – Propriedades Fundamentais
Gabarito: letra D. Estão corretas apenas as afirmativas II, III e IV. A afirmativa I erra ao inverter a relação de ordem: na subárvore esquerda de um nó, todas as chaves são menores (ou menores ou iguais, em caso de duplicatas) que a chave do nó, e não maiores ou iguais. O percurso in-order produz chaves ordenadas (II); as operações básicas têm complexidade O(h) (III); e o pior caso de altura é Θ(n) (IV).
A banca testa a definição clássica de BST. A principal armadilha está no enunciado da propriedade da subárvore esquerda, que aparece invertida.
Afirmativa
Conteúdo
Correção
Justificativa
I
Para qualquer nó x, se y é um nó na subárvore esquerda de x, então a chave de y é maior ou igual à chave de x.
❌ Incorreta
A propriedade correta é que chaves na subárvore esquerda são menores (ou menores ou iguais) que a chave de x. A afirmativa inverte a relação de ordem.
II
O percurso em ordem (in-order tree walk) de uma árvore binária de busca imprime as chaves em ordem crescente.
✅ Correta
O percurso in-order visita subárvore esquerda, raiz e subárvore direita, gerando sequência crescente (ou não decrescente, com duplicatas).
III
O tempo de execução das operações básicas, como inserção e busca em uma BST, é proporcional à altura da árvore.
✅ Correta
As operações percorrem da raiz até a posição desejada, realizando no máximo h comparações, onde h é a altura. Complexidade O(h).
IV
No pior caso, a altura de uma árvore binária de busca com n nós é Θ(n).
✅ Correta
Em árvore degenerada (lista encadeada), a altura é n-1 ou n, resultando em Θ(n).
Propriedades BST: Subárvore esquerda (Chaves maiores ou iguais (erro), Chaves menores); Percurso in-order (Imprime em ordem crescente); Complexidade (Operações: O(h), Pior caso: Θ(n))
Afirmativa I — ❌ Incorreta
A propriedade fundamental de uma BST é: para todo nó x, todos os nós na subárvore esquerda têm chaves menores (ou menores ou iguais, dependendo da política para duplicatas) que a chave de x. A afirmativa diz "maior ou igual", o que é o oposto. Esse erro inverte completamente a definição, fazendo a árvore perder a propriedade de busca.
Afirmativa II — ✅ Correta
O percurso em ordem (in-order) visita primeiro a subárvore esquerda, depois a raiz, depois a subárvore direita. Como a subárvore esquerda contém chaves menores e a direita chaves maiores, a sequência impressa é estritamente crescente (se não houver duplicatas) ou não decrescente (se duplicatas forem permitidas, dependendo da implementação). Essa é uma propriedade clássica e amplamente usada para ordenar elementos a partir de uma BST.
Afirmativa III — ✅ Correta
As operações de busca, inserção e remoção em uma BST partem da raiz e descem até encontrar a posição desejada ou uma folha. O número de comparações realizadas é no máximo a altura da árvore (h). Portanto, o tempo de execução é O(h), ou seja, proporcional à altura. Em árvores balanceadas, h é O(log n), mas o enunciado afirma corretamente a proporcionalidade à altura, sem restringir a altura.
Afirmativa IV — ✅ Correta
No pior caso, a BST pode degenerar em uma lista encadeada (árvore inclinada) se as chaves forem inseridas em ordem crescente ou decrescente. Nessa situação, a altura é igual a n-1 (ou n), que é Θ(n). Portanto, a afirmativa está correta.
PEGA ESSA DICA!
Para memorizar rapidamente as propriedades da BST, associe: Esquerda = Em (E > R? Não: Esquerda = Em (Entradas Menores). A subárvore esquerda tem chaves menores (M), a direita tem chaves maiores (M). O in-order (E, R, D) dá ordem crescente. E altura = h → complexidade O(h).
Gabarito: letra D – afirmativas II, III e IV corretas.