Considere o seguinte algoritmo para salvar e recuperar árvores de busca (BST) balanceadas em/de arquivos. No exemplo, consideramos uma árvore Rubro-Negra.

Salvar arvore em arquivo

1. Percorra a árvore em-ordem, e salve os elementos em um arquivo na ordem em que foram percorridos.

Recuperar uma arvore a partir de um arquivo:

2. Leia o arquivo, e coloque os elementos em um vetor. Estes elementos estarão ordenados.

3. Insira os elementos, na ordem em que foram lidos, em uma árvore Rubro-Negra

4. Temos uma BST com os elementos originais.

Se existe uma alternativa falsa entre a) e d), marque-a; senão, marque e).

Se há alguma opção falsa entre a) e d), marque-a; senão, marque e). Se uma árvore tem n > 3 nós:

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 opção mais correta e precisa. Se uma árvore tem n nós, o número de arestas é:

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.

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?