Lista de exercícios de Estruturas de dados com respostas

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

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

Em um grafo, o que é um ciclo?

1. AUm vértice sem arestas
2. BUm caminho que começa e termina no mesmo vértice
3. CUma aresta com peso zero
4. DUm caminho que visita todos os vértices

Qual estrutura de dados é usada para fazer um percurso por níveis (level-order) de uma árvore?

1. AFila de prioridade
2. BPilha
3. CTabela hash
4. DFila

Um percurso em ordem (in-order) de uma árvore binária de busca visita as chaves em:

1. ASempre ordem decrescente
2. BOrdem por nível
3. COrdem crescente
4. DOrdem de inserção

Quanto tempo leva a busca de uma palavra de comprimento L em uma trie com alfabeto fixo?

1. AO(L), independentemente de quantas palavras estão armazenadas
2. BO(n), em que n é o número de palavras
3. CO(L × n)
4. DO(log n), em que n é o número de palavras

Como funciona o extract-min em um min-heap binário?

1. ARemove-se a raiz e desloca-se todos os elementos uma posição à esquerda
2. BMove-se o último elemento para a raiz e faz-se sift-down
3. CRemove-se o último elemento do array
4. DProcura-se o novo mínimo em todas as folhas

Sob hashing uniforme simples, qual é o tempo esperado de uma busca em uma tabela hash com encadeamento, n chaves e m buckets?

1. AO(1 + α), em que α = n / m
2. BO(n)
3. CO(log n)
4. DO(m)

Para uma tabela hash funcionar corretamente, que regra o hash e a igualdade devem seguir?

1. AChaves diferentes devem ter valores hash diferentes
2. BChaves iguais devem ter valores hash iguais
3. CValores hash iguais implicam chaves iguais
4. DOs valores hash devem ser números primos