Atividade 05

LISTA 3

Belo Horizonte

LISTA 3

Trabalho apresentado a disciplina
Algoritmo e Estruturas de Dados, curso de graduação em Sistemas de Informação

Belo Horizonte

Exercícios
1. Considere as técnicas de pesquisa seqüencial, pesquisa binária e a pesquisa baseada em hashing.
a) Descreva as vantagens e desvantagens de cada uma das técnicas acima, dando um exemplo de situação na qual você usaria cada uma delas.

Pesquisa seqüencial
Algoritmo que procura em todo o conjunto de dados.
Vantagem: simplicidade
Desvantagem: Se o conjunto de dados for muito grande esta pesquisa fica inviável.

Pesquisa Binária
Seu algoritmo minimiza o numero de operações ao particionar o conjunto a cada passo.
Vantagem: busca mais rápida
Desvantagem: Quando o elemento não é encontrado.

Pesquisa baseada em hashing
Método que realiza um endereçamento direto de um valor em uma tabela.
Vantagem: O método de armazenar os dados é basicamente o mesmo de localizar.
Desvantagem: Há possibilidades de ocorrer colisões de endereço.

b) Dê a ordem do pior caso e do caso médio de tempo de execução para cada método

Pesquisa seqüencial
Pior caso: O(1)
Caso médio: O(n)

Pesquisa Binária
Pior caso: O(1)
Caso médio: O(logn)

Pesquisa baseada em hashing
Pior caso:
Caso médio:

2. Desenhe a árvore binária de pesquisa que resulta da inserção sucessiva das chaves Q U E S T A O F C I L numa árvore inicialmente vazia.

3. Desenhe as árvores resultantes das retiradas dos elementos E e depois U da árvore obtida na questão anterior.

4. Escreva, em C# ou pseudocódigo, um método iterativo que faça a busca de um elemento em uma árvore binária de pesquisa. Este método deve retornar o nodo encontrado ou nulo se ele não existir.
Esta em python
# 'no' refere-se ao nó-pai, neste caso def arvore_binaria_buscar(no, valor): if no