Questões de Algoritmos e Estrutura de Dados - Algoritmos de Busca para Concurso
Foram encontradas 118 questões
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