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

Algoritmos e Estruturas de Dados Árvores Binárias de Busca

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

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

Gabarito disponível

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

Selecione uma alternativa A) A árvore ótima é aquela que apresenta custo mínimo. B) Em uma árvore binária de busca ordinária, a chave real e a chave de partilha coincidem. C) Os comprimentos de caminho externo, E(T), e interno, I(T), guardam entre si a seguinte relação: E(T) = I(T) * n, sendo n o número de nós. D) Uma árvore binária de busca com os nós externos incorporados é sempre estritamente binária. E) A complexidade da busca para uma árvore T, no pior caso, é igual à sua altura.

Resolução comentada

A relação correta é E(T) = I(T) + 2n, não I(T)·n.

Em árvores binárias com nós externos incorporados, o comprimento do caminho externo é E(T) = I(T) + 2n, onde n é o número de nós internos. A alternativa C apresenta um produto, o que é incorreto.

Análise das alternativas

A) Correta: a árvore ótima tem o menor custo esperado de busca. B) Correta: na árvore ordinária a chave real do nó é também a chave de partilha. D) Correta: com os nós externos incorporados, todo nó interno tem dois filhos (árvore estritamente binária). E) Correta: no pior caso a busca percorre um caminho da raiz à folha, ou seja, a altura.

Referência: Árvores binárias de busca: comprimentos de caminho interno e externo.

Resolução comentada do VaiConcursos.