Lista de exercícios de Estruturas de dados com respostas

Em uma lista simplesmente encadeada, cada nó contém:

1. ADados e uma referência para o próximo nó
2. BDados e um índice
3. CDados e referências para todos os outros nós
4. DApenas dados

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

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

Em que ordem um percurso em pré-ordem (preorder) de uma árvore binária visita os nós?

1. ANó, depois subárvore esquerda, depois subárvore direita
2. BNível por nível a partir do topo
3. CSubárvore esquerda, depois subárvore direita, depois nó
4. DSubárvore esquerda, depois nó, depois subárvore direita

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

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

Você tem uma referência para um nó no meio de uma lista. Em qual lista é possível removê-lo em O(1)?

1. AUm array dinâmico
2. BUma lista simplesmente encadeada
3. CUm array ordenado
4. DUma lista duplamente encadeada

Quanta memória uma matriz de adjacência usa para um grafo com V vértices?

1. AO(V + E)
2. BO(E)
3. CO(V²)
4. DO(log V)

Um nó AVL está desbalanceado porque a subárvore direita do seu filho esquerdo ficou alta demais (caso esquerda-direita). Qual correção é aplicada?

1. AUma rotação à direita no filho esquerdo e depois uma à esquerda no nó
2. BUma rotação simples à direita no nó
3. CUma rotação à esquerda no filho esquerdo e depois uma à direita no nó
4. DUma rotação simples à esquerda no 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 array ordenado com todos os n 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