Uma consulta busca um registro, em um arquivo, utilizando um...

Próximas questões
Com base no mesmo assunto
Q491589 Algoritmos e Estrutura de Dados
Uma consulta busca um registro, em um arquivo, utilizando um índice auxiliar, que é uma árvore binária balanceada, cujos nós têm ponteiros para os registros do arquivo principal. O arquivo A tem 12Kb de tamanho, enquanto o arquivo B tem 12Gb. A consulta é executada sobre os dois arquivos. Quantas comparações são feitas a mais, quando a consulta é executada sobre o segundo arquivo?
Alternativas

Gabarito comentado

Confira o gabarito comentado por um dos nossos professores

Gabarito: A

Fundamento decisivo: Como a consulta usa um índice binário balanceado, deve-se comparar os custos pelo logaritmo da razão entre as quantidades de registros. Na interpretação adotada para os arquivos, essa razão é 2^20, o que resulta em 20 comparações adicionais e sustenta a alternativa A.

Tema central: Busca em índice balanceado
Análise das alternativas
A
Certa
Interpretando o índice como uma árvore binária de busca balanceada, a busca percorre um caminho limitado pela altura, que permanece em O(log n). A banca adota a aproximação C(n) ≈ log2(n), com correspondência equivalente entre registros e entradas dos índices. Assumindo registros de mesmo tamanho médio e a interpretação binária das unidades, nB/nA = (12 × 2^30)/(12 × 2^10) = 2^20. Logo, ΔC ≈ log2(nB) − log2(nA) = log2(nB/nA) = 20. A alternativa A expressa esse incremento idealizado; o enunciado não permite garantir exatamente 20 comparações adicionais em toda consulta, pois a contagem concreta depende da estrutura e do caminho percorrido.
B
Errada
64 não corresponde à diferença entre os custos logarítmicos: para a razão de 2^20 entre as quantidades de registros, o incremento calculado é log2(2^20) = 20.
C
Errada
256 não resulta da comparação exigida. No modelo adotado, subtrair log2(nA) de log2(nB) equivale a calcular o logaritmo da razão nB/nA, cujo resultado é 20.
D
Errada
1024 não é o acréscimo de comparações. É necessário aplicar log2 à razão completa entre as quantidades de registros, 2^20, obtendo 20.
E
Errada
2048 não decorre da diferença entre os custos de busca. O cálculo pedido é log2(nB/nA) = log2(2^20) = 20, e não um aumento linear associado ao tamanho do arquivo.
Pegadinha da questão
Confundir o fator de crescimento do arquivo com o acréscimo de comparações, ou calcular o custo do segundo arquivo isoladamente quando se pede a diferença entre os custos.
Dica para questões semelhantes
  • Ao comparar buscas no modelo C(n) ≈ log2(n), calcule o incremento por log2(nB/nA), não apenas pelo custo do conjunto maior.
  • Só converta a razão entre tamanhos de arquivos em razão entre quantidades de registros explicitando a hipótese de mesmo tamanho médio e de correspondência equivalente com as entradas dos índices.
  • Verifique a convenção das unidades antes de calcular: a solução pretendida usa os fatores binários 2^10 e 2^30, embora as grafias Kb e Gb não sejam as notações normativas desses múltiplos.
  • Não transforme O(log n) em uma contagem exata: o balanceamento fundamenta o crescimento logarítmico, mas a quantidade concreta de comparações depende do caminho percorrido.

Clique para visualizar este gabarito

Visualize o gabarito desta questão clicando no botão abaixo

Comentários

Veja os comentários dos nossos alunos

HANNNN?????

Clique para visualizar este comentário

Visualize os comentários desta questão clicando no botão abaixo