Questão 325369

• Banca: FUNCAB
• Órgão: SEJUS-RO
• Ano: 2010
• Provas: FUNCAB - 2010 - SEJUS-RO - Analista de Sistemas
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Complexidade de Algoritmos

Considere um arquivo não ordenado, organizado sequencialmente e contendo N registros.O número médio de acessos que precisa ser feito para localizar um registro nesse arquivo, numacesso sequencial é:

• A. N!
• B. N/2
• C. (N-1)/2
• D.
• E. N+ (N-1)

Gabarito: B

Comentários

• Se a busca é sequencial, o melhor caso é encontrar na pesquisa 1. O pior caso é na pesquisa N. Logo a média é N / 2.
• Se fosse pela média, o resultado seria (N+1)/2, não?
  A resposta é N/2 por esse ser o caso médio da complexidade do algoritmo.
  Mas, na minha opinião, essa questão está incompleta, pois para o caso médio deve-se pressupor conhecida uma certa distribuição de entrada. A única que fala é que o arquivo não está ordenado, mas não afirma que, por exemplo, a distribuição dos registros é uniforme ou que todos os valores das buscas foram encontrados no arquivo. Essas duas condições impactariam consideravelmente o caso médio do algorimo, e consequentemente o numero médio de acessos do mesmo.
• A questão é simples. Pesquisa sequencial, como o próprio nome diz, significa buscar em sequência, do primeiro ao último elemento. Como são N registros, em média será necessário acessar a metade, ou seja, N/2.