AP1 Estrutura de Dados 2013 2 Gabarito

Curso de Tecnologia em Sistemas de Computa¸ca˜o
Disciplina: Estrutura de Dados e Algoritmos
AP1 - 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. Defina:
(a) (1,0) Complexidade de pior caso de um algoritmo.
Resposta: Sejam A um algoritmo, E = {E1 , · · · , En } o conjunto de todas as entradas poss´ıveis de A e ti o n´ umero de passos efetuados por A, quando a entrada for Ei . A complexidade de pior caso de
A ´e definida por maxEi ∈E {ti | Ei ∈ E}.
(b) (1,0) Algoritmo o´timo.
Resposta: Sendo o limite inferior do problema, um algoritmo ´e o´timo se sua complexidade ´e O( ).
´
(c) (1,0) Arvore estritamente bin´aria.
Resposta: Uma a´rvore ´e estritamente bin´aria se cada n´o possui 0 ou 2 filhos.
2. Considere uma lista sequencial ordenada L dada como um vetor de n posi¸co˜es. Forne¸ca as complexidades (em nota¸c˜ao O) dos seguintes algoritmos: (a) (0,5) Busca sequencial de um elemento x em L (forne¸ca a complexidade de pior caso).
Resposta: O(n)
(b) (0,5) Busca bin´aria de um elemento x em L (forne¸ca a complexidade de pior caso).
Resposta: O(log n)
(c) (0,5) Remo¸ca˜o de um elemento x que se encontra na posi¸ca˜o de L, isto ´e, x = L[ n2 ]
Resposta: O(n)

n
2

(d) (0,5) Inser¸c˜ao de um elemento x em L tal que x > L[i] para todo i = 1, . . . , n.
Resposta: O(1)
3. Dado um vetor contendo os n´ umeros 3, 8, 11, 0, 5, 9, pede-se:
(a) (1,0) Desenhe todas as trocas de elementos que o m´etodo de ordena¸c˜ao por sele¸c˜ao efetua. Exemplo: se as trocas fossem “3 por
8”, “5 por 9”, “0 por 3” etc., vocˆe desenharia a seguinte sequˆencia
2

de vetores: