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

Revisão de nível de licenciatura que exige bases de programação: 32 cartões sobre vetores, listas, hashing, árvores, heaps, tries, Union–Find, filtros de Bloom e complexidade.

Category
Computer Science
Level
basic
Languages
pt → pt
Cards
32
Markdown
Estruturas de Dados, Análise de Complexidade (Big-O) e Algoritmos Essenciais (.md)

Flashcards (32)

#Front (Term / Question)Back (Definition / Answer)ExampleMultiple-Choice Options
1O que é uma trie e quando pesquisar 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 pesquisa custa O(L) se cada transição para o próximo carácter custa O(1).
2Quanto custa construir um heap de baixo para cima com n elementos?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.
3Quais são as ordens dos percursos pré-ordem, em ordem e pós-ordem numa árvore binária?Pré-ordem: nó → esquerda → direita. Em ordem: esquerda → nó → direita. Pós-ordem: esquerda → direita → nó.
4Como corrigir um desequilíbrio esquerda-direita após uma inserção AVL?Primeiro, rode o filho esquerdo para a esquerda; depois, o nó desequilibrado para a direita.
5Como 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.
6Quanto custam inserir, remover a raiz e consultar a raiz num heap binário?O(log n), O(log n) e O(1), respetivamente, se não for necessário redimensionar o vetor. Um redimensionamento pode custar O(n).
7Quais 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.
8Que propriedades uma função hash deve ter para pesquisas numa 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).
9Quais 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, pesquisa/eliminaçã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).
10Que respostas um filtro de Bloom que só permite inserções pode dar?Um resultado negativo indica que o elemento não foi inserido; um positivo, que pode ter sido. Os hashes ativam bits num vetor: falsos positivos são possíveis, mas falsos negativos não, se o estado estiver intacto.
11Qual é 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).
12Como 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 a ser entradas separadas.
13Para 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₀.
14Que invariante de ordem define uma árvore binária de pesquisa (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.
15Que regras de cor mantêm uma BST rubro-negra equilibrada?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).
16Compare inserção no início e acesso por índice numa 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.
17O 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).
18Como 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, respetivamente. A sondagem quadrática exige parâmetros adequados.
19Com a capacidade a duplicar, 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.
20Ordene 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!.
21Como funciona uma pilha e quando é que as suas operações custam O(1)?LIFO: o último elemento 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).
22Qual é a diferença entre O, Ω e Θ?Indicam limites assintóticos superior, inferior e justo, respetivamente. Descrevem uma função de custo especificada; O não significa, por si só, pior caso.
23Como um percurso por níveis visita uma árvore binária?Usa uma fila FIFO para visitar um nível de profundidade de cada vez. Enfileirar o filho esquerdo antes do direito produz a ordem da esquerda para a direita.
24O que fazem find e union numa estrutura de conjuntos disjuntos?find(x) devolve 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.
25Como pesquisa, inserção e eliminação numa BST dependem da altura h?Custam O(h). Uma árvore equilibrada 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.
26Qual é a condição de equilíbrio AVL?Em cada nó, altura(esquerda) − altura(direita) ∈ {−1, 0, 1}. A árvore também satisfaz o invariante de ordem da BST.
27Por que uma lista duplamente encadeada pode eliminar um nó dado em O(1)?As suas ligações anterior e seguinte permitem reconectar diretamente os vizinhos. Atualizam-se início e fim quando necessário; não é preciso procurar o predecessor.
28Como 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.
29Onde estão o pai e os filhos do nó i num 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.
30Por que o acesso por índice num 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.
31Qual é 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.
32O 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.