Pesquisa binária Teoria dos Grafos e Análise de Algoritmos - Exercícios

Prévia do material em texto

Pesquisa binária – Teoria dos Grafos e Análise de Algoritmos 
Exercícios
1. A estrutura de dados de árvore apresenta grande versatilidade. Pode ser aplicada
na solução de um leque de problemas, como em indexação de bancos de dados, em
buscas, em estruturas de diretórios em sistemas de arquivos, entre outros.
Considerando uma árvore binária de busca, qual destas é uma de suas
propriedades?
Você acertou!
B. A subárvore esquerda de um nó contém os nós com chaves menores ou iguais que a
do nó.
Para uma árvore agir como uma árvore de busca, os valores armazenados em
cada nó devem ser maiores que qualquer outro que esteja na subárvore esquerda
e menores do que os salvos em subárvores à direita. Logo, a subárvore esquerda
de   um   nó   contém   os   nós   com   chaves   menores   ou   iguais   ao   nó   referente;   a
subárvore direita de um nó contém os nós com chaves maiores que o nó referente;
e as subárvores esquerda e direita também devem ser uma árvore de pesquisa
binária.
De acordo com a propriedade de uma árvore de busca, uma subárvore à esquerda
não pode receber chaves maiores que o nó. Além disso, em uma árvore binária de
busca,   cada   nó   pode   ter,   no   máximo,   dois   filhos.   Sobre   o   tipos   e   os   valores
armazenados nos nós, não exitem restrições: pode ser tanto uma string como um
valor numérico qualquer, e, quando se trata de valores numéricos, também não
existem restrições se o valor é positivo ou negativo.
2. Uma árvore binária de busca é conhecida pela sua eficiência quando é necessária
a pesquisa de algum valor, seguindo as regras de buscas, ramificando para a
esquerda e para a direita.
Sabendo disso, de acordo com a árvore na imagem, determine qual caminho a
chave de busca percorreu para pesquisa do valor 87 e se este existe ou não.
Você acertou!
D. 
Visitou chave 70.
Visitou chave 90.
Visitou chave 83.
Visitou chave 85.
Visitou chave 89.
Resultado: falha.
Considerando   que   a   raiz   da   árvore   corresponde   ao   valor   70,   para   o   número
procurado (87), precisaremos caminhar pela subárvore à direita. Em seguida, será
visitado nó de chave 90, porém o valor procurado ainda não é esse, e, como 87 é
menor   que   90,   será   explorada   à   subárvore   à   esquerda   do   nó   de   chave   90,
resultando   em   uma   visita   ao   nó   de   chave   83.   Como   87   é   maior   que   83,
seguiremos à procura pela subárvore à direita desse nó, chegando ao nó de chave
85. O valor 87 é maior que 85, fazendo com que seja realizada a leitura ao último
nó dessa ramificação: o nó de chave 89.
Como não existem mais elementos a serem explorados a partir do nó de chave 89,
o resultado obtido é de falha, pois o elemento 87 não existe.
3. Sempre que vimos uma árvore, presumimos a ordem em que seus elementos
foram adicionados. Dessa forma, conforme a imagem utilizada no exercício anterior,
defina uma possível ordem do vetor que culminou na árvore apresentada,
lembrando que o primeiro valor corresponde à raiz da árvore.
Você acertou!
B. [70,90,4,114,2,23,83,116,72,15,85,89,63].
Podemos verificar a ordem de cada elemento fazendo uma pequena inserção em
uma   árvore   abstrata.  Ao   criar   uma   árvore   binária   sem   balanceamento,   temos
sempre que considerar sua forma de organizar seus valores. Logo, se o valor 89,
que é uma folha, for adicionado antes do valor 85, o valor 89 que antes não tinha
nenhuma ramificação passará a ter o nó 85 como subárvore esquerda.
Seguindo   esse   raciocínio,   podemos   estabelecer   uma   possível   ordem   como:
[70,90,4,114,2,23,83,116,72,15,85,89,63].
4. Uma árvore binária de busca, como o próprio nome sugere, é uma estrutura de
dados que armazena dados de maneira que permita a realização de busca binária.
Essa busca segue o paradigma de divisão e conquista e acaba tendo uma eficiência
melhor do que uma busca linear.
Existem duas abordagens para realizar a implementação dessa busca: a
implementação recursiva e iterativa. Qual a principal diferença entre essas
implementações?
Você acertou!
C. Na abordagem recursiva, um nó definido como base nele próprio realiza a repetição
dos seus passos invocando a si próprio, executando todos os seus passos novamente até
encontrar o valor buscado. Diferentemente da busca recursiva, a busca iterativa considera
as ramificações de maneira explícita de cada nó para percorrer seus nós, pois não há
uma chamada interna para a mesma função.
A  abordagem   recursiva   realiza   autorreferência,   ou   seja,   ocorre   quando   algo   é
definido em termos de si mesmo. No caso da árvore, um nó é definido com base
nele próprio até achar o valor buscado; já no método iterativo, a busca é realizada
percorrendo   explicitamente   todos   os   nós   da   árvore   até   se   encontrar   o   valor
buscado.
Além disso, apenas o método iterativo usa laços de repetição, como while e for. E,
apesar   de   serem   abordagens   diferentes,   ambas   visitam   os   mesmos   nós   no
processo de busca por determinado valor.
5. Em termos de alocação de memória, podemos implementar uma árvore de busca
binária utilizando alocação dinâmica ou alocação estática.
Considerando a alocação estática, como ocorre a representação de uma árvore de
pesquisa binária em um vetor?
Você acertou!
A. 
1- O nó raiz deve ficar na posição inicial do vetor.
2-  Para cada nó em determinada posição  i  de um vetor,  seu filho esquerdo ficará na
posição 2*i + 1, e seu filho direito ficará na posição 2*i + 2.
As árvores também podem ser implementadas sob listas fixas ou estáticas, que
ocorrem por meio da distribuição dos nós da árvore ao longo de um vetor (array).
Essa distribuição ocorre da seguinte forma: o nó raiz será o primeiro elemento do
vetor, e, para cada nó em determinada posição i do vetor, seu filho esquerdo ficará
na posição 2*i + 1, e seu filho direito ficará na posição 2*i + 2.
	Pesquisa binária – Teoria dos Grafos e Análise de Algoritmos
	Exercícios