Faculdade de Gestão de Recursos Naturais e Mineralogia
Curso de Tecnologias de Informação
ESTRUTURAS DE DADOS E ALGORITMOS
ÁRVORES DE PESQUISA BINÁRIAS E ESTRUTURAS LINEARES
EXERCÍCIOS RESOLVIDOS
Assinale com V ou F, as afirmações verdadeiras ou falsas, respectivamente:
a) (F) A remoção de um nó de uma árvore binária de nível 4, altera necessariamente o seu nível para 3.
b) (V) A remoção de um elemento num vector, pode implicar o deslocamento dos demais elementos.
c) (F) numa árvore de pesquisa binária, todos os nós da subárvore direita de um determinado nó, têm chaves
menores a este.
d) (V) Numa árvore de pesquisa binária, uma operação pode implicar a mudança da raiz da árvore.
e) (V) Uma lista pode ter implementação em array e em lista ligada.
f) (F) Top, Drop, Pop e Push são operações aplicáveis a uma pilha.
g) (V) A inserção e remoção na pilha só envolvem o topo.
h) (F) Ambas a fila e a pilha, obedecem à filosofia Last In, First Out (LIFO).
i) (V) Numa fila com um único elemento x, a operação dequeue ( ) torna a fila vazia.
j) (V) Numa fila com três elementos a,b,c, a operação enqueue(x) torna o tamanho da fila iguala a 4.
2.Explique o processo de inserção numa árvores de pesquisa binária.
A inserção de um novo elemento na árvore de pesquisa binária é dada da seguinte forma:
Receber um valor X a ser inserido
Caso a árvore esteja vazia, o elemento a ser inserido passa a ser o elemento raiz da
árvore.
Caso contrário, comparamos o valor da chave do novo elemento com a chave do
elemento raiz da árvore. Caso a chave do novo elemento seja menor, ele deve ser
inserido na subárvore esquerda. Caso ela seja maior, o elemento deve ser inserido
na subárvore direita. Essa comparação é realizada novamente com os elementos
seguintes, até que uma posição vazia é encontrada e o novo elemento é inserido.
3. O que é factor de balanceamento numa árvore de pesquisa binária?
O Factor de Balanceamento (FB) de um nó (p) é a diferença entre a altura da subárvore
esquerda em relação à subárvore direita.
1
Faculdade de Gestão de Recursos Naturais e Mineralogia
Curso de Tecnologias de Informação
ESTRUTURAS DE DADOS E ALGORITMOS
4. Dada a seguinte sequência de chaves, determine a árvore de busca obtida quando as chaves
são inseridas uma a uma segundo a ordem dada em uma árvore inicialmente vazia: 4, 2, 1, 3,
6, 5, 7.
