A questão se refere 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.

Marque a alternativa mais correta.

Marque a alternativa mais correta.

Ainda sobre a notação Big-O, marque a alternativa incorreta de a) a d), ou se todas estão corretas, marque e).

De acordo com a notação Big-O, marque a alternativa incorreta de a) a d), ou se todas estão corretas, marque e).

Para a questão, entre as seguintes estruturas de dados:

1. Árvore de busca balanceada
2. Árvore de busca não balanceada
3. Vetor de elementos ordenados
4. Lista ligada de elementos ordenados
5. Lista duplamente ligada de elementos ordenados

Quantas permitem buscar elementos em \( O(\log n) \) tempo e \( O(\log n) \) espaço adicional, no pior caso?

Para a questão, entre as seguintes estruturas de dados:

1. Árvore de busca balanceada
2. Árvore de busca não balanceada
3. Vetor de elementos ordenados
4. Lista ligada de elementos ordenados
5. Lista duplamente ligada de elementos ordenados

Quantas permitem buscar elementos em \( O(\log n) \) tempo e \( O(1) \) espaço adicional, no pior caso?

Para a questão, entre as seguintes estruturas de dados:

1. Árvore de busca balanceada
2. Árvore de busca não balanceada
3. Vetor de elementos ordenados
4. Lista ligada de elementos ordenados
5. Lista duplamente ligada de elementos ordenados

Quantas permitem percorrer os elementos tanto em ordem crescente quanto decrescente em \( O(n) \) tempo e \( O(n) \) espaço adicional, no pior caso?

Para a questão, entre as seguintes estruturas de dados:

1. Árvore de busca balanceada
2. Árvore de busca não balanceada
3. Vetor de elementos ordenados
4. Lista ligada de elementos ordenados
5. Lista duplamente ligada de elementos ordenados

Quantas permitem percorrer os elementos tanto em ordem crescente quanto decrescente em \( O(n) \) tempo e \( O(\log n) \) espaço adicional, no pior caso?

Sobre as estruturas listadas abaixo (árvores balanceadas, listas), quais destas estruturas de dados NÃO podem ser concatenadas em O(1), mantendo as propriedades indicadas em cada alternativa?