Primeira prova_ Algoritmos e Estruturas de Dados III - Ciencia da Computacao - Campus Coracao Eucaristico - PMG - Tarde - G1_T1 - 2021_1

Prévia do material em texto

Primeira prova
Entrega 26 de mar de 2021 em 7:00 Pontos 18 Perguntas 3
Disponível 24 de mar de 2021 em 7:00 - 26 de mar de 2021 em 7:00 2 dias
Limite de tempo Nenhum
Instruções
Este teste não está mais disponível, pois o curso foi concluído.
Histórico de tentativas
Tentativa Tempo Pontuação
MAIS RECENTE Tentativa 1 1.780 minutos 10,5 de 18
 As respostas corretas estão ocultas.
Pontuação deste teste: 10,5 de 18
Enviado 25 de mar de 2021 em 16:02
Esta tentativa levou 1.780 minutos.
A primeira avaliação engloba os seguintes tópicos:
Tipos de dados
Java IO
Memória secundária
Arquivos sequenciais
Arquivos indexados
Ordenação externa
Você tem 48 horas para realizar a prova e contará com o horário oficial da aula para tirar dúvidas.
As questões envolvem alguma atividade de criação e isso deve ser entendido como algo pessoal. A prova,
portanto, é individual e a correção considerará a originalidade de cada resposta. Respostas semelhantes terão
os valores reduzidos. Se houver alguma dúvida no entendimento do que é para fazer, envie uma mensagem
para o professor.
A prova só permitirá uma tentativa. Assim, você pode realizar a prova e contar com o salvamento automático.
Só envie a prova, quando estiver com segurança sobre suas respostas.
Algumas questões podem ser resolvidas mais facilmente em papel ou usando algum software on-line. Se for o
caso, envie a foto ou imagem da sua solução na caixa de respostas (mas ajuste o tamanho da imagem para
que fique de fácil visualização).
https://pucminas.instructure.com/courses/63791/quizzes/174767/history?version=1
3,5 / 5 ptsPergunta 1
Sua Resposta:
Escolha um tipo de entidade concreta ou abstrata qualquer do mundo real. Em
seguida, faça o seguinte:
a. Descreva essa entidade por meio de pelo menos 5 atributos relevantes.
Entre esses atributos deve haver, no mínimo, um número, uma string e uma
data. Para cada atributo, indique o seu tipo, nome e valores possíveis.
b. Descreva a estrutura de um registro para esse tipo de entidade, por meio de
seus campos. Para cada campo, indique seu tipo e a quantidade de bytes a
serem usados, além de quaisquer operações de conversão ou bytes de
controle necessários.
Entidade Carro:
a)
Atributos: 
 Campo | Tipo | Exemplo 
 ================================== 
 Código Renavam | bigint | 0123456789 
 Cor | string | Amarelo 
 Placa | string | ABC-1234 
 Data CRLV* | bigint | 1616593208 
 Categoria | string | Passeio
* Em timestamp, coversão de D/M/Y - H:i:s para ms
b)
 
O código RENAVAM pode ter zeros à esquerda. Seria importante
controlar a ocorrência desses zeros. Não é uma boa ideia usar strings
de tamanho fixo, a não ser que exista uma restrição específica para o
uso de strings de tamanho variável. Para a PLACA, está ok, mas para a
COR não. Placas de carro não tem o "-". O atributo de CATEGORIA
deveria ser numérico. Como só há poucos tipos e eles são fixos, não
vale a pena armazenar como string (pode ser um byte).
3 / 5 ptsPergunta 2
Para esta questão, você usará os 20 primeiros caracteres do seu nome usando
apenas letras maiúsculas, contando com os espaços em branco (␣) e
removendo todos os acentos. Por exemplo, se o seu nome fosse “Maria
Conceição Araújo”, então esses caracteres seriam:
“MARIA␣CONCEICAO␣ARAU”.
Caso o seu nome não tenha 20 caracteres, repita o último sobrenome até que
os 20 caracteres sejam alcançados. Por exemplo, se o seu nome fosse “José
Reis”, esses caracteres seriam: “JOSE␣REIS␣REIS␣REIS␣”.
Assim a primeira parte desta questão é que você registre 20 caracteres do seu
nome, usando letras maiúsculas, sem acentos, e considerando os espaços em
branco como caracteres válidos. No meu caso, seria: 
M A R C O S ␣ A N D R E ␣ S I L V E I R
Agora, você deve fazer uma ordenação por intercalação balanceada com
segmentos de tamanho variável desses caracteres (que poderiam ser
considerados chaves de registros). Nessa intercalação, você deve usar dois
caminhos e uma capacidade de ordenação em memória principal de apenas
três caracteres e usando uma estrutura de fila de prioridades como o heap de
mínimo (seleção por substituição). 
Outras informações bem importantes para você apresentar a sua solução são:
Represente todas as etapas, isto é, apresente o resultado da fase de
distribuição e de cada intercalação, até que o arquivo esteja totalmente
ordenado.
Na fase de distribuição, você deve registrar todas as inserções e remoções
no heap, mas não precisa representar o próprio heap. Use texto simples
para isso. Por exemplo, suponha que você tenha tirado a chave J do heap
(menor chave) e inserido a chave P (próxima chave do arquivo). Escreva
assim: "Retira J. Insere P" (ou de qualquer forma parecida).
Sua Resposta:
Quando você encontrar duas letras iguais em uma comparação, considere
menor a que vier primeiro. Por exemplo, se você tem uma letra A no arquivo
temporário 1 e outra letra A no arquivo temporário 2, use a do arquivo
temporário 1 primeiro.
O espaço em branco (␣) deve ser considerado como um caractere comum
e esta presente em todas as etapas da ordenação. Seu valor, porém,
deverá ser considerado maior que o de todos os outros caracteres. Assim,
eles deverão aparecer no fim do arquivo final, quando já estiver ordenado.
 
A distribuição com o Heap ficou errada. Não há uma divisão das chaves
de 3 em 3. As intercalações estão corretas.
4 / 8 ptsPergunta 3
Imagine um sistema em que registros 256 bytes (tamanho fixo) em um arquivo
são organizados em blocos de 4 setores (16 KB no total). Cada bloco conterá
alguns dados de controle e até 63 registros. Entre esses dados de controle,
haverá um número inteiro de 1 byte informando quantos registros de fato
existem no bloco (de 0 a 63).O bloco seria algo mais ou menos assim:
n outros dados de controle R R R R ... R
Nesse sistema, um registro nunca é lido ou escrito individualmente. Quando
precisamos criar um registro, alterá-lo ou excluí-lo, todo o seu bloco é
carregado na memória principal, a operação é realizada ainda em memória
1 2 3 4 63
Sua Resposta:
principal, e o bloco já alterado é escrito completamente no arquivo. Durante
essas operações em memória, os registros devem ser mantidos ordenados
dentro do bloco (usando quicksort ou qualquer outro algoritmo de ordenação
em memória principal). O critério de ordenação é uma chave numérica
exclusiva como um ID.
Durante uma inclusão, se um bloco estourar, isto é, se esse bloco já estiver
cheio (com 63 registros) e precisar receber mais um registro, então ele deve
ser dividido em dois blocos, ficando cada bloco (o original e o novo) com
metade dos registros (32 em cada). De forma parecida, se bloco só tiver 1
registro e esse registro for excluído, então o bloco deve ser apagado (não se
preocupe com o espaço desperdiçado no arquivo).
Esse arquivo conta com um índice de bloco (ou agrupamento), isto é, um índice
que aponta para a chave do primeiro registro de cada bloco. O índice também
é um arquivo sequencial em que as chaves podem ser consultadas por meio de
um laço de repetição. O detalhes da implementação do índice são irrelevantes,
basta saber que ele possui a seguinte interface de programação:
create(chave, endereço) — insere um par de chave e endereço no índice;
read(chave) — encontra o endereço associado a uma determinada chave
no índice (ou -1, se não encontrado);
update(chave, novoEndereço) — atualiza o endereço de uma determinada
chave no índice;
delete(chave) — exclui uma chave (e seu endereço) do índice;
next() — retorna a próxima chave no índice em leituras sequenciais (essa
chave será a primeira chave na primeira chamada do método ou a chave
seguinte àquela retornada na última chamada do método).
Considerando isso, escreva o pseudocódigo (como apresentado no material da
disciplina) para as 4 operações básicas com registros em um arquivo: create,
read, update e delete.
algoritmo create(chave, endereco)
 mover o ponteiro para o início do arquivo(cabecalho)ler quantidadeRegistros
 se quantidadeRegistros == 0 ou arquivoVazio então
 criar bloco
 armazenar índice bloco no dado de controle
 escrever 1 //Definindo a quantidadeRegistros
 mover ponteiro 255 Bytes
 inserir registro
 armazenar índice primeiro registro no dado de controle
 se-não-se quantidadeRegistros < 63 então
 escrever quantidadeRegistros + 1
 inserir registro
 se-não então
 faca
 ler quantidadeRegistros
 mover o ponteiro para o novo bloco
 enquanto quantidadeRegistros < 63 e o bloco existe
 se bloco existe então:
 escrever quantidadeRegistros + 1
 inserir registro
 se-não:
 criar bloco
 escrever 1
 armazenar índice bloco no dado de controle
 inserir registro
 armazenar índice primeiro registro no dado de controle
 fim-se
 fim-se
fim-algoritmo
algoritmo read(chave)
 mover o ponteiro para o início do arquivo(cabecalho)
 ler quantidadeRegistros
 ler chavePrimeiro
 mover o ponteiro para o chavePrimeiro do arquivo
 faca
 mover o ponteiro para o próximo bloco
 ler quantidadeRegistros
 enquanto não atingir o fim do arquivo e quantidadeRegistros != 0
 next()
 ler id
 se id == chave então
 retornar objeto e terminar
 fim-se
 fim-enquanto
 enquanto existe próximo bloco
 retornar -1
fim-algoritmo
algoritmo update(chave, novoEndereco)
 objeto obj
 obj = read(chave)
 se obj == -1 então:
 retornar falso;
 se-não
 mover ponteiro para chave do obj
 alterar chave do obj por novoEndereco
 fim-se
fim-algoritmo
 algoritmo delete(chave)
 mover o ponteiro para o início do arquivo(cabecalho)
 ler quantidadeRegistros
 ler chavePrimeiro
 mover o ponteiro para o chavePrimeiro do arquivo
 faca
 mover o ponteiro para o novo bloco
 ler quantidadeRegistros
 enquanto não atingir o fim do arquivo e quantidadeRegistros != 0
 next()
 ler id
 se id == chave então
 excluir endereço do índice
 excluir chave do índice
 mover o ponteiro para o início do arquivo(cabecalho)
 ler quantidadeRegistros
 escrever quantidadeRegistros - 1
 terminar
 fim-se
 executar a função 
 fim-enquanto
 enquanto existe próximo bloco
 retornar false
fim-algoritmo
O create ficou um pouco confuso. Não localizei ali, especificamente, a
hora em que você divide o bloco em 2 movendo metade das chaves
para o novo bloco. No read, há uma confusão. O certo seria usa o next()
para localizar o bloco e, em seguida, buscar o registro dentro desse
bloco. O uso do next() ali ficou parecendo que era para um busca dentro
do bloco. Além disso, para que esse método funcionasse nos métodos
delete e update, ele deveria retornar o endereço do bloco (e não o
próprio objeto). Ou seja, teria que ser outro método. No update, a
operação não vai funcionar. Você poderia ter alteração de valores e não
só do endereço. No delete, também ficou um pouco dessa confusão
quanto, pois no índice está apenas a chave do primeiro registro do bloco
e não o ID buscado.
Pontuação do teste: 10,5 de 18