Caderno de Exercícios

Estruturas de Dados Lineares e Gestão de Memória em C

---

1. 🎯 Introdução e Contextualização

O domínio de ponteiros, alocação dinâmica e da correta arquitetura de Tipos Abstratos de Dados (TADs) é um divisor de águas entre um programador iniciante e um engenheiro de computação.

Na prática:

• Eficiência não é acidental → é resultado de decisões conscientes
• Organização de dados impacta diretamente o desempenho
• Gestão de memória é crítica para estabilidade e segurança

Um código que funciona em pequena escala pode falhar sob carga se:

• houver uso incorreto do heap
• faltar encapsulamento
• não existir controle do ciclo de vida da memória

O objetivo deste caderno é fazer você pensar como arquiteto de software, não apenas como programador.

---

2. 📏 Critérios de Avaliação (Rigor Arquitetural)

Para que uma solução seja considerada correta:

Segurança de Alocação

• Sempre verificar o retorno de malloc, calloc ou realloc
• NULL não tratado = erro crítico

Gestão de Memória (Accountability)

• Todo malloc deve ter um free
• Vazamento de memória = falha grave

Encapsulamento

• main.c deve usar apenas funções do .h
• Acesso direto à struct = violação de projeto

Sem Variáveis Globais

• Comunicação entre módulos → via parâmetros e retornos

---

3. 🧠 Parte I — Fundamentos Teóricos (11 Questões)

Conceito central

Separar:

• O que fazer (interface) → .h
• Como fazer (implementação) → .c

---

Questões

1. Passagem por valor vs referência

   Explique por que funções como empilha(Pilha *p, int x) usam ponteiros.

   O que aconteceria se a pilha fosse passada por valor?

---

1. Stack vs Heap

   Diferencie:

   • Stack (automática)
   • Heap (dinâmica)

   Quem gerencia cada uma?

   Por que retornar variável local é perigoso?

---

1. Tipo Abstrato de Dado (TAD)

   Defina formalmente um TAD.

   Qual o papel do .h?

---

1. LIFO e aplicações reais

   Explique LIFO e aplique em:

   • Navegadores (histórico)
   • Editores (undo/redo)
   • Chamadas de função (recursão)

---

1. Ponteiros e vetores

   Explique:

v[i] == *(v + i)

Como o compilador calcula o endereço?

---

1. Complexidade (Pior Caso)

   Qual o custo da busca em lista não ordenada?

   Por que usamos pior caso?

---

1. Encapsulamento na prática

   Por que main.c não deve acessar l->ultimo?

---

1. Alocação dinâmica vs estática

   Compare:

   • Flexibilidade
   • Fragmentação

---

1. Comparação de Pilhas

Critério	Estática (Vetor)	Dinâmica (Encadeada)
Overhead	Baixo	Alto
Cache	Alto	Baixo
Crescimento	Fixo	Dinâmico
Limite	Compilação	RAM

---

1. Operador >

   Explique por que:

*p.membro   // errado
(*p).membro // correto
p->membro   // correto

---

1. Rastreamento de memória

   Dado:

topo = -1

Simule:

push(10)
push(20)
pop()
push(30)
push(40)

Desenhe a tabela de memória

---

4. 💻 Parte II — Implementação Prática (15 Questões)

Aqui começa o nível engenharia real: ponteiros mal usados = bugs graves.

---

Exercícios

1. Struct + Ponteiro
   • Crie struct Ponto
   • Função que altera via ponteiro

---

1. Alocação segura
   • Criar vetor dinâmico
   • Verificar erro
   • Inicializar com zero

---

1. Refatoração

   • Remover globais:

     int pilha[MAX];
     int topo;
     

   • Criar TAD

---

1. Push com verificação
   • Implementar empilha
   • Tratar overflow

---

1. Pop em lista encadeada
   • Remover nó
   • Liberar memória

---

1. Inicialização segura
   • Lista* criaLista()
   • Retornar NULL se falhar

---

1. Busca sequencial
   • Implementar
   • Justificar O(n)

---

1. Inserção com deslocamento
   • Lista estática
   • Validar posição

---

1. Liberação de lista
   • Liberar todos os nós
   • Evitar perda de referência

---

1. realloc seguro
2. Dobrar tamanho
3. Usar ponteiro temporário

---

1. Busca por posição
2. Vetor → O(1)
3. Lista → O(n)

---

1. Inversão com pilha
2. Usar estrutura auxiliar

---

1. Lista circular

2. Último aponta para primeiro

   O while (atual != NULL) funciona?

---

1. Reuso de funções (DRY)

2. removeValor usando outras funções

   Qual a complexidade total?

---

1. Bug de precedência

   Corrigir:

*p.membro = 10;

Explique o erro

---

5. 📊 Análise de Complexidade

Comparativo

Operação	Vetor	Lista Encadeada
Acesso	O(1)	O(n)
Inserção início	O(n)	O(1)
Inserção fim	O(1)	O(n)*
Localidade	Alta	Baixa
- Pode ser O(1) com ponteiro para o último

---

6. 🧪 Questão Bônus (Projeto)

Desenvolva uma pilha com:

• push
• pop
• findMax() → O(1)

Dica:

Use uma pilha auxiliar de máximos

---

7. ✅ Checklist Final

Antes de entregar:

• [ ] Todo malloc tem free
• [ ] Verificou NULL
• [ ] Estrutura validada antes de uso
• [ ] Sem variáveis globais
• [ ] Encapsulamento respeitado

---

⚠️ Regra de Ouro

Variáveis globais são proibidas.

Controle de memória e escopo é responsabilidade do programador.

---