Lista de exercícios de Estruturas de dados com respostas

Qual é a característica que define um conjunto (set) como tipo abstrato de dados?

1. AArmazena elementos em ordem crescente
2. BPermite acesso apenas por uma das pontas
3. CArmazena elementos sem duplicatas
4. DArmazena pares chave–valor

A profundidade de um nó em uma árvore é:

1. AO número de filhos desse nó
2. BO número de arestas da raiz até esse nó
3. CO número de arestas desse nó até a folha mais profunda
4. DO número de nós da sua subárvore

Qual estrutura de dados é mais adequada para a função "desfazer" (undo) de um editor de texto?

1. APilha (stack)
2. BGrafo
3. CFila (queue)
4. DConjunto hash (hash set)

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

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

Árvores AVL e árvores rubro-negras garantem:

1. AAltura O(log n) por meio do rebalanceamento
2. BBusca em tempo constante em todos os casos
3. CQue nenhum nó tenha dois filhos
4. DQue as chaves fiquem armazenadas na ordem de inserção

Qual é o custo de inserir um elemento no meio de um array de n elementos?

1. AO(n), porque os elementos seguintes precisam ser deslocados
2. BO(log n), por causa da busca binária
3. CO(1), porque o índice é conhecido
4. DO(n²), porque cada elemento se move n vezes

O que uma splay tree faz depois de cada acesso?

1. ARecolore os nós do caminho de busca
2. BReconstrói a árvore inteira na forma balanceada
3. CMove o nó acessado para uma folha
4. DLeva o nó acessado até a raiz por rotações

Qual propriedade uma árvore rubro-negra deve satisfazer?

1. AA raiz deve ser vermelha
2. BTodo nó deve ser vermelho
3. CTodo nó vermelho deve ter filhos vermelhos, então nós vermelhos sempre formam cadeias ininterruptas até as folhas
4. DTodo caminho de um nó até suas folhas descendentes tem o mesmo número de nós pretos