Lista de exercícios de Estruturas de dados com respostas

Na representação de um grafo por lista de adjacência, o que é armazenado para cada vértice?

1. AO número total de arestas do grafo
2. BO caminho mínimo até todos os outros vértices
3. CUma linha de V valores booleanos
4. DUma lista dos seus vértices vizinhos

O que faz a operação peek (ou top) em uma pilha?

1. ARemove todos os elementos da pilha
2. BRemove o elemento do topo e o retorna
3. CRetorna o elemento da base da pilha
4. DRetorna o elemento do topo sem removê-lo

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

1. APush
2. BDequeue
3. CInsert
4. DEnqueue

Qual estrutura de dados é usada pela busca em profundidade (DFS) na versão iterativa?

1. AApenas uma tabela hash
2. BUma fila
3. CUma pilha
4. DUm heap

Em um heap binário armazenado em um array a partir do índice 0, onde está o pai do nó no índice i?

1. ANo índice 2i + 1
2. BNo índice i − 1
3. CNo índice ⌊(i − 1) / 2⌋
4. DNo índice ⌊i / 2⌋ + 1

Á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. CQue nenhum nó tenha dois filhos
4. DAltura O(log n) por meio do rebalanceamento

Como detectar se uma lista simplesmente encadeada contém um ciclo usando O(1) de memória extra?

1. AMover um ponteiro um passo e outro dois passos e verificar se eles se encontram
2. BGuardar cada nó visitado em um conjunto hash
3. COrdenar a lista e procurar duplicatas
4. DContar os nós até a contagem passar do campo de tamanho da lista

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

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