MO417 - Questão para a prova oral

Número:

Enunciado: Com relação aos algoritmos Heapsort e Quicksort, assinale a alternativa correta:

A) Assim como Mergesort, Heapsort baseia-se na técnica de divisão e conquista.

B) Heapsort e Quicksort não são algoritmos estáveis, uma vez que a ordem relativa dos elementos iguais não é alterada após a ordenação.

C) No pior caso, Quicksort tem um desempenho superior a execução de Mergesort.

D) O tempo de execução do melhor caso de Quicksort é o mesmo tempo de execução do Heapsort  para um arranjo já ordenado em ordem crescente.

E) N.D.A

Ideia original de: Thaís Harumi Ussami

MO417 - Questão para a prova oral

Número:

Enunciado: Considere as seguintes recorrências:

T1(n) = 1, n = 1

        = T1(n/2) + n, n > 1

T2(n) = 1, n = 1

        = T2(n/2) + n^2, n > 1

T3(n) = 1, n = 1

        = T3(n/2) + n^3, n > 1

Com relação às ordens de crescimento das funções, é correto afirmar que: 

A) T2(n) > T3(n) > T1(n)

B) T2(n) > T1(n) > T3(n)

C) T3(n) > T2(n) > T1(n)

D) T3(n) > T1(n) > T2(n)

E) N.D.A

Ideia original de: Thaís Harumi Ussami

MO417 - Questão para a prova oral

Número:

Enunciado: Considere uma variação do Bubblesort com o seguinte funcionamento: Dado um vetor A[1...n], nas iterações ímpares o bubblesort comum é executado, já nas iterações pares o bubblesort é executado no sentido contrário, ou seja, do final do vetor para o começo. Dado a entrada do pior caso do algoritmo de Bubblesort comum, qual o tempo de execução para essa entrada no algoritmo de Bubblesort alterado?

A) ϴ(n)

B) ϴ(n²)

C) ϴ(nlgn)

D) ϴ(n³)

E) N.D.A

Ideia original de: Thaís Harumi Ussami