Lista de exercícios de Estruturas de dados com respostas

Qual estrutura de dados funciona segundo o princípio "primeiro a entrar, primeiro a sair" (FIFO)?

1. APilha (stack)
2. BFila (queue)
3. CHeap
4. DÁrvore binária

A profundidade de um nó em uma árvore é:

1. AO número de nós da sua subárvore
2. BO número de filhos desse nó
3. CO número de arestas desse nó até a folha mais profunda
4. DO número de arestas da raiz até esse nó

Qual estrutura de dados funciona segundo o princípio "último a entrar, primeiro a sair" (LIFO)?

1. ATabela hash
2. BLista encadeada
3. CFila (queue)
4. DPilha (stack)

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

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

Quanto tempo leva a busca de uma palavra de comprimento L em uma trie com alfabeto fixo?

1. AO(L × n)
2. BO(L), independentemente de quantas palavras estão armazenadas
3. CO(log n), em que n é o número de palavras
4. DO(n), em que n é o número de palavras

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

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

A complexidade de tempo de decrease-key em um heap binário (dada a posição do elemento) é:

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

No algoritmo de Kruskal para árvore geradora mínima, para que serve a estrutura union-find?

1. AEscolher o vértice inicial
2. BVerificar se as duas extremidades de uma aresta já estão conectadas
3. COrdenar as arestas por peso
4. DArmazenar durante a busca a distância atual de cada vértice até a origem