Exercícios de Fixação 03 - Análise de Algoritmos de Busca

Prévia do material em texto

ANÁLISE DE ALGORITMOS
Bacharelado em Ciências da Computação
Lista de Exercícios de Fixação 03
Análise de Algoritmos de Busca
1. Considere as técnicas de pesquisa sequencial, pesquisa binária e pesquisa baseada em
hashing. Descreva as vantagens e desvantagens de cada uma dessas técnicas, indicando em
que situações, são de fato viáveis.
2. Explique por que a busca binária:
a. É mais eficiente do que a busca sequencial.
b. Só pode ser efetuada em um array.
3. Considere a lista linear sequencial de inteiros no vetor, a seguir.
2 4 6 8 10 12 14 16
 
a. Considerando o método da busca binária:
1. Quantas comparações (e com quais chaves) são necessárias na busca pelo valor 15?
2. Idem para o inteiro 6.
b. Considerando a Busca Sequencial: 
1. Quantas comparações (e com quais chaves) são necessárias pelo valor 15?
2. Idem para o inteiro 6.
c. Generalize o número máximo de comparações na Busca Binária e na Busca Sequencial,
considerando o tamanho do vetor igual a n. 
4. Suponha que você tenha uma árvore binária na qual estão armazenadas uma chave em cada
nodo. Suponha também que a árvore foi construída de tal maneira que, ao caminhar nela na
ordem central, as chaves são visitadas em ordem crescente. Sendo assim, qual propriedade
entre as chaves deve ser satisfeita para que isso seja possível?
5. Em uma tabela hash com 100 entradas, as colisões são resolvidas usando listas encadeadas.
Para reduzir o tempo de pesquisa, decidiu-se que cada lista seria organizada como uma
árvore binária de pesquisa sem balanceamento. A função utilizada é h(k) = k mod 100.
ANÁLISE DE ALGORITMOS
Bacharelado em Ciências da Computação
Infelizmente, as chaves inseridas seguem o padrão ki = 50i, onde ki corresponde à i-ésima
chave inserida.
a. Mostre a situação da tabela após a inserção de ki, com i = 1, 2, …, 8 (esquematize);
b. Considerando a busca nessa tabela hash, qual é a complexidade para o pior caso?
6. Tabelas de dispersão (tabelas hash) armazenam elementos com base no valor absoluto de
suas chaves e em técnicas de tratamento de colisões. As funções de dispersão transformam
chaves em endereços-base da tabela, ao passo que o tratamento de colisões resolve conflitos
em casos em que mais de uma chave é mapeada para um mesmo endereço-base da tabela.
Suponha que uma aplicação utilize uma tabela de dispersão com 23 endereços-base (índices
de 0 a 22) e empregue h(x) = x mod 23 como função de dispersão, em que x representa a
chave do elemento cujo endereço-base deseja-se computar. Inicialmente, essa tabela de
dispersão encontra-se vazia. Em seguida, a aplicação solicita uma sequência de inserções de
elementos cujas chaves aparecem na seguinte ordem: 44, 46, 49, 70, 27, 71, 90, 97, 95.
a. Apresente o conjunto das chaves envolvidas em colisões.
b. Assuma que a tabela de dispersão trate colisões por meio de encadeamento exterior.
Esboce a tabela de dispersão para mostrar seu conteúdo após a sequência de inserções
referida.
7. Qual é o pior tempo para inserir n elementos em uma tabela hashing inicialmente vazia, com
colisões sendo resolvidas por listas encadeadas? Qual seria o melhor caso?
8. Considerando que as chaves inseridas em um Hashing não provocaram colisão,
independente do algoritmo, podemos dizer que a pesquisa por uma chave na tabela será de
ordem de complexidade constante, ou seja, T(n) = 1? Podemos dizer que este algoritmo é
ótimo? Justifique.
	Lista de Exercícios de Fixação 03