Exércicio 04 Estrutura de dados

Prévia do material em texto

ESTRUTURA DE DADOS
 4a aula
 Lupa 
Vídeo
 
PPT
 
MP3
 
 
Exercício: CCT0753_EX_A4_201801153345_V1 19/03/2019 (Finaliz.)
Aluno(a): JORGIVALDO NOGUEIRA LEAL 2019.1 EAD
Disciplina: CCT0753 - ESTRUTURA DE DADOS 201801153345
 
 1a Questão
É um método de pesquisa ou busca, cujo algoritmo parte do pressuposto de que o vetor está ordenado e
realiza sucessivas divisões do espaço de busca, comparando o elemento buscado (chave) com o elemento
no meio do vetor. Se o elemento do meio do vetor for a chave, a busca termina com sucesso. Caso
contrário, se o elemento do meio vier antes do elemento buscado, então a busca continua na metade
posterior do vetor. E finalmente, se o elemento do meio vier depois da chave, a busca continua na metade
anterior do vetor.
A descrição apresentada trata-se do método denominado busca ...... 
linear.
por contagem.
 binária.
por comparação.
randômica.
Gabarito
 Coment.
 
 
 2a Questão
Entre os diversos algoritmos de pesquisa existentes, certamente os mais famosos são os da pesquisa sequencial e o da
pesquisa binária. A busca ou pesquisa sequencial pode ser aplicada em vetores independente destes estarem ordenados,
entretanto a busca binária só se aplica em vetores ordenados.
Seja o vetor A= {10,35,41,55,69,70,98}, suponha que o número 70 foi pesquisado pelo algoritmo da busca sequencial e
também pelo algoritmo da busca binária, ambos algoritmos realizam testes nos elementos do vetor até achar o que
procuram ou definirem que o elemento não se encontra no vetor. Sendo assim marque a alternativa que expressa o número
de testes realizados pela busca sequencial e o número de testes realizados pela busca binária, respectivamente, até
encontrarem o 70.
6 e 1
6 e 4
5 e 5
 6 e 2
7 e 1
Gabarito
 Coment.
 
 
 3a Questão
O processo de rearranjar um conjunto de dados em uma ordem crescente ou decrescente é chamado de ordenação. Existem várias
técnicas de ordenação, entretanto a técnica que procura o menor valor entre todos os elementos do vetor e troca-o pelo primeiro
elemento; para os n - 1 elementos restantes, determinação do elemento de menor valor e troca pelo segundo elemento e assim
sucessivamente, é chamado de:
Inserção
Binária
Hash
Bolha
 Seleção
Gabarito
 Coment.
 
 
 4a Questão
Considere a função misterio e o trecho abaixo.
void misterio(int v[ ], int n) { //n é o número de elementos de v
 int i, j, m, aux;
 for (j = 0; j < n-1; j++) {
 m = j;
 for (i = j+1; i < n; i++) {
 if (v[i] < v[m])
 m = i;
 }
 aux = v[j];
 v[j] = v[m];
 v[m] = aux;
 }
}
Trecho na main : 
int v[4] = {40,30,10,20};
misterio(v, 4);
Marque a opção correta. Como ficará o vetor após a execução da função misterio ?
 
 10 20 30 40 
5 10 20 30 
10 20 40 30 
10 30 20 40
10 30 40 20 
 
 
Explicação:
O aluno precisa fazer um teste de mesa para achar a solução.
A função implementa a ordenação por seleção, colocando o vetor de entrada em ordem crescente.
 
 
 5a Questão
Sabendo-se que o método de seleção também é um método de ordenação que baseia seu algoritmo em trocas entre os elementos de
um vetor, se submetermos a sequencia de inteiros armazenada em um vetor inicialmente na seguinte ordem : 13, 23, 3, 8, 1. Pode-
se dizer que quando o menor elemento do vetor alcançar sua posição final, a ordenação apresentada no vetor é:
1,3,23,8,13
1,8,3,23,13
 1,23,3,8,13
1,13,23,8,3
1,23,13,8,3
Gabarito
 Coment.
 
 
 6a Questão
Analisando o trecho de código a seguir:
inicio=0; 
 fim= tamanho - 1;
 meio=(inicio+fim)/2; 
 while(procura != nomeVetor[meio] && inicio != fim)
 {
 if(procura > nomeVetor[meio]) 
 inicio=meio+1;
 else 
 fim=meio; 
 meio=(inicio+fim)/2; 
 }
 if(nomeVetor[meio]==procura)
 cout<<"\n....: "< < outroVetor[meio]<else 
 cout<<"\nDado nao encontrado\n";
Pode-se afirmar que:
trata-se da implementação do algortimo de ordenação por inserção.
trata-se da implementação do algortimo de ordenação por seleção.
trata-se da implementação do algortimo de ordenação bolha.
 trata-se da implementação do algortimo de busca binária.
trata-se da implementação do algortimo de busca sequencial
Gabarito
 Coment.
 
 
 7a Questão
 if(vet[j-1] < vet[j] )
 { 
 aux=vet[j];
 vet[j]= vet[j-1];
 vet[j-1]=aux; 
 }
if(vet[j] < vet[j-1] )
 { 
 aux=vet[j];
 vet[j-1]= vet[j];
 vet[j-1]=aux; 
 }
if(vet[j] == vet[j-1] )
 { 
 aux=vet[j];
 vet[j]= vet[j-1];
 vet[j-1]=aux; 
 }
if(vet[j] < vet[j-1] )
 { 
 aux=vet[j];
 vet[j]< vet[j-1];
 vet[j-1]=aux; 
 }
if(vet[j-1] > vet[j] )
 { 
 aux=vet[j];
 vet[j]= vet[j-1];
 vet[j-1]=aux; 
 }
 
 
 8a Questão
Os algoritmos de busca são muito utilizados em estrutura de dados. Sendo assim, o algoritmo que realiza a busca em vetores e que
exige acesso aleatório aos elementos do mesmo e que parte do pressuposto de que o vetor está ordenado e realiza sucessivas
divisões do espaço de busca comparando o elemento que se deseja com o elemento do meio do vetor, é chamado de:
Pesquisa sequêncial
Pesquisa de seleção
 Pesquisa binária
Pesquisa ordenada
Tabela Hash
 
 
Explicação:
O enunciado descreve a busca binária.
A busca sequencial trabalha sequencialmente testando elemento a elemento.
Pesquisa de seleção ou ordenada não foram abordadas.
Tabela hash trabalha com função hash e não se encaixa na descrição feita.