Questões de Algoritmos e Estrutura de Dados - Algoritmos de Busca para Concurso
Foram encontradas 97 questões
Considere um método busca que recebe como parâmetros um elemento x do tipo inteiro e um vetor V de inteiros. O objetivo do método é verificar se o elemento x está contido no vetor V. Em caso positivo, a posição de x em V é retornada. Caso contrário, o valor -1 é retornado. Assim, por exemplo, se o método busca é executado com V = [1,7,5] e x = 2, o valor -1 é retornado. Se o método busca é chamado com V = [1,7,5] e x = 7, o valor 1 é retornado.
Usando a técnica de teste funcional, a seguinte partição do domínio de entrada foi definida:
Característica: localização do elemento na lista
Bloco 1: elemento é o primeiro da lista
Bloco 2: elemento é o último da lista
Bloco 3: elemento está em alguma posição na lista, exceto na primeira e na última
Tendo em vista que cada teste é composto por uma tupla (V, x), assinale a alternativa que apresenta, de forma correta, o conjunto de testes definidos com base na partição acima.
Considere os seguintes métodos de busca/indexação:
I. Busca binária
II. Tabelas hash
III. Índices B-trees
Considere ainda um universo de busca com aproximadamente um milhão de chaves, para o qual cada método tenha sido implementado adequadamente.
Num benchmark extensivo, cada método apresentou um número médio de acessos até que cada chave fosse localizada.
Esses tempos médios, em ordem crescente, correspondem aos métodos: