Questões de Concurso Público PROCEMPA 2014 para Analista em TI e Comunicação - Analista em Programação e Suporte de Sistemas Informatizados e Georeferenciados

Considere uma busca por uma chave entre 1.000.000, que pode ser feita através de uma Busca binária, Hashing ou Árvore B de ordem 20.

Supondo que os três operam em condições semelhantes e satisfatórias, com os registros armazenados num disco rígido, assinale a opção que mostra as alternativas na ordem do menor para o maior tempo de busca

Analise o pseudocódigo de uma função que realiza uma busca binária, onde k é a chave procurada, V é um array unidimensional contendo N chaves ordenadas em ordem crescente, indexadas a partir de 1, e “\” é um operador de divisão inteira (e.g. 5\2 retorna 2).
A função retorna a posição da chave k em V, ou -1 se não for encontrada.
O símbolo *** denota uma expressão lógica propositalmente omitida.

                                  define buscabinaria(k)
                                        p=1
                                        u=N
                                         repeat
                                                x=(p+u)\2
                                                if k < V[x]
                                                   then u = x-1
                                                   else p = x+1
                                         until ***
                                          if k = V[x]
                                             then return(x)
                                             else return(-1) 


Assinale a opção que apresenta o trecho que deve substituir o símbolo *** para que o algoritmo acima funcione de acordo com a especificação.