1:Ordenação

1. Introdução à Ordenação
Objetivo: Organizar dados (ex.: arrays) de forma crescente/decrescente.

Importância:

Escolher o algoritmo certo equilibra desempenho vs. legibilidade.

Não usar algoritmos complexos para problemas simples (ex.: BubbleSort para 10
elementos).

Análise de Algoritmos:

Complexidade (Big O):

Pior caso, Caso médio, Melhor caso.

Exemplo: BubbleSort tem melhor caso

O
(
n
)
O(n) (já ordenado) e pior caso
O
(
n
2
)
O(n
2
).

2. Algoritmos Elementares
a) BubbleSort
Funcionamento:

Compara pares adjacentes e troca se estiverem fora de ordem.

Os maiores elementos "borbulham" para o final.

Complexidade:

Pior caso:
O
(
n
2
)
O(n
2
)

Melhor caso:
O
(
n
)
O(n)
Código Java (clássico):

java
for (int i = 0; i < n; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (vetor[j] > vetor[j + 1]) {
int aux = vetor[j];
vetor[j] = vetor[j + 1];
vetor[j + 1] = aux;
}
}
}
Indicação: Pequenos conjuntos de dados.

b) InsertionSort
Funcionamento:

"Insere" cada elemento na posição correta à esquerda (como ordenar cartas).

Complexidade:

Pior caso:
O
(
n
2
)
O(n
2
)

Melhor caso:
O
(
n
)
O(n) (array já ordenado).

Código Java:

java
for (int i = 1; i < n; i++) {
int aux = vetor[i];
int j = i - 1;
while (j >= 0 && vetor[j] > aux) {
vetor[j + 1] = vetor[j];
j--;
}
vetor[j + 1] = aux;
}
Indicação: Pequenos volumes ou dados parcialmente ordenados.

c) SelectionSort
Funcionamento:

Seleciona o menor elemento a cada iteração e o coloca na posição correta.

Complexidade: Sempre
O
(
n
2
)
O(n
2
) (até no melhor caso).

Código Java:

java
for (int i = 0; i < n; i++) {
int menor = i;
for (int j = i + 1; j < n; j++) {
if (vetor[j] < vetor[menor]) menor = j;
}
int aux = vetor[i];
vetor[i] = vetor[menor];
vetor[menor] = aux;
}
Indicação: Simples, mas ineficiente para grandes volumes.

d) QuickSort
Funcionamento:

Divisão e conquista: Escolhe um pivô, particiona o array (menores à esquerda,

maiores à direita) e repete recursivamente.

Complexidade:

Pior caso:
O
(
n
2
)
O(n
2
) (raro)

Caso médio:
O
(
n
log
⁡
n
)
O(nlogn)

Código Java (recursivo):

java
static void ordenaQuickSort(int[] vetor, int esq, int dir) {
if (esq < dir) {
int p = particao(vetor, esq, dir); // Método de partição
ordenaQuickSort(vetor, esq, p);
ordenaQuickSort(vetor, p + 1, dir);
 }
}
Indicação: Mais eficiente para grandes volumes (melhor caso médio).

3. Comparação de Desempenho
Algoritmo 100 elementos 10.000 elementos 100.000 elementos
BubbleSort 0 ms 130 ms 12.693 ms
InsertionSort 0 ms 7 ms 401 ms
SelectionSort 0 ms 23 ms 2.098 ms
QuickSort 0 ms 1 ms 17 ms
Conclusão: QuickSort é o mais rápido para grandes conjuntos de dados.

4. Dicas para a Questão de Código

Foco comum: Implementar BubbleSort ou InsertionSort (são os mais simples).

Passos típicos:

Criar um array com valores aleatórios.

Implementar o algoritmo de ordenação.

Exibir o array antes/depois da ordenação.

Exemplo (BubbleSort):

java
int[] vetor = new int[10];
// Preencher com valores aleatórios
for (int i = 0; i < [Link]; i++) {
vetor[i] = (int) ([Link]() * 100);
}
// Ordenar com BubbleSort
for (int i = 0; i < [Link]; i++) {
for (int j = 0; j < [Link] - i - 1; j++) {
if (vetor[j] > vetor[j + 1]) {
int aux = vetor[j];
vetor[j] = vetor[j + 1];
vetor[j + 1] = aux;
}
}
}
5. Conceitos Teóricos para Revisar
Complexidade Assintótica:

O
(
n
2
)
O(n
2
): BubbleSort, InsertionSort, SelectionSort.

O
(
n
log
⁡
n
)
O(nlogn): QuickSort (caso médio).

Estabilidade:

BubbleSort e InsertionSort são estáveis (não alteram ordem de elementos iguais).

Quando usar:

BubbleSort/InsertionSort: Poucos elementos ou arrays quase ordenados.

QuickSort: Grandes volumes de dados.

Boa prova! Estude a implementação dos algoritmos e suas complexidades. Foque em

BubbleSort e InsertionSort para a questão de código.

2: Listas Encadeadas

Resumo para Prova de Java - Listas Encadeadas e Pilhas

Conceitos-chave e pontos para estudo (7 questões teóricas + 1 prática):

1. Listas Encadeadas vs. Vetores

Vetores (Array):

Estático: Tamanho fixo, alocação contígua de memória.

Acesso direto por índice (ex: vetor[2]).

Listas Encadeadas (Dinâmica):

Dinâmico: Tamanho variável, elementos alocados sob demanda (não contíguos).

Elementos são ligados por ponteiros (referências).

Não permite acesso direto por índice (precisa percorrer).

2. Estrutura da Lista Encadeada

Nó (Node): Unidade básica.

Armazena:

elemento: dado.

proximo: ponteiro para o próximo nó.

Lista Encadeada:

Mantém referências para:

inicio: primeiro nó.

fim: último nó.

tamanho: quantidade de nós (otimiza consulta).

3. Operações Básicas (Implementação Manual)

a) Adicionar Elemento (final):
java
public void adiciona(Tipo elemento) {
 No<Tipo> novoNo = new No<>(elemento);
if (inicio == null) { // Lista vazia
inicio = novoNo;
fim = novoNo;
} else {
[Link](novoNo); // Liga último ao novo
fim = novoNo; // Atualiza fim
}
tamanho++;
}
b) Buscar Nó por Posição:
java
public No get(int posicao) {
No atual = inicio;
for (int i = 0; i < posicao; i++) {
atual = [Link]();
}
return atual;
}
c) Remover Elemento (casos):
Remoção no início:

java
[Link] = [Link]();
Remoção no fim:

java
[Link] = anterior;
[Link](null);
Remoção no meio:

java
[Link]([Link]());
4. Classe LinkedList do Java (API Pronta)
Implementa lista encadeada:

java
LinkedList<String> lista = new LinkedList<>();
Métodos principais:

add("dado"): Adiciona no final.

getFirst() / getLast(): Acesso ao início/fim.

get(2): Busca por posição.

contains("Elis"): Verifica existência.

remove(2) ou remove("Claudio"): Remove por posição ou conteúdo.

5. Pilhas (Stacks)
LIFO (Last-In-First-Out): Último a entrar é o primeiro a sair.

Operações:

push(): Insere no topo.

pop(): Remove do topo.

peek(): Consulta o topo.

Implementação com LinkedList:

java
LinkedList<String> pilha = new LinkedList<>();
[Link]("A"); // [A]
[Link]("B"); // [B, A]
[Link](); // Remove "B"
6. Complexidade
Operação Lista Encadeada Vetor
Inserir no fim O(1) O(1)
Buscar por índice O(n) O(1)
Remover do início O(1) O(n)
7. Dicas para a Questão de Código
Implementação manual:

Foco em adiciona(), remover(), get().

Tratar casos especiais (lista vazia, remoção no início/fim).

Uso da API:

Saber usar métodos da LinkedList (ex: remove("dado")).

Exemplo de inicialização:

java
ListaEncadeada<String> lista = new ListaEncadeada<>();
[Link]("A");
[Link]("A");
8. Conceitos Teóricos para Revisar
Ponteiros: Conceito de referência entre nós.

Vantagens das listas encadeadas:

Crescimento dinâmico.

Inserções/remoções eficientes.

Desvantagens:

Acesso sequencial (não direto).

Uso extra de memória (ponteiros).

Boa prova! Estude a lógica de manipulação de ponteiros e os métodos da LinkedList.

Foque nos casos especiais de remoção.

3:Lista Duplamente Encadeada

Resumo para Prova de Java - Listas Duplamente Encadeadas
Conceitos-chave e pontos para estudo (7 questões teóricas + 1 prática):

1. Listas Duplamente Encadeadas vs. Simples

Simples:

Cada nó aponta apenas para o próximo (proximo).

Operações no fim são ineficientes (O(n)).

Duplamente Encadeada:

Cada nó tem dois ponteiros:

anterior: Aponta para o nó precedente.

proximo: Aponta para o nó seguinte.

Vantagens:

Navegação bidirecional (frente/trás).

Remoções no fim O(1).

2. Estrutura do Nó
java
class NoDuplo<T> {
T dado;
NoDuplo<T> anterior;
NoDuplo<T> proximo;

public NoDuplo(T dado) {

[Link] = dado;
[Link] = null;
[Link] = null;
}
}
3. Operações Principais (Implementação Manual)
a) Adicionar no Final:
java
public void adicionar(T dado) {
NoDuplo<T> novoNo = new NoDuplo<>(dado);
if (inicio == null) { // Lista vazia
inicio = novoNo;
fim = novoNo;
} else {
[Link] = novoNo;
[Link] = fim;
fim = novoNo; // Atualiza o fim
}
}
b) Remover por Índice:
java
public void remover(int indice) {
NoDuplo<T> atual = inicio;
for (int i = 0; i < indice; i++) atual = [Link];
 if (atual == inicio) { // Remoção no início
inicio = [Link];
[Link] = null;
} else if (atual == fim) { // Remoção no fim
fim = [Link];
[Link] = null;
} else { // Meio
[Link] = [Link];
[Link] = [Link];
}
}
c) Buscar Antecessor:
java
public T antecessor(T dado) {
NoDuplo<T> atual = inicio;
while (atual != null) {
if ([Link](dado)) {
if (atual == inicio)
throw new Exception("Primeiro elemento não tem antecessor!");
return [Link];
}
atual = [Link];
}
throw new Exception("Elemento não encontrado!");
}
4. Casos Especiais
Lista vazia: inicio e fim são null.

Único elemento:

inicio e fim apontam para o mesmo nó.

anterior e proximo são null.

Adicionar/remover no início/fim: Atualizar inicio/fim e ponteiros adjacentes.

5. Complexidade
Operação Complexidade
Inserir no início/fim O(1)
Remover no início/fim O(1)
Busca por índice O(n)
6. Aplicações Práticas
Navegadores: Histórico (avançar/voltar).

Editores de texto: Operações "undo/redo".

Playlists: Controle bidirecional de músicas.

7. Dicas para a Questão de Código

Foco comum: Implementar adicionar(), remover(), buscarAntecessor().

Passos críticos:

Tratar lista vazia.

Atualizar ponteiros anterior e proximo.

Atualizar inicio/fim quando necessário.

Exemplo de inicialização:

java
ListaDuplaEncadeada<String> lista = new ListaDuplaEncadeada<>();
[Link]("A");
[Link]("B");
[Link](0); // Remove "A"
8. Conceitos Teóricos para Revisar
Vantagens: Eficiência em operações no fim da lista.

Desvantagens:

Consumo extra de memória (dois ponteiros por nó).

Complexidade de implementação.

Diferença para lista simples: Capacidade de navegação reversa.

Boa prova! Estude a lógica de manipulação dos ponteiros anterior e proximo e os

casos especiais de inserção/remoção.

4:Grafos

Resumo para Prova de Java - Grafos

Conceitos-chave e pontos para estudo (7 questões teóricas + 1 prática):

1. Definição e Conceitos Básicos

Grafo: Estrutura matemática
G
=
(
V
,
E
)
G=(V,E) onde:

V
V: Conjunto de vértices (nós)

E
E: Conjunto de arestas (conexões entre vértices)

Aplicações:

Mapas (ruas = arestas, cruzamentos = vértices)

Redes sociais (pessoas = vértices, relações = arestas)

Redes de computadores (topologias)

2. Tipos de Grafos
Tipo Característica Exemplo
Não direcionado Arestas bidirecionais Redes sociais
Direcionado (Dígrafo) Arestas com direção (
u
→
v
u→v) Rotas de voo
Ponderado Arestas com pesos Distâncias entre cidades
Simples Sem arestas paralelas ou self-loops Árvores binárias
3. Terminologia Importante
Adjacência: Vértices conectados por uma aresta.

Grau de um vértice: Número de arestas incidentes.

Caminho: Sequência de vértices conectados por arestas.

Laço (self-loop): Aresta que conecta um vértice a si mesmo.

Vértice isolado: Sem conexões com outros vértices.

4. Implementação em Java
Classes Fundamentais:
Vertice<T>:

java
class Vertice<T> {
private T dado;
private List<Aresta<T>> arestasSaida; // Conexões de saída
private List<Aresta<T>> arestasEntrada; // Conexões de entrada
}
Aresta<T>:

java
class Aresta<T> {
private double peso;
private Vertice<T> inicio;
private Vertice<T> fim;
}
Grafo<T>:

java
class Grafo<T> {
private List<Vertice<T>> vertices;
private List<Aresta<T>> arestas;
}
Operações Básicas:
Adicionar vértice:

java
public void adicionarVertice(T dado) {
Vertice<T> novoVertice = new Vertice<>(dado);
[Link](novoVertice);
}
Adicionar aresta:

java
public void adicionarAresta(double peso, T inicio, T fim) {
Vertice<T> vInicio = buscarVertice(inicio);
 Vertice<T> vFim = buscarVertice(fim);
Aresta<T> aresta = new Aresta<>(peso, vInicio, vFim);
[Link]().add(aresta);
[Link]().add(aresta);
[Link](aresta);
}
5. Algoritmos de Busca
a) Busca em Largura (BFS):
Lógica: Visita vértices nível por nível (usa fila).

Implementação:

java
public void buscaEmLargura(Vertice<T> inicio) {
Queue<Vertice<T>> fila = new LinkedList<>();
Set<Vertice<T>> visitados = new HashSet<>();

[Link](inicio);
[Link](inicio);

while (![Link]()) {
Vertice<T> atual = [Link]();
[Link]([Link]());

for (Aresta<T> aresta : [Link]()) {

Vertice<T> vizinho = [Link]();
if () {
[Link](vizinho);
[Link](vizinho);
}
}
}
}
b) Busca em Profundidade (DFS):
Lógica: Explora ramificações profundamente antes de retroceder (usa
pilha/recursão).

6. Complexidade
Operação Complexidade
Adicionar vértice
O
(
1
)
O(1)
Adicionar aresta
O
(
1
)
O(1)
BFS / DFS ( O( V + E ) )
7. Casos de Estudo Clássicos
Problema das Pontes de Königsberg:

Primeiro problema resolvido com teoria dos grafos (Euler, 1736).

Problema do Caixeiro-Viajante:
Encontrar o caminho mais curto que visita todas as cidades.

Colorização de Mapas:

Número mínimo de cores para países vizinhos não compartilharem a mesma cor.

8. Dicas para a Questão de Código

Implementação típica:

Criar classes Vertice, Aresta, e Grafo.

Implementar adição de vértices/arestas.

Implementar BFS ou DFS.

Exemplo de uso:

java
Grafo<String> grafo = new Grafo<>();
[Link]("São Paulo");
[Link]("Rio de Janeiro");
[Link](400.0, "São Paulo", "Rio de Janeiro");
[Link]([Link]("São Paulo"));
9. Conceitos Teóricos para Revisar
Representações alternativas: Matriz de adjacência vs. Lista de adjacências.

Grafos conexos: Todos os vértices estão conectados por caminhos.

Dígrafos fortemente conexos: Caminhos direcionados entre todos os pares de

vértices.

Boa prova! Estude a implementação de BFS e a estrutura das classes Vertice/Aresta.

Foque nos casos de uso práticos (redes sociais, mapas).

5:Arvores

Conceitos Fundamentais de Árvores

Definição Formal:

Estrutura de dados não-linear e acíclica.

Composta por nós, com um nó especial chamado raiz (sem pai).

Cada nó (exceto a raiz) tem exatamente um pai e zero ou mais filhos.

Propriedades:

Nós internos: Possuem pelo menos um filho.

Folhas (nós externos): Sem filhos.

Ancestral/Descendente: Relação hierárquica entre nós (ex: D é ancestral de N).

Irmãos: Nós com o mesmo pai.

Terminologia:

Nível: Distância da raiz até o nó (raiz = nível 1).

Altura: Maior caminho da raiz até uma folha.

Profundidade: Comprimento do caminho da raiz ao nó.

Grau de um nó: Número de filhos (folha = grau 0).

Grau da árvore: Maior grau entre seus nós.

Representações de Árvores
Hierárquica:

plaintext
A
├─ B
│ ├─ E
│ └─ F
└─ C
└─ G
Parentizada:
(A (B (D() E())) (C (F())))

Não-Parentizada:
A 2 B 2 D 0 E 0 C 1 F 0

Exemplos Práticos
Aplicações:

Organogramas empresariais.

Sistemas de arquivos (diretórios/pastas).

Árvores genealógicas.

Exemplo de Árvore Corporativa:

plaintext
Electronics R' Us
├─ P&D
├─ Vendas
│ ├─ Nacional
│ └─ Internacional
└─ Manufatura
├─ TV
└─ CD
Implementação de Árvores Binárias
Usando Arrays
Adequado para árvores completas ou quase completas.
Armazenamento sequencial com indexação predefinida.

Usando Nós Dinâmicos (Java)

java
class No {
int dado;
No esquerda;
No direita;

public No(int dado) {

[Link] = dado;
[Link] = null;
[Link] = null;
}
}
Algoritmos de Busca
Pré-ordem (raiz-esq-dir):

java
void preOrdem(No no) {
if (no != null) {
[Link]([Link] + " ");
preOrdem([Link]);
preOrdem([Link]);
}
}
Em ordem (esq-raiz-dir):

java
void emOrdem(No no) {
if (no != null) {
emOrdem([Link]);
[Link]([Link] + " ");
emOrdem([Link]);
}
}
Pós-ordem (esq-dir-raiz):

java
void posOrdem(No no) {
if (no != null) {
posOrdem([Link]);
posOrdem([Link]);
[Link]([Link] + " ");
}
}
Exercícios Resolvidos (Páginas 31-43)
Raiz: A

Nós terminais: E, G, H, J, K, L, M, ... (folhas).

Grau da árvore: 4 (nó A tem 4 filhos).

Nível da árvore: 6 (maior caminho: A → B → C → H → S → #).

Descendentes de D: I, J, K, L, M, N, ...

Ancestrais de #: S, H, C, A
4 e 5 são irmãos? Não (pais diferentes: 4 filho de W, 5 filho de 3).

Caminho entre C e S? Sim (C → H → S).

Nível do nó 5: 5.

Grau de S: 2 (filhos: 8 e 9).

Observações Importantes
Convenções:

Altura de uma folha = 1.

Altura da árvore vazia = 0.

Profundidade da raiz = 1.

Representação Computacional:

Raiz no topo (contrário da natureza).