AD1-2-2021 (1)

Prévia do material em texto

Estrutura de Dados - 2o. peŕıodo de 2021
Primeira Avaliação à Distância
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 =
√
n, g = log n
(c) f = n
√
n, 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 contêm 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 al-
goritmo ao pior caso, em relação ao número de comparações efetuadas. Assuma que n
(número de elementos) é 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á L2 deve armazenar os
elementos maiores ou iguais a x. A lista L não pode ser alterada e seus nós não podem
ser compartilhados com as listas novas.
5. (1,5) Considere uma fila circular F contendo as posições de 1 a 5. A variável f marca a
posição de ińıcio da fila (“frente”), e a variável r marca a posição de fim da fila (“reta-
guarda”). No ińı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 sequência 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 sequência 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, podeŕı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,
enquanto que P2 ocupa as posições a partir da extremidade direita e se desenvolve, em
sequência, para a esquerda. Para inserirmos um dado x em uma pilha P (P = P1 ou
P = P2), usamos o comando I(P, x); para removermos um dado, usamos o comando
R(P ). Pede-se:
(a) (1,0) Considerando que V tem 5 posições e que, inicialmente, P1 e P2 estão vazias,
desenhe V após cada comando, para a seguinte sequência de comandos: I(P1, A),
I(P1, B), R(P1), I(P1, C), I(P2, D), I(P2, E), R(P1), R(P2), I(P2, F ), I(P2, G). In-
dique, na condição final de V , os valores dos topos de P1 e P2.
(b) (1,0) Determine as condições de overflow e underflow para cada pilha.