Lista de exercícios de Estruturas de dados com respostas

Qual estrutura de dados é usada para fazer um percurso por níveis (level-order) de uma árvore?

1. AFila
2. BPilha
3. CTabela hash
4. DFila de prioridade

O que é a propriedade de max-heap?

1. AA chave de todo pai é maior ou igual às chaves dos seus filhos
2. BA chave de todo filho esquerdo é maior ou igual à chave de seu irmão direito
3. CAs chaves estão ordenadas da esquerda para a direita
4. DTodas as folhas contêm a chave máxima

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

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

Quanto tempo leva verificar se a aresta (u, v) existe usando uma matriz de adjacência?

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

Qual é a altura no pior caso de uma árvore binária de busca com n nós se as chaves forem inseridas em ordem crescente?

1. A1
2. B√n
3. Clog₂ n
4. Dn (ela vira uma lista encadeada)

Uma fila é implementada com duas pilhas: push numa pilha "in" e pop numa pilha "out", reabastecida a partir de "in" quando está vazia. Qual é o custo amortizado por operação?

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

Como uma radix tree (trie compactada) melhora uma trie simples?

1. AFunde cadeias de nós com um só filho em uma aresta rotulada com uma string
2. BOrdena os filhos de cada nó por frequência
3. CArmazena cada palavra em uma tabela hash na raiz em vez de em nós separados
4. DGuarda só a primeira letra de cada palavra

Um filtro de Bloom pode responder "este elemento está no conjunto?" com:

1. ARespostas sempre exatas
2. BRespostas apenas para números
3. CPossíveis falsos negativos, mas nenhum falso positivo
4. DPossíveis falsos positivos, mas nenhum falso negativo