Estrutura de Dados Primeira Avaliação `a Distancia
Por: Marcio Maia • 12/9/2021 • Exam • 515 Palavras (3 Páginas) • 252 Visualizações
Estrutura de Dados - 2o. período de 2021
Primeira Avaliação `a Distancia
1. (1.0) Para cada par de funções f e g abaixo, responda se f = O(g), g = O(f) ou ambos.
(a) f = n2 + 3n + 4, g = 6n + 7
(b) f = pn, g = log n
(c) f = npn, g = n2
− n
(d) f = 2n
− 2, g = n4 + n2
2. (2,0) Sejam V 1 e V 2 duas listas ordenadas, implementadas por vetores. Apresente um
algoritmo que construa um vetor contendo os elementos comuns a V 1 e V 2. (Suponha
que tanto V 1 como V 2 não contem elementos repetidos.) Determine a complexidade do
algoritmo, em função dos tamanhos de V 1 e V 2.
3. (1,5) Forneça um exemplo de entrada para o algoritmo de busca binária que leva o algoritmo
ao pior caso, em relação ao n´úmero de comparações efetuadas. Assuma que n
(número de elementos) ´e igual a 15. Mostre todas as comparações que foram efetuadas
ao longo da execução do algoritmo.
4. (2.0) Construa um algoritmo que receba como entrada uma lista simplesmente encadeada
L e um inteiro x, e separe os elementos de L em duas novas listas: L1 e L2. Em L1, seu
algoritmo deve armazenar apenas os elementos menores que x. J´a L2 deve armazenar os
elementos maiores ou iguais a x. A lista L n˜ao pode ser alterada e seus n´os n˜ao podem
ser compartilhados com as listas novas.
5. (1,5) Considere uma fila circular F contendo as posi¸c˜oes de 1 a 5. A vari´avel f marca a
posição de início da fila (“frente”), e a variável r marca a posição de fim da fila (“retaguarda”).
No início, a fila F encontra-se vazia, e as variáveis f e r valem zero.
Usamos a notação R para denotar a operação de remoção de um elemento da fila F, e a
notação I(X) para denotar a operação de inserção de um elemento X na fila F.
Considere a seguinte sequencia de operações em F:
I(A), I(B), I(C), I(D), R, I(E), R, I(F), R, I(G), I(H), R
Desenhe como fica a fila F após a sequencia de operações acima, e forneça os valores finais
das variáveis f e r. Use um traço (–) para denotar as posições vazias. Como exemplo de
configuração, poderíamos ter: F = ( − − C D − ), com f = 3 e r = 4.
6. Considere um vetor V que armazena duas pilhas P1 e P2, que compartilham V da seguinte
forma: P1 se desenvolve sequencialmente da extremidade esquerda de V para a direita,
...