MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Dado um vetor de n elementos inteiros, qual é a quantidade máxima de comparações necessárias para se encontrar, simultaneamente, tanto o elemento de menor valor quanto o elemento de maior valor?

A) n - 1

B) n lg n

C) 2n - 2

D) ⌊3n/2⌋

E) N.D.A.

Ideia original de: Tiago Pedroso da Cruz de Andrade

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Com relação ao QUICK SORT, qual das afirmações abaixo está INCORRETA?

A) Ele é local e não estável.

B) O pior caso ocorre quando o menor item do vetor é selecionado como pivo.

C) Ele possui complexidade O(n^2) para o pior caso.

D) O melhor caso ocorre quando a partição produz dois subproblemas com a mesma quantidade de elementos.

E) N.D.A.

Ideia original de:  Tiago Pedroso da Cruz de Andrade

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Dada a recorrência T(n) = 2T(n/2) + n lg n, qual é o seu limite assintótico?

A) n lg n

B) n

C) n^2

D) n lg^2 n

E) N.D.A.

Ideia original de:  Tiago Pedroso da Cruz de Andrade

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Dadas as recorrências abaixo, qual NÃO pode ser resolvida pelo método Mestre?

A) T(n) = 9T(n/3) + n

B) T(n) = T(2n/3) + 1

C) T(n) = 3T(n/4) + n lg n

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

E) N.D.A.

Ideia original de:  Tiago Pedroso da Cruz de Andrade

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Dado um vetor com n inteiros quaisquer ordenado crescentemente, qual das funções abaixo melhor reflete o tempo de execução para verificar de forma correta e eficiente se um dado valor inteiro x esta contido neste vetor?  

A) log n 

B) n log n 

C) n 

D) n^2 

E) N.D.A.

Ideia original de:  Tiago Pedroso da Cruz de Andrade