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?

Definição da operação de Partição:

Entrada: uma lista ordenada de números, e um valor pivô. Saída: a mesma lista reordenada. Tal que sigam a seguinte ordenação: valores menores que pivô, seguidos de valores iguais a pivô, seguidos de valores maiores que pivô.

Por exemplo:

Entrada: {3, 4, 2, 9, 4, 5, 2, 8}, pivo 5

Saída: {3, 4, 2, 4, 2, 5, 9, 8}

Partição é usada para implementar a função Quicksort.

Se alguma opção de a) a d) for falsa, marque-a. Caso contrário, marque e).

Considere as definições:

public class SuperClass {
    public int op(int a, int b) { return a - b; }
}
public class SubClass extends SuperClass {
    public int op(int a, int b) { return a + b; }
}
// código Cliente de SuperClass e SubClass
SuperClass supC = new SuperClass( ); // linha 01
SubClass subC = new SubClass( );    // linha 02
x1 = supC.op(6,4);                  // linha 03
supC = subC;                        // linha 04
x2 = supC.op(6,4);                  // linha 05

Assinale a alternativa mais correta sobre os valores de x1 e x2 depois da execução do pseudo-código acima.