Questões "Estrutura de Dados"

Arquivo ORIGINAL anexado.



Estrutura de Dados - 2o. Per´ıodo de 2019
Primeira Avalia¸c˜ao `a Distˆancia
1. (1,0) Escreva as seguintes fun¸c˜oes em nota¸c˜ao :
n2 + log2 n; 2n2
− 3; n2 log n; log n + pn; n! + 2n.


2. (0,5 cada) Para cada item abaixo, responda “certo” ou “errado”, justificando em ambos
os casos:
(a) Se a complexidade de melhor caso de um algoritmo for (f), ent˜ao o n´umero de
passos que o algoritmo efetua no pior caso ´e
(f).
(B) Se um limite inferior para um problema P ´e n2, ent˜ao todo algoritmo ´otimo para P
ter´a complexidade de pior caso
(n).
(C) Se um algoritmo A que resolve um problema P tem o pior caso mais baixo assintoticamente
dentre todos os algoritmos conhecidos que resolvem P, ent˜ao A ´e ´otimo.


3. (0,5 cada) Considere a seguinte lista ordenada: 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20.
Utilizando busca bin´aria, determine:
(a) Um elemento cuja busca resulte em um n´umero m´ınimo de compara¸c˜oes.
(B) Um elemento pertencente `a lista cuja busca resulte em um n´umero m´aximo de
compara¸c˜oes.

Determine quais compara¸c˜oes foram efetuadas.
(C) Um elemento n˜ao pertencente `a lista cuja busca resulte em um n´umero m´aximo
de compara¸c˜oes. Determine quais compara¸c˜oes foram efetuadas.


4. Considere a lista: 56 12 8 2 95 23 10. Desenhe todas as trocas de elementos e
determine o n´umero de trocas efetuadas, utilizando:
(a) (0,8) Ordena¸c˜ao por sele¸c˜ao
(b) (1,2) Ordena¸c˜ao por bolha
5. (1,5) Sejam L1 e L2 duas listas ordenadas, simplesmente encadeadas com n´o-cabe¸ca.


Escreva um algoritmo que construa uma 3a lista ordenada (sem alterar L1 e L2) contendo
os elementos que pertencem a apenas uma das listas de entrada, mas n˜ao a ambas.
6. (1,5) Seja V um vetor com n posi¸c˜oes. Escreva um algoritmo que construa uma lista
encadeada L, com n´o cabe¸ca, a partir de V , de forma que os elementos de L sejam os
mesmos de V , de forma ordenada crescente. Por exemplo, se V contiver os elementos
1 9 3 5 7, nesta ordem, a lista L dever´a conter os elementos 1 3 5 7 9, nesta ordem.


7. (0,5 cada) Para cada item abaixo, desenhe uma ´arvore bin´aria T que satisfa¸ca os requisitos
pedidos.
a. T ´e uma ´arvore estritamente bin´aria, com 3 n´ıveis e n´umero m´ınimo de n´os.
b. T ´e uma ´arvore completa, mas n˜ao cheia, com altura 4 e n´umero m´aximo de n´os.