Estrutura de Dados
Resumo de Estrutura de Dados para Concursos Públicos
1. Conceitos Básicos
Estruturas de dados são formas organizadas de armazenar e gerenciar dados em um computador, visando eficiência no acesso e manipulação. Incluem tipos abstratos de dados (TADs) e suas implementações.
2. Principais Estruturas de Dados
Vetores/Arrays: Coleção contígua de elementos do mesmo tipo, com acesso direto por índices.
Listas Ligadas: Elementos (nós) conectados por ponteiros, podendo ser simples (unidirecional) ou duplamente encadeadas.
Pilhas (LIFO): Operações push (inserir) e pop (remover) no topo. Usadas em chamadas de função, DFS.
Filas (FIFO): Inserção no fim e remoção no início. Podem ser circulares ou de prioridade.
Árvores: Estrutura hierárquica com raiz, nós internos e folhas. Destaque para árvores binárias e árvores balanceadas (AVL, Rubro-Negras).
Grafos: Conjunto de vértices e arestas, podendo ser direcionados ou não, com aplicações em redes e caminhos.
Tabelas Hash: Mapeamento de chaves para valores via função hash, com tratamento de colisões (encadeamento, sondagem).
3. Operações e Complexidade
Acesso: O(1) em arrays; O(n) em listas.
Inserção/Remoção: O(1) em pilhas/filas (caso médio); O(log n) em árvores balanceadas.
Busca: O(log n) em buscas binárias; O(1) em tabelas hash (caso médio).
4. Tópicos Relevantes para Concursos
• Diferença entre estruturas lineares e não lineares.
• Implementação de pilhas e filas com arrays ou listas.
• Recursão e seu uso em árvores.
• Algoritmos de ordenação (QuickSort, MergeSort) e busca.
• Aplicações práticas: avaliação de expressões (pilhas), BFS/DFS (grafos).
5. Bibliografia Sugerida
• "Estruturas de Dados e Algoritmos" - Cormen et al.
• "Data Structures and Algorithms" - Aho, Hopcroft.
• Provas anteriores de concursos com ênfase em TI.