QUESTÕES:

1 - (POSCOMP 2023) Sobre as árvores binárias de busca, é correto afirmar que:
A) Seja x um nó em uma árvore de busca binária. Se y é um nó na subárvore esquerda de x, então y.chave >= x.chave. Se y é um nó na subárvore direita de x, então x.chave <= y.chave.
B) A propriedade de árvore de busca que permite imprimir todas as chaves em sequência ordenada por meio de um simples algoritmo recursivo é denominada percurso de árvore em pré-ordem.
C) Para excluir um nó z de uma árvore de busca binária T , se z tem apenas um filho, então simplesmente o removemos modificando seu pai de modo a substituir z por NIL como seu filho.
D) Para excluir um nó z de uma árvore de busca binária T, se z tem dois filhos, então elevamos o primeiro filho para que ocupe a posição de z na árvore modificando o pai de z de modo a substituir z pelo filho de z.
E) Para encontrar um nó em uma árvore de busca binária cuja chave é um mínimo, deve-se seguir os ponteiros de filhos da esquerda desde a raiz até encontrar um valor NIL.

Passo 1

Beleza, aqui a gente tem uma questão de teoria de árvores binárias de busca (BST). O enunciado apresenta cinco afirmações sobre BSTs e pede pra identificar qual delas é correta. Para resolver, a gente vai precisar lembrar das propriedades fundamentais de BST (orde­nam­ento, percurso e exclusão).

Passo 2

Teoria básica:
Em uma BST, para todo nó :
  • Qualquer nó na subárvore esquerda de satisfaz .
  • Qualquer nó na subárvore direita de satisfaz .
    Além disso, o percurso in-order (esquerda, raiz, direita) imprime as chaves em ordem crescente, e a exclusão tem três casos:
  1. Nó sem filhos: remove direto.
  2. Nó com um filho: substitui o nó pelo seu filho.
  3. Nó com dois filhos: acha o sucessor (menor da subárvore direita), copia a chave e exclui o sucessor.

Passo 3

Analisando a opção A:
“A) Se está na subárvore esquerda de , então . Se está na subárvore direita de , então .”
– Isso está invertido: na esquerda deve valer . Logo A é falsa.

Passo 4

Analisando a opção B:
“B) A propriedade que permite imprimir as chaves em sequência ordenada é denominada percurso de árvore em pré-ordem.”
– Na verdade a ordenação crescente vem do in-order, não do pré-ordem. Então B é falsa.

Passo 5

Analisando a opção C:
“C) Para excluir um nó , se tem apenas um filho, simplesmente o removemos modificando seu pai para substituir por NIL.”
– Errado: se tem um filho, você substitui pelo seu filho, não por NIL. Então C é falsa.

Passo 6

Analisando a opção D:
“D) Para excluir um nó com dois filhos, elevamos o primeiro filho para ocupar o lugar de .”
– Também não: o procedimento correto é usar o sucessor (ou predecessor) para manter a ordenação, não “promover” o filho direto. D é falsa.

Passo 7

Analisando a opção E:
“E) Para encontrar a chave mínima, deve-se seguir os ponteiros de filhos da esquerda desde a raiz até encontrar um valor NIL.”
– Isso bate com o algoritmo padrão: você anda sempre à esquerda até que o ponteiro seja NIL; o último nó não-NIL encontrado é o mínimo. E é verdadeira.

Resposta

E

Exercícios relacionados