Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — FGV 2024
Algoritmos e Estrutura de Dados›Estrutura de Dados
Código
fg086230
Banca
FGV
Órgão
INPE
Ano
2024
Nível
Superior
Cargo
Tecnologista Pleno I - Desenvolvimento de Software para Processamento de Imagens e Dados Adquiridos por Satélites e Sensores Meteorológicos
Um sistema de banco de dados normalmente possui estruturas de dados auxiliares, chamadas de índices ou estruturas de indexação, que são utilizadas para agilizar a recuperação de registros em resposta a certas condições de pesquisa. Existem diversos métodos de indexação, tanto para dados convencionais, baseados em tipos numéricos e textuais, quanto para dados espaciais representados por pontos, linhas e polígonos.Nesse contexto, analise as afirmativas a seguir e assinale (V) para a verdadeira e (F) para a falsa.( ) Tanto as Árvores-B+ quanto as Árvores-R são árvores balanceadas.( ) Em uma Árvore-B+, uma busca por um valor de chave iniciada pelo nó raiz percorre apenas um único caminho até um nó folha (ou terminal).( ) Em uma Árvore-R, uma busca iniciada pelo nó raiz pode exigir a verificação de mais de uma sub-árvore desse nó raiz para selecionar os itens que satisfazem o critério de busca.( ) Uma quad-tree sempre é uma árvore balanceada.( ) Uma das desvantagens de um Árvore-k-d (k-d-tree) é que ela é uma estrutura sensível à ordem nos quais os pontos são inseridos.As afirmativas são, respectivamente,
AV – V – F – F – V.
BF – F – F – V – V.
CF – V – V – V – F.
DV – V – V – F – V.
EF – F – F – F – F.
Revelar gabarito e comentário▾
GabaritoD — V – V – V – F – V.
Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.
Estruturas de indexação (B+, R, Quad-tree, k-d tree)
Gabarito: letra D (V – V – V – F – V). A sequência correta baseia-se nas propriedades fundamentais dessas estruturas: tanto B+ quanto R são balanceadas; busca em B+ percorre um único caminho; busca em R pode exigir múltiplas subárvores; quad-tree não é sempre balanceada; e k-d tree é sensível à ordem de inserção. Esses são conceitos clássicos da área de estruturas de dados.
1ª afirmativa — ✅ Verdadeira
Tanto as Árvores-B+ quanto as Árvores-R são árvores balanceadas. As B+ mantêm-se balanceadas por split/merge, garantindo altura logarítmica. As R também são balanceadas (height-balanced), pois usam heurísticas de divisão para manter os nós com quantidade similar de entradas.
2ª afirmativa — ✅ Verdadeira
Em uma Árvore-B+, as chaves estão apenas nos nós folha. A busca da raiz até a folha segue um único caminho, pois em cada nível a comparação com as chaves internas decide exatamente qual subárvore seguir – não há retrocesso nem exploração de múltiplos ramos.
3ª afirmativa — ✅ Verdadeira
Nas Árvores-R, as regiões (bounding boxes) podem se sobrepor. Por isso, uma consulta pode intersectar mais de uma subárvore da raiz, exigindo verificação de todos os ramos cujas caixas envolventes atendam ao critério. Portanto, a busca pode necessitar explorar múltiplos caminhos.
4ª afirmativa — ❌ Falsa
Uma quad-tree não é necessariamente balanceada. Dependendo da distribuição dos pontos inseridos, a árvore pode tornar-se bastante desbalanceada – por exemplo, quando os pontos se concentram em uma região. Diferente de B+ e R, o balanceamento não é garantido pela definição da quad-tree.
5ª afirmativa — ✅ Verdadeira
A k-d tree (árvore k-d) é sensível à ordem de inserção dos pontos. Se os pontos forem inseridos em uma sequência que favoreça divisões desequilibradas, a árvore pode se tornar profundamente desbalanceada, prejudicando a eficiência das buscas. Essa é uma desvantagem conhecida.
NÃO CAIA NESSA!
A quarta afirmativa tenta generalizar que “toda árvore com nome ‘quad’ é balanceada”, mas não é. O candidato pode pensar que, por ser uma estrutura de indexação espacial, ela seria balanceada, mas a quad-tree não garante isso – seu balanceamento depende dos dados. Lembre-se: apenas estruturas como B+, R, AVL, rubro-negra garantem balanceamento.
Alternativa A — ❌ Incorreta
Sequência: V – V – F – F – V. O erro está na 3ª afirmativa que é Falsa quando na verdade é Verdadeira (Árvore-R pode exigir múltiplas subárvores). Além disso, a 4ª afirmativa deveria ser Falsa, está correta nessa alternativa. Como pelo menos um elemento está trocado, a alternativa está incorreta.
Alternativa B — ❌ Incorreta
Sequência: F – F – F – V – V. As três primeiras estão erradas: a 1ª (ambas são balanceadas), a 2ª (busca em B+ percorre um único caminho) e a 3ª (R pode exigir múltiplas subárvores) deveriam ser Verdadeiras. Além disso, a 4ª (quad-tree balanceada) é Falsa, mas aqui aparece como Verdadeira. Múltiplos erros.
Alternativa C — ❌ Incorreta
Sequência: F – V – V – V – F. A 1ª afirmativa deveria ser Verdadeira (B+ e R são balanceadas) e a 4ª deveria ser Falsa (quad-tree não é sempre balanceada). A 5ª é Verdadeira, mas aparece como Falsa. Portanto, três erros.
Alternativa D — ✅ Correta ⟵ GABARITO
Sequência: V – V – V – F – V. Corresponde exatamente ao julgamento correto de cada afirmativa, conforme justificado acima.
Alternativa E — ❌ Incorreta
Sequência: F – F – F – F – F. Todas as afirmativas são falsas, mas sabemos que apenas a 4ª é falsa; as demais são verdadeiras. Totalmente equivocada.