Exercícios de Estrutura de Dados II

Prévia do material em texto

Lista de Exercícios – Estrutura de Dados II
1. O que significa dizer que uma função g(n) é O(f(n))?
2. Dados dois algoritmos A1 que executa em n5 passos e A2 que executa em 2n passos. 
Qual é o melhor algoritmo? Justifique a sua resposta.
3. Quais das igualdades abaixo são verdadeiras? Justifique.
a) 10n = O(n2) b) 10n2 = O(n)
4. É verdade que n2+200n+300 = O(n2)? Justifique.
5. É verdade que n2-200n-300 = O(n)? Justifique.
6. Analise a complexidade do seguinte algoritmo:
for (i=0; i < n; i++)
 for (j=0; j < n; j++) {
 s = 0;
 for (k=0; k < n; k++)
 s += A[i][k] * B[k][j];
 C[i][j] = s;
 }
7. Modifique o algoritmo de ordenação por inserção de forma que ele utilize a busca 
binária para encontrar a posição de inserção de um elemento no vetor destino.
8. Determine o número de comparações realizadas no algoritmo modificado do 
exercício anterior.
9. Considere uma matriz retangular. Coloque em ordem crescente os elementos de 
cada linha. A seguir, ordene em ordem crescente os elementos de cada coluna. 
Prove que os elementos de cada linha continuam em ordem.
10. Acompanhe o algoritmo heapsort para o seguinte vetor de entrada: 6, 3, 5, 1, 7, 2, 4, 
8. Mostre a heap (no vetor e em forma de árvore binária) a cada passo do 
algoritmo.
11. Acompanhe o algoritmo quicksort para o vetor de entrada da questão anterior. 
Mostre o vetor a cada chamada recursiva.
12. Implemente o algoritmo de ordenação heapsort parcial.
13. Mostre como o vetor ABABABA é particionado quando se escolhe o elemento do 
meio, A[(esq+dir) div 2], como pivô.
14. Mostre as etapas de funcionamento do QuickSort para ordenar as chaves 
QUICKSORT. Considere que o pivô escolhido é o elemento do meio, A[(esq+dir) 
div 2].
15. Considere o arquivo de 10 registros: BALANCEADA.
a) Considerando o algoritmo de ordenação externa denominado intercalação 
balanceada de 2-caminhos, utilizando apenas três fitas magnéticas e uma memória 
interna com capacidade de armazenar três registros. Mostre todas as etapas para 
ordenar o arquivo.
b) Quantas passadas foram realizadas?
16. Modifique o algoritmo de ordenação BubbleSort para fazer a ordenação decrescente 
das chaves no vetor, do maior para o menor.
17. Modifique o algoritmo de ordenação SeleçãoDireta para fazer a ordenação 
decrescente das chaves no vetor, do maior para o menor.