MO417 - QUESTÃO PARA PROVA ORAL

Número:

Enunciado: Qual modificação devemos realizar no algoritmo PARTITION, para utilizá-lo como rotina auxiliar de um algoritmo que determina o i-ésimo menor elemento de um vetor em tempo linear no pior caso? Observação: pivô é um elemento do vetor ao redor do qual será feito o particionamento.

  PARTITION(A, p, r)

  1. x = A[r]       /* A[r] é o elemento pivô */

  2. i = p - 1

  3. for j = p to r - 1

  4.     if A[j] <= x

  5.         i = i + 1

  6.         exachange A[i] with A[j]

  7. exchange A[i + 1] with A[r]

  8. return i + 1

1. não modifica-se o PARTITION, pois sua modificação não garante uma boa divisão do vetor ao ser particionado;
2. modifica-se o PARTITION para que divida o vetor em 5 partições;
3. modifica-se o PARTITION criando uma rotina auxiliar que seleciona um elemento aleatório  como pivô e faz sua troca antes do particionamento real;
4. modifica-se o PARTITION para que receba como parâmetro de entrada o elemento pivô;
5. NDA.

Ideia original de: Laurindo de Sousa Britto Neto

MO417 - QUESTÃO PARA PROVA ORAL

Número:

Enunciado: Dadas as afirmações abaixo, marque a alternativa correta:

I. Counting Sort é uma ordenação estável. Portanto, a ordem em que os elementos repetidos aparecem na entrada se mantém inversa após a ordenação;

II. O Radix Sort utiliza o Counting Sort como ordenação estável intermediária, visto que o Counting Sort efetua ordenações locais economizando memória principal;

III. O Bucket Sort pressupõe que a entrada possui uma distribuição normal.

1. Apenas a afirmação II é verdadeira;
2. Apenas a afirmação III é verdadeira;
3. As afirmações II e III são verdadeiras;
4. As afirmações I, II e III são falsas;
5. NDA.

Ideia original de: Laurindo de Sousa Britto Neto

MO417 - QUESTÃO PARA PROVA ORAL

Número:

Enunciado: Dada a equação de recorrência abaixo, marque a alternativa CORRETA:

T(n) = 8T(n/8) + nlgn

1. O método mestre se aplica à equação e T(n) = ϴ(n);
2. O método mestre se aplica à equação e T(n) = ϴ(nlgn);
3. O método mestre não se aplica à equação, pois nlgn é assintoticamente maior que n;
4. O método mestre não se aplica à equação, pois nlgn não é polinomialmente maior que n;
5. NDA

Ideia original de: Laurindo de Sousa Britto Neto

MO417 - QUESTÃO PARA PROVA ORAL

Número:

Enunciado: Analise as assertivas abaixo, realizando abstrações simplificadoras em termos da notação assintótica O, e marque a alternativa INCORRETA:

1. n² > 2log₂nⁿ
2. 10^-128n³ > 10¹²⁸n²
3. (7/2)ⁿ > 2²ⁿ
4. 100⁴⁵ = 200²⁰
5. NDA

Ideia original de: Laurindo de Sousa Britto Neto