Question

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).

Accepted Answer

E) Todas as anteriores são verdadeiras.

Answer

A) A operação Partição pode ser implementada com entrada do tipo vetor de inteiros, em O(n) tempo e O(1) espaço adicional.

Answer

B) A operação Partição pode ser implementada com entrada do tipo lista simplesmente ligada, em O(n) tempo e O(1) espaço adicional, apenas manipulando-se ponteiros, sem alocar ou desalocar nenhuma outra lista ou nó.

Answer

C) A função Quicksort pode ser implementado com entrada do tipo lista simplesmente ligada, em O(n · log n) tempo e O(log n) espaço adicional.

Answer

D) A operação Partição pode ser implementada com entrada do tipo lista simplesmente ligada, em O(n) tempo e O(1) espaço adicional, se alocarmos 3 listas auxiliares para os valores menores, iguais, e maiores que o pivô, e depois concatenarmos estas 3 listas.

Mais questões de Algoritmos de ordenação, busca e complexidade