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 pares chave–valor
2. BArmazena elementos em ordem crescente
3. CPermite acesso apenas por uma das pontas
4. DArmazena elementos sem duplicatas

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

1. APilha (stack)
2. BFila (queue)
3. CTabela hash
4. DLista encadeada

Em um grafo não direcionado, o que é o grau de um vértice?

1. ASua posição na lista de adjacência
2. BO comprimento do caminho mais longo a partir dele
3. CO número de arestas ligadas a ele
4. DO número de vértices do grafo

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

1. A(i − 1) mod n
2. B(i + 1) mod n
3. Ci + 1
4. D2i + 1

Uma trie (árvore de prefixos) é especialmente eficiente para:

1. ABuscas por prefixo, como o preenchimento automático
2. BOrdenar números
3. CArmazenar matrizes
4. DEncontrar caminhos mínimos

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

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

Qual propriedade uma árvore rubro-negra deve satisfazer?

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

Sem união por posto nem compressão de caminho, qual é o custo no pior caso de um único find em uma estrutura union-find com n elementos?

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