2020 2 AV2 Teoria (1)

Prévia do material em texto

CENTRO UNIVERSITÁRIO CARIOCA – UNICARIOCA TEORIA EM GRAFOS – PROF.: JÚLIO SILVEIRA – 2020/2 AV2
· ATENÇÃO: O TRABALHO É INDIVIDUAL!
TRABALHO COM INDÍCIOS DE SIMILARIDADE, TODOS SERÃO AVALIADOS COM GRAU ZERO.
· FORMA DE ENTREGA: postagem de arquivo EXCLUSIVAMENTE no formato PDF, no link disponível no AVA.
· PRAZO PARA ENTREGA: até a data indicada no mesmo link para envio do arquivo com a solução.
· FORMATO DO TRABALHO: arquivo em formato PDF, gerado por um editor eletrônico de textos e gráficos para os grafos e/ou indicados. NÃO SERÃO CONSIDERADAS respostas com fotos ou texto manuscrito.
· LEIA AS INSTRUÇÕES: o DESENVOLVIMENTO DA QUESTÃO É OBRIGATÓRIO, quando solicitado!
· ATENÇÃO: o cabeçalho do arquivo deve conter as informações abaixo:
NOME COMPLETO:	 	
MATRÍCULA: 	DISCIPLINA: 	TURMA: 	
Questão 1 (2.0 pontos)
Calcule o número mínimo e o número máximo de folhas presentes em uma árvore heap de altura OITO?
 Maximo - 2 ^ ( 8 – 1 ) = ( 2 ^7 ) = 128
 Minimo - 2 ^( h-2) = 64
ATENÇÃO: mostre todos os seus cálculos com clareza!
Questão 2 (2.0 pontos)
Considere uma árvore AVL T, inicialmente vazia, onde serão inseridos os nós correspondentes aos valores: 10, 20, 50, 40, 60, 30;
inseridos NESTA ORDEM. Mostre o passo a passo com o desenho resultante da inserção de cada um dos nós acima. Cada inserção será representada por uma ou duas figuras, conforme as instruções abaixo:
a) Desenhe T imediatamente após a inserção de cada valor, sem contar o balanceamento.
Segunda possibilidade a confirmar com o professor! 
b) Caso T fique DESBALANCEADA, indicar qual o nó sofrerá a rotação, e qual é a rotação a ser realizada. A seguir, desenhe T após o balanceamento do nó indicado.
Questão 3 (2.6 pontos)
a) (2.0) Construa uma árvore heap com os valores armazenados no vetor abaixo. Utilize OBRIGATORIAMENTE o algoritmo descrito no TEXTO DE APOIO.
	1
	2
	3
	4
	5
	6
	7
	8
	9
	10
	11
	12
	13
	14
	15
	10
	30
	29
	22
	50
	40
	27
	44
	75
	54
	80
	62
	
	
	
NOTA: não precisa mostrar o vetor. APENAS DESENHE A ÁRVORE RESULTANTE, com os valores em suas posições.
b) (0.6) Na árvore heap gerada pelo item a), REMOVER a raiz.
DESENHE A ÁRVORE RESULTANTE, com seus valores. NÃO PRECISA MOSTRAR O VETOR.
Questão 4 (1.4 pontos)
Desenhe a ARVORE BINÁRIA DE BUSCA, não necessariamente balanceada, cujo percurso PÓS ORDEM gere a saída: 10, 40, 60, 50, 70, 80, 30.
BONS ESTUDOS!