Lista de exercícios de Estruturas de dados com respostas

Onde fica o menor elemento de um min-heap binário?

1. ANa folha mais à esquerda
2. BNa última posição do array
3. CEm qualquer folha, que precisa ser procurada
4. DNa raiz

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

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

A altura de uma árvore é comumente definida como:

1. AO número de arestas no caminho mais longo da raiz até uma folha
2. BO número de folhas da árvore
3. CO número total de nós da árvore, contando a raiz e todas as folhas
4. DO número de filhos da raiz

Em uma tabela hash com endereçamento aberto, qual é o fator de carga máximo possível?

1. A0,5
2. B2
3. CNão há máximo
4. D1

Qual estrutura de dados é usada pela busca em profundidade (DFS) na versão iterativa?

1. AUm heap
2. BUma pilha
3. CUma fila
4. DApenas uma tabela hash

Como se encontra a menor chave em uma árvore binária de busca?

1. AOlhando apenas a raiz
2. BSeguindo os filhos esquerdos a partir da raiz até não haver filho esquerdo
3. CVisitando todas as folhas e comparando-as
4. DSeguindo os filhos direitos a partir da raiz até não haver filho direito

A complexidade de tempo de decrease-key em um heap binário (dada a posição do elemento) é:

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

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²)
2. BO(n)
3. CO(α(n)), a inversa da função de Ackermann, praticamente constante
4. DExatamente O(log n)