AP2 Estrutura de Dados 2013 2 Gabarito
752 palavras
4 páginas
Curso de Tecnologia em Sistemas de Computa¸c˜aoDisciplina: Estrutura de Dados e Algoritmos
Gabarito da AP2 - Segundo Semestre de 2013
Nome Assinatura -
Observa¸c˜oes:
1. Prova sem consulta e sem uso 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 da prova 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˜oes das 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
18
Inserir 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