Teste sobre Quicksort (ordenação rápida)
Quicksort (Ordenação Rápida): Guia Completo para Estudantes
Test: Algoritmo Quicksort
20 perguntas
Pergunta 1: No pior caso do Quicksort, a escolha do pivô geralmente resulta em particionamentos equilibrados, dividindo o array em sub-arrays de tamanhos aproximadamente iguais, mantendo a complexidade O(n log n).
A. Sim
B. Não
Explicação: O estudo indica que o pior caso do Quicksort, com complexidade O(n²), ocorre especificamente quando a escolha do pivô resulta em particionamentos extremamente desequilibrados, não equilibrados. Particionamentos equilibrados levam ao caso médio ou melhor caso, com complexidade O(n log n).
Pergunta 2: A estratégia de 'Mediana de três' para a escolha do pivô no Quicksort geralmente resulta em particionamentos mais equilibrados, contribuindo para um melhor desempenho na prática?
A. Sim
B. Não
Explicação: A seção 'Escolha do Pivô' dos materiais de estudo afirma que a estratégia de 'Mediana de três' 'geralmente produz um pivô mais próximo da mediana real do sub-array, levando a particionamentos mais equilibrados e melhor desempenho na prática'.
Pergunta 3: É uma prática comum e recomendada na implementação do Quicksort que a lógica de particionamento inclua o pivô novamente nos sub-arrays recursivos.
A. Sim
B. Não
Explicação: A lógica de particionamento deve garantir que o pivô seja colocado em sua posição final e que os sub-arrays não incluam o pivô novamente. Incluir o pivô nos sub-arrays seria um erro que poderia causar problemas no algoritmo.
Pergunta 4: A escolha de um pivô fixo (primeiro ou último elemento) no Quicksort pode resultar no pior caso de desempenho.
A. Sim
B. Não
Explicação: A escolha de um pivô fixo (primeiro ou último elemento) é simples de implementar, mas pode levar ao pior caso de desempenho se o array já estiver quase ordenado ou inversamente ordenado, pois o particionamento será desequilibrado.
Pergunta 5: Conforme a descrição lógica do algoritmo Quicksort apresentada, a função de particionamento sempre seleciona o primeiro elemento do sub-array como pivô para iniciar o processo de ordenação.
A. Sim
B. Não
Explicação: A descrição lógica da função 'particionar' no material de estudo indica explicitamente que 'pivo = array[fim]', ou seja, o último elemento do sub-array é escolhido como pivô, e não o primeiro.