Na linguagem C, uma lista sequencial com n elementos pode ...

Próximas questões
Com base no mesmo assunto
Q445743 Programação
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:
Alternativas

Gabarito comentado

Confira o gabarito comentado por um dos nossos professores

Alternativa correta: A - I e II.

A questão aborda o conceito de um algoritmo de busca com sentinela na linguagem de programação C. Este é um método para encontrar um elemento em uma lista sequencial armazenada em um vetor. A busca com sentinela consiste em adicionar o elemento buscado (chave) ao final da lista (como uma sentinela) para garantir que o algoritmo termine, mesmo que o elemento não esteja presente nas posições originais do vetor.

A afirmativa I está correta porque, para o algoritmo funcionar como esperado, é necessário que haja espaço para adicionar a sentinela. Isso significa que o vetor vet deve ter pelo menos n+1 posições, onde n é o número de elementos originais da lista. A sentinela é adicionada na posição vet[n], que seria a posição subsequente à última do vetor se este tivesse apenas n posições. Portanto, o vetor precisa ter uma posição extra para acomodar a sentinela.

A afirmativa II também está correta porque o algoritmo terá o pior desempenho quando a chave não for encontrada entre as posições 0 a n-1. Isso ocorre porque o algoritmo terá que percorrer todo o vetor até alcançar a sentinela adicionada, resultando no número máximo de comparações possíveis (n comparações, pois a sentinela está na posição n).

A afirmativa III está incorreta. Se a chave estiver na posição t do vetor, na realidade serão realizadas t+1 comparações até que ela seja localizada. A primeira comparação é com o elemento na posição 0, e assim prossegue até chegar na posição t, onde a chave está localizada. Logo, se chave está na posição 0, uma comparação é realizada, se está na posição 1, duas comparações, e assim por diante.

Portanto, as afirmativas I e II estão corretas, o que torna a alternativa A a escolha certa para esta questão.

Clique para visualizar este gabarito

Visualize o gabarito desta questão clicando no botão abaixo

Comentários

Veja os comentários dos nossos alunos

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".

Clique para visualizar este comentário

Visualize os comentários desta questão clicando no botão abaixo