Informações para o 3º Teste Prático
Informações Gerais
- Data: 5 de Junho de 2019 (quarta-feira)
- Hora: Existirão dois turnos: um com início às 14:00 e outro com início às 16:00.
Notem que devem ir ao turno que vos foi atribuído! (atribuições serão publicadas na sexta-feira, dia 31 de Maio).
Se tiverem alguma razão para ir a um turno em particular, enviem um email ao regente até quinta-feira, dia 30 de Maio.
- Duração: 2h (exercícios dimensionados para menos tempo)
- Método: irão ter acesso a computador, documentação do Java, código base (de árvores, dicionários e recursividade) e irão submeter no Mooshak, sendo que poderão ver os casos onde falha, tal como nas aulas práticas.
- Dicas: tal como no teste #2 os problemas vão ter algumas dicas: não deixem de as ler.
- Pontuação: este teste vale um terço da nota prática (são três testes práticos), ou seja, vale 2 valores em 20.
São 4 pequenos exercícios cotados com 30%+30%+30%+10%.
Em cada exercício podem existir cotações parciais (ex: passa nalguns testes, falha noutros). Só em casos muito excepcionais a pontuação será diferente da atribuida pelo Mooshak. Podem acontecer casos onde recebem mais pontos do que o Mooshak atribuiu (ex: está tudo certo e falta apenas um ponto e vírgula :)) ou menos pontos (ex: não fizeram o pedido ou tentaram fazer "batota" usando o facto de saberem os testes quando falham). Se tentarem genuinamente fazer os problemas não vão ter nenhum "chatice".
Objectivos específicos para cada exercício e problemas de treino
- [30%] Exercício 1: implementar um método simples para árvores binárias.
Terão de adicionar um novo pequeno método à classe BTree. Será dada como base a implementação dada nas aulas e será descrito o método a implementar, incluindo a assinatura do método (qual o tipo de retorno e o tipo dos argumentos). Irão submeter a classe como nas aulas (com o novo método adicionado). O esforço de implementação esperado é muito pequeno (menos que 10 linhas de código).
- [30%] Exercício 2: implementar método estático para árvores binárias.
Terão de implementar um método estático que recebe como argumento uma árvore binária (simples - uma BTree - ou de pesquisa, uma BSTree) e faz algo sobre ela. O esforço de implementação esperado é também pequeno, mas será um pouco mais complicado que o exercício 1 e poderá dar jeito criar métodos auxiliares.
- [30%] Exercício 3: programa completo (incluindo ler e escrever) que usa conjuntos e/ou dicionários.
Terão de implementar um programa completo, que leia um dado input (usando a classe Scanner) e escreva o resultado pedido. O tema do problema implicará que é conveniente usar conjuntos e/ou dicionárioos, mas poderão usar qualquer implementação (ex: usar a base de código dada nas aulas, usar TADs do próprio Java, ou usar uma qualquer implementação vossa).
- [10%] Exercício 4: pequeno problema envolvendo recursividade.
Terão de resolver um pequeno problema, para o qual terão de pensar no algoritmo adequado. O problema envolverá recursividade e será útil conhecer as ideias de flood fill e/ou subconjuntos e/ou permutações.. Este problema é destinado a alunos que desejem ter uma nota alta, e só deverá ser tentando depois dos outros três exercícios estarem feitos (daí ter menos pontuação atribuída). Poderá consultar e adaptar o código base das aulas práticas que lhe será dado.
Código Base Disponível
Terão acesso a todo o código base de árvores binárias, dicionários e recursividade, nomeadamente:
Árvores Binárias
- BTree - Arvore binaria simples (ex. metodos: numero de nos, altura, contains; impressoes preorder, inorder, postorder, em largura)
- BSTree - Arvore binaria de pesquisa (ex. metodos: numero de nos, altura, contains, insercao e remocao; impressoes preorder, inorder, postorder, em largura)
- BSTMap - Dicionario de pares (chave,valor) implementado com arvores binarias de pesquisa (ex. metodos: put, get e keys)
Recursividade
- TestFloodFill - Fazendo "flood fill" de uma matriz
- TestSets - Gerando todos os subconjuntos de um array
- TestPerm - Gerando todas as permutacoes de um array
Ao submeter, o Mooshak irá reconhecer e compilar código que use estas classes (também daremos acesso às classes de listas, pilhas e filas que são necessárias para compilar o código de árvores).