Nesse post vamos praticar nossas habilidades por meio de exercícios sobre algoritmos de busca. Os exercícios podem ser resolvido em qualquer linguagem que suporte vetores. Recomenda-se que você use a linguagem C ou C++, visto que elas permitem maior controle dos endereços de memória e outros aspectos importantes.
Lembre-se também que é interessante que você use uma IDE de programação como o DEVcpp ou então o codeblocks.
Esses exercícios fazem parte de um conjunto maior de exercícios sobre estruturas de dados. Veja mais sobre isso aqui.
Busca sequencial e binária
1- Implemente os algoritmos de busca sequencial e de busca sequencial e inserção em C para vetores.
2- Compare a eficiência de procurar numa tabela ordenada sequencial, de tamanho n, e numa tabela desordenada de mesmo tamanho, pela chave key. Exiba os resultados com exemplos e número de comparações considerando os seguintes casos:
a) se nenhum registro com a chave key estiver presente;
b) se um registro com a chave key estiver presente e somente um for pesquisado;
c) se mais de um registro com a chave key estiver presente e se quisermos encontrar somente o primeiro;
d) se mais de um registro com a chave key estiver presente e quisermos encontrar todos eles.
3- Dado a estrutura de lista sequencial. Escreva um programa que realiza busca em uma estrutura de Lista ligada.
4- Considere uma tabela ordenada implementada como um vetor ou como uma lista duplamente ligada, de modo que a tabela possa ser pesquisada seqüencialmente, quer para trás, quer para frente. Suponha que um único ponteiro p aponte para o último registro recuperado com sucesso. A busca começa sempre no registro apontado por p, mas pode prosseguir em ambas as direções. Escreva um rotina, searchitable, p, key), para o caso de um vetor e de uma lista duplamente ligada a fim de recuperar um registro com a chave key e modificar p concomitantemente. Demonstre que o número de comparações de chaves nos dois casos, com e sem sucesso, é idêntico ao do método do exercício anterior, no qual a tabela pode ser pesquisada apenas em uma direção, mas o processo de varredura pode iniciar em um de dois pontos.
5- Modifique a busca seqüencial indexada de modo que, no caso de vários registros com a mesma chave, ela retorne o primeiro desses registros na tabela.
6- Considere a seguinte versão da busca binária, que presume que as chaves estejam contidas em k(l) até k{n) e que o elemento especial k(0) seja menor que toda chave possível;
mid = n / 2;
len = (n - l) / 2;
while (key != k(mid)) {
if (key < k(mid))
mid -= len / 2;
else mid += len / 2
if (len == 0) return (-l);
len /= 2;
} /* fim while */
return (mid);
7- Prove que esse algoritmo está correto. Quais as vantagens e/ou desvantagens desse método sobre o método apresentado nesta seção?
8- Implemente a busca binária utilizando recursividade e mostre em número de saltos sua eficiência.
Busca em árvores
1- Escreva um algoritmo de inserção eficiente para uma árvore de busca binária inserir um novo registro cuja chave não existe na árvore.
2- Verifique por simulação que, se os registros forem apresentados para a árvore de busca binária e para o algoritmo de inserção em ordem aleatória, o número de comparações de chave será 0(log n).
3- Escreva um algoritmo para eliminar um nó de uma árvore binária que substitua o nó por seu predecessor em ordem e não por seu sucessor em ordem.
Respostas
Estes exercícios estão em construção, se você sabe resolvê-los e quer compartilhar com a comunidade deixe nos comentários.
As respostas estarão disponíveis aqui
