MO417 - Questão para a prova oral

Número:

Enunciado: Considere as seguintes informações sobre o algoritmo de seleção RANDOMIZED-SELECT, cujo código segue abaixo:

RANDOMIZED-SELECT(A,p,r,i)
if (p == r)
   return A[p]
q = RANDOMIZED-PARTITION(A,p,r)
k = q-p-1
if (i == k)
   return A[q]
else if (i < k)
   return RANDOMIZED-SELECT(A,p,q-1,i)
else return RANDOMIZED-SELECT(A,q+1,r,i-k)

I. O algoritmo executa em tempo linear, uma vez que adota premissas sobre a entrada.
II. O algoritmo realiza primeiro uma ordenação dos elementos para então selecionar o i-ésimo menor elemento do arranjo A[p...r].
III. Para determinar qualquer estatística de ordem, considerando elementos distintos do arranjo, o tempo esperado é linear.
IV. O algoritmo utiliza a técnica de divisão e conquista para retornar o i-ésimo menor elemento do arranjo A[p...r].

Assinale a alternativa correta:

A) I e II estão correta.
B) I, III e IV estão corretas.
C) I e III estão corretas.
D) III e IV estão corretas.
E) N.D.A

Ideia original de: Thaís Harumi Ussami

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