Lista de exercícios de Estruturas de dados com respostas

Qual estrutura de dados funciona segundo o princípio "primeiro a entrar, primeiro a sair" (FIFO)?

1. APilha (stack)
2. BHeap
3. CFila (queue)
4. DÁrvore binária

Em um grafo, o que é um ciclo?

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

O que é a propriedade de max-heap?

1. AA chave de todo pai é maior ou igual às chaves dos seus filhos
2. BTodas as folhas contêm a chave máxima
3. CAs chaves estão ordenadas da esquerda para a direita
4. DA chave de todo filho esquerdo é maior ou igual à chave de seu irmão direito

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

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

Qual é a complexidade de tempo da busca de uma chave em uma árvore binária de busca balanceada?

1. AO(1)
2. BO(n log n)
3. CO(log n)
4. DO(n)

Uma árvore binária tem raiz 1 com filho esquerdo 2 e filho direito 3; o nó 2 tem filhos 4 (esquerdo) e 5 (direito). Qual é o percurso em pré-ordem?

1. A1 2 4 5 3
2. B4 2 5 1 3
3. C1 2 3 4 5
4. D4 5 2 3 1

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

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

Você precisa guardar os k menores valores de um fluxo de n números usando O(k) de memória. Qual abordagem funciona em tempo O(n log k)?

1. AUma fila FIFO com os últimos k valores
2. BUm max-heap de tamanho k, substituindo a raiz quando chega um valor menor
3. CUm min-heap com todos os n valores, do qual os k menores são removidos no final
4. DUm array ordenado com todos os n valores