Pular para o conteúdo principal

Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — IV - UFG 2024

Algoritmos e Estrutura de DadosEstrutura de Dados
Código
qg269480
Banca
IV - UFG
Órgão
Prefeitura de Rio Branco - AC
Ano
2024
Nível
Superior
Cargo
Analista de Sistemas - Especialização em Desenvolvimento Back-End
Leia o caso a seguir.Considere uma função de busca recursiva em uma estrutura de dados do tipo árvore binária de busca. A eficiência dessa função é crucial para a performance de consultas em um banco de dados que utiliza essa estrutura para indexação.Elaborado pelo(a) autor(a).Dada a importância da escalabilidade e do consumo eficiente de recursos, e considerando uma árvore binária de busca balanceada, a opção que oferece a melhor implementação para a função de busca é aquela que
  1. Arealiza a busca em profundidade, verificando cada nó e seus descendentes, sem qualquer mecanismo de corte.
  2. Bverifica apenas os nós folha, pois estes contêm todas as chaves necessárias para a busca.
  3. Cdivide a árvore em sub árvores menores e realiza a busca sequencialmente em cada uma delas.
  4. Dcompara a chave de busca com a chave de cada nó visitado, descartando metade da árvore a cada passo.
Revelar gabarito e comentário

GabaritoD — compara a chave de busca com a chave de cada nó visitado, descartando metade da árvore a cada passo.

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”.

Busca em Árvore Binária de Busca Balanceada

Gabarito: alternativa D. Em uma árvore binária de busca (BST) balanceada, a busca eficiente é feita comparando a chave procurada com a chave do nó atual e, a cada passo, descartando metade da árvore (subárvore esquerda ou direita), resultando em complexidade O(log n).

A BST possui a propriedade fundamental: para cada nó, todos os valores da subárvore esquerda são menores, e todos da direita são maiores. Uma busca recursiva que explora essa propriedade atinge o desempenho logarítmico desejado — exatamente o que a alternativa D descreve.

  1. 1Compara chave com nó atual
  2. 2Igual? → encontrou
  3. 3Menor? → busca na esquerda
  4. 4Maior? → busca na direita
  5. 5Descarta metade a cada passo
  6. 6Complexidade O(log n)
LEVEL · soulevel.com.br

Alternativa A — ❌ Incorreta

Realizar busca em profundidade sem qualquer mecanismo de corte (pruning) significa percorrer todos os nós, mesmo os que não podem conter a chave. Isso resulta em complexidade O(n), ineficiente para grandes volumes.

Alternativa B — ❌ Incorreta

Afirmar que apenas os nós folha contêm as chaves necessárias é falso. Em uma BST, as chaves estão distribuídas em todos os nós (folhas e internos). Ignorar nós internos inviabiliza a busca correta.

Alternativa C — ❌ Incorreta

Dividir a árvore em subárvores menores e buscar sequencialmente em cada uma não aproveita a ordenação da BST. Equivale a uma busca linear nas subárvores, sem o descarte logarítmico, mantendo complexidade alta.

Alternativa D — ✅ Correta ⟵ GABARITO

A implementação clássica de busca em BST: compara a chave de busca com a chave do nó visitado. Se for igual, encontrou; se menor, busca na subárvore esquerda (descartando a direita); se maior, busca na direita (descartando a esquerda). A cada passo, metade dos nós restantes é eliminada, garantindo complexidade O(log n) em árvores balanceadas.

Gabarito: letra D.

Link permanente: /questoes/qg269480