MO417 - Questão para a prova oral

Número:

Enunciado: Em uma implementação de cache têm-se um espaço fixo que permite armazenar pares compostos por (valor, numero_de_acessos).  Existem algumas restrições quanto à implementação dessa cache:

1. deve sempre conter os elementos mais acessados
2. o tempo para encontrar um elemento qualquer e o tempo para encontrar outro elemento qualquer devem ser os mais próximos possíveis
3. o tempo para encontrar um elemento e o tempo para descobrir se um elemento não se encontra na cache devem ser os mais próximos possíveis
4. periodicamente os elementos menos acessados devem ser descartados, sendo que a eficiência para encontrar esses elementos nao é prioritária em relação aos outros requisitos

Qual é a melhor estrutura de dados a ser utilizada para representar essa cache?

A) Vetor ordenado crescentemente em função do número de acessos.
B) Árvore binária balanceada ordenada pelo número de acessos.
C) Árvore binária balanceada ordenada pelo valor.
D)Vetor ordenado decrescentemente em função do número de acessos.
E) N.D.A

Ideia original de: Thaís Harumi Ussami

MO417 - Questão para a prova oral

Número:

Enunciado: Com relação aos algoritmos de divisão e conquista e programação dinâmica, indique a alternativa INCORRETA: 

A) Os algoritmos de divisão e conquista resolvem repetidamente os subproblemas comuns. 
B) Programação dinâmica é aplicada para encontrar uma solução com valor ótimo, que é computado a partir de combinações de soluções ótimas previamente calculadas e memorizadas.
C) Os algoritmos de divisão e conquista são mais indicados em problemas que existem sobreposições de subproblemas.
D) A característica de memorização de soluções previamente calculadas da programação dinâmica é útil quando o número de subproblemas repetidos cresce exponencialmente de acordo com o tamanho da entrada.
E) N.D.A

Ideia original de: Thaís Harumi Ussami

MO417 - Questão para a prova oral

Número:

Enunciado: Considere as seguintes informações sobre o algoritmo de seleção RANDOMIZED-SELECT, cujo código segue abaixo:

RANDOMIZED-SELECT(A,p,r,i)
if (p == r)
   return A[p]
q = RANDOMIZED-PARTITION(A,p,r)
k = q-p-1
if (i == k)
   return A[q]
else if (i < k)
   return RANDOMIZED-SELECT(A,p,q-1,i)
else return RANDOMIZED-SELECT(A,q+1,r,i-k)

I. O algoritmo executa em tempo linear, uma vez que adota premissas sobre a entrada.
II. O algoritmo realiza primeiro uma ordenação dos elementos para então selecionar o i-ésimo menor elemento do arranjo A[p...r].
III. Para determinar qualquer estatística de ordem, considerando elementos distintos do arranjo, o tempo esperado é linear.
IV. O algoritmo utiliza a técnica de divisão e conquista para retornar o i-ésimo menor elemento do arranjo A[p...r].

Assinale a alternativa correta:

A) I e II estão correta.
B) I, III e IV estão corretas.
C) I e III estão corretas.
D) III e IV estão corretas.
E) N.D.A

Ideia original de: Thaís Harumi Ussami

MO417 - Questão para a prova oral

Número:

Enunciado: Com relação aos algoritmos Heapsort e Quicksort, assinale a alternativa correta:

A) Assim como Mergesort, Heapsort baseia-se na técnica de divisão e conquista.

B) Heapsort e Quicksort não são algoritmos estáveis, uma vez que a ordem relativa dos elementos iguais não é alterada após a ordenação.

C) No pior caso, Quicksort tem um desempenho superior a execução de Mergesort.

D) O tempo de execução do melhor caso de Quicksort é o mesmo tempo de execução do Heapsort  para um arranjo já ordenado em ordem crescente.

E) N.D.A

Ideia original de: Thaís Harumi Ussami

MO417 - Questão para a prova oral

Número:

Enunciado: Considere as seguintes recorrências:

T1(n) = 1, n = 1

        = T1(n/2) + n, n > 1

T2(n) = 1, n = 1

        = T2(n/2) + n^2, n > 1

T3(n) = 1, n = 1

        = T3(n/2) + n^3, n > 1

Com relação às ordens de crescimento das funções, é correto afirmar que: 

A) T2(n) > T3(n) > T1(n)

B) T2(n) > T1(n) > T3(n)

C) T3(n) > T2(n) > T1(n)

D) T3(n) > T1(n) > T2(n)

E) N.D.A

Ideia original de: Thaís Harumi Ussami

MO417 - Questão para a prova oral

Número:

Enunciado: Considere uma variação do Bubblesort com o seguinte funcionamento: Dado um vetor A[1...n], nas iterações ímpares o bubblesort comum é executado, já nas iterações pares o bubblesort é executado no sentido contrário, ou seja, do final do vetor para o começo. Dado a entrada do pior caso do algoritmo de Bubblesort comum, qual o tempo de execução para essa entrada no algoritmo de Bubblesort alterado?

A) ϴ(n)

B) ϴ(n²)

C) ϴ(nlgn)

D) ϴ(n³)

E) N.D.A

Ideia original de: Thaís Harumi Ussami