Questões de Concurso Comentadas sobre algoritmos de busca em algoritmos e estrutura de dados

Suponha uma estrutura de dados do tipo vetor, a qual possui algumas centenas de elementos ordenados. Buscas por valores dos elementos desse vetor são constantes e, portanto, é necessário utilizar um método de busca eficiente. Das seguintes opções, qual seria o método de busca ou o algoritmo mais adequado?

Considere uma lista ordenada, contendo 20 chaves únicas, na qual seja realizada uma busca binária. Assinale o número máximo de acessos necessários para encontrar uma determinada chave.

Em sistemas de Recuperação de Informação, os termos de indexação podem ser extraídos diretamente do texto dos documentos, fornecendo uma visão lógica dos documentos. Assinale a alternativa que apresenta corretamente uma das operações realizadas para obter as palavras-chaves. 

Formalmente, um algoritmo de busca é aquele que aceita um argumento e tenta encontrar o registro cuja chave seja igual ao argumento. Assim, analisando o seguinte passo a passo de um algoritmo de busca, é correto afirmar que se trata de um algoritmo

1. Defina que min= 1 e max = n.

2. Encontre a média de max e min, arredondando para baixo para que seja um inteiro.

3. Se você tiver adivinhado o número certo. Pare – Fim algoritmo!

4. Se o palpite foi muito baixo, defina o min como 1 a mais do que o palpite.

5. Se o palpite foi muito alto, defina o max como 1 a menos do que o palpite.

6. Volte ao passo dois.

Qual o algoritmo de busca que se baseia no princípio de dividir os dados na posição central, testando o elemento a ser encontrado com o elemento que está nessa posição (central)? Considere que, caso o elemento sendo buscado não seja o elemento central, então metade do conjunto de dados já pode ser descartado.

A técnica de hashing que, no pior caso, realiza O(1) acessos à memória para executar uma busca é denominada hashing

Um método de busca bastante utilizado, conhecido como hash, baseia-se na utilização que mapeia chaves em endereços de memória, de modo que os dados associados a cada chave possam ser rapidamente localizados e lidos. Quando há conflitos de localização, algum algoritmo de separação é adotado.

Considere uma tabela hash armazenada em um arquivo no disco rígido. Supondo-se que a mesma possua uma função de hash razoavelmente protegida de conflitos, o número médio de acessos ao disco, necessários para localizar uma chave em um universo de N chaves, é mais próximo de

Analise as sentenças relacionadas abaixo, retiradas da obra Projeto de algoritmos com implementações em Pascal e C, de Ziviani (1999), acerca de métodos de pesquisa em memória primária. I - Método de pesquisa para registros ordenados que consiste em comparar a chave com o registro que está no meio da tabela, se a chave é menor, então o registro procurado está na primeira metade da tabela; se a chave é maior, então o registro procurado está na segunda metade da tabela. O processo é repetido até que a chave seja encontrada ou retorne pesquisa sem sucesso. II - Neste método de pesquisa, podemos implementá-lo de duas maneiras: não-balanceada e balanceada. Ambas possuem nodos, todo nodo interno contém um registro e, para cada nodo, a seguinte propriedade é verdadeira: todos os registro com chaves menores estão à esquerda, e todos os registros com chaves maiores estão à direita. III - O método de pesquisa mais simples que existe e funciona da seguinte forma: a partir do primeiro registro, pesquise sequencialmente até encontrar a chave procurada ou o fim do registro e, então, pare.
Tais sentenças se referem, respectivamente, aos métodos de pesquisa:

Um método que implementa um algoritmo de busca binária recebe como parâmetros um vetor de inteiros ordenados descendentemente, o comprimento desse vetor e um número inteiro que se deseja localizar no vetor. O cabeçalho desse método é o seguinte:

                                                             public int buscaBin(int vet[], int n, int val)

Admitindo-se que o vetor passado como parâmetro tenha 750 elementos, qual será o número máximo de iterações que o algoritmo irá realizar até que o valor (val) seja localizado ou que seja detectado que esse valor não se encontra no vetor?

Sobre algoritmos de busca, analise as informações a seguir.

I. Uma busca linear sobre um array de uma dimensão pode ser implementada com um laço e possui complexidade, no pior caso, linearmente relacionada ao tamanho do array.

II. Uma busca binária sobre um array de uma dimensão pode ser implementada com um laço e possui complexidade, no pior caso, linearmente relacionada ao logaritmo do tamanho do array.

III. Uma busca binária recursiva sobre um array de uma dimensão pode ser implementada sem laços e possui complexidade, no pior caso, linearmente relacionada ao logaritmo do tamanho do array.

IV. Uma busca linear sobre um array de duas dimensões pode ser implementada com dois laços e possui complexidade, no pior caso, linearmente proporcional à soma da quantidade de linhas e colunas do array.

V. Uma busca em uma estrutura de dados chamada Tabela de Dispersão (Hash Table) pode ser implementada sem laços e possui complexidade, no pior caso, constante, independentemente do tamanho do array.

Estão CORRETAS, apenas, as proposições

Basicamente, existem dois métodos de pesquisa em um vetor de números, a Busca Linear e a Busca Binária. A Busca Binária é mais eficiente do que a Busca Linear, mas ela só funciona se o vetor estiver ordenado. Assinale a alternativa que indique a ordem de complexidade do pior caso da Busca Binária em um vetor de n números ordenados.

Qual é o método de pesquisa, no qual os registros armazenados em uma tabela são diretamente endereçados a partir de uma função aritmética sobre a chave de pesquisa?

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.

Pesquisa Binária e Hash Code são duas técnicas de busca de dados em um arquivo ou tabela muito usados em informática, com grande vantagem sobre a Pesquisa Sequencial. Sobre essas técnicas, assinale a afirmação INCORRETA.

Considere um vetor de números inteiros, em que se deseja buscar um dos elementos que está presente neste vetor. O algoritmo de busca binária requer que

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: