Lista de exercícios de Estruturas de dados com respostas

Em uma lista simplesmente encadeada, cada nó contém:

1. ADados e uma referência para o próximo nó
2. BDados e referências para todos os outros nós
3. CApenas dados
4. DDados e um índice

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 número de arestas ligadas a ele
4. DO comprimento do caminho mais longo a partir dele

O que faz uma função hash em uma tabela hash?

1. AMapeia uma chave para um índice da tabela
2. BConta quantas chaves estão armazenadas
3. CCriptografa os valores da tabela
4. DOrdena as chaves da tabela

Uma rede rodoviária tem 100,000 cruzamentos, cada um ligado a cerca de 4 outros. Qual representação é mais adequada?

1. AUm heap binário de arestas
2. BUm único array ordenado de vértices
3. CMatriz de adjacência
4. DLista de adjacência

Uma árvore binária tem raiz 1 com filho esquerdo 2 e filho direito 3; o nó 2 tem filhos 4 (esquerdo) e 5 (direito). Qual é o percurso em pós-ordem?

1. A4 2 5 1 3
2. B5 4 3 2 1
3. C4 5 2 3 1
4. D1 2 4 5 3

Quantos nós tem uma árvore binária perfeita de altura h, com a altura contada em arestas?

1. A2^h
2. Bh²
3. C2h + 1
4. D2^h+1 − 1

As chaves 5, 3, 8, 1 são inseridas nessa ordem em um min-heap binário vazio baseado em array. Qual é o array final?

1. A[1, 3, 5, 8]
2. B[1, 5, 8, 3]
3. C[1, 3, 8, 5]
4. D[3, 1, 8, 5]

Uma árvore de Fenwick (binary indexed tree) sobre um array de n números permite quais operações em O(log n)?

1. AConsultas de soma de prefixo e atualizações de um único elemento
2. BOrdenar o array e fazer busca binária
3. CInserir elementos em qualquer posição
4. DEncontrar a mediana em O(1)