Lista de exercícios de Estruturas de dados com respostas

O que é a raiz de uma árvore?

1. AQualquer nó no meio
2. BO nó com o maior valor
3. CO nó do topo, sem pai
4. DUm nó sem filhos

Qual operação é lenta em um array, mas rápida no início de uma lista encadeada?

1. ALer o último elemento pelo índice
2. BInserir no início
3. CObter o tamanho de um array de tamanho fixo
4. DAcessar o 5º elemento

O que define uma árvore binária?

1. ATodo nó tem exatamente dois filhos
2. BTodo nó armazena um número binário
3. CA árvore tem exatamente dois níveis
4. DTodo nó tem no máximo dois filhos

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

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

Qual é a complexidade de tempo da busca de uma chave em uma árvore binária de busca balanceada?

1. AO(n)
2. BO(1)
3. CO(log n)
4. DO(n log n)

Que condição de balanceamento uma árvore AVL mantém em todo nó?

1. AAs duas subárvores de todo nó têm exatamente o mesmo número de nós
2. BAs alturas das subárvores esquerda e direita diferem no máximo em 1
3. CTodas as folhas estão exatamente na mesma profundidade
4. DTodo nó é colorido de vermelho ou preto

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(n)
4. DTempo O(n) e espaço extra O(1)

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

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