Estrutura de Dados - CEETEPS 2015

Prévia do material em texto

Centro Estadual de Educação Tecnológica Paula Souza - CEETEPS
Curso de Analise e Desenvolvimento de Sistemas
 - 2o. Semestre de 2015 
Estrutura de Dados
Enviar por e-mail: sergio_moraes_2005@yahoo.com colocar no assunto ed2015 pre-prova
Observação: realização e entrega individual (envio até 25/11/2015 – antes da aula)
1. O que é a estrutura linear pilha? Qual é o seu critério de restrição de acesso? Dê um esquema demonstrativo de suas características.
2. O que é a estrutura linear fila? Qual é o seu critério de restrição de acesso? Dê um esquema demonstrativo de suas características.
3. Quais das figuras abaixo não representam árvores? Por quê?
4. Dada a árvore abaixo, complete:
	
	a) _____________ é o nó raiz.
b) Nível de U: _______________; nível de V: __________________;
 nível de X: _______________; nível de Z: ___________________.
c) Altura da árvore: ____________________
d) Grau de Z: _____________; de T: ___________; da raiz: ________
e) Grau da árvore: __________________
f) Nós folhas: folhas_________________________________________
g) T é o pai de V e de W; W é ________________de V.
h) S e T são ________________de H.
i) X é ______________________de U e U é__________________ de X.
j) Z é ______________________de T e ______________________ de R.
5. Represente na forma usual a árvore M (S ( K, T, X ( F, R )), H )
6. Uma árvore binária em que todo o nó que não é folha possui subárvores, esquerda e direita, não vazias é dita uma árvore estritamente binária. Se uma árvore desse tipo possuir n folhas, quantos nós ela terá ao todo?
7. Uma árvore binária é dita completa se ela tem todos os níveis, exceto o de valor mais alto, completamente preenchidos, e o nível de valor mais alto tem todos os seus nós preenchidos. Se uma árvore binária completa de profundidade p tem todas as suas folhas no nível p, qual o número de nós dessa árvore?
8. Faça uma função para calcular a profundidade de uma árvore binária completa, alocada dinamicamente, apontada por Raiz.
9. Dada a árvore binária abaixo, liste o resultado dos três tipos de caminhamento.
	
	
10. Idem para as árvores binárias abaixo: 
	
	
	
(a) pré-ordem 
(b) pré-ordem 
 (c) pré-ordem 
 em-ordem 
 em-ordem
 
 em-ordem 
 pós-ordem 
 
 pós ordem
 pós-ordem 
11. Uma árvore binária foi percorrida conforme os caminhamentos abaixo, resultando nas duas listas de nós. Desenhe a árvore na forma usual.
12. Uma árvore binária foi percorrida conforme os caminhamentos abaixo, resultando nas duas listas de nós. Desenhe a árvore na forma usual.
 
 
Pré-ordem: 
A B L T M F G
 
Ordem central: 
L T B M A F G
13. Idem para:
 
Pré-ordem: 
H T J R U F
 
Ordem final: 
J U F R T H
14. Diga se as seguintes sequências lineares podem ser resultantes de caminhamentos em uma mesma árvore. Se isso for possível, mostre a árvore binária.
 
 a) 
Pré-ordem: 
A B D E F C G H J I K
 
Ordem simétrica: 
E F D B A G J H I C K
 
 b) 
Pré-ordem: 
A B D E F C G H J I K
 
Ordem simétrica: 
E F D A B G J H I C K
 
 c) 
Ordem final: 
C F G E D B A
 
Ordem central: 
C B D F E G A
 d) 
Pré-ordem: 
A B D E C G H F
 
Ordem final: 
D E B H F G C A
15. Dada uma árvore binária e a sequência resultante de um caminhamento sobre ela, diga qual foi o tipo de caminhamento feito.
	
 K T S P R 
	
A D C B G H F
(a)
 (b)
a) Pré-ordem: 
�
�
b) Ordem simétrica: 
�
�
c) Pós-ordem
�
�