Questão 5 — Árvores Binárias (Algoritmos e Estruturas de Dados) — Serviço de Seleção do Pessoal da Marinha (SSPM) · Marinha do Brasil 2021

Algoritmos e Estruturas de Dados Árvores Binárias

Serviço de Seleção do Pessoal da Marinha (SSPM) 2021

Marinha do Brasil · Ingresso no Quadro Técnico do Corpo Auxiliar da Marinha (CP-T) — Informática · Caderno Amarela

Gabarito disponível

Com relação às árvores binárias, assinale a opção correta.

Selecione uma alternativa A) Uma árvore binária T é um conjunto infinito de elementos denominados nós ou vértices. B) Uma árvore binária não pode ter duas subárvores vazias, enquanto o mesmo ocorre com árvores gerais. C) Uma árvore estritamente binária é uma árvore binária em que cada nó possui somente 2 filhos. D) Uma árvore binária, cuja raiz armazena o elemento R, é denominada árvore de busca binária se todo elemento armazenado na subárvore direita for menor que R, nenhum elemento armazenado na subárvore esquerda for menor que R e as subárvores esquerda e direita também forem árvores de busca binária. E) A árvore binária que possui altura máxima é aquela cujos nós interiores possuem exatamente uma subárvore vazia. Essas árvores são denominadas zigue-zague.

Resolução comentada

A árvore binária de altura máxima é a zigue-zague (nós interiores com uma subárvore vazia).

A árvore de altura máxima para n nós ocorre quando cada nó interior possui exatamente uma subárvore vazia, formando uma cadeia, denominada zigue-zague na terminologia adotada.

Análise das alternativas

A) Uma árvore binária é um conjunto finito de nós. B) Uma árvore binária pode ter subárvores vazias (inclusive as duas, como nas folhas e na árvore vazia). C) Árvore estritamente binária é aquela em que cada nó tem 0 ou 2 filhos, não somente 2. D) A definição de árvore de busca está invertida: a subárvore esquerda deve ter elementos menores e a direita, maiores (ou não menores).

Referência: Estruturas de Dados – árvores binárias (Szwarcfiter; Ziviani).

Resolução comentada do VaiConcursos.