Estrutura de dados

Disponível somente no TrabalhosFeitos
  • Páginas : 3 (611 palavras )
  • Download(s) : 0
  • Publicado : 17 de março de 2013
Ler documento completo
Amostra do texto
Estrutura de Dados - 1o. per´ıodo de 2012
Gabarito da Segunda Avalia¸c˜ao `a Distˆancia
1. (1,0) Falso ou verdadeiro? (Justifique.) O fator de carga de qualquer tabela de dispers˜ao
´e no m´aximoigual a 1.
Resposta: Falso. O fator de carga ´e dado pelo n´umero de chaves dividido pelo n´umero
de compartimentos da tabela. Logo, se o n´umero de chaves for maior que o de compartimentos,
ofator de carga ser´a maior que 1.
2. (1,5) Desenhe uma ´arvore bin´aria de busca CHEIA COM ALTURA 4, colocando dentro
de cada n´o o valor de sua chave. As chaves s˜ao 1, 2, . . . , k (k ´e o n´umero den´os da
´arvore, que ´e um valor que vocˆe deve deduzir). A seguir, escreva a sequˆencia de chaves
que corresponde ao percurso em PR´E-ORDEM desta ´arvore.
Resposta: O percurso em pr´e-ordem desta´arvore ´e: 8 4 2 1 3 6 5 7 12 10 9 11 14 13 15.
8
6
4
1 3
2
5 7
14
12
9 11
10
13 15
3. (1,5) Suponha que vocˆe deseja remover um n´o de uma ´arvore bin´aria de busca. Ap´os
remˆove-lo,como vocˆe deve reestruturar a ´arvore de modo que ela continue sendo uma
´arvore bin´aria de busca? Dˆe um exemplo que mostre seu racioc´ınio. (Sugest˜ao: use a
´arvore que vocˆe desenhou na quest˜aoanterior, removendo um n´o qualquer e reestruturandoa.)
Resposta: Se o n´o removido for uma folha, n˜ao h´a necessidade de reestrutura¸c˜ao, pois a
´arvore resultante continuar´a sendo bin´aria debusca. Em caso contr´ario (remo¸c˜ao de um
n´o interno), podemos:
(a) substituir o n´o removido pelo n´o mais `a direita (de maior valor) de sua sub´arvore
esquerda (se este n´o for uma folha), ou(b) substituir o n´o removido pelo n´o mais `a esquerda (de menor valor) de sua sub´arvore
direita (se este n´o for uma folha).
No exemplo da ´arvore da quest˜ao anterior, ao removermos o n´o 12,por exemplo, obter´ıamos
uma das duas ´arvores abaixo, dependendo da estrat´egia que adot´assemos ((a) ou (b)).
8
6
4
1 3
2
5 7
14
13
9 11
10
15
8
6
4
1 3
2
5 7
14
11
9
10
13...
tracking img