# Algoritmos, grafos, programação dinâmica e bancos de dados relacionais

> 32 cartões de revisão de graduação sobre ordenação, algoritmos de grafos, programação dinâmica, SQL, índices e transações. Requer programação básica, estruturas de dados e SQL.

- **Canonical URL:** https://flashcards.world/flashcards/sets/e55e30f2-b097-4c84-ab4d-596a3a7b359a/
- **Markdown URL:** https://flashcards.world/flashcards/sets/e55e30f2-b097-4c84-ab4d-596a3a7b359a.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 | Quais são as duas fases do bloqueio em duas fases (2PL)? | Crescimento: adquirir bloqueios sem liberá-los. Encolhimento: liberar bloqueios sem adquirir novos. Com bloqueios adequados para leituras e escritas conflitantes, 2PL garante escalonamentos serializáveis por conflito, mas impasses continuam possíveis. |  |  |
| 2 | Por que quicksort pode levar Θ(n²) e como a aleatoriedade ajuda? | Partições repetidamente desequilibradas, como escolher sempre a menor chave entre chaves distintas, causam trabalho quadrático. Com chaves distintas ou tratamento adequado de duplicatas, pivôs aleatórios dão tempo esperado O(n log n). A mediana de três é uma heurística útil, não uma garantia para o pior caso. |  |  |
| 3 | O que é uma leitura suja e qual primeiro nível padrão a impede? | Ler dados não confirmados de outra transação, independentemente de ela ser depois desfeita. READ COMMITTED e os níveis padrão superiores proíbem leituras sujas. |  |  |
| 4 | Como funciona a ordenação por inserção e de que depende seu custo em dados quase ordenados? | Ela insere cada item em um prefixo ordenado. A versão usual com deslocamentos ou trocas adjacentes leva Θ(n+I), sendo I o número de inversões. É linear quando I=O(n); uma entrada pequena não muda o pior caso Θ(n²). |  |  |
| 5 | O que torna estável um algoritmo de ordenação? | Itens com chaves iguais mantêm sua ordem relativa original. Merge sort pode ser estável se escolher primeiro o item da esquerda em empates; o quicksort usual no próprio vetor geralmente é instável. A estabilidade depende da implementação. |  |  |
| 6 | Como a busca em profundidade detecta um ciclo em um grafo dirigido? | DFS aprofunda a exploração usando recursão ou uma pilha explícita. Uma aresta para um vértice ainda ativo no caminho DFS atual é de retorno e comprova um ciclo dirigido; apontar para qualquer vértice já visitado não basta. |  |  |
| 7 | Como se comparam matriz de adjacência e listas de adjacência comuns? | Com V vértices e E arestas, a matriz usa O(V²) espaço e verifica uma aresta em O(1). As listas usam O(V+E); procurar (u,v) em uma lista não ordenada custa O(deg(u)), sendo deg(u) o comprimento dessa lista. |  |  |
| 8 | Como a busca em largura encontra caminhos mínimos em um grafo não ponderado? | BFS usa uma fila FIFO e explora por distância em número de arestas. Marcar um vértice ao inseri-lo na fila evita visitas repetidas. O primeiro caminho descoberto até um vértice alcançável tem o menor número de arestas. |  |  |
| 9 | Por que árvores B+ são úteis para índices e consultas por intervalo? | A alta ramificação mantém a árvore baixa e reduz acessos a páginas. Chaves ordenadas e folhas encadeadas permitem percorrer intervalos. Índices hash visam buscas por igualdade e não oferecem por si só o mesmo acesso ordenado por intervalo. |  |  |
| 10 | O que é uma ordem topológica e como o algoritmo de Kahn a encontra? | Em um DAG, cada aresta u→v coloca u antes de v. Retira-se repetidamente um vértice de grau de entrada zero, removendo suas arestas de saída e enfileirando os novos vértices de grau zero. Se saírem menos de V vértices, há um ciclo dirigido. |  |  |
| 11 | Como diferem memoização e programação dinâmica de baixo para cima? | A memoização avalia subproblemas sob demanda, geralmente por recursão, e guarda os resultados. A abordagem de baixo para cima avalia estados quando suas dependências já estão disponíveis, normalmente preenchendo uma tabela. |  |  |
| 12 | Como INNER JOIN e LEFT JOIN diferem? | INNER JOIN retorna combinações de linhas que satisfazem a condição de junção. LEFT JOIN também mantém cada linha esquerda sem correspondência, com NULL nas colunas direitas. Várias correspondências podem produzir várias linhas por linha esquerda. |  |  |
| 13 | O que significam as propriedades ACID de uma transação? | Atomicidade: todos os efeitos ou nenhum. Consistência: transações corretas preservam restrições e invariantes da aplicação. Isolamento: a concorrência respeita o nível escolhido. Durabilidade: efeitos confirmados sobrevivem às falhas cobertas pelas garantias configuradas. |  |  |
| 14 | O que a busca binária exige e quando leva O(log n)? | Ela divide repetidamente o intervalo de busca ao meio em dados ordenados segundo o critério de comparação. Em um vetor com acesso por índice O(1) e comparações de tempo constante, buscar entre n elementos custa O(log n). |  |  |
| 15 | Qual é a recorrência para o comprimento da maior subsequência comum (LCS)? | L[i,j] é o comprimento da LCS de prefixos de comprimentos i,j. L[0,j]=L[i,0]=0. Se os últimos caracteres coincidem, L[i,j]=1+L[i−1,j−1]; senão, L[i,j]=max(L[i−1,j],L[i,j−1]). A tabela completa usa O(mn) tempo e espaço. |  |  |
| 16 | O que exigem a primeira, segunda e terceira formas normais? | 1FN: valores atômicos. 2FN: 1FN e nenhum atributo não primo depende de uma parte própria de qualquer chave candidata. 3FN: 1FN e, em toda dependência não trivial X→A, X é superchave ou A é primo. Um atributo primo pertence a alguma chave candidata. |  |  |
| 17 | O que é uma leitura fantasma e como evitá-la? | Repetir uma consulta com predicado encontra outro conjunto de linhas correspondentes após alterações confirmadas por outra transação. SERIALIZABLE a impede no modelo padrão; algumas implementações, como REPEATABLE READ do PostgreSQL, também a impedem em um nível inferior. |  |  |
| 18 | Como Bellman–Ford trata arestas negativas e detecta um ciclo negativo alcançável? | Relaxa todas as arestas até V−1 vezes. Uma melhora adicional a partir de um vértice alcançável revela um ciclo negativo alcançável da origem. O pior caso custa O(VE); vértices alcançáveis desse ciclo não têm custo mínimo finito. |  |  |
| 19 | Como o WAL apoia a durabilidade do PostgreSQL com commit síncrono normal? | Os registros necessários chegam ao armazenamento durável antes da confirmação do commit e antes da gravação das páginas alteradas. Após uma falha, o WAL pode reproduzir alterações ausentes nas páginas. O commit assíncrono pode perder transações recentes já confirmadas. |  |  |
| 20 | Como funciona o merge sort padrão para vetores e quais são seus custos? | Ele ordena recursivamente duas metades e as intercala em tempo linear. A versão padrão leva Θ(n log n) tempo e O(n) espaço auxiliar, supondo comparações de tempo constante. |  |  |
| 21 | O que é uma leitura não repetível e qual nível padrão a impede? | Ao reler uma linha, seus dados mudaram ou ela desapareceu após outra transação confirmar uma atualização ou exclusão. REPEATABLE READ e SERIALIZABLE impedem essa anomalia. |  |  |
| 22 | Quais são o tempo no pior caso e o espaço extra do heapsort no próprio vetor? | Construir o heap custa O(n); as extrações somam O(n log n). Com descida iterativa no vetor de entrada, heapsort leva O(n log n) no pior caso e usa O(1) espaço extra. |  |  |
| 23 | Como WHERE e HAVING diferem em uma consulta agrupada? | WHERE filtra linhas de entrada antes do agrupamento. HAVING filtra os grupos resultantes e pode usar condições com agregações, como COUNT(*)>1. |  |  |
| 24 | Por que a programação dinâmica é útil em muitos problemas de otimização? | A subestrutura ótima permite expressar um ótimo por meio de ótimos dos subproblemas. Quando eles se sobrepõem, guardar as respostas evita trabalho repetido. Os estados e a recorrência precisam representar corretamente o problema original. |  |  |
| 25 | Quando Dijkstra é válido e qual é um custo usual com heap? | Com pesos não negativos, ele fixa repetidamente o vértice com menor distância provisória. Uma implementação com listas de adjacência e heap binário mínimo leva O((V+E) log V). Arestas negativas podem invalidar o argumento de distância definitiva. |  |  |
| 26 | Como um algoritmo guloso difere da programação dinâmica? | O guloso assume uma escolha local e exige prova de que essas escolhas preservam um ótimo. A programação dinâmica compara alternativas por uma recorrência e reutiliza resultados. O ótimo global exige modelo e recorrência corretos, não apenas o nome “DP”. |  |  |
| 27 | Quando counting sort ou radix sort podem levar tempo linear? | Counting sort custa O(n+k) para n chaves em um intervalo de k valores. Radix sort com d passadas estáveis por dígitos e base b custa O(d(n+b)). Só são lineares quando esses parâmetros permitem; exploram a estrutura das chaves além das comparações. |  |  |
| 28 | Qual é uma ordem lógica simplificada de processamento de uma consulta SQL SELECT? | Sem CTEs, funções de janela nem operações de conjuntos: FROM/JOIN → WHERE → GROUP BY e agregações → HAVING → SELECT → DISTINCT → ORDER BY → LIMIT/OFFSET. É um modelo lógico, não necessariamente a ordem física escolhida pelo otimizador. |  |  |
| 29 | Como Kruskal e Prim constroem uma árvore geradora mínima? | Em um grafo conexo, não dirigido e ponderado, Kruskal considera arestas por peso crescente e usa Union–Find para rejeitar ciclos. Prim expande uma árvore escolhendo uma aresta de peso mínimo que conecta a árvore a um vértice externo. |  |  |
| 30 | Como diferem chaves primárias e estrangeiras no PostgreSQL? | A primária identifica linhas por valores únicos e não NULL. A estrangeira exige correspondência com valores da chave referenciada, segundo suas regras de NULL. Pode referenciar uma chave UNIQUE elegível ou uma primária da mesma tabela ou de outra. |  |  |
| 31 | Qual é a recorrência padrão da mochila 0/1 com capacidade inteira W? | D[i,w] é o melhor valor usando os primeiros i itens, capacidade w e pesos inteiros positivos wᵢ. D[0,w]=0. Se wᵢ>w, copia-se D[i−1,w]; senão, usa-se max(D[i−1,w],vᵢ+D[i−1,w−wᵢ]). O tempo O(NW) é pseudopolinomial. |  |  |
| 32 | Como diferem índices clustered e nonclustered de armazenamento por linhas no SQL Server? | O clustered armazena as linhas em ordem de chave, então há no máximo um por tabela. O nonclustered possui suas próprias chaves e localizadores de linhas e pode incluir outras colunas. Termos e detalhes de armazenamento variam entre sistemas. |  |  |

---
Study this deck interactively with FSRS-6 spaced repetition, audio review, and multiple-choice mode at [Flashcards World](https://flashcards.world/flashcards/sets/e55e30f2-b097-4c84-ab4d-596a3a7b359a/).