MO417 - Questão para a prova oral

Número:

Enunciado: Assinale a alternativa verdadeira sobre o algoritmo SELECT e o algoritmo RANDOMIZED-SELECT.

a) No pior caso do RANDOMIZED-SELECT, todas as partições dividem o arranjo em 2 subarranjos, sendo um com 0 e outro com n-1 elementos. No SELECT, o método para a escolha do pivô não permite este caso.
b) No pior caso o SELECT possui tempo Θ(n) enquanto o randomized possui tempo Θ(nlgn).
c) No SELECT, se o i-ésimo termo for menor que o pivô X, então ele sera buscado no subconjunto com 5 elementos anterior ao subconjunto que contém X.
d) A recursão do SELECT particiona o problema em 5 subproblemas, enquanto que a recursão do RANDOMIZED-SELECT particiona em 2 subproblemas.
e) NDA.

Ideia original de: Jacqueline Midlej do Espírito Santo

MO417 - Questão para a prova oral

Número:

Enunciado: Considere o algoritmo do quicksort ligeiramente modificado para sempre eleger o elemento aproximadamente do meio para ser o pivô. Isto é, PARTITION(A,p,r) elege o elemento A[⌈(r-p+1)/2⌉] como pivô. Desta forma, é correto afirmar que:

a) Quando e entrada A está em ordem decrescente o tempo de execução do quicksort é T(n)=Θ(nlgn), refletindo o pior caso.

b) Quando a entrada A está em ordem crescente o tempo de execução do quicksort é T(n)=Θ(n), refletindo o melhor caso.

c) Quando a entrada A está em ordem crescente ou decrescente, no fim de cada execução de PARTITION, o pivô sempre começa e termina na mesma posição.

d) Quando a entrada A está em ordem crescente ou decrescente o tempo de execução do quicksort é T(n)=Θ(nlgn), refletindo o melhor caso.

e) NDA

Ideia original de: Jacqueline Midlej do Espírito Santo

MO417 - Questão para a prova oral

Número:

Enunciado: Considere o algoritmo abaixo para a resolução do problema Torre de Hanoi.

Algoritmo Hanoi (n, ori, des, aux)
 se n = 1
      então “move pino” de ori para des
 senão Hanoi (n − 1, ori, aux, des)
      “move pino” de ori para des
      Hanoi (n − 1, aux, des, ori)

Desta forma, considere a recorrência para este problema:

T(n)=1                 para n=1
T(n)=2T(n-1)+1   para n>1

É correto afirmar que:
a. T(n)=Θ(nlg(n))
b. T(n)=Θ(n²log(n))
c. T(n)=Θ(2ⁿ)
d. T(n)=Θ(n²)
e. NDA

Ideia original de: Jacqueline Midlej do Espírito Santo

MO417 - Questão para a prova oral

Número:


Enunciado:Sobre as seguintes afirmações, NÃO é correto afirmar que:

a. O(g(n)) ∩ Ω(g(n)) = Θ(g(n))
b. o(g(n)) ∩ Θ(g(n)) = ∅
c. o(g(n)) ∩ O(g(n)) = Θ(g(n))
d. o(g(n)) ⊂ O(g(n))
e. NDA

Ideia original de: Jacqueline Midlej do Espírito Santo

Teste

Teste