Lista de exercícios de Estruturas de dados com respostas

O que é a propriedade de max-heap?

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

Em que ordem um percurso em pré-ordem (preorder) de uma árvore binária visita os nós?

1. ANível por nível a partir do topo
2. BSubárvore esquerda, depois subárvore direita, depois nó
3. CNó, depois subárvore esquerda, depois subárvore direita
4. DSubárvore esquerda, depois nó, depois subárvore direita

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

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

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

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

Em um min-heap binário armazenado em um array (índices começando em 0), os filhos do nó no índice i estão em:

1. A2i e 2i + 1
2. Bi/2 e i/2 + 1
3. C2i + 1 e 2i + 2
4. Di + 1 e i + 2

Em um heap binário armazenado em um array a partir do índice 0, onde está o pai do nó no índice i?

1. ANo índice ⌊(i − 1) / 2⌋
2. BNo índice 2i + 1
3. CNo índice ⌊i / 2⌋ + 1
4. DNo índice i − 1

Uma árvore de Fenwick (binary indexed tree) sobre um array de n números permite quais operações em O(log n)?

1. AEncontrar a mediana em O(1)
2. BConsultas de soma de prefixo e atualizações de um único elemento
3. CInserir elementos em qualquer posição
4. DOrdenar o array e fazer busca binária

As chaves 5, 3, 8, 1 são inseridas nessa ordem em um min-heap binário vazio baseado em array. Qual é o array final?

1. A[3, 1, 8, 5]
2. B[1, 3, 8, 5]
3. C[1, 5, 8, 3]
4. D[1, 3, 5, 8]