Lista de Exercicios EDA

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

LISTA DE EXERCÍCIOS DE ESTRUTURA DE DADOS E ALGORITMOS I
HEAPS, FILAS DE PRIORIDADE E BUSCAS
1. (2004) Considere um vetor com os seguintes valores armazenados:
[1 2 10 15 20 23 25 30 40 70 80 100]
Mostre os passos utilizados para se buscar o valor 23 no vetor acima,
considerando-se o método de busca por interpolação. Quantas comparações
foram feitas até que o elemento seja encontrado?
2. (2004) Considere um vetor com os seguintes elementos (nesta ordem):
40, 10, 20, 15, 60, 80, 30, 12
Este vetor atende às propriedades de um heap? Se não, organize os elementos de
forma que estas propriedades sejam atendidas.
3. (2005) Considere um vetor com os seguintes valores armazenados:
10 20 25 30 35 38 60 80
(a) Mostre os passos utilizados para se buscar o valor 20 no vetor acima,
considerando-se o método de busca por interpolação. Quantas comparações
foram feitas até o elemento ser encontrado?
(b) Mostre os passos utilizados para se buscar o valor 20 no vetor acima,
considerando-se o método de busca binária. Quantas comparações foram
feitas até o elemento ser encontrado?
4. (2005) Considere uma implementação de fila de prioridade máxima em que os
elementos são mantidos em uma lista ordenada de forma decrescente pela
prioridade dos elementos. Compare esta implementação com uma
implementação de filas de prioridade utilizando heaps em relação à eficiência
das operações de inserção de um elemento na fila de prioridades e de remoção
do elemento de maior prioridade.
5. (2005) Considere um vetor com os seguintes valores armazenados:
5 10 20 35 45 55 80 200
(a) Mostre os passos utilizados para se buscar o valor 55 no vetor acima,
considerando-se o método de busca por interpolação. Quantas comparações
foram feitas até o elemento ser encontrado?
(b) Mostre os passos utilizados para se buscar o valor 55 no vetor acima,
considerando-se o método de busca binária. Quantas comparações foram
feitas até o elemento ser encontrado?
6. (2005) Responda às questões abaixo:
(a) Mostre um exemplo em que a busca por interpolação faz o maior número de
consultas (pior caso) para se procurar um determinado valor em um vetor
com cinco números inteiros (mostre o vetor e o valor que será procurado).
(b) Mostre um exemplo em que a busca binária faz o maior número de consultas
(pior caso) para se procurar um determinado valor em um vetor com cinco
números inteiros (mostre o vetor e o valor que será procurado).
7. (2005) Responda às questões abaixo:
(a) O vetor abaixo representa um heap máximo válido? Justifique.
50 40 30 20 34 35
(b) Em um heap máximo com n elementos, considerando-se uma
implementação com vetor, o elemento de menor chave estará
necessariamente na posição n deste vetor? Justifique.