tha

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