Questões de Concurso
Comentadas sobre algoritmos de busca em algoritmos e estrutura de dados
Foram encontradas 98 questões
O método de busca mais rápido, em qualquer tipo de arquivo, denomina-se pesquisa binária.
A pesquisa sequencial de uma tabela, ou seja, pela comparação do argumento da pesquisa com a chave de cada entrada, terá o desempenho reduzido se a tabela for ordenada a partir do valor da chave.
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.
Um algoritmo de computador é composto por várias etapas que, em conjunto, executam uma determinada tarefa. Sobre os algoritmos de computadores, julgue o item a seguir.
Entre alguns exemplos, estão os algoritmos
destinados à busca e à ordenação de dados
e também os que percorrem grafos para o
cumprimento de tarefas.
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
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
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.