Estruturas de dados: questões para praticar com explicações

1O que é uma estrutura de dados

Uma estrutura de dados é uma forma de organizar dados na memória para que certas operações sejam rápidas: encontrar um item, inserir um, remover um.

Nenhuma estrutura é rápida em tudo. Escolher uma significa escolher quais operações devem ser baratas. Seus custos são escritos em notação Big O, com n o número de itens.

Os dois blocos básicos são o vetor (array) e a lista encadeada.

Um vetor (array) guarda seus itens num único bloco de memória, um depois do outro. O computador calcula onde está o item i, então ler a[i] custa O(1). Inserir no início exige deslocar todos os itens: O(n).

Uma lista encadeada guarda cada item num nó com um ponteiro para o próximo nó. O último ponteiro é nulo (null). Inserir na cabeça (h) altera apenas um ponteiro: O(1). Mas, para chegar ao item i, é preciso seguir i ponteiros: O(n).

Uma lista duplamente encadeada também tem um ponteiro para o nó anterior, então é possível percorrê-la nos dois sentidos.

2Pilhas e filas

Uma pilha (stack) é como uma pilha de pratos: só se adiciona e remove no topo. O último a entrar é o primeiro a sair: LIFO.

• push coloca um item no topo, pop remove o item do topo, peek lê o topo sem remover. Todas custam O(1).
• Usos: a função desfazer de um editor, a pilha de chamadas de um programa, a verificação de parênteses balanceados, a busca em profundidade.

Uma fila (queue) é como a fila de um caixa: entra-se no fim e sai-se no início. O primeiro a entrar é o primeiro a sair: FIFO.

• enqueue adiciona no fim, dequeue remove do início. Ambas custam O(1).
• Usos: trabalhos de impressão, mensagens esperando para serem tratadas, busca em largura.

Uma deque (fila de duas pontas) permite adicionar e remover nas duas extremidades. Uma fila de prioridade sempre remove primeiro o item de maior prioridade; costuma ser construída como um heap.

3Árvores, heaps, tabelas hash e grafos

Uma árvore tem um nó no topo, a raiz. Todo outro nó tem exatamente um pai. Nós sem filhos são folhas. Uma árvore com n nós tem n − 1 arestas.

Numa árvore binária, cada nó tem no máximo dois filhos. Uma árvore binária de busca (BST) acrescenta uma regra: as chaves da subárvore esquerda são menores que o nó, as da subárvore direita são maiores.

A busca numa BST segue um único caminho para baixo, então custa O(altura). Uma árvore balanceada (AVL, rubro-negra) mantém a altura próxima de log₂ n. Chaves inseridas em ordem crescente formam uma cadeia de altura n.

Um heap é uma árvore binária em que todo pai é menor que seus filhos (min-heap) ou maior (max-heap). O mínimo ou o máximo está na raiz, e inserir e remover custam O(log n).

Uma tabela hash guarda pares chave–valor. Uma função hash transforma a chave em um índice, então inserir e buscar levam O(1) em média. Duas chaves com o mesmo índice formam uma colisão, resolvida por encadeamento (uma lista por posição) ou por endereçamento aberto (tentar outra posição).

Um grafo tem vértices ligados por arestas, que podem ter direção ou peso. É armazenado como matriz de adjacência, com memória O(V²), ou como listas de adjacência, O(V + E).

4O método passo a passo

As questões costumam descrever uma tarefa e perguntar qual estrutura se adequa, ou perguntar como fica uma estrutura depois de algumas operações.

1. Encontre a operação que precisa ser rápida: acesso por posição, por chave, o item mais novo, o mais antigo, o menor ou um intervalo.
2. Associe-a a uma estrutura: índice → vetor, chave → tabela hash, mais novo → pilha, mais antigo → fila, menor ou maior → heap, ordem ou intervalos → árvore de busca balanceada.
3. Verifique o custo das outras operações de que a tarefa precisa, em Big O.
4. Numa questão de simulação, execute as operações uma de cada vez e anote o estado após cada uma.
5. Confira o estado final com a regra da estrutura: LIFO, FIFO, a ordem da BST ou a ordem do heap.

5Um exemplo resolvido

Acompanhe cada passo. Tente prever o próximo antes de abri-lo.

6Erros comuns

• Confundir LIFO e FIFO. Uma pilha devolve o item mais novo, uma fila o mais antigo.
• Achar que uma lista encadeada dá acesso rápido por índice. Ela precisa percorrer a partir da cabeça.
• Supor que uma BST é sempre O(log n). Só uma árvore balanceada é; inserções em ordem crescente dão O(n).
• Esquecer as colisões numa tabela hash. O(1) é a média, não o pior caso.
• Confundir os percursos. Pré-ordem: nó primeiro. Em ordem: nó no meio. Pós-ordem: nó por último.
• Usar uma matriz de adjacência para um grafo grande e esparso. Ela desperdiça memória O(V²).

7Como são as questões de prova

• Fácil: termos e fatos essenciais. LIFO e FIFO, o que é um nó, uma raiz ou uma folha, a regra da BST, o que faz uma função hash.
• Médio: aplicação dos conceitos. Qual estrutura se adequa a uma tarefa, o resultado de push e pop ou de inserções numa BST, percursos de árvores, uma tabela hash com sondagem linear, custos em Big O.
• Difícil: casos e análise. Árvores balanceadas, heaps em vetores, árvores B, tries, union-find, filtros de Bloom e projetos como um cache LRU.

Para um heap guardado num vetor a partir do índice 0, os filhos do índice i estão em 2i + 1 e 2i + 2, e o pai está em ⌊(i − 1) / 2⌋.