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 um único bloco contíguo, um após o outro
3. CEspalhados, ligados por ponteiros
4. DEm posições aleatórias escolhidas por um hash

O que é um grafo ponderado?

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

Qual operação é lenta em um array, mas rápida no início de uma lista encadeada?

1. AObter o tamanho de um array de tamanho fixo
2. BInserir no início
3. CAcessar o 5º elemento
4. DLer o último elemento pelo índice

Em uma tabela hash com endereçamento aberto, qual é o fator de carga máximo possível?

1. A0,5
2. BNão há máximo
3. C2
4. D1

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(1)
2. BO(n)
3. CO(log n)
4. DO(n²)

Árvores AVL e árvores rubro-negras garantem:

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

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

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

Quais são os custos de tempo e de espaço extra para inverter no próprio lugar uma lista simplesmente encadeada?

1. ATempo O(1) e espaço extra O(1)
2. BTempo O(n) e espaço extra O(n)
3. CTempo O(n) e espaço extra O(1)
4. DTempo O(n log n) e espaço extra O(1)