Exercícios Estrutura de Dados

Prévia do material em texto

Lista de Exercícios – Estrutura de Dados – Prof. Janderson Aguiar 
Curso de Ciência da Computação – CCEA/UEPB 
 
CENTRO DE CIÊNCIAS EXATAS E SOCIAIS APLICADAS — CCEA 
CURSO DE BACHARELADO EM CIÊNCIA DA COMPUTAÇÃO 
ESTRUTURA DE DADOS 
LISTA DE EXERCÍCIOS 
 
ANÁLISE DE ALGORITMOS 
1) Suponha que há dois computadores: o computador A (que executa um bilhão de instruções 
por segundo) e o computador B (que executa dez milhões de instruções por segundo). 
Suponha ainda que um programador criou um código para o computador A que exige 3n² 
instruções para ordenar n números. Por outro lado, para ordenar n números no computador 
B, outro programador criou um código que exige 25n.log2n instruções. Quanto tempo esses 
computadores ordenam cem números? E mil números? E um milhão de números? 
 
2) Qual é o menor valor de n tal que um algoritmo cujo tempo de execução é 100n² funciona 
mais rápido que um algoritmo cujo tempo de execução é 2n na mesma máquina? 
 
3) Expresse a função n³/1000 - 100n² - 100n + 3 em termos da notação Θ. 
 
4) Considere as seguintes funções f(n) e g(n). Prove ou conteste que f(n) = O(g(n)). 
a) f(n)=n³ e g(n)=200n² 
b) f(n)=2n²+3n+4 e g(n)=n² 
c) f(n)=3+(2/n) e g(n)=1 
 
5) Considere um algoritmo de pesquisa linear (que faz a varredura de um array de n números 
para procurar um valor v). Quantos elementos da sequência de entrada precisam ser 
verificados em média, supondo-se que o elemento que está sendo procurado tenha a 
mesma probabilidade de ser qualquer elemento no array? E no pior caso? Quais são os 
tempos de execução do caso médio e do pior caso da pesquisa linear em notação Θ? 
Justifique suas respostas. 
 
6) Por que a declaração “o tempo de execução no algoritmo A é no mínimo O(n²)” é isenta de 
significado? 
 
7) É verdade que 2n+1 = O(2n)? 
 
8) É verdade que 22n = O(2n)? 
 
9) Considerando que f(n) e g(n) são funções assintoticamente positivas, prove ou conteste 
cada uma destas conjecturas: 
a) f(n)=O(g(n)) implica g(n)=O(f(n)) 
b) f(n)+g(n) = Θ(min(f(n),g(n))) 
c) f(n)=O((f(n))²) 
 
10) Use o método de árvore de recursão para demonstrar que: 
a) T(n) = T(n/3) + T(2n/3) + n ∈ O(n lg n) 
b) T(n) = 3T(n/4) + n ∈ O(n) 
c) T(n) = T(n-1) + Θ(1) ∈ O(n) 
 
Lista de Exercícios – Estrutura de Dados – Prof. Janderson Aguiar 
Curso de Ciência da Computação – CCEA/UEPB 
11) Use o método mestre para fornecer limites assintóticos superiores e inferiores para T(n) em 
cada uma das seguintes recorrências. 
a) T(n) = 4T(n/3) + n 
b) T(n) = 4T(n/2) + n²√n 
c) T(n) = 3T(n/3 − 2) + n/2 
 
12) [POSCOMP 2012] Em relação à pesquisa sequencial e binária, assinale a alternativa correta. 
a) A pesquisa binária em média percorre a metade dos elementos do vetor. 
b) A pesquisa binária percorre no pior caso log2 n elementos. 
c) A pesquisa binária pode ser feita sobre qualquer distribuição dos elementos. 
d) A pesquisa sequencial exige que os elementos estejam completamente ordenados. 
e) A pesquisa sequencial percorre todos os elementos para encontrar a chave. 
 
13) Realize uma análise relativa a algoritmos de Busca Linear e Busca Binária. 
a) Abordagem experimental: implemente e execute os algoritmos (usando Java), 
sem usar recursividade. 
i. Entradas para os algoritmos: 
 Elemento procurado: -1. 
 Vetor (variar!): [1, ... ,100]; [1, ... ,1000]; [1, ... ,10000]. 
ii. Execução do experimento: para cada um dos três vetores de entrada criados, 
execute cada algoritmo de busca pelo menos 10 vezes e registre a média dos 
tempos de execução (colocar em uma tabela como a apresentada abaixo). 
 
Tamanho do 
vetor de entrada 
Média dos tempos de execução 
do algoritmo ‘Busca Linear’ 
(em nanosegundos) 
Média dos tempos de execução 
do algoritmo ‘Busca Binária’ 
(em nanosegundos) 
100 elementos 
1000 elementos 
10000 elementos 
 
iii. Apresentação dos resultados: gerar um gráfico de colunas (sugestão: usar o Excel) 
com estas características: 
 Eixo x: tamanho do vetor de entrada 
 Eixo y: média dos tempos de execução observados 
 Cada algoritmo terá uma barra de uma cor (pode ser preto e branco) 
b) Realize também uma análise do custo de ambos os algoritmos (Busca Linear e 
Busca Binária) com base na identificação das operações primitivas e das outras 
operações (método analítico). 
 
ALGORITMOS DE ORDENAÇÃO 
14) É possível modificar um algoritmo de ordenação para que, no melhor caso, o tempo de 
execução seja Θ(n)? Se sim, como? 
 
15) [POSCOMP 2010] Considere o problema de ordenação onde os vetores a serem ordenados, 
de tamanho n > 0, possuem ⌊n/2⌋ valores iguais a um número real x e ⌈n/2⌉ valores iguais a 
um outro número real y. Considere que os números reais x e y são conhecidos e fixos, 
porém estão distribuídos aleatoriamente no vetor a ser ordenado. Neste caso, é correto 
afirmar: 
a) Podemos ordenar estes vetores a um custo O(n). 
b) No caso médio, o Quicksort será o algoritmo mais eficiente para este problema, 
com um custo O(n log n). 
c) O algoritmo de ordenação por inserção sempre opera no melhor caso com um 
custo O(n). 
d) O limite inferior para esta classe de problema é Ω(n²). 
e) O limite inferior para esta classe de problema é Ω(n logn). 
Lista de Exercícios – Estrutura de Dados – Prof. Janderson Aguiar 
Curso de Ciência da Computação – CCEA/UEPB 
16) Realize uma análise experimental relativa a algoritmos de ordenação (não decrescente). 
a) Implemente estes algoritmos de ordenação: Bubble Sort, Selection Sort, Insertion 
Sort, Merge sort, Quicksort, Counting Sort, Radix Sort, Bucket sort. 
b) Crie três arrays de tamanho 20: 
i. Um array com elementos distintos ordenados de maneira crescente; 
ii. Um array com elementos distintos ordenados de maneira decrescente; 
iii. Um array com elementos aleatórios. 
c) Para cada algoritmo implementado, calcule o tempo de execução (em 
milisegundos ou nanosegundos) relativo a cada um dos três arrays (letra b) a 
serem passados como entrada. Execute pelo menos 10 vezes e calcule a média. 
 OBS. 1: Não se deve criar arrays aleatórios distintos como entrada para cada algoritmo. Os 
arrays devem ser os mesmos para realizar a comparação. 
 OBS. 2: Deve-se atentar para não passar como entrada de um algoritmo a saída de outro 
algoritmo (pois, neste caso, a entrada sempre estará ordenada). 
 OBS. 3: Para as repetições (pelo menos 10 vezes), use a mesma entrada (inclusive no caso 
de array aleatório criado). 
d) Repita o processo (letra b e letra c) com arrays de tamanho 2000. 
e) Apresente os resultados obtidos em uma tabela (como a seguinte) e comente-os. 
i. Cada célula da tabela deve indicar a tempo médio de execução (pelo menos 10 execuções). 
 
Algoritmo 
Entrada ordenada Entrada aleatória Entrada ordenada inversamente 
n=20 n=2000 n=20 n=2000 n=20 n=2000 
Bubble sort 
Selection sort 
Insertion sort 
Merge sort 
Quicksort 
Counting sort 
Radix sort 
Bucket sort 
 
PILHA / FILA 
17) Como fica o estado de uma pilha inicialmente vazia após a execução destes comandos: 
 push(10) 
 push(5) 
 pop() 
 push(7) 
 top() 
 pop() 
 isEmpty() 
 
18) Como fica o estado de uma fila inicialmente vazia após a execução dos comandos: 
 enqueue(10) 
 enqueue(5) 
 dequeue() 
 enqueue(7) 
 head() 
 dequeue() 
 isEmpty() 
 
Lista de Exercícios – Estrutura de Dados – Prof. Janderson Aguiar 
Curso de Ciência da Computação – CCEA/UEPB 
19) Suponha que uma pilha S inicialmente vazia realizou um total de 25 operações PUSH, 12 
operações TOP e 10 operações POP em uma determinada ordem. 3 operações POP 
retornaram StackUnderflowException. Qual é o tamanho atual da pilha S? 
 
20) Em relação às estruturas Pilha e Fila, implemente em Java: 
a) Uma Pilha, utilizando um array de tamanho 10. 
b) Uma Fila (abordagem circular), utilizando um array de tamanho 10. 
c) Uma Fila a partir de duas Pilhas (com base na implementaçãoda letra a). 
d) Uma Pilha a partir de duas Filas (com base na implementação da letra b). 
 
LISTA ENCADEADA 
21) Implemente em Java: 
a) Uma Lista Simplesmente Encadeada utilizando métodos iterativos. 
b) Uma Lista Simplesmente Encadeada utilizando métodos recursivos. 
c) Uma Pilha, a partir de uma Lista Simplesmente Encadeada (item a ou b), com as 
operações PUSH e POP em tempo O(1). 
d) Uma Fila, a partir de uma Lista Simplesmente Encadeada (item a ou b), com as 
operações ENQUEUE e DEQUEUE em tempo O(1). 
e) Refaça os itens a e b para uma Lista Duplamente Encadeada. 
 
22) Considere que se tem a implementação de uma SingleLinkedList com as operações 
getHead(), size() e isEmpty(). Considere também que cada elemento dessa estrutura 
de dados é um SingleLinkedListNode, com as operações getNext(), getData() e 
isNIL(). Escreva métodos iterativos (pseudocódigos) para: 
a) Encontrar o maior elemento da lista; 
b) Encontrar o menor elemento da lista; 
c) Inverter os elementos da lista. 
 
ÁRVORE BINÁRIA DE BUSCA 
23) Implemente em Java uma Árvore Binária de Busca (BST). Considere que a árvore é criada 
a partir das inserções de uma sequência de números inteiros (passados por meio de um 
array). Além dos elementos passados pelo array, deve ser possível inserir mais elementos 
na BST. Além disso, deve ser possível mostrar na tela os elementos da árvore via 
percursos de Pré-ordem, Em-ordem e Pós-Ordem. 
 
24) Considere duas sequências de elementos representando uma determinada Árvore Binária 
de Busca: a sequência <4,2,1,3,6,5,7> representa o percurso Pré-ordem e a 
sequência <1,2,3,4,5,6,7> representa o percurso Em-ordem. A partir dessas 
sequências, é possível recuperar a estrutura da árvore? Se sim, desenhe a árvore e mostre 
a sequência resultante do percurso Pós-Ordem. 
 
HEAP 
25) Implemente em Java uma Max Heap e uma Min Heap. Considere que as estruturas são 
criadas a partir de uma sequência de números inteiros (passados por meio de um array). 
Além dos elementos passados pelo array, deve ser possível inserir mais elementos nas 
heaps. Além disso, considerando que a estrutura se trata de uma Árvore Binária, deve ser 
possível mostrar na tela os elementos da árvore via percursos de Pré-ordem, Em-ordem e 
Pós-Ordem. 
OBS.: Considerando a abordagem 
recursiva para a implementação de uma 
SingleLinkedList, refaça a questão 
22 escrevendo métodos recursivos! 
Lista de Exercícios – Estrutura de Dados – Prof. Janderson Aguiar 
Curso de Ciência da Computação – CCEA/UEPB 
26) A sequência <23,17,14,6,13,10,1,5,7,12> é uma Min heap? É uma Max heap? 
 
27) Considere o array A=[27,17,3,16,13,10,1,5,7,12,4,8,9,0] que representa uma 
Max heap. Ilustre a operação de HEAPIFY(A, 3). 
 
28) Considere um array A que representa uma Max heap. Comente o efeito de chamar 
HEAPIFY(A,i) nos seguintes casos: (i) quando o elemento A[i] é maior que seus filhos; 
(ii) para i > heap-size[A]/2. 
 
29) Ilustre a operação de BUILD-MAX-HEAP sobre o array A=[5,3,17,10,84,19,6,22,9]. 
 
TABELAS HASH 
30) Implemente, em Java, uma Tabela Hash, resolvendo colisões por meio de endereçamento 
fechado (usando uma Lista Simplesmente Encadeada, com inserções no início) e usando o 
método da divisão (passando m como parâmetro na criação da tabela). Além dos métodos 
de inserção, busca e remoção, implemente um método print() para mostrar na tela todos os 
elementos de cada posição da tabela. Lembrete: não deve ser permitido armazenar 
elementos repetidos. 
 
31) Desenhe uma tabela hash com endereçamento aberto e tamanho 9 (com probing linear). 
Use a função de hash h(k)=k%9. Insira as chaves: 5, 29, 20, 0, 27 e 18 na tabela nessa 
ordem e mostre o estado final da tabela após executar todas as operações. 
 
32) Suponha que você deseja fazer um estudo comparativo entre duas tabelas hash de 
tamanho 11. Uma delas usa endereçamento aberto com probing linear e função primária 
de hash h(k)=k%m. A outra usa a mesma função primária e probing quadrático com c1=1 e 
c2=3. Qual a melhor tabela considerando que as operações realizadas foram apenas 
inserções dos valores: 10, 22, 31, 4, 15, 28, 17, 88, 59? 
 
33) [POSCOMP 2009] Considere uma tabela de espalhamento (tabela hash) de comprimento 
m=11, que usa endereçamento aberto (open addressing), a técnica de tentativa linear 
(linear probing) para resolver colisões e com a função de dispersão (função hash) 
h(k) = k mod m, onde k é a chave a ser inserida. Considere as seguintes operações 
sobre essa tabela: 
 Inserção das chaves 3, 14, 15, 92, 65, 35 (nesta ordem); 
 Remoção da chave 15; e 
 Inserção da chave 43. 
Escolha a opção que representa esta tabela após estas operações: 
a) 65 – ø – 35 – 14 – ø – 92 – 3 – ø – ø – ø – 43 
b) 43 – ø – 35 – 3 – 14 – 92 – ø – ø – ø – ø – 65 
c) 65 – ø – 35 – X – 14 – 92 – 3 – ø – ø – ø – 43 
d) 65 – ø – 35 – 3 – 14 – 92 – ø – ø – ø – ø – 43 
e) 43 – ø – 35 – 3 – 14 – X – 92 – ø – ø – ø – 65 
 
ÁRVORES AVL 
34) Partindo de uma árvore AVL vazia, realize a inserção da seguinte sequência de chaves: 99, 
44, 71, 80, 74, 63, 59, 120, 98, 150. Redesenhe a árvore após cada inserção. Indique para 
cada rotação feita, o nó desregulado e a rotação aplicada (LL, RR, LR, RL). 
 
Lista de Exercícios – Estrutura de Dados – Prof. Janderson Aguiar 
Curso de Ciência da Computação – CCEA/UEPB 
35) Usando a árvore construída no exercício anterior, remova os nós 59 e 63 mostrando as 
árvores resultantes a cada exclusão e a rotação aplicada (quando necessário). 
 
36) Um programador A inseriu os elementos do vetor [14,8,25,19,16,6,3,4,5] em ordem em 
uma árvore AVL inicialmente vazia. Um programador B inseriu os elementos do vetor 
[14,8,25,19,16,6,3,5,4] em ordem em uma outra árvore AVL inicialmente vazia. Ambos 
programadores afirmam que apenas rotações simples aconteceram. Eles estão corretos? 
Justifique sua resposta. 
 
37) Imagine que você tem o seguinte vetor [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16] e quer 
inserir seus elementos em uma árvore AVL inicialmente vazia de forma a evitar rotações. 
Note que, se você inserir nessa ordem, a árvore começa a pesar para a direita e as 
rotações inevitavelmente acontecem. Você teria alguma ideia para inserir esses elementos 
na árvore AVL de forma a evitar qualquer rotação? Se sim, descreva sua ideia. 
 
ÁRVORES SPLAY 
38) Dada uma árvore splay inicialmente vazia, insira as chaves 0, 2, 4, 6, 8 (nessa ordem) e 
desenhe a árvore depois de cada operação. 
 
39) Considerando a árvore splay construída na questão anterior (após as inserções), pesquise 
pelas chaves 1, 3, 5, 7 (nessa ordem) e mostre as árvores splay resultantes após cada 
operação de busca. 
 
40) Considerando a árvore splay da questão anterior (após as operações de busca), remova as 
chaves 0, 2, 4, 6, 8 (nessa ordem) e mostre as árvores resultantes após cada operação de 
remoção. 
 
41) Dada a seguinte árvore splay: 
 
a) Mostre a árvore resultante do splay do nó 14. 
b) Encontre uma sequência de operações (inserir, excluir ou pesquisar) na árvore 
inicialmente vazia, que resultará na seguinte árvore. 
 
 
42) Mostre o resultado da inserção (árvore final) dos elementos 3, 1, 4, 5, 2, 9, 6, 8 em uma 
árvore splay inicialmente vazia. Em seguida remova o elemento 3 e mostre a árvore 
resultante. 
 
Lista de Exercícios – Estrutura de Dados – Prof. Janderson Aguiar 
Curso de Ciência da Computação – CCEA/UEPB 
ÁRVORES PV 
43) Insira os seguintes valores em uma árvore PV inicialmente vazia e mostre a árvore 
(incluindo a cor dos nós) após cada operação: 41, 38, 31, 12, 19, 8. 
 
44) Suponha que uma chave x é inserida em uma árvore PV e logo em seguida é removida. A 
árvore resultante é a mesma antes da inserção de x? Justifique sua resposta. 
 
45) Implemente um algoritmo recursivo que retorna a quantidade de nós pretos em uma árvore 
PV. 
 
46) Qual a altura máxima de uma árvore PV com altura preta igual a 4? 
 
ÁRVORES B47) Qual a ordem da árvore B a seguir? 
 
 
48) Qual o número máximo de elementos que podem ser armazenados em uma árvore B de 
ordem 20 com altura 2? Justifique sua resposta. 
 
49) Considerando a representação abaixo de árvore B, implemente um método (usando 
recursão) que retorna o maior elemento armazenado em uma árvore B. 
 
 
public class BNode<T extends Comparable<T>> { 
LinkedList<T> elements; 
LinkedList<BNode<T>> children; 
BNode<T> parent; 
intmaxKeys; 
intmaxChildren; 
... 
} 
 
public class BTreeImpl<K,V> implementsBTree<K, V> { 
BNode<K,V> root; 
int order; 
... 
}