2020 2 AV2 Teoria em Grafos

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? 
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. 
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!