Objectivos para o exame
Aqui fica uma lista dos principais objectivos para o exame de Estruturas de Dados.
Podem também consultar um exame modelo para poderem ficar com uma ideia do tipo de questões que serão colocadas.
Java e Programação Orientada a Objectos
Fundamentos de Java
- Conhecer o modelo de programação do Java, como criar um programa com um método main para iniciar a execução, como compilar e como executar um programa;
- Conhecer os principais tipos de dados primitivos e os respectivos Wrappers
- Conhecer os principais operadores (+, -, *, /, %, ++, --, !, &&, ||, ==, <, >, <<, >>);
- Conhecer as instruções condicionais e de ciclo
- Saber como representar strings em Java e seus principais métodos
- Saber como criar e usar arrays (com uma ou mais dimensões)
- Saber como usar a classe Scanner para ler a partir da entrada padrão e como escrever na saída padrão
- Saber escrever o conteúdo de variáveis
Fundamentos de Programação Orientada a Objectos
- Perceber o que é uma classe, uma referência e um objecto.
- Saber como criar um objecto (operador new) e como criar e chamar construtores;
- Saber como definir atributos e métodos numa classe;
- Perceber o conceito de overload e override de métodos;
- Saber como comparar objectos (método equals(x)) e como escrevê-los (método toString());
- Perceber o significado dos classificadores private e public;
- Perceber o conceito de variáveis e métodos estáticos;
- Perceber o conceito de tipos genéricos
Tipos Abstractos de Dados
- Perceber o que é um Tipo Abstracto de Dados (TAD)
- Perceber e saber usar o conceito de Interface, incluindo como definir uma implementação concreta que implementa esse interface
- Saber criar um TAD simples (ex: Point, Rectangle, Vector, Matrix, Fraction, IntSet, BigNumber)
- Perceber que podem existir varias implementações possíveis para o mesmo TAD, com consequentes vantagens e desvantagens e diferentes complexidades de tempo e memória.
Complexidade Algorítmica
Notação
- Conhecer a notação assintótica (O, Ω e Θ) e o seu significado
- Saber comparar funções usando esta notação
- Saber o que significa análise do pior caso e caso médio
- Conhecer as classes habituais de complexidade (linear, logarítmica, linearítmica, etc)
Análise da Complexidade de um Programa
- Saber analisar o custo temporal de um programa simples com ciclos e sem recursão
- Saber analisar uma recursão simples (que use a ideia de dividir para conquistar), e saber escrever a recorrência e a árvore de recorrência
- Saber estimar a complexidade de um programa sabendo o tempo que demora para um conjunto de inputs
- Saber prever o tempo de execução de um algoritmo quando se saber a sua complexidade
Listas, Pilhas e Filas
Fundamentos de Listas Ligadas
- Perceber o conceito de nó, lista ligada simples, lista circular e lista duplamente ligada
- Perceber os principais métodos (ex: tamanho, adicionar e remover elementos)
- Conseguir implementar métodos simples de listas
TADs sequenciais (ou lineares)
- Conhecer o conceito do TAD Pilha, a ordem em que acede aos elementos e os principais métodos (push e pop)
- Conhecer o conceito do TAD Fila, a ordem em que acede aos elementos e os principais métodos (enqueue e dequeue)
- Conhecer o conceito de TAD Deque, a ordem em que acede aos elementos e os principais métodos (adicionar e remover no princípio e fim)
Árvores Binárias e Heaps
Fundamentos de Árvores
- Conhecer o conceito de árvore
- Conhecer a terminologia básica (ex: nós, raíz, folhas, filhos, pais, altura, profundidade)
Árvores Binárias Simples
- Perceber o conceito de árvore binária;
- Saber como implementar uma árvore binária simples com conteúdo genérico;
- Saber implementar métodos recursivos simples (ex: número de nós, altura, escrever todos os nós)
- Perceber os conceitos de pesquisa em profundidade (preorder, inorder e postorder) e de pesquisa em largura, sabendo como implementá-los;
Árvores Binárias de Pesquisa
- Perceber o conceito de árvores binárias de pesquisa (BST - Binary Search Tree);
- Perceber os principais métodos (inserir, remover e verificar se existe um elemento)
- Perceber qual a pior altura possível e qual a altura média para uma ordem aleatória e as consequências disso na complexidade dos métodos associados;
- Saber implementar métodos simples para BSTs
- Perceber o conceito do TADs Conjunto, quais as principais operações e como poderia ser implementado com BSTs, e quais a vantagens e desvantagens quando comparado com outras implementações
- Perceber o conceito do TAD Dicionário, quais as principais operações e como poderia ser implementado com BSTs, e quais a vantagens e desvantagens quando comparado com outras implementações
Filas de Prioridade e Heaps
- Conhecer o conceito do TAD Fila de Prioridade e as principais operações (inserir e remover elemento prioritário);
- Saber o que é e como funciona uma heap, como armazena os elementos num array, que invariante mantém, como pode ser usada para implementar uma fila de prioridade e que complexidades garante para as suas operações.
)