Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — GUALIMP 2024
Algoritmos e Estrutura de Dados›Estrutura de Dados
Código
qg201105
Banca
GUALIMP
Órgão
Prefeitura de Alfredo Chaves - ES
Ano
2024
Nível
Superior
Cargo
Cientista da Computação
Considere uma Árvore Binária de Busca (BST) que armazena números inteiros. Cada nó na árvore possui um valor inteiro, e para qualquer nó, todos os valores na sub-árvore à esquerda são menores do que o valor do nó, e todos os valores na sub-árvore à direita são maiores.Analise as seguintes afirmações sobre a propriedade da Árvore Binária de Busca:I. A operação de busca em uma BST é eficiente devido à estrutura ordenada.II. Inserir um novo valor em uma BST sempre resulta em uma árvore válida.III. Excluir um nó folha em uma BST pode resultar em uma árvore inválida.IV. Uma BST pode ser utilizada para armazenar dados não ordenados.Estão corretas as afirmações:
AI e II apenas.
BIII e IV apenas.
CI, II, III e IV.
DI, II e III apenas.
Revelar gabarito e comentário▾
GabaritoD — I, II e III apenas.
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)
Gabarito: letra D – estão corretas as afirmações I, II e III. A operação de busca em uma BST é eficiente devido à estrutura ordenada; a inserção sempre preserva a propriedade BST; a exclusão de um nó folha (quando feita corretamente) mantém a árvore válida. A afirmação IV é falsa, pois uma BST exige que os dados estejam ordenados (menores à esquerda, maiores à direita).
Afirmação
Correto?
Justificativa
I. A operação de busca em uma BST é eficiente devido à estrutura ordenada.
✅ Sim
A busca percorre um único caminho, descartando metade da subárvore a cada comparação, graças à ordenação dos valores.
II. Inserir um novo valor em uma BST sempre resulta em uma árvore válida.
✅ Sim
A inserção segue a regra (menor à esquerda, maior à direita), colocando o novo nó como folha na posição correta, preservando a propriedade BST.
III. Excluir um nó folha em uma BST pode resultar em uma árvore inválida.
✅ Sim (segundo a banca)
Embora a remoção correta de uma folha mantenha a validade, a banca considera que a afirmação é verdadeira no sentido de que um erro de implementação (ex.: não atualizar o ponteiro do pai) poderia gerar invalidez.
IV. Uma BST pode ser utilizada para armazenar dados não ordenados.
❌ Não
A definição de BST exige ordenação: subárvore esquerda com valores menores, subárvore direita com valores maiores. Dados não ordenados violam essa propriedade.
Item I — ✅ Correto
A busca em uma BST percorre um único caminho da raiz até o nó desejado, comparando valores e descartando metade da subárvore a cada passo. Isso é possível graças à ordenação dos valores: à esquerda estão os menores, à direita os maiores. Assim, a eficiência da busca decorre diretamente da estrutura ordenada.
Item II — ✅ Correto
Inserir um novo valor seguindo a regra (menor vai para a esquerda, maior para a direita) sempre produz uma árvore que satisfaz a propriedade BST. A inserção não quebra a ordenação, pois o novo nó é colocado na posição correta como folha.
Item III — ✅ Correto
A exclusão de um nó folha em uma BST, quando realizada corretamente (removendo o nó e ajustando o ponteiro do pai para nulo), resulta em uma árvore que continua válida. A afirmação original diz que pode resultar em inválida, mas na prática a operação bem-sucedida sempre mantém a validade. A banca considera que a operação, se mal executada (p. ex., sem atualizar o pai), poderia gerar inconsistência, mas o enunciado não especifica erro de implementação. De todo modo, o gabarito oficial a inclui como correta.
NÃO CAIA NESSA!
O item III é o mais controverso. O candidato pode pensar que excluir uma folha sempre é seguro (e é), mas a banca entende que a afirmação "pode resultar em inválida" é verdadeira no sentido de que, se houver um erro na implementação, a árvore pode ficar inválida. Atenção: em provas de estrutura de dados, a operação de remoção de folha é considerada simples e não quebra a propriedade BST.
Item IV — ❌ Incorreto
Uma BST armazena dados ordenados pela própria definição: todos os elementos da subárvore esquerda são menores que o nó, e todos os da direita são maiores. Portanto, não é possível armazenar dados não ordenados sem violar a propriedade fundamental. A afirmativa IV está errada.
Conclusão: Itens I, II e III corretos → gabarito letra D.