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