Informações para o 2º Teste Prático
Informações Gerais
- Data: 15 de Maio de 2019 (quarta-feira)
- Hora: Existirão pelo menos 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! (atrbuições serão publicadas na segunda-feira, dia 13 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 listas ligadas) e irão submeter no Mooshak, sendo que poderão ver os casos onde falha, tal como nas aulas práticas.
- 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: implementação de métodos para listas ligadas simples.
Terão de adicionar um ou mais pequenos métodos à classe SinglyLinkedList. Será dada como base a implementação dada nas aulas (ver slides | ver implementação) e serão descritos o métodos 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 os novos métodos adicionados).
- [30%] Exercício 2: implementar método que usa API de pilhas e/ou filas.
Terão de implementar um novo método que recebe como argumentos (ou usa) os TADs pilhas e/ou filas. Terão de usar a API do TAD respectivo (ex: push ou pop nas pilhas, enqueue ou dequeue nas filas). A pilha e/ou fila será dada ou poderá ser usada com o código das aulas (ver slides | MyStack | MyQueue).
- [30%] Exercício 3: programa completo (incluindo ler e escrever) que usa listas, pilhas e/ou filas.
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 listas, pilhas ou filas, 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). O esforço de implementação esperado é pequeno (se souberem o que estão a fazer).
- [10%] Exercício 4: pequeno problema envolvendo eficiência algorítmica.
Terão de resolver um pequeno problema, para o qual terão de pensar no algoritmo adequado. O problema não será completamente resolúvel com uma solução exaustiva de "força bruta" e será necessário ser eficiente. A complexidade esperada será dada no enunciado e não será dado nenhum código base.
Código Base Disponível
Terão acesso a todo o código base de listas ligadas, pilhas e filas, nomeadamente:
- SinglyLinkedList - lista ligada simples (ex operações: tamanho, adicionar no início e no fim, retirar no início e no fim)
- CircularLinkedList - lista ligada circular (ex operações: tamanho, adicionar no início e no fim, retirar no início e no fim, rodar elementos)
- DoublyLinkedList - lista duplamente ligada (ex operações: tamanho, adicionar no início e no fim, retirar no início e no fim)
- TAD MyStack - Uma pilha (coleção LIFO: último a entrar é o primeiro a sair)
- TAD MyQueue - Uma fila (coleção FIFO: primeiro a entrar é o primeiro a sair)
- TAD MyDeque - Generalização de fila (possivel inserir e remover no início e no final da fila)
Ao submeter, o Mooshak irá reconhecer e compilar código que use estas classes.