lista2

Prévia do material em texto

Universidade de Bras´ılia
Departamento de Cieˆncia da Computac¸a˜o
Organizac¸a˜o de Arquivos - Turma B
Prof. Pedro de Azevedo Berger
Lista 2
1. Codifique (usando Lempel-Ziv) a sequeˆncia ¨O RATO ROEU A ROUPA DO REI DE ROMA¨.
(1,5)
2. Descreva a estrate´gia LED para recuperac¸a˜o de espac¸o em disco (0,75). No caso da utilizac¸a˜o da
LED, qual a melhor estrate´gia de ajuste? (0,75)
3. Dado o vetor de heap:
C F D G H I
• Acrescente ao heap as chaves de entrada: Z, J e A, mostrando passo a passo a´ a´rvore de
construc¸a˜o. (1,5)
4. Organize o arquivo de ı´ndice secunda´rio a seguir como uma lista invertida, mostrando o arquivo
secunda´rio de chaves e a lista encadeada de chaves prima´rias. (1,5)
Ordem de Inserc¸a˜o Temporal Chave secunda´ria Chave prima´ria
3 Kubitschek 13795
5 Kubitschek 19201
4 Kubitschek 18807
1 Kubitschek 22626
7 Goulart 23699
6 Vargas 31809
2 Sales 12312
5. Considere um arquivo de 1800 MB, com 18.000.000 de registros de 100 B. Considere tambe´m que a
memo´ria dispon´ıvel para ordenac¸a˜o e´ de 10 MB (sem contar memo´ria para manter o programa, SO,
buffer de I/O, etc.). Queremos ordenar o arquivo utilizando o Multistep Merge (em dois passos!),
no primeiro mergesort devem ser utilizados 9 conjuntos de runs. Calcule o nu´mero total de seeks
necessa´rios para ordenar o arquivo (2,0),
6. Considere os seguintes dados:
47, 3, 89, 43, 75, 20, 82, 21, 12 7, 5, 1, 53 ← In´ıcio dos dados.
Utilize um buffer de tamanho 3 para ordena´-los com replacement selection. Apresente os pas-
sos da construc¸a˜o de cada run (2,0).
1