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.

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ó.

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.

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).

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!.

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.

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.

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.

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).

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).

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.

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.

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.

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.

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.

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).

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.

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).

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).

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).

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.

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.

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.

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.

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.

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.

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).

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.

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.

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.

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₀.

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.

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.

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

Flashcards (32)

#	Front (Term / Question)	Back (Definition / Answer)
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.