ATIVIDADE 02 DE ESTRUTURA DE DADOS

Prévia do material em texto

UNIVERSIDADE ABERTA DO BRASIL
Agosto de 2016
Curso: Licenciatura em Computação
Disciplina: Estrutura de Dados
Professor: André Luiz
Aluna: Viviane Bernardino
ATIVIDADE II
Relacionado ao método de busca, como funciona o método de comparação?
Compara a chave com cada item na array, até encontrar um item de dado cujo valor é igual o valor da chave.
Crie o algoritmo e o programa (Pode ser Java, pascal ou C) de acordo com as estruturas:
a) Nome, data de nascimento, sexo, determinar se a pessoa é maior de 18 anos;
b) Implemente o programa para calcular fatorial. e execute-o para 5, 10 e 20.
Conceitue a estrutura árvore e qual a sua diferença com relação a vetores e listas?
Árvore é uma estrutura com formação hierárquica que tem como base a topologia em árvore, onde o primeiro elemento é denominado a Raiz da estrutura, com base nela são distribuídos os nós (elementos pós-raiz) e destes são gerados os nós-filhos, sendo o nó antecedente o nó-pai. A Raiz é o único elemento que não possui um Pai (elemento antecedente). É dado esse nome a este tipo de estrutura pela sua característica que, pela sua configuração, se assemelha a uma árvore, onde as suas ramificações tendem a convergir para uma raiz, ou a sua origem.
Vetores ou arrays são estruturas de dados lineares e estáticas, isto é, são compostas por um número fixo (finito) de elementos de um determinado tipo de dados. O tempo de acesso aos elementos de um vetor é muito rápido, sendo considerado constante: o acesso aos elementos é feito pelo seu índice no vetor. Porém, a remoção de elementos pode ser custosa se não for desejável que haja espaços "vazios" no meio do vetor, pois nesse caso é necessário "arrastar" de uma posição todos os elementos depois do elemento removido.
Lista é uma estrutura de dados linear. Uma lista ligada, também chamada de encadeada, é linear e dinâmica, é composta por nós que apontam para o próximo elemento da lista, o último elemento apontará para nulo. Para compor uma lista encadeada, basta guardar seu primeiro elemento.
Explique as operações disponibilizadas através da interface TAD da estrutura de dados Pilha e explique. (Pode ser com a ajuda gráfica):
a) Criar a pilha
b) Inserir os valores 15 e 42 na Pilha
c) Remover o elemento do topo da Pilha
d) Consultar o topo da pilha
e) Verificar se a pilha esta vazia
f) Consultar o tamanho da pilha
Criar a pilha
	
	
	
 Criado uma Pilha = // Cria uma pilha vazia 
 pilha Criar ();
Inserir os valores 15 e 42 na Pilha
	
	15
	42
 Inserido dois valores diferentes = //insere um novo elemento no topo da pilha.
 int Push (Pilha p, tipo_base dado);
 
Remover o elemento do topo da Pilha
	
	15
	42
 
 Pilha Removida = //Remove e retorna o elemento do topo
 tipo_base Pop (Pilha p);
Consultar o topo da pilha
	
	
	42
 
 Topo da pilha = // consulta pelo elemento que se encontra no topo
 tipo_base Top (Pilha p); 
 
Verificar se a pilha esta vazia
	
	
	42
 
 Pilha não esta vazia = /* Retorna 1 se não tem mais elementos na pilha, ou 0 
 em caso contrario.*
 int Vazia (Pilha p).
Consultar o tamanho da pilha 
	
	
	42
 Tamanho da pilha = // Retorna a quantidade de elementos na pilha.
 int Tamanho (Pilha p)
Explique:
a) As Árvores
Uma árvore é um tipo abstrato de dados que armazena elementos de maneira hierárquica. Como exceção do elemento do topo, cada elemento tem um elemento pai e zero ou mais elementos filhos. Uma árvore normalmente é desenhada colocando-se os elementos dentro de elipses ou retângulos e conectando pais e filhos com linhas retas. Normalmente o elemento topo é chamado de raiz da árvore, mas é desenhado como sendo o elemento mais alto, com todos os demais conectados abaixo (exatamente ao contrário de uma árvore real).
b) A Busca Avançada
A eficiência alcançada para resolver o problema da busca ou recuperação de informação a partir de uma estrutura de dados é um indicador da eficiência da estrutura. Nesta parte são apresentados métodos específicos de busca que objetivam reduzir a complexidade em relação aos métodos de busca padrão apresentados em partes anteriores.
c) Métodos de Ordenação (Bolha, Seleção, Inserção e QuickSort)
O Método Bolha - É bastante simples e intuitivo. Nesse método os elementos da lista são movidos para as posições adequadas de forma contínua, assim como uma bolha move-se num líquido.
O Método Seleção - Tem como ponto forte o fato de que ele realiza poucas operações de swap. Seu desempenho, em termos absolutos, costuma ser superior ao do Método Bolha, mas inferior ao do Método Inserção. 
Método Inserção - Nesse método consideramos que a lista está dividida em parte esquerda, já ordenada, e parte direita, em possível desordem. Além disso, os elementos da parte esquerda são todos menores ou iguais aos elementos da parte direita. O Método Inserção, também conhecido como Inserção Direta, é bastante simples e apresenta um desempenho significativamente melhor que o Método Bolha, em termos absolutos.
Quicksort - Adota a estratégia de divisão e conquista. A estratégia consiste em rearranjar as chaves de modo que as chaves "menores" precedam as chaves "maiores". Em seguida o Quicksort ordena as duas sublistas de chaves menores e maiores recursivamente até que a lista completa se encontre ordenada.
d) Temos como Percursos da Arvore a (pre-ordem, in-ordem e pos-ordem) explique cada um.
Pré-ordem: Você deve visitar primeiro a raiz, depois a sub-árvore esquerda e por último a sub-árvore direita.
Em-ordem: Você deve visitar primeiro a sub-árvore esquerda, depois a raiz e por último a sub-árvore direita.
Pós-ordem: Você deve visitar primeiro a sub-árvore esquerda, depois a sub-árvore direita e por último a raiz. 
Crie uma árvore binária de acordo com a seguinte sequência de números, na ordem:{20, 5, 12, 36, 27, 45, 9, 2, 6, 17, 40}.
a) Remova os nós: 9, 5, e 20. Mostre a árvore resultante após cada remoção.
b) Inclua os seguintes números na ordem {3, 6, 9, 11, 10, 14, 12}. Mostre a árvore resultante em cada inclusão.
a) 
c)