Lista de exercícios de Estruturas de dados com respostas

Em uma árvore binária de busca, os valores na subárvore esquerda de um nó são:

1. AIguais ao valor do nó
2. BEm ordem aleatória
3. CMenores que o valor do nó
4. DMaiores que o valor do nó

O que é um grafo direcionado?

1. AUm grafo cujas arestas têm um sentido de um vértice para outro
2. BUm grafo que não tem ciclos
3. CUm grafo cujas arestas têm todas pesos
4. DUm grafo em que todo par de vértices distintos está ligado por uma aresta

Em uma lista simplesmente encadeada, o que contém o ponteiro next do último nó?

1. AO número de nós da lista
2. BNull (nenhum nó)
3. CO endereço do primeiro nó
4. DO endereço do nó anterior

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. Ai + 1 e i + 2
2. B2i + 1 e 2i + 2
3. Ci/2 e i/2 + 1
4. D2i e 2i + 1

Árvores AVL e árvores rubro-negras garantem:

1. AAltura O(log n) por meio do rebalanceamento
2. BQue nenhum nó tenha dois filhos
3. CQue as chaves fiquem armazenadas na ordem de inserção
4. DBusca em tempo constante em todos os casos

Como funciona o extract-min em um min-heap binário?

1. ARemove-se a raiz e desloca-se todos os elementos uma posição à esquerda
2. BProcura-se o novo mínimo em todas as folhas
3. CMove-se o último elemento para a raiz e faz-se sift-down
4. DRemove-se o último elemento do array

Qual é a principal vantagem de uma skip list em relação a uma lista encadeada ordenada?

1. AEla armazena as chaves sem ordem
2. BBusca esperada em O(log n) usando vários níveis de ponteiros para a frente
3. CEla não usa memória extra
4. DBusca em O(1) garantido, porque cada nó guarda um ponteiro para todos os outros nós

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

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