Lista de exercícios de Estruturas de dados com respostas

Onde fica o menor elemento de um min-heap binário?

1. ANa folha mais à esquerda
2. BNa raiz
3. CEm qualquer folha, que precisa ser procurada
4. DNa última posição do array

Em uma tabela hash, o que é uma colisão?

1. ADuas chaves iguais são armazenadas duas vezes
2. BUma chave não pode ser processada pelo hash
3. CA tabela fica sem memória
4. DDuas chaves diferentes são mapeadas para o mesmo índice

Em que ordem um percurso em pré-ordem (preorder) de uma árvore binária visita os nós?

1. ANó, depois subárvore esquerda, depois subárvore direita
2. BSubárvore esquerda, depois nó, depois subárvore direita
3. CNível por nível a partir do topo
4. DSubárvore esquerda, depois subárvore direita, depois nó

Árvores AVL e árvores rubro-negras garantem:

1. ABusca em tempo constante em todos os casos
2. BQue as chaves fiquem armazenadas na ordem de inserção
3. CAltura O(log n) por meio do rebalanceamento
4. DQue nenhum nó tenha dois filhos

Quanta memória uma lista de adjacência usa para um grafo com V vértices e E arestas?

1. AO(V + E)
2. BO(E²)
3. CO(V × E)
4. DO(V²)

Em uma tabela hash com endereçamento aberto, qual é o fator de carga máximo possível?

1. A2
2. B0,5
3. C1
4. DNão há máximo

Uma árvore de segmentos (segment tree) é normalmente usada para:

1. AImplementar uma pilha
2. BArmazenar as arestas de um grafo
3. CResponder a consultas por intervalo (como somas de intervalos) e atualizações em O(log n)
4. DOrdenar strings alfabeticamente guardando cada prefixo em um nó separado da árvore

Um filtro de Bloom pode responder "este elemento está no conjunto?" com:

1. APossíveis falsos positivos, mas nenhum falso negativo
2. BRespostas sempre exatas
3. CPossíveis falsos negativos, mas nenhum falso positivo
4. DRespostas apenas para números