Questão 238303

• Banca: CESPE / CEBRASPE
• Órgão: ABIN
• Ano: 2010
• Provas: CESPE - 2010 - ABIN - Oficial Técnico de Inteligência - Área de Suporte a Rede de Dados
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Algoritmos de Busca

A respeito dos métodos de ordenação, pesquisa e hashing, julgue
os seguintes itens.

Árvore binária é uma estrutura de dados adequada à representação de hierarquia, sendo usada frequentemente em ordenação e pesquisa. Para a busca em um vetor ordenado, pode-se utilizar o algoritmo de busca binária, o qual não exige a implementação de uma árvore binária.

• C. Certo
• E. Errado

Gabarito: C

Comentários

• Para fazer a busca binário podemos usar um array.

  1 - Verificar se elemento buscado é maior que o elemento na metade do vetor.

  a - se não for, buscar na metade superior

  b - se for, buscar na metade inferior

  2 - Repetir passo 1 com a metade da lista escolhida.

  Este algoritomo permite busca binária sem implementação da árvore.

• "Árvore binária é uma estrutura de dados adequada à representação de hierarquia, sendo usada frequentemente em ordenação e pesquisa."
  - uma árvore é perfeitamente adequada para representar uma hierarquia
  - árvore binária de busca (ou pesquisa) é uma árvore ordenada cujos nós a esquerda de um nó pai são menores que ele, e cujos nós a direita de um nó pai são maiores que ele usada frequentemente em ordenação e pesquisa.
  
  "Para a busca em um vetor ordenado, pode-se utilizar o algoritmo de busca binária, o qual não exige a implementação de uma árvore binária."
  - Sim, a busca binária não exige nenhuma implementação de árvore binária.
  - A pesquisa ou busca binária (em inglês binary search algorithm ou binary chop) é um algoritmo de busca em vetores que requer acesso aleatório aos elementos do mesmo. Ela parte do pressuposto de que o vetor está ordenado e realiza sucessivas divisões do espaço de busca (divisão e conquista) comparando o elemento buscado (chave) com o elemento no meio do vetor. Se o elemento do meio do vetor for a chave, a busca termina com sucesso. Caso contrário, se o elemento do meio vier antes do elemento buscado, então a busca continua na metade posterior do vetor. E finalmente, se o elemento do meio vier depois da chave, a busca continua na metade anterior do vetor. http://pt.wikipedia.org/wiki/Pesquisa_bin%C3%A1ria
• "Árvore binária é uma estrutura de dados adequada à representação de hierarquia, sendo usada frequentemente em ordenação e pesquisa. Para a busca em um vetor ordenado, pode-se utilizar o algoritmo de busca binária, o qual não exige a implementação de uma árvore binária."
  
  Vamos por partes:
  
  1. "Árvore binária é uma estrutura de dados adequada à representação de hierarquia". Correto. Não apenas as árvores binárias, mas as árvores em sentido amplo representam seus elementos de forma hierárquica.
  
  2. "sendo usada frequentemente em ordenação e pesquisa." Correto. No que se refere à ordenação, árvores binárias podem ser usadas para auxiliar a implementação das técnicas (algoritmos) de árvore de decisão e HeapSort  (o heap pode ser representado por uma árvore binária ou por uma fila de prioridades). Já no que se refere à busca, as árvores podem ser usadas na implementação da busca binária.
  
  3. "Para a busca em um vetor ordenado, pode-se utilizar o algoritmo de busca binária, o qual não exige a implementação de uma árvore binária." Correto. Como eu falei no ponto anterior, pode-se usar uma árvore binária para se implementar a busca binária (situação em que aquela é chamada de árvore binária de busca). Porém a implementação da referida técnica de busca também pode ser feita através de um vetor (array), não exigindo, portanto, a árvore binária de busca.
  
  Bons estudos
• Prezados,
  
  O comando da questão tem 2 afirmativas, vamos olhar uma a uma.
  
  1) Árvore binária é uma estrutura de dados adequada à representação de hierarquia, sendo usada frequentemente em ordenação e pequisa. Isso está correto, a árvore binária pode representar a hierarquia com o relacionamento dos seus nós , um nó sendo pai , filho , etc.. , além disso a árvore binária é muito usada em ordenação e pequisa, como por exemplo é usada no algoritmo heapsort.
  
  2) Para a busca de um vetor ordenado, pode-se utilizar o algoritmo de busca binária, o qual não exige a implementação de uma árvore binária. Isso está correto também , a busca binária não tem nada a ver com arvore binária , ela consiste em dividir a lista sempre pela metade, e testar se o valor procurado é maior ou menor que o valor procurado , e ai fazer o mesmo processo na metade da lista.
  
  Portanto a questão está correta.
  

• RESOLUÇÃO:

  A Árvore binária é uma estrutura de dados adequada à representação de hierarquia, sendo usada frequentemente em ordenação e pesquisa. Para a busca em um vetor ordenado, pode-se utilizar o algoritmo de busca binária, o qual não exige a implementação de uma árvore binária.

  Resposta: Certo