Lista de exercícios de Estruturas de dados com respostas

Qual é a principal diferença entre um array estático e um array dinâmico?

1. AUm array estático tem acesso por índice mais lento
2. BUm array dinâmico armazena seus elementos em nós encadeados para poder crescer um de cada vez
3. CUm array estático só pode armazenar números
4. DUm array dinâmico pode crescer passando para um bloco de memória maior

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

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

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. BUma linha de V valores booleanos
3. CO caminho mínimo até todos os outros vértices
4. DUma lista dos seus vértices vizinhos

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

1. ANão há máximo
2. B2
3. C0,5
4. D1

Um buffer circular (ring buffer) é comumente usado para implementar:

1. AUma fila de tamanho fixo
2. BUma função hash
3. CUm percurso em grafo
4. DUma árvore binária de busca

Como um novo elemento é inserido em um heap binário?

1. AReconstrói-se o heap inteiro do zero
2. BInsere-se na posição ordenada, deslocando uma posição à direita todos os elementos maiores
3. CColoca-se na raiz e faz-se sift-down
4. DColoca-se no fim do array e faz-se sift-up enquanto violar a propriedade de heap

Uma árvore de Fenwick (binary indexed tree) sobre um array de n números permite quais operações em O(log n)?

1. AConsultas de soma de prefixo e atualizações de um único elemento
2. BOrdenar o array e fazer busca binária
3. CEncontrar a mediana em O(1)
4. DInserir elementos em qualquer posição

Em uma tabela hash com endereçamento aberto, por que a remoção costuma ser feita com um marcador de "lápide" (tombstone)?

1. ALápides aceleram o hashing
2. BChaves removidas precisam ser mantidas para sempre por segurança, então as posições nunca podem ser reutilizadas
3. CIsso deixa a tabela ordenada
4. DEsvaziar a posição poderia quebrar a sequência de sondagem de outras chaves