# Estruturas de Dados, Análise de Complexidade (Big-O) e Algoritmos Essenciais

> Revisão de graduação que exige noções básicas de programação: 32 cartões sobre vetores, listas, hashing, árvores, heaps, tries, Union–Find, filtros de Bloom e complexidade.

- **Canonical URL:** https://flashcards.world/flashcards/sets/b94c6e27-e5b7-4000-a693-3cda8d452d49/
- **Markdown URL:** https://flashcards.world/flashcards/sets/b94c6e27-e5b7-4000-a693-3cda8d452d49.md
- **Level:** basic
- **Languages:** pt-br → pt-br
- **Total Cards:** 32

## Flashcards (32 Cards)

| # | Front (Term / Prompt) | Back (Definition / Answer) | Example | Multiple-Choice Options |
| :--- | :--- | :--- | :--- | :--- |
| 1 | Como sondagem linear e quadrática diferem no endereçamento aberto? | As entradas ficam no vetor. Para tamanho m e índice inicial h, usam-se (h+i) mod m e (h+c₁i+c₂i²) mod m, respectivamente. A sondagem quadrática exige parâmetros adequados. |  |  |
| 2 | Quais são as ordens dos percursos pré-ordem, em ordem e pós-ordem em uma árvore binária? | Pré-ordem: nó → esquerda → direita. Em ordem: esquerda → nó → direita. Pós-ordem: esquerda → direita → nó. |  |  |
| 3 | Quais são as duas propriedades de um heap binário mínimo? | É uma árvore binária completa, e a chave de cada pai não supera as de seus filhos. Assim, a raiz contém um mínimo. |  |  |
| 4 | Quais são os custos esperados e de pior caso de uma tabela hash com encadeamento separado? | Com carga limitada, hashes bem distribuídos e operações sobre chaves de custo constante, busca/exclusão têm custo esperado O(1). Com crescimento geométrico, inserir custa O(1) amortizado esperado. Uma cadeia de n chaves em colisão pode causar O(n). |  |  |
| 5 | Ordene estes crescimentos do mais lento ao mais rápido quando n → ∞: n!, n, 1, n², log n, 2ⁿ, n log n. | Assintoticamente: 1 < log n < n < n log n < n² < 2ⁿ < n!. |  |  |
| 6 | Por que uma lista duplamente encadeada pode excluir um nó dado em O(1)? | Seus elos anterior e seguinte permitem reconectar diretamente os vizinhos. Atualizam-se início e fim quando necessário; não é preciso procurar o predecessor. |  |  |
| 7 | Que invariante de ordem define uma árvore binária de busca (BST) com chaves distintas? | Em cada nó, todas as chaves da subárvore esquerda são menores e todas as da direita são maiores. A regra vale recursivamente. |  |  |
| 8 | Compare inserção no início e acesso por índice em uma lista simplesmente encadeada e um vetor dinâmico. | Lista: inserção inicial O(1), acesso por índice O(n). Vetor: inserção inicial O(n), acesso por índice O(1); inserir no início desloca elementos. |  |  |
| 9 | O que é uma trie e quando buscar uma chave de L caracteres custa O(L)? | É uma árvore de prefixos que armazena chaves em caminhos de caracteres, com marcas para chaves completas. A busca custa O(L) se cada transição para o próximo caractere custa O(1). |  |  |
| 10 | Que regras de cor mantêm uma BST rubro-negra balanceada? | Os nós são vermelhos ou pretos; raiz e folhas NIL são pretas. Nós vermelhos não têm filhos vermelhos. Todo caminho de um nó a uma folha NIL descendente contém o mesmo número de nós pretos. Isso limita a altura a O(log n). |  |  |
| 11 | Como um percurso por níveis visita uma árvore binária? | Usa uma fila FIFO para visitar um nível de profundidade por vez. Enfileirar o filho esquerdo antes do direito produz a ordem da esquerda para a direita. |  |  |
| 12 | Qual é a diferença entre O, Ω e Θ? | Indicam limites assintóticos superior, inferior e justo, respectivamente. Descrevem uma função de custo especificada; O não significa, por si só, pior caso. |  |  |
| 13 | Como uma fila em vetor circular evita deslocamentos após uma retirada? | Os índices inicial e final avançam módulo a capacidade. A retirada avança o índice inicial, permitindo reutilizar posições livres sem mover os outros elementos. |  |  |
| 14 | O que é o fator de carga de uma tabela hash e por que ela pode ser redimensionada? | α = n/m: n entradas e m compartimentos ou posições. Ultrapassar o limiar da implementação pode provocar ampliação e recálculo da distribuição; 0,75 não é universal. |  |  |
| 15 | Com a capacidade dobrando, qual é o custo amortizado de acrescentar ao final de um vetor dinâmico? | O(1) por inserção. Redimensionar pode custar O(n), mas n inserções ao final, partindo de um vetor vazio, custam O(n) no total. |  |  |
| 16 | O que produz um percurso em ordem de uma BST com chaves distintas? | Todas as chaves em ordem estritamente crescente, visitando n nós em O(n). |  |  |
| 17 | Como diferem compressão de caminhos, união por posto e união por tamanho? | A compressão redireciona os nós visitados à raiz. Por posto, a raiz de menor posto fica sob a de maior posto; por tamanho, o conjunto menor fica sob o maior. O posto não precisa ser a altura atual. |  |  |
| 18 | Quanto custam inserir, remover a raiz e consultar a raiz em um heap binário? | O(log n), O(log n) e O(1), respectivamente, se não for necessário redimensionar o vetor. Um redimensionamento pode custar O(n). |  |  |
| 19 | Qual é a regra de acesso de uma fila e quais são os custos típicos de suas operações? | FIFO: inserir no fim e retirar do início. Ambas custam O(1) com elos para início/fim ou um buffer circular de capacidade fixa; deslocar um vetor torna a retirada O(n). |  |  |
| 20 | Que propriedades uma função hash deve ter para buscas em uma tabela? | Deve ser determinística e distribuir bem as chaves esperadas. Calcular o hash de chaves de tamanho fixo pode custar O(1); o de uma nova cadeia de L caracteres costuma custar O(L). |  |  |
| 21 | Qual é o custo amortizado de union/find com compressão de caminhos e união por posto? | O(α(n)) por operação, onde α é a inversa de Ackermann e n é o número de elementos. Inicializar custa O(n); o limite vale para uma sequência, não como custo constante de pior caso de cada chamada. |  |  |
| 22 | O que fazem find e union em uma estrutura de conjuntos disjuntos? | find(x) retorna o representante do conjunto de x. union(x,y) une os conjuntos se forem diferentes; se já forem o mesmo, a partição não muda. |  |  |
| 23 | Como o encadeamento separado resolve colisões de hash? | Cada compartimento contém uma coleção de entradas com aquele índice, frequentemente uma lista encadeada. Chaves diferentes no mesmo compartimento continuam sendo entradas separadas. |  |  |
| 24 | Como busca, inserção e exclusão em uma BST dependem da altura h? | Custam O(h). Uma árvore balanceada tem h = O(log n); uma cadeia, h = O(n). O custo esperado O(log n) exige hipóteses como ordem aleatória de inserção. |  |  |
| 25 | Onde estão o pai e os filhos do nó i em um vetor de heap com comprimento n e índices a partir de zero? | Pai: ⌊(i−1)/2⌋ para i>0. Filhos: 2i+1 e 2i+2, somente se esses índices forem menores que n. O índice 0 não tem pai. |  |  |
| 26 | Como corrigir um desequilíbrio esquerda-direita após uma inserção AVL? | Primeiro, rotacione o filho esquerdo para a esquerda; depois, o nó desequilibrado para a direita. |  |  |
| 27 | Como funciona uma pilha e quando suas operações custam O(1)? | LIFO: o último item inserido sai primeiro. No início de uma lista encadeada, inserir, retirar e consultar o topo custam O(1); redimensionar um vetor pode tornar uma inserção O(n). |  |  |
| 28 | Qual é a condição de balanceamento AVL? | Em cada nó, altura(esquerda) − altura(direita) ∈ {−1, 0, 1}. A árvore também satisfaz o invariante de ordem da BST. |  |  |
| 29 | Que respostas um filtro de Bloom que só permite inserções pode dar? | Um resultado negativo indica que o item não foi inserido; um positivo, que pode ter sido. Os hashes ativam bits em um vetor: falsos positivos são possíveis, mas falsos negativos não, se o estado estiver intacto. |  |  |
| 30 | Por que o acesso por índice em um vetor de tamanho fixo custa O(1)? | As posições de mesmo tamanho são contíguas: endereço(i) = base + i·tamanho_posição. Supõe-se que calcular endereços leve tempo constante. |  |  |
| 31 | Para funções não negativas f e g, o que significa f(n) ∈ O(g(n))? | Existem constantes c > 0 e n₀ ≥ 0 tais que f(n) ≤ c·g(n) para todo n ≥ n₀. |  |  |
| 32 | Quanto custa construir um heap de baixo para cima com n itens? | O(n). A maioria dos nós fica perto das folhas e exige poucas descidas; somar o trabalho por altura do nó resulta em custo linear. |  |  |

---
Study this deck interactively with FSRS-6 spaced repetition, audio review, and multiple-choice mode at [Flashcards World](https://flashcards.world/flashcards/sets/b94c6e27-e5b7-4000-a693-3cda8d452d49/).