[Exercícios] Algoritmos de Busca #1



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 seqüencial, 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.

[Exercícios] Algoritmos de Busca #1 [Exercícios] Algoritmos de Busca #1 Reviewed by Vinicius dos Santos on 07:01:00 Rating: 5

Nenhum comentário

Escreve ai sua opinião!