Disciplina Estrutura de Dados II ATIVIDADE AVALIATIVA ESPECIAL (AAE) 2 - referente as aulas 5 a 8

Prévia do material em texto

/
CENTRO UNIVERSITÁRIO DA GRANDE DOURADOS
Curso: Engenharia de Software
Semestre: 4º 
Disciplina: Estrutura de Dados II
ATIVIDADE AVALIATIVA ESPECIAL (AAE) 2 - referente as aulas 5 a 8
Professor: Marcos Alves Mariano
Observação:
Cada Atividade respondida de forma correta terá até 1 ponto por anotação correta
Responda Aqui!
	1°
	2°
	3°
	4°
	5°
	6°
	7°
	8°
	9°
	
	
	
	
	
	
	
	
	
1º) Considere as definições a seguir:
I. O nível do nó raiz de uma árvore é 1.
II. O nível de qualquer nó subsequente é igual ao nível do seu nó pai mais 1.
III. A profundidade de uma árvore é igual ao maior nível encontrado dentre todos os seus nós.
Partindo-se das premissas acima, a menor e a maior quantidade de nós, respectivamente, que poderiam existirem uma árvore binária de profundidade 3 são:
a) 3 e 15.
b) 3 e 7.
c) 3 e 16.
d) 4 e 7.
e) 5 e 16.
2º) Pesquisar um valor que corresponda a um valor chave em uma árvore AVL com 128 elementos requer no máximo:
a) oito comparações.
b) quatro comparações.
c) cinco comparações.
d) seis comparações.
e) sete comparações.
3º) Uma árvore de busca binária cheia tem, no 5º nível, uma quantidade de nós igual a:
a) 31
b) 32
c) 64
d) 15
e) 16
4º) Dada a árvore de busca binária abaixo, assinale a alternativa que representa o seu percurso in-ordem:
a) 50, 17, 72, 12, 23, 54, 76, 9, 14, 19, 67.
b) 9, 12, 14, 17, 19, 23, 50, 54, 67, 72, 76.
c) 9, 14, 12, 19, 23, 17, 67, 54, 76, 72, 50.
d) 50, 17, 12, 9, 14, 23, 19, 72, 54, 67, 76.
e) 76, 72, 67, 54, 50, 23, 19, 17, 14, 12, 9.
5º) Uma estrutura de dados onde cada nó mantém uma informação adicional, chamada fator de balanceamento, que indica a diferença de altura entre as subárvores esquerda e direita, é conhecida por árvore:
a) de busca binária.
b) ordenada.
c) AVL.
d) binária.
e) hiberbólica.
6º) Em uma árvore AVL balanceada significa que, para cada nó da árvore, a diferença entre as alturas das suas sub- árvores (direita e esquerda) sempre será:
a) menor ou igual a 2.
b) igual a 0 ou -1.
c) maior que 1.
d) igual a 1.
e) igual a -1, 0 ou 1.
7º) Após a inserção de um nó, é necessário verificar cada um dos nós ancestrais desse nó inserido, relativamente à consistência com as regras estruturais de uma árvore AVL.
PORQUE
O fator de balanceamento de cada nó, em uma árvore AVL, deve pertencer ao conjunto formado por {−2, −1, 0, +1, +2}.
Analisando-se as afirmações acima, conclui-se que:
a) as duas afirmações são verdadeiras, e a segunda justifica a primeira.
b) as duas afirmações são verdadeiras, e a segunda não justifica a primeira.
c) a primeira afirmação é verdadeira, e a segunda é falsa.
d) a primeira afirmação é falsa, e a segunda é verdadeira.
e) as duas afirmações são falsas.
8º) Considerando a árvore B abaixo apresentada abaixo, se removermos os registros de chaves 60, 8, 53, 15 e 77, as chaves dos registros remanescentes, nos nós raiz e no nó folha mais à esquerda, são, respectivamente:
a) raiz: 31; nó folha esquerdo: 15.
b) raiz: 31 e 49; nó folha esquerdo: 84.
c) raiz: 31; nó folha esquerdo: 17 e 27.
d) raiz: 31 e 49; nó folha esquerdo: 17 e 27.
e) raiz: 31; nó folha direito: 17 e 27.
9º) O algoritmo de Huffman, comumente utilizado em procedimentos para compressão de dados, baseia-se na utilização de códigos de tamanho:
a) fixo, que dependem da probabilidade de ocorrência de cada possível símbolo de entrada.
b) variável, que dependem da probabilidade de ocorrência de cada possível símbolo de entrada.
c) fixo, que estabelecem uma espécie de índice, que é associado a cada possível símbolo de entrada.
d) variável, que dependem da ordenação lógica de todos os possíveis símbolos de entrada.
e) fixo, que são importados de uma biblioteca padrão previamente estabelecida para cada tipo de símbolo.
10º) Sobre compactação de arquivos, cite as principais diferenças entre a Codificação run-length e o Algoritmo de Huffman.