Algoritmos de Busca

Algoritmos de Busca

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.

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


Vinicius dos Santos

Apenas um apaixonado por Ciência da Computação e forma com que ela pode transformar vidas!

Deixe uma resposta