Question

Considere o algoritmo de busca sequencial executado em uma lista de tamanho n >= 4. A partir da sua análise, aplique os conceitos estudados para avaliar as afirmações: Se a chave estiver na primeira posição da lista, o algoritmo realiza uma comparação com o valor da chave. Se a chave estiver na última posição da lista, o algoritmo realiza n comparações com o valor da chave. Se a chave estiver no meio da lista, ele realiza n/2 comparações com o valor da chave. Quando um algoritmo realiza n comparações no pior caso, dizemos que ele é da ordem de O(n)

Answer 1

Resposta: Todas são verdadeiras

Explicação passo a passo: Sequencial é quando se analisa item por item até achar um igual ao índice (o número que você procura), assim interrompendo a execução neste momento, sem necessariamente ir ao final, por isso ele vai operar apenas 1 comparação caso seja o primeiro item e todas as comparações possíveis caso seja o último ("n" comparações, sendo "n" o tamanho da lista) e assim também caso esteja no meio só será necessário metade. E a ordem de O(n) é verdadeira já que no pior caso ele faz "n" comparações.

Answer 2

Explicação passo a passo:

Na busca sequencial percorre-se a lista iniciando-se pelo seu primeiro elemento e continuando até o último elemento (acaso a chave não seja encontrada antes).

Caso a chave esteja na primeira posição, somente uma comparação será feita [ I - Correta]

Caso a chave esteja na última posição, ter-se-á que percorrer toda a lista, então serão feitas n  comparações [II - Correta]

Caso a chave esteja no meio da lista, a lista é percorrida até a metade. Por isso, serão feitas n/2 comparações [III - Correta]

Quando no pior caso o número de comparações é igual a n, tem-se um algorítimo O(n) ou linear. [IV - Correta]

Todas são verdeiras.