aed3-2011-1-exercicio-6

Prévia do material em texto

Universidade Federal de Lavras
Departamento de Ciência da Computação
GCC109 – Algoritmos e Estruturas de Dados III
Professor: Denilson Alves Pereira
Lista de Exercícios 6
 Data Limite de Entrega: 26/06/11 (turma 10A) e 28/06/11 (turma 14A)
 O exercício deve ser entregue pelo Moodle (http://aluno.dcc.ufla.br). Envie arquivos somente nos 
formatos txt e pdf (não enviar .doc, .docx, .odt etc.). Arquivos compactados somente .zip e .tar.gz (não 
enviar .rar, .z etc.). Não use acentos e nem “ç” nos nomes de arquivo.
 Exercícios copiados receberão nota zero
1. Mostre os passos para a ordenação externa dos número inteiros com as especificações abaixo, 
considerando o método de intercalação balanceada de vários caminhos (estratégia geral com 
blocos de tamanho fixo).
Arquivo com os dados (53 registros): 13 45 67 23 89 98 65 43 21 12 12 55 66 99 43 32 37 59 61 
62 11 5 4 7 8 90 10 20 60 40 30 2 3 6 8 98 76 62 23 26 28 13 8 9 0 21 19 18 27 25 71 73 37
Memória interna para 5 registros
8 unidades de fita (intercalação-de-4-caminhos)
2. No exercício 1, se estivessem disponíveis apenas 5 fitas, mostre como seria a intercalação 
usando 4+1 fitas?
3. Usando os dados do Exercício 1, mostre como seria a ordenação considerando a implementação 
por meio da seleção por substituição usando um heap.
4. Usando o resultado obtido na primeira fase da intercalação balanceada de vários caminhos 
implementada por meio da seleção por substituição do Exercício 3, mostre os passos para uma 
intercalação polifásica com 5 fitas.
5. Mostre os passos para ordenar os número inteiros abaixo usando o Quicksort Externo. Você tem 
disponível uma memória interna com capacidade para armazenar 4 registros.
Registros: 21 43 4 3 15 16 10 12 66 33 9 8 7 6
	GCC109 – Algoritmos e Estruturas de Dados III
	Lista de Exercícios 6