Lista de exercícios de Estruturas de dados com respostas

Um grafo é formado por:

1. AVértices (nós) conectados por arestas
2. BLinhas e colunas
3. CApenas uma raiz e folhas
4. DApenas chaves e hashes

O que define uma árvore binária?

1. AA árvore tem exatamente dois níveis
2. BTodo nó armazena um número binário
3. CTodo nó tem exatamente dois filhos
4. DTodo nó tem no máximo dois filhos

O que é a propriedade de max-heap?

1. AA chave de todo filho esquerdo é maior ou igual à chave de seu irmão direito
2. BTodas as folhas contêm a chave máxima
3. CAs chaves estão ordenadas da esquerda para a direita
4. DA chave de todo pai é maior ou igual às chaves dos seus filhos

Por que percorrer um array costuma ser muito mais rápido na prática do que percorrer uma lista encadeada do mesmo tamanho?

1. APercorrer um array é O(1) no total, enquanto percorrer uma lista encadeada é O(n)
2. BOs elementos do array são contíguos, então aproveitam bem o cache da CPU
3. CListas encadeadas sempre armazenam os elementos em disco
4. DArrays usam menos instruções para comparar valores

Uma tabela hash de tamanho 7 usa h(k) = k mod 7 e sondagem linear. Depois de inserir 10, onde 17 é armazenado?

1. ANo índice 6
2. BNo índice 0
3. CNo índice 4
4. DNo índice 3

Em uma fila circular armazenada em um array de capacidade n, como se calcula a posição seguinte ao índice i?

1. A(i − 1) mod n
2. B(i + 1) mod n
3. C2i + 1
4. Di + 1

Você precisa guardar os k menores valores de um fluxo de n números usando O(k) de memória. Qual abordagem funciona em tempo O(n log k)?

1. AUm min-heap com todos os n valores, do qual os k menores são removidos no final
2. BUm max-heap de tamanho k, substituindo a raiz quando chega um valor menor
3. CUm array ordenado com todos os n valores
4. DUma fila FIFO com os últimos k valores

Inserir uma chave em uma árvore AVL deixa a subárvore esquerda de um nó alta demais, e a nova chave foi para a subárvore esquerda do seu filho esquerdo (caso esquerda-esquerda). Qual correção é aplicada?

1. AUma rotação à esquerda no filho e depois uma à direita no nó
2. BRecolorir o nó e o seu filho
3. CUma rotação simples à esquerda no nó desbalanceado
4. DUma rotação simples à direita no nó desbalanceado