MO417 - Questão para a prova oral

Número: 

Enunciado: Considere as seguintes afirmações: 
  
  (I)  Para localizar simultaneamente o elemento mínimo e o elemento máximo de um vetor com n elementos, onde n é impar, tem 3*(floor(n/2)) comparações. Se removemos o primeiro elemento do vetor o número de comparações para localizar simultaneamente o elemento mínimo e o elemento máximo é  3*(floor(n/2))  - 7/2.

 (II)  O algoritmo RANDOMIZED-SELECT pode encontrar o i-th elemento mais large de um vetor em Θ(n)

(III)  O tempo de execução do algoritmo RANDOMIZED-SELECT quando o vetor de entrada é ordenada em forma crescente é Θ(n²)

Assinale a alternatica correta:

1. Somente (I) é verdadeira.
2. Somente (II) é verdadeira.
3. (I) e (II) são verdadeiras.
4. (II) e (III) são verdadeiras.
5. NDA

Ideia original de: Jhon Anthony Campos Arteaga

MO417 - Questão para a prova oral

Número: 

Enunciado: Seja o vetor A=[2^n-1, 2^n-2, ……, 1], se aplicamos o algoritmo counting-sort para ordenar o vetor A, quais das seguintes afirmações são verdadeiras:

  (I)  Si n ≥ lg 2cn, a ordenação funciona em Θ(n), para c=1.

 (II)  Si n ≤ lg 2cn, a ordenação funciona em Θ(n), para c=1.

(III)  O algoritmo counting-sort sempre cumpre a propriedade de estabilidade.

Assinale a alternativa correta:

1. Somente (I) é verdadeira.
2. Somente (II) é verdadeira.
3. (I) e (II) são verdadeiras.
4. (II) e (III) são verdadeiras.
5. NDA

Ideia original de: Jhon Anthony Campos Arteaga

MO417 - Questão para a prova oral

Número: 

Enunciado: Considere as seguintes afirmações sobre a função de recorrência  

T(n)=2T(n/2) + n lg n   :

  
  (I)  Podemos utilizar o método master para resolver a recorrência.

 (II)  A função não e uma série geométrica decrescente.

(III)  T(n)=Θ(n log² n)

Assinale a alternatica correta:

1. Somente (I) é verdadeira.
2. Somente (II) é verdadeira.
3. (I) e (II) são verdadeiras.
4. (II) e (III) são verdadeiras.
5. NDA

Ideia original de: Jhon Anthony Campos Arteaga

MO417 - Questão para a prova oral

Número: 

Enunciado: Dada a seguinte função f(n)=n ln n. Assinale a alternativa correcta:

1.  f(n)=O(n^(1- a)), onde  0<a<1
2.  f(n)=o(n^(1+a)), onde  0<a<1
3.  f(n)=O(n^(1+a)), onde  0<a<1
4.  f(n)=O(lg n)
5.  NDA

Ideia original de: Jhon Anthony Campos Arteaga