UNIVERSIDADE FEDERAL DE MINAS GERAIS

INSTITUTO DE CIÊNCIAS EXATAS

DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO

ALGORITMOS E ESTRUTURAS DE DADOS II

Prof. Raquel O. Prates 26 de junho de 2006

Lista de Exercícios Indicados 2

1. Exercícios do Livro Capítulo 4: 1, 2, 3, 4, 11, 12

2. Exercícios do Livro Capítulo 5: 1, 3, 4, 6, 10, 11, 12, 13, 18, 19

3. 1. Para os algoritmos de ordenação por comparação de chaves vistos em sala (Bolha, Inserção, Seleção, Shellsort, Quicksort (pivô: elemento do meio do vetor), Heapsort e RadixSort), escreva:

a. Uma descrição sucinta, em português, do funcionamento do algoritmo.

b. Discuta a ordem de complexidade dos algoritmos (melhor caso e pior caso).

c. Explique se o algoritmo é estável ou não e por quê.

d. Os pontos fortes e fracos do algoritmo.

e. Situações onde o algoritmo é indicado.

4. Mostre como os algoritmos de ordenação vistos em sala – Bolha, Inserção, Seleção, Shellsort, Quicksort (pivô: elemento do meio do vetor), Heapsort e RadixSort vão ordenar as chaves “MINHAORDENC”. Para o RadixSort crie uma representação binária de 6 bits para cada uma das letras. Most.re os passos para cada um deles

5. Considere a execução do algoritmo Quicksort visto em sala (pivô escolhido no meio do vetor) com o vetor [ 2 10 1 8 20 5 14 13 9 ]. Quantas chamadas do procedimento Partição serão feitas para ordenar esse vetor? Qual o pivô utilizado em cada uma das chamadas? Quais são as partições (sub-vetores) resultantes de cada uma dessas chamadas?

6. Que diferença se pode notar na eficiência do algoritmo para este caso, se você considerer as melhorias para o Quicksort: pivô como mediana e não empilhar conjuntos de apenas 1 elemento.

7. Altere o código do Quicksort para implementar estas melhorias.

8. Para alguns dos algoritmos de pesquisa vistos em sala (Seqüencial, Binária, Árvore Binária de Pesquisa sem balanceamento, e Hash):

a. Forneça uma descrição sucinta, em português, do funcionamento do algoritmo.

b. Discuta qual é ordem de complexidade do número de comparações no pior caso, melhor caso e caso médio.

c. Discuta a eficiência da estrutura para as operações de inserção e impressão de todos os registros em ordem.

9. Implemente um algoritmo não recursivo para realizar uma pesquisa em uma árvore binária. Qual é a ordem de complexidade do seu algoritmo? Explique.

10. Dada a árvore abaixo, liste a ordem em que as chaves serão impressas caso se use o caminhamento:

	a) pré-ordem
	b) central
	c) pós-ordem