Estrutura de dados

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´aximo igual 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, o fator 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 de n´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˜ao anterior, 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 de busca. 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 15