AP3 Estrutura de Dados 2013 2 Gabarito

Curso de Tecnologia em Sistemas de Computa¸ca˜o
Disciplina: Estrutura de Dados e Algoritmos
Gabarito da AP3 - 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. (3,0) Forne¸ca as defini¸c˜oes dos seguintes conceitos:
´
(a) (1,5) Algoritmo Otimo
Resposta: Um algoritmo ´e ´otimo quando sua complexidade de pior caso ´e igual ao limite inferior para o problema.
´
(b) (1,5) Arvore
AVL
Resposta: Uma ´arvore bin´aria T ´e uma ´arvore AVL quando todos os seus n´os est˜ao regulados (as alturas de suas sub´arvores esquerda e direita diferem de at´e uma unidade).
2. (2,0) Responda os itens a seguir:
(a) (1,0) Desenhe uma ´arvore bin´aria de busca que seja estritamente bin´ aria e de altura 4. N˜ao se esque¸ca de colocar os valores das chaves dentro de cada n´o.
Resposta:
6
4
2
1

8
5

7

9

3

(b) (1,0) Escreva a sequˆencia que corresponde `a ordem dos n´os visitados no percurso em ordem sim´ etrica. Resposta: Percurso em ordem sim´etrica: 1, 2, 3, 4, 5, 6, 7, 8, 9.
3. (2,0) Desenhe e explique os passos intermedi´arios do algoritmo de ordena¸ca˜o Heapsort para o seguinte vetor de entrada: 34, 23, 89, 12, 67, 58, 45.
Resposta:
23↔67: 34, 67, 89, 12, 23, 58, 45
34↔89: 89, 67, 34, 12, 23, 58, 45
34↔58: 89, 67, 58, 12, 23, 34, 45
89↔45: 45, 67, 58, 12, 23, 34, 89
45↔67: 67, 45, 58, 12, 23, 34, 89
67↔34: 34, 45, 58, 12, 23, 67, 89
34↔58: 58, 45, 34, 12, 23, 67, 89
58↔23: 23, 45, 34, 12, 58, 67, 89
23↔45: 45, 23, 34, 12, 58, 67, 89
45↔12: 12, 23, 34, 45, 58, 67, 89

12↔34: 34, 23, 12, 45, 58, 67, 89
34↔12: 12, 23, 34, 45, 58, 67, 89
12↔23: 23, 12, 34, 45, 58,