SóProvas

ID
696553
Banca
FCC
Órgão
TJ-RJ
Ano
2012
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

O algoritmo conhecido como busca binária é um algoritmo de desempenho ótimo para encontrar a posição de um item em

Alternativas
Comentários
  • a) uma árvore B. A árvore já esta balanceada, logo a busca é feita percorrendo-se a árvore (sem necessidade de algoritmo de busca binária) com complexidade O(d log2dN) onde d é a ordem da árvore B
    b) uma lista ligada ordenada. Para se achar o próximo item da lista encadeada é necessário saber o anterior, logo não é possível aplicar a busca binária
    c) uma árvore de busca binária. Os elementos já estão ordenados em uma árvore binária, logo basta percorrer a árvore.
    d) um heap binário. Os elementos já estão ordenados segundo uma heap, basta localiza-los na heap (e.g. HeapSort)
    e) um vetor ordenado. Correto

  • BUSCA BINÁRIA:

     

    � A ideia básica do algoritmo é percorrer o vetor como se folheia, por exemplo, uma lista telefônica. Abandonando-se as partes do catálogo onde o nome procurado, com certeza, não será encontrado.
    � Para a realização desse tipo de busca, o vetor deve estar ordenado.
    � Esse método exige acesso aleatório aos elementos do conjunto.
    � Algoritmo possui complexidade no pior caso O(logn).
    � O pior caso ocorre quando o elemento procurado é o último a ser verificado, ou mesmo não é encontrado.

     

    Fonte: Itnerante