Lista de exercícios de Estruturas de dados com respostas

Uma tabela hash armazena dados como:

1. APares chave–valor localizados por uma função hash
2. BUma string de tamanho fixo
3. CUma árvore com chaves ordenadas
4. DApenas uma lista ordenada

Em uma tabela hash, o que é uma colisão?

1. AA tabela fica sem memória
2. BUma chave não pode ser processada pelo hash
3. CDuas chaves iguais são armazenadas duas vezes
4. DDuas chaves diferentes são mapeadas para o mesmo índice

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

1. AFila (queue)
2. BPilha (stack)
3. CHeap
4. DÁrvore binária

Uma aplicação precisa de buscas rápidas e também de listar as chaves em ordem e responder a consultas por intervalo. Qual estrutura é a mais adequada?

1. AUma lista encadeada não ordenada
2. BUma árvore binária de busca balanceada
3. CUma tabela hash
4. DUma pilha

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

1. A2^h
2. Bh²
3. C2^h+1 − 1
4. D2h + 1

O que é verdade sobre a matriz de adjacência de um grafo não direcionado?

1. AÉ sempre triangular superior
2. BCada linha tem exatamente um 1
3. CÉ simétrica em relação à diagonal principal
4. DA diagonal principal sempre contém uns

Quanto tempo leva buscar uma chave arbitrária em um min-heap binário de n elementos?

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

A estrutura union-find (conjuntos disjuntos) com união por posto e compressão de caminho tem custo amortizado por operação de:

1. AO(α(n)), a inversa da função de Ackermann, praticamente constante
2. BO(n²)
3. CExatamente O(log n)
4. DO(n)