Questão Q445743

Question

Na linguagem C, uma lista sequencial com n elementos pode ser armazenada em um vetor, ocupando as posições cujos índices variam de 0 a n-1. Considere o seguinte algoritmo de pesquisa, denominado busca com sentinela:

int pesquisa (int vet[], int n, int chave)
{

int ind;

vet[n] = chave; /* sentinela */

ind = 0;
while (vet[ind] != chave)
ind = ind + 1;

if (ind == n)
return –1; /* Não encontrou * /
else
return ind; /* Encontrou */
}

Sobre essa implementação do algoritmo de busca com sentinela, analise as afirmativas a seguir:

I. Para que ela funcione corretamente, é necessário que o vetor vet contenha, pelo menos, n+1 posições, sendo as n primeiras (de 0 a n-1) ocupadas pelos elementos e a última, vaga, que abrigará a sentinela.

II. Nesta implementação, o algoritmo tem seu pior desempenho quando o valor de chave não se encontra em nenhuma das posições de 0 a n-1 de vet; em outras palavras, quando chave não pertence à lista.

III. Se o valor de chave se encontra armazenado na posição t de vet, sendo 0 ≤ t < n, são realizadas exatamente t comparações envolvendo chave até localizá-la.

Está correto somente o que se afirma em:

Answer

I - Correta

II- Correta

III - Se o valor de chave se encontra armazenado na posição t de vet, sendo 0 ≤ t < n, são realizadas exatamente t comparações envolvendochave até localizá-la.

Imaginemos que um vetor n de tamanho 5 armazena o valor procudado na ultima posição.

Posição 0 -> Um valor;Posição 1 -> Um valor; Posição 2 -> Um valor; Posição 3 -> Um valor;Posição 4 -> VALOR PROCURADO;

Então: 0 ≤ t < n é igual a 0≤4

Sendo assim, o erro da questão estão em dizer que são realizadas t comparações. O correto seria "t+1 comparações".

SóProvas

Continue usando...

O que está incluso