Trabalho de Algoritimos e Estrutura de Dados

FACULDADE COTEMIG
BACHARELADO EM SISTEMAS DE INFORMAÇÃO
Disciplina: Algoritmos e Estrutura de Dados I
Professor(a): Virgilio Borges de Oliveira
TERCEIRA LISTA DE EXERCÍCIOS
Aluno(a): Michael Douglas Rodrigues Almeida
________________________________________________________________
Questão 1
Faça uma análise comparativa entre vetores ordenados,, listas encadeadas, árvores binárias de pesquisa e tabela hash, no que diz respeito inserção,remoção e pesquisa de chaves. Fale sobre as vantagens e desvantagens de cada um e como ocorrem.
 Lista encadeada
Inserção : As chaves podem ser inseridas no inicio ou no fim!
Remoção: Remoção pode ser realizada com todos elementos.
Pesquisa: A pesquisa é linear
Vantagens: facilidade para inserir valores
Desvantagens: dificuldades na pesquisa
 Árvore Binárias
Inserção : Não pode conter chaves duplicadas, a inserção sempre é realizada nos últimos nodos;
Remoção: Pode acontecer em três casos, quando o nó tem filhos, não tem filhos e tem somente um filho.
Pesquisa: Se a arvore estiver ordenada, valores menores na esquerda e menores na direita a pesquisa é (log n)
Vantagens: Organização, pesquisar, inserir valores já organizados.
Desvantagens:
 Tabela Hash
Inserção : o valor inserido passa por uma transformação
Remoção: só remover o valor pelo indice
Pesquisa: pesquisa mais eficiente
Vantagens: pesquisa
Desvantagens: gasto de memoria

 Vetor Ordenado
Inserção : o valor inserido passa por uma transformação
Remoção: só remover o valor pelo indice
Pesquisa: pesquisa mais eficiente
Vantagens: pesquisa
Desvantagens: gasto de memoria

b) Mostre a seqüência de chaves impressa pelo passeio Em Ordem.
RESPOSTA: 4 , *, 8, -, 3, +, 2, *, 7, /, 2
c) Mostre a seqüência de chaves impressa pelo passeio Pré-Ordem.
RESPOSTA: *,4,/,+,-,8,3,*,2,7,2
d) Mostre a seqüência de chaves impressa pelo passeio Pós-Ordem.
RESPOSTA: 4,8,3,-,2,7,*,+,2,/,*
Questão 3
a) Faça a inserção das seguintes chaves em uma árvore