MO417 - QUESTÃO PROVA ORAL

Numero:

Enunciado: Dado o procedimento FUNCTION (A) abaixo, podemos afirmar que:

FUNCTION (A)

1             if (A.length%2!=0)

2                             max=min=A[1]

3                             iniciaFor=2

4             elseif(A[1] > A[2]){

5                             max = A[1]

6                             min = A[2]

7                             iniciaFor=3

8             else       max=A[2]

9                           min=A[1]

10                         iniciaFor=3

11           for (i= iniciaFor;i<A.length;i=i+2)

12                           if(A[i]>A[i+1])

13                                          if(max<A[i])

14                                                          max=A[i];

15                                          if (min>A[i+1])

16                                                          min=A[i+1];

17                           elseif(max<A[i+1])

18                                          max=A[i+1]

19                                           if (min>A[i])

20                                              min=A[i]

21           RETURN (max,min)

               

a) Busca os elementos máximo e mínimo independentemente, fazendo no máximo 3(n-3)/2 comparações.

b) Busca os elementos máximo e mínimo independentemente, fazendo no máximo 2n – 2 comparações.

c) Busca os elementos máximo e mínimo simultâneos, fazendo no máximo  (3n)/2 -2 comparações.

d) Busca os elementos máximo e mínimo simultâneos, fazendo no máximo 3⌊n/2⌋ comparações.

e) NDA

Ideia original de: Lucas Oliveira Batista

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Um estudante de bioinformática possui uma lista com N enzimas e um arranjo A (ilustrado abaixo) que contém inibidores de enzimas associados a uma enzima específica.

1	2	3	4	5	6	7	8	9	10	…	N
A	B	C	F	L	A	A	H	J	Y	…	Z

Tomando os 10 primeiros elementos como exemplo, o estudante deseja ordenar os inibidores de enzimas, de forma que elementos repetidos na entrada tenha a mesma ordem de precedência na saída e sem utilizar uma estrutura de dados adicional, da seguinte forma:

1	2	3	4	5	6	7	8	9	10
A	A	A	B	C	F	H	J	L	Y

Qual algoritmo de ordenação poderia ser utilizado?

a) Bucket-sort, Radix-sort e Heap-sort.

b) Todos os algoritmos classificados como divisão e conquista.

c) Selection-sort, Insertion-sort e Quick-sort.

d) Counting-sort, Insertion-sort e Heap-sort.

e) NDA

Ideia original de: Lucas Oliveira Batista

MO417 - QUESTÃO PARA PROVA ORAL

Número:

Enunciado: Dada a seguinte função recursiva:

        Function (n)

              if (n ≤ 1)

                    PARAR

              else

                    Ativar processo X

                    Function (n/2)

                 

A fórmula de recorrência que representa esta função é:

       
          T(n) = 1 + T(n/2),       n>1
          T(1) = 0

Sendo T(n) o número de ativações do processo X, podemos afirmar que:

a) A recorrência não pode ser resolvida pelo método mestre, pois não existe a constante “a”.

b) T(n) = Θ (lg n), logo o processo x será ativado lg n vezes.

c) T(n) = Θ (n lg n), logo o processo x será ativado n lg n vezes.

d) T(n) = Θ (2ⁿ), logo o processo x será ativado 2ⁿ vezes.

e) NDA

Ideia original de: Lucas Oliveira Batista

MO417 - Questão para a prova oral

Número:

Enunciado: Sobre a notação O, Ω e algoritmos, assinale V para verdadeiro e F para falso:

(  ) O (lê-se o maiúsculo) fornece um limite assintótico superior e é formalmente definido como O(g(n)) = {f(n): existem constantes positivas c e n₀ tais que 0 ≤ f(n) ≤ cg(n) para todo n>n₀}
(  ) Ao contrário de O (lê-se o maiúsculo), Ω fornece um limite assintótico inferior e é formalmente definido como Ω(g(n)) = {f(n): existem constantes positivas c e n₀ tais que 0 ≤ cg(n) < f(n) para todo n>n₀}
(  ) Um limite inferior para um problema P é uma função h(n). Todo algoritmo que resolve P efetua pelo menos Ω(h(n)) operações.
(  ) Dado um problema P, se P é Ω(h(n)) e encontramos um algoritmo A com complexidade O(h(n)) entao A é um algoritmo ótimo para P.
(  ) O tempo de execução do algoritmo selection_sort para o pior caso é O(n²) e para o melhor caso O(n)


a. V - V - V F - V
b. F - F - F - V - F
c. V - F - F - F - V
d. V - F - V - V - F
e. NDA

Ideia original de: Lucas Oliveira Batista

MO417 - Complexidade de Algoritmos I

Blog com a finalidade de auxiliar na etapa de aprendizagem pós aula.