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.

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

---