Lista de exercícios de Estruturas de dados com respostas

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

1. ALista encadeada
2. BFila (queue)
3. CTabela hash
4. DPilha (stack)

Em uma árvore, o que são nós irmãos?

1. AUm nó e o seu pai
2. BNós que não têm filhos
3. CNós que têm o mesmo pai
4. DNós na mesma profundidade em subárvores diferentes

O que cada nó de uma lista duplamente encadeada contém?

1. ADuas cópias dos dados e um ponteiro
2. BDados e apenas um ponteiro para o próximo nó
3. CDados e dois ponteiros, um para o próximo nó e outro para o nó seguinte a ele
4. DDados, um ponteiro para o próximo nó e um ponteiro para o nó anterior

Quantos nós tem uma árvore binária perfeita de altura h, com a altura contada em arestas?

1. A2h + 1
2. B2^h+1 − 1
3. Ch²
4. D2^h

O que acontece quando uma tabela hash faz rehash depois que o fator de carga passa de um limite?

1. AAs chaves mais antigas são apagadas para abrir espaço
2. BSó as chaves que colidiram são movidas para uma nova lista de overflow no fim da tabela
3. CAs chaves existentes são ordenadas no próprio lugar
4. DUma tabela maior é alocada e todas as chaves são inseridas de novo

Em uma fila circular armazenada em um array de capacidade n, como se calcula a posição seguinte ao índice i?

1. Ai + 1
2. B(i − 1) mod n
3. C(i + 1) mod n
4. D2i + 1

Qual é a principal vantagem de uma skip list em relação a uma lista encadeada ordenada?

1. ABusca esperada em O(log n) usando vários níveis de ponteiros para a frente
2. BEla não usa memória extra
3. CEla armazena as chaves sem ordem
4. DBusca em O(1) garantido, porque cada nó guarda um ponteiro para todos os outros nós

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. AUm array ordenado com todos os n valores
2. BUma fila FIFO com os últimos k valores
3. CUm max-heap de tamanho k, substituindo a raiz quando chega um valor menor
4. DUm min-heap com todos os n valores, do qual os k menores são removidos no final