Question

11

As questões 21, 22, e 23 se referem ao problema definido abaixo:

Definição do problema: para uma árvore binária balanceada (não necessariamente uma árvore de busca; cada nó contém apenas chave e dois ponteiros para os filhos esquerdo e direito), calcular o custo do caminho mais caro entre a raiz e uma folha, e imprimir o custo total e a lista de chaves dos nós deste caminho.

Notas:

• O custo de um caminho em uma árvore é a soma das chaves dos nós deste caminho. • Considere que a altura da árvore é denotada por h, e que o tipo dos dados é inteiro.

Marque a alternativa FALSA.

Accepted Answer

D) Pode ser resolvido em O(n · h) tempo e O(h) espaço adicional, sem modificar a estrutura de dados, mesmo se for permitido passar uma pilha como parâmetro apenas por valor de forma que seja necessário copiar todo o conteúdo da pilha passada como parâmetro a cada chamada de função.

Answer

A) É possível estender o algoritmo de percurso pré-ordem recursivo para resolver este problema. Uma das soluções envolve passar uma pilha de inteiros como um parâmetro adicional na chamada recursiva do percurso pré-ordem.

Answer

B) É possível estender o algoritmo de percurso pré-ordem iterativo para resolver este problema. Uma das soluções envolve manipular uma pilha de inteiros adicional.

Answer

C) Pode ser resolvido em O(n · h) tempo e O(h) espaço adicional, sem modificar a estrutura de dados, se for permitido passar uma pilha como parâmetro por referência, de forma que não seja necessário copiar todo o conteúdo da pilha quando esta for passada como parâmetro.

Answer

E) Se a árvore for balanceada, h = O(log n) e, portanto, as classes de complexidade O(n · h) e O(h) poderiam ser escritas como O(n · log n) e O(log n), respectivamente.

Mais questões de Árvores e grafos