Questão 868681

• Banca: CESPE / CEBRASPE
• Órgão: TRE-MS
• Ano: 2013
• Provas: CESPE - 2013 - TRE-MS - Técnico Judiciário - Programação de Sistemas
• Disciplina: Banco de Dados
• Assuntos: Métodos de acesso

Considerando que se deseje efetuar uma pesquisa de um valor sobre a chave primária de uma tabela de um banco de dados com uma chave primária com um tipo de campo que receba um valor inteiro e que se possa fazer essa pesquisa utilizando-se a busca sequencial ou a busca binária, assinale a opção correta.

• A. O método de busca binária requer, no máximo, ln(n) comparações para determinar o elemento pesquisado, em que n é o número de registros.
  
• B. O método de busca binária será sempre mais rápido que o método de busca sequencial, independentemente de a tabela estar ordenada com base no elemento pesquisado.
  
• C. O método de busca sequencial requererá, no máximo, n2 comparações para determinar o elemento pesquisado, em que n será o número de registros.
  
• D. O método de busca binária sempre efetuará menos comparações que o método de pesquisa sequencial.
  
• E. O método de busca sequencial efetuará menos comparações para encontrar o elemento pesquisado quando a tabela estiver ordenada em comparação à situação quando a tabela estiver desordenada.
  

Gabarito: A

Comentários

• Ir para: navegação, pesquisa

  Pesquisa binária
  classe	Algoritmo de busca
  estrutura de dados	Array, Listas ligadas
  complexidade caso médio
  complexidade melhor caso
  complexidade de espaços pior caso
  otimo	Sim
  espaço
  Algoritmos

• A Disciplina nao e BD e sim Estrutura de Dados.
• a) CORRETA. A complexidade da busca binária é de logn comparações
  b) ERRADA. Para se efetuar a busca binária, a tabela TEM que estar ordenada. A busca sequencial pode ser mais rápida do que a binária se o elemento buscado estiver na primeira posição.
  c) ERRADA. o método sequencial requer no máximo n comparações
  d) ERRADA.  Conforme dito no item b.
  e) ERRADA. Isso é independente. No mínimo será 1, caso encontre o elemento na primeira posição e no máximo n caso.
• A questão deveria ser anulada. O item a) está incorreto, pois:
  1) não é ln mas log_2. ln é logaritmo natural, na base e (de euler) e não na base 2 como deveria ser;
  2) o número máximo de comparações não é log₂n, mas ceil(log₂n) [o valor arredondado para cima do log], isso porque o valor de n pode não dar um número inteiro, nesse caso o número máximo de comparações é o primeiro inteiro maior que o log, ou seja, ceil().
  Um bom recurso anularia essa questão (ainda mais falando de CESPE).

• log 2 n = ln n / ln 2 = O(ln n)