Estrutura de Dados Primeira Avaliação `a Distancia

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,