INF01203 - Estruturas de Dados - Instituto de Informática (UFRGS) - Prof. Dennis Giovani Balreira
Aula 15 - Revisão Prova 1 + Simulado
Esta aula reúne um roteiro de revisão de todos os tópicos cobertos na Área I da disciplina (Aulas 1 a 12), que constituem o conteúdo da Prova 1. Para cada tópico há um resumo dos conceitos essenciais, as perguntas que você deve ser capaz de responder e os tipos de exercícios que podem aparecer. Use este material como um guia de estudo — não como substituto da leitura das aulas.
Estrutura da Prova 1
A Prova 1 avalia compreensão conceitual e capacidade de implementação em C. Os tipos de questão mais frequentes são:
- Definições e propriedades (conceituais, sem código).
- Traçar a execução de um algoritmo sobre uma estrutura de dados dada.
- Implementar funções em C para operações sobre as estruturas estudadas.
- Analisar a complexidade de operações e justificar.
- Comparar estruturas de dados, apontando vantagens e desvantagens.
1. Complexidade de Algoritmos (Aula 2a)
O que saber
- Notação O (big O): o que ela mede e o que ela ignora (constantes, termos de menor ordem).
- Hierarquia de complexidades:
O(1) < O(log n) < O(n) < O(n log n) < O(n²).
- Como calcular a complexidade de funções simples: contar iterações de laços, identificar recursão linear vs. recursão que dobra o trabalho.
- Diferença entre pior caso, melhor caso e caso médio.
Ponto de atenção: a complexidade de uma operação em uma estrutura de dados depende de como ela está organizada internamente. Inserir no início de uma lista encadeada é O(1); inserir no início de um vetor é O(n). Buscar em uma Abp balanceada é O(log n); na mesma Abp degenerada, é O(n). Sempre justifique a complexidade relacionando com a estrutura.
|
2. Tipos Abstratos de Dados — TAD (Aula 2b)
O que saber
- O que é um TAD: separação entre interface (o que a estrutura faz) e implementação (como ela faz).
- Por que usar TAD: modularidade, encapsulamento, substituição de implementação sem afetar o código que usa a estrutura.
- Diferença entre um TAD e uma estrutura de dados concreta.
3. Listas (Aulas 2c, 4, 6a, 6b)
O que saber
- Lista contígua (vetor): acesso direto
O(1) por índice; inserção/remoção no meio é O(n) (desloca elementos).
- Lista simplesmente encadeada: inserção/remoção eficiente em qualquer posição conhecida (
O(1) dados os ponteiros); percurso só para frente; sem acesso direto por índice.
- Lista duplamente encadeada: percurso nos dois sentidos; inserção/remoção mais simples (não precisa do ponteiro anterior separado); maior uso de memória (dois ponteiros por nó).
- Lista circular: o último nó aponta para o primeiro; útil quando o percurso deve "dar a volta" indefinidamente.
- Para cada tipo: estrutura do nó, do descritor, e implementação das operações básicas (criar, inserir, remover, buscar, destruir).
| Operação |
Vetor (contíguo) |
Lista enc. simples |
Lista enc. dupla |
| Acesso por índice |
O(1) |
O(n) |
O(n) |
| Inserir no início |
O(n) |
O(1) |
O(1) |
| Inserir no final |
O(1)* |
O(n) (sem ponteiro final) / O(1) (com) |
O(1) (com ponteiro final) |
| Remover (posição conhecida) |
O(n) |
O(1) (com ponteiro anterior) |
O(1) |
| Busca sequencial |
O(n) |
O(n) |
O(n) |
* Amortizado; pode ser O(n) se for necessário realocar o vetor.
4. Algoritmos de Ordenação (Aula 8)
O que saber
- Insertion Sort: mantém um prefixo ordenado; a cada passo, insere o próximo elemento na posição correta dentro do prefixo.
O(n²) no pior caso; O(n) para vetores quase ordenados.
- Shell Sort: generalização do Insertion Sort com saltos (gap) decrescentes; na prática, muito mais rápido que Insertion Sort; análise teórica depende da sequência de gaps escolhida.
- Como rastrear a execução de um passo de cada algoritmo sobre um vetor dado.
5. Pilhas, Filas e Deques (Aulas 9a, 9b, 9c)
O que saber
- Pilha (LIFO): o último a entrar é o primeiro a sair. Operações:
push (empilhar), pop (desempilhar), top (topo). Aplicações: avaliação de expressões, verificação de parênteses, chamadas recursivas.
- Fila (FIFO): o primeiro a entrar é o primeiro a sair. Operações:
enqueue (enfileirar), dequeue (desenfileirar). Aplicações: agendamento de processos, BFS em grafos e árvores.
- Deque (double-ended queue): inserção e remoção em ambas as extremidades. Generaliza pilha e fila.
- Implementação encadeada e suas complexidades (todas
O(1) com ponteiros corretos).
|
Relação com caminhamentos: DFS (pré, em, pós-ordem em árvores) usa pilha implícita (recursão). BFS (caminhamento em nível) usa fila explícita. Saber justificar essa relação é frequentemente cobrado em prova.
|
6. Árvores Binárias e Caminhamentos (Aula 11)
O que saber
- Terminologia: raiz, pai, filho, irmão, folha, nó interno, subárvore, nível/profundidade, altura de nó, altura da árvore.
- Conversão de árvore genérica para binária: representação "filho-esquerdo, irmão-direito".
- Por que árvores "pedem" recursão: definição recursiva da estrutura.
- Tipos de árvore binária: cheia, perfeita, balanceada, degenerada.
- Os quatro caminhamentos: pré-ordem, em-ordem, pós-ordem (DFS, recursivos) e em nível (BFS, iterativo com fila).
- Dado um caminhamento, ser capaz de rastrear a ordem de visita dos nós.
7. Árvore Binária de Pesquisa (Aula 12)
O que saber
- A propriedade de ordenação da Abp e por que ela deve valer recursivamente.
- Por que a Abp não usa descritor (como as listas usam).
- Como as operações (buscar, inserir, remover, destruir, altura) são implementadas recursivamente.
- Os três casos da remoção e por que o caso de dois filhos usa o sucessor em-ordem.
- Complexidade de todas as operações em função da altura
h.
- O problema da árvore degenerada: o que é, quando ocorre, e como afeta a complexidade.
8. Resumo de Complexidades
| Estrutura |
Busca |
Inserção |
Remoção |
| Vetor não ordenado |
O(n) |
O(1) (fim) |
O(n) |
| Vetor ordenado |
O(log n) (binária) |
O(n) (mantém ordem) |
O(n) |
| Lista encadeada |
O(n) |
O(1) (dado o nó anterior) |
O(1) (dado o nó anterior) |
| Pilha / Fila |
— |
O(1) |
O(1) |
| Abp balanceada |
O(log n) |
O(log n) |
O(log n) |
| Abp degenerada |
O(n) |
O(n) |
O(n) |