A1 Estruturas de Dados II

Prévia do material em texto

�
	
	CENTRO UNIVERSITÁRIO AUGUSTO MOTTA
	CURSO:
	CIÊNCIA DA COMPUTAÇÃO 
	
	
	
	
	
	TURMA:
	INF0301N
	VISTO DO COORDENADOR
	PROVA
	TRAB.
	GRAU
	RUBRICA DO PROFESSOR
	DISCIPLINA:
	ESTRUTURA DE DADOS
	AVLIAÇÃO REFERENTE:
	A1 FORMCHECKBOX �
	A2 FORMCHECKBOX �
	A3 FORMCHECKBOX �
	PROFESSOR:
	MARCO ANTÔNIO X VALENTIM
	MATRÍCULA: 
	
	Nº NA ATA:
	
	DATA:
	06/04/2017
	 NOME DO ALUNO:
	
OBSERVAÇÕES (PROVA A):
Alunos que usarem material de consulta (notas de aulas, livros, etc.) vão receber nota zero.
Alunos que usarem aparelhos eletrônicos (celulares, calculadoras, mp3 players, etc.) vão receber nota zero.
Alunos que colarem vão receber nota zero.
Respostas a lápis não terão direito à reclamação na vista de prova.
Tempo mínimo para entregar a prova é de 2 tempos de aula (a não ser que todos os alunos estejam presentes).
1.a Questão: 1.0 ponto (nível 1)
Enade 2005
Tendo como base a árvore acima, faça o que se pede nos itens a seguir.
Considerando que o nó de valor 33 seja a raiz da árvore, descreva a ordem de visita para uma varredura em pré-ordem(r-e-d, ou pré-fixado à esquerda) na árvore. (valor: 0,5 pontos)
Considerando que a árvore cuja raiz é o nó de valor 33 represente uma árvore de busca binária, desenhe a nova árvore que será obtida após a realização das seguintes operações: inserir um nó de valor 21; remover o nó de valor 47; inserir um nó de valor 48. (valor: 0,5 pontos)
2.a Questão: 1.0 ponto (nível 1)
Poscomp 2005
Em uma estrutura de árvore binária de busca, foram inseridos os elementos “h",” “b", “c", “i", “j", nesta sequencia. O tamanho do caminho entre um número qualquer da árvore e a raiz é dado pelo número de arestas neste caminho. Qual o tamanho do maior caminho na árvore, após a inserção dos dados acima?
(a) 2
(b) 6
(c) 4
(d) 5
(e) 3
3.a Questão: 1.5 pontos (nível 2)
Poscomp 2007
Seja T uma árvore AVL vazia. Supondo que os elementos 5, 10, 11, 7, 9, 3 e 6 sejam inseridos nessa ordem em T, indique a sequencia abaixo que corresponde a um percurso de T em pós-ordem.
(a) 3, 5, 6, 7, 9, 10 e 11.
(b) 7, 5, 3, 6, 10, 9 e 11.
(c) 9, 10, 7, 6, 11, 5 e 3.
(d) 11, 10, 9, 7, 6, 5 e 3.
(e) 3, 6, 5, 9, 11, 10 e 7.
4.a Questão: 1.5 pontos (nível 2)
Crie uma árvore binária contendo os valores (chaves) 50, 40, 15, 62, 93, 47, 35, 68, 10, 37 e 22. Apresente os percursos em pré-ordem, em-ordem, pós-ordem para essa árvore. Depois, remova os valores 93 e 40. Mostre a nova árvore após a remoção.
5.a Questão: 1.5 pontos (nível 2)
Considere as seguintes chaves: 14, 5, 1, 31, 9, 12, 6, 19, 45, 11 e 22. Inclua passo a passo essas chaves em uma árvore AVL T, inicialmente vazia. Indique o fator de balanceamento dos vértices a cada inserção e faça as rotações necessárias para o balanceamento.
6.a Questão: 1.5 pontos (nível 2)
Inserir as chaves 11, 7, 6, 1, 2, 9, 10 em uma árvore Rubro Negra desenhando a árvore após cada inserção e realizando o balanceamento quando for necessário.
7.a Questão: 2.0 pontos (nível 3)
Desenhe a árvore binária que deu origem às seguintes sequencias em pré-ordem e em-ordem.
Pré-ordem: [ 1 2 3 4 5 6 7 8 9]
Em-ordem: [ 3 2 6 5 4 1 7 8 9]