SóProvas


ID
906781
Banca
FCC
Órgão
TRT - 9ª REGIÃO (PR)
Ano
2013
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

Considere as afirmativas sobre

i) Métodos de pesquisa sequencial e de pesquisa binária

ii) Métodos de ordenação

Sabendo que N se refere ao número de elementos do conjunto, a alternativa em que i) e ii) estão ambas ERRADAS, é

Alternativas
Comentários
  • b) i) O método de pesquisa binária não pode ser aplicado quando os dados estão ordenados em ordem decrescente, mesmo se o código do método for readequado.  Está errada pois a pesquisa binária pode sim ser realizada em um array cuja ordem é decrescente, para isso basta alterar o algoritmo, adaptando-o a esse tipo de ordenação.

    ii) O método de Seleção (Selection sort) é o método mais rápido para qualquer tamanho de N se os elementos já estão ordenados, pois este é o seu melhor caso, que é O(Log2 N). Está errada pois esses fatos tratam-se na verdade sobre o insertion sort, esse algoritmo possui uma grande flexibilidade com relação ao grau de ordenação prévia do vetor, se adaptando bem aos casos onde o vetor está razoavelmente pré-ordenado, sendo em seu melhor caso O(Log² N).

  • Que complexidade é essa? O(Log² N)? Nos materiais do provas de TI as complexidades para o melhor caso para o Selection e o Insertion são respectivamente O(n²) e O(n). 

  • b-

    A pesquisa ou busca binária é um algoritmo de busca em vetores que segue o paradigma de divisão e conquista. Ela parte do pressuposto de que o vetor está ordenado e realiza sucessivas divisões do espaço de busca 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.

    https://pt.wikipedia.org/wiki/Pesquisa_bin%C3%A1ria

  • Força Guerreiro!!!!!!