Lista de exercícios de Estruturas de dados com respostas

Em um grafo, o que é um ciclo?

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

A profundidade de um nó em uma árvore é:

1. AO número de filhos desse nó
2. BO número de nós da sua subárvore
3. CO número de arestas desse nó até a folha mais profunda
4. DO número de arestas da raiz até esse nó

Qual é o nome da operação de fila que remove o elemento do início?

1. ADequeue
2. BInsert
3. CPush
4. DEnqueue

Em um min-heap binário armazenado em um array (índices começando em 0), os filhos do nó no índice i estão em:

1. A2i + 1 e 2i + 2
2. B2i e 2i + 1
3. Ci + 1 e i + 2
4. Di/2 e i/2 + 1

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

1. A0,5
2. BNão há máximo
3. C1
4. D2

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

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

Quais são os custos de tempo e de espaço extra para inverter no próprio lugar uma lista simplesmente encadeada?

1. ATempo O(n log n) e espaço extra O(1)
2. BTempo O(1) e espaço extra O(1)
3. CTempo O(n) e espaço extra O(1)
4. DTempo O(n) e espaço extra O(n)

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(log n)
3. CO(n)
4. DO(m)