AP2 Estrutura de Dados 2013 2 Gabarito

Páginas: 4 (752 palavras) Publicado: 1 de setembro de 2015
Curso de Tecnologia em Sistemas de Computa¸c˜ao
Disciplina: Estrutura de Dados e Algoritmos
Gabarito da AP2 - Segundo Semestre de 2013
Nome Assinatura -

Observa¸c˜oes:
1. Prova sem consulta e semuso de m´aquina de calcular.
2. Use caneta para preencher o seu nome e assinar nas folhas de quest˜oes
e nas folhas de respostas.
3. Vocˆe pode usar l´apis para responder as quest˜oes.
4. Ao final daprova devolva as folhas de quest˜oes e as de respostas.
5. Todas as respostas devem ser transcritas nas folhas de respostas. As
respostas nas folhas de quest˜oes n˜ao ser˜ao corrigidas.

1

1. (1,5)Conceitue ´arvore bin´aria de busca.
Resposta: Seja S = {s1 , · · · , sn } um conjunto de chaves satisfazendo
s1 < · · · < sn . Uma ´arvore bin´aria de busca para S ´e uma a´rvore
bin´aria rotulada T ,com as seguintes caracter´ısticas:
(i) T possui n n´os. Cada n´o v corresponde a uma chave distinta sj ∈ S
e possui como r´otulo o valor r(v) = sj .
(ii) Seja um n´o v de T . Seja tamb´em v1 ,pertencente a` sub´arvore
esquerda de v. Ent˜ao, r(v1 ) < r(v). Analogamente, se v2 pertence a`
sub´arvore direita de v, r(v2 ) > r(v).
2. (2,0) Desenhe a ´arvore AVL obtida pela sequˆencia de inser¸c˜oesdas
chaves 19, 16, 18, 15, 17, 6, 2, nesta ordem. Desenhe tamb´em os passos intermedi´arios, incluindo as rota¸c˜oes efetuadas que conduziram a`
solu¸c˜ao obtida.
Resposta:
In´ıcio:

Inserir 19:´arvore vazia

19

19

Inserir 16:
16

19

* desregulado!
18
RDD

Inserir 18:

16

16

18

2

19

18

Inserir 15:

16

19

15

18

Inserir 17:

16

19

15

17

18

* desregulado!

16

19

16

15

RD

18Inserir 6:
15

17

6

17

19

6

16

desregulado!

*

16

RD

15

18

6

18

Inserir 2:
6

17

19

2

15

17

19

2

3. (1,5) Desenhe uma ´arvore B de ordem 3 que contenha as seguintes
3

chaves: 1, 3,6, 8, 14, 32, 36, 38, 39, 41, 43, 45, 50, 53.
Resposta:
14

1

3

6

8

41

32 36 38 39

43 45 50 53

4. (1,5) Considere a seguinte sequˆencia: 33 32 27 31 29 28 25 30 26.
Responda, justificando...
Ler documento completo

Por favor, assinar para o acesso.

Estes textos também podem ser interessantes

  • AP3 Estrutura de Dados 2013 2 Gabarito
  • AP2 Biofisica 2013 2 Com GABARITO
  • AP2 Sistemas Operacionais 2013 2 Gabarito
  • Gabarito Ap2 2013
  • Gabarito AP2 Mat P Adm 2013 2 PatriciaSousa
  • AP2 CPW 2014 2 Gabarito
  • AP2 PDA 2012 2 Gabarito
  • AP2 PDA 2014 2 Gabarito

Seja um membro do Trabalhos Feitos

CADASTRE-SE AGORA!