Estruturas básicas para representação de informações: listas, árvores, grafos, e suas generalizações. Algoritmos para construção, consulta, e manipulação de tais estruturas. Desenvolvimento, implementação e testes de programas usando tais estruturas em aplicações específicas.
Tópicos a serem estudados (preferencialmente nesta ordem):
1 – Algoritmos recursivos de ordenação (Merge Sort e Quicksort)
2 – Estruturas ligadas: nó, apontador, variável apontadora, alocação dinâmica de memória
3 – Listas ligadas: operações básicas (busca, inserção e remoção)
4 – Exemplos de algoritmos para listas ligadas (inversão, cópia e concatenação)
5 – Comparação de listas ligadas com vetores
6 – Listas circulares, duplamente ligadas, com nó cabeça
7 – Algoritmos de ordenação em listas ligadas (Selection Sort, Insertion Sort e Bubble Sort)
8 – Intercalação de listas ligadas (merge) e aplicações (Merge Sort)
9 – Pilhas, filas e aplicações
10 – Fila de prioridade (heap) e Heapsort
11 – Árvores binárias: representação e percurso (recursivo e não recursivo)
12 – Árvores de busca (busca, inserção e remoção)
13 – Árvores binárias de busca balanceadas (AVL, Rubro-Negra ou Auto-Ajustáveis)
14 – Árvores gerais: definição, representação por listas ligadas e percursos
15 – Árvores B e generalizações
16 – Introdução ao espalhamento (hashing): conceito, implementação com listas ligadas
17 – Grafos: conceitos básicos, representação por matrizes e listas ligadas
18 – Percurso de grafos em largura e profundidade
Tópicos opcionais:
– Matrizes esparsas
– Listas generalizadas
– Listas invertidas
– Implementação de estruturas de dados em disco