Resumêra

Questão 1 (Média): Sobre árvores binárias, qual afirmação é verdadeira?

1.50 pontos Média

Escolha a opção correta:

A) Em uma árvore binária, todo nó tem dois filhos obrigatoriamente. B) Folhas são nós sem filhos. C) A raiz é sempre um nó folha. D) A profundidade de toda árvore é igual a 1. E) Em uma árvore binária completa, o último nível pode estar incompleto.

Resposta correta: B) Folhas são nós sem filhos.

Observação: folhas não possuem filhos; nós internos têm pelo menos um filho.

Questão 2 (Difícil): Na representação de uma árvore binária, para que serve a notação polonesa (pré-ordem)?

2.50 pontos Difícil

Escolha a opção correta:

A) Organizar a notação de expressões com parênteses explícitos. B) Representar expressões com o operador vindo antes dos operandos, evitando ambiguidades. C) Permitir apenas avaliação de árvores com pós-ordem. D) Transformar árvores em grafos não direcionados. E) Substituir a raiz pela folha mais próxima.

Resposta correta: B) Representar expressões com o operador vindo antes dos operandos, evitando ambiguidades.

Observação: a notação polonesa (pré-ordem) resulta em uma forma clara de avaliação sem dependência de parênteses.

Questão 3 (Difícil): Em uma árvore com N nós, qual é o número total de arcos (bordas)?

2.50 pontos Difícil

Escolha a opção correta:

A) N arcos B) N-1 arcos C) 2N-2 arcos D) N+1 arcos E) 0 arcos

Resposta correta: B) N-1 arcos.

Observação: em uma árvore com N nós, a soma do grau dos nós é 2(N-1); uma propriedade clássica de árvores.

Questão 4 (Extremamente difícil): Sobre a prova por indução de que em uma árvore com N nós existem 2N-2 extremidades de arcos, qual é o passo-chave ao passar de N para N+1?

3.50 pontos Extrema

Escolha a opção correta:

A) Remover uma folha e o arco, aplicar IH na árvore restante, depois recontruir adicionando a folha e o arco. B) Adicionar um nó raiz e manter as folhas inalteradas, sem usar IH. C) Desconsiderar o nó folha e apenas contarmos arcos. D) Converter a árvore em grafo não dirigido. E) A IH não se aplica para N+1 nós.

Resposta correta: A) Remover uma folha e o arco, aplicar IH na árvore restante, depois recontruir adicionando a folha e o arco.

Explicação: o passo de indução envolve reduzir para uma árvore com N nós (IH) e, ao retornar, para N+1 nós, adicionando de volta a folha removida e o arco correspondente.

Árvores em Computação: estruturas, representações e algoritmos de percurso

Questões sobre o assunto