Lista de exercícios de Estruturas de dados com respostas

Em um grafo não direcionado, o que é o grau de um vértice?

1. ASua posição na lista de adjacência
2. BO número de vértices do grafo
3. CO comprimento do caminho mais longo a partir dele
4. DO número de arestas ligadas a ele

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

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

O que é um deque (fila de duas pontas)?

1. AUma estrutura que permite inserção e remoção nas duas pontas
2. BDuas filas separadas que compartilham um array
3. CUma fila que só permite remoção no final
4. DUma fila ordenada por prioridade

Uma aplicação precisa de buscas rápidas e também de listar as chaves em ordem e responder a consultas por intervalo. Qual estrutura é a mais adequada?

1. AUma árvore binária de busca balanceada
2. BUma tabela hash
3. CUma pilha
4. DUma lista encadeada não ordenada

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

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. BRemove-se o último elemento do array
3. CMove-se o último elemento para a raiz e faz-se sift-down
4. DProcura-se o novo mínimo em todas as folhas

Por que não se pode simplesmente remover elementos de um filtro de Bloom padrão zerando seus bits?

1. AEsses bits podem pertencer também a outros elementos, o que causaria falsos negativos
2. BRemover aumentaria a taxa de falsos positivos para 100%
3. COs bits de um filtro de Bloom não podem ser alterados depois da criação
4. DFiltros de Bloom armazenam os elementos completos, que não podem ser localizados de novo depois do hash

Para cada elemento de um array, você quer o próximo elemento maior à sua direita, em tempo total O(n). Qual estrutura ajuda?

1. AUma fila que guarda todos os pares de elementos
2. BUma árvore binária de busca reconstruída para cada elemento
3. CUma tabela hash com todos os elementos
4. DUma pilha que guarda os elementos que esperam pela resposta