Lista de exercícios de Estruturas de dados com respostas

Como os elementos de um array são armazenados na memória?

1. AEm uma árvore de páginas de memória
2. BEm posições aleatórias escolhidas por um hash
3. CEm um único bloco contíguo, um após o outro
4. DEspalhados, ligados por ponteiros

O que é um grafo ponderado?

1. AUm grafo armazenado em disco
2. BUm grafo com mais arestas do que vértices
3. CUm grafo em que cada aresta tem um valor numérico, como um custo ou uma distância
4. DUm grafo em que alguns vértices são mais pesados que outros por terem mais arestas

O que cada nó de uma lista duplamente encadeada contém?

1. ADados, um ponteiro para o próximo nó e um ponteiro para o nó anterior
2. BDuas cópias dos dados e um ponteiro
3. CDados e dois ponteiros, um para o próximo nó e outro para o nó seguinte a ele
4. DDados e apenas um ponteiro para o próximo nó

Qual é a complexidade de tempo da busca de uma chave em uma árvore binária de busca balanceada?

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

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

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

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

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

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

A estrutura union-find (conjuntos disjuntos) com união por posto e compressão de caminho tem custo amortizado por operação de:

1. AExatamente O(log n)
2. BO(n²)
3. CO(α(n)), a inversa da função de Ackermann, praticamente constante
4. DO(n)