Lista de exercícios de Estruturas de dados com respostas

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

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

Em uma árvore, o que são nós irmãos?

1. ANós na mesma profundidade em subárvores diferentes
2. BNós que não têm filhos
3. CUm nó e o seu pai
4. DNós que têm o mesmo pai

Qual estrutura é normalmente usada para implementar uma fila de prioridade?

1. AUma lista simplesmente encadeada sem ordem
2. BUma string
3. CUma pilha
4. DUm heap

Quanta memória uma matriz de adjacência usa para um grafo com V vértices?

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

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

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

Quanta memória uma lista de adjacência usa para um grafo com V vértices e E arestas?

1. AO(V + E)
2. BO(V²)
3. CO(V × E)
4. DO(E²)

Em um buffer circular, front == rear pode significar vazio ou cheio. Qual é uma forma comum de distinguir os dois casos?

1. AFazer o tamanho do buffer ser uma potência de dois
2. BManter uma contagem separada de elementos, ou sempre deixar uma posição sem uso
3. CGuardar front e rear na mesma variável
4. DSempre limpar o buffer quando front for igual a rear, de modo que o estado seja vazio

A remoção de um nó com dois filhos de uma árvore binária de busca normalmente é feita:

1. AReconstruindo do zero a subárvore abaixo dele e reinserindo todas as chaves que ela continha
2. BSubstituindo-o pelo seu sucessor em ordem (ou predecessor) e removendo esse nó
3. CTrocando-o com a raiz
4. DRemovendo a subárvore inteira