Algoritmos de Ordenação e Busca em Estrutura de Dados

Prévia do material em texto

ESTRUTURA DE DADOS 
4a aula Lupa 
 
 
 
 
 
 
Disciplina: CCT0826 - ESTRUTURA DE DADOS 
 
 
1 
 Questão 
 
 
Analise o seguinte trecho de algoritmo de ordenação de dados, cujos elementos estão dispostos em um vetor de nome v 
com n elementos. 
... 
{ 
int i, j, aux; 
for (j = 1; j < n; j++) 
for (i=j; i > 0 && v[i-1]> v[i]; i--) { 
aux = v[i-1]; 
v[i-1] = v[i]; 
v[i] = aux; 
} 
} 
... 
Assinale o método ao qual o trecho de algoritmo pertence. 
 
 
Inserção 
 
Heapsort 
 
Quicksort 
 
Bolha 
 
Seleção 
Respondido em 21/09/2020 19:04:20 
 
 
Gabarito 
Comentado 
 
 
 
 
 
2 
 Questão 
 
 
https://simulado.estacio.br/bdq_simulados_exercicio_preview.asp?cod_prova=4106908257&cod_hist_prova=205790006&pag_voltar=otacka
https://simulado.estacio.br/bdq_simulados_exercicio_preview.asp?cod_prova=4106908257&cod_hist_prova=205790006&pag_voltar=otacka
javascript:diminui();
javascript:aumenta();
"Algoritmo de ordenação por trocas que varre um vetor um certo número de vezes, comparando os 
elementos vizinhos dois a dois. A cada varredura, se o par de elementos está em ordem crescente, nada 
é feito, caso contrário os elementos do par são permutados". Esta definição está descrevendo o 
algoritmo de ordenação conhecido por : 
 
 
QuickSort 
 
SelectionSort 
 
InsertionSort 
 
MergeSort 
 
BubbleSort 
Respondido em 21/09/2020 19:05:09 
 
 
Explicação: 
Das opções apresentadas, as únicas que são ordenações por troca são Bubblesort e Quicksort. 
Dessas duas ordenações, a única que trabalha com duplas de elementos vizinhos é o Bubblesort. O 
Quicksort, que está fora do escopo da disciplina, trabalha com pivô. 
 
 
 
3 
 Questão 
 
 
Marque a afirmativa correta para a "inserção incremental". 
 
 
Consiste em adicionar um valor no vetor, mantendo a ordem existente e ajustando o total de 
elementos. 
 
A técnica é boa quando os dados ficam uniformemente distribuídos entre os seus 
compartimentos. 
 
Os pivôs são escolhidos aleatoriamente. 
 
É um tipo de sequenciação por intercalação. 
 
É um tipo de ordenação por intercalação 
Respondido em 21/09/2020 19:05:48 
 
 
Gabarito 
Comentado 
 
 
 
 
 
4 
 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 
https://simulado.estacio.br/bdq_simulados_exercicio_preview.asp?cod_prova=4106908257&cod_hist_prova=205790006&pag_voltar=otacka
https://simulado.estacio.br/bdq_simulados_exercicio_preview.asp?cod_prova=4106908257&cod_hist_prova=205790006&pag_voltar=otacka
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 ...... 
 
 
binária. 
 
randômica. 
 
por contagem. 
 
linear. 
 
por comparação. 
Respondido em 21/09/2020 19:08:47 
 
 
Gabarito 
Comentado 
 
 
 
 
 
5 
 Questão 
 
 
Estude atentamente o código a segir: 
int deciframe(int v[ ], int tam, int e){ 
int i = 0, f = tam -1, m; 
while ( i <= f ){ 
m = ( i + f ) / 2; 
if ( v[m] == e ) { return m; } 
if ( e < v[m] ) { f = m - 1; } 
else { i = m + 1; } 
} 
return -1; 
} 
Sabendo que a chamada da mesma foi feita com os parâmetros recebendo os seguintes valores, o que 
ela retornaria? 
v[10] = {0, 2, 4, 6, 8, 10, 20, 100} 
tam = 8 
e = 0 
 
 
-1 
 
1 
 
0 
 
-2 
 
2 
Respondido em 21/09/2020 19:08:36 
 
 
Explicação: 
A busca pode retornar o índice do elemento encontrado ou pode retornar -1, caso o elemento e não seja 
encontrado. Vemos que o valor de e é encontrado. Logo, a função retornará a posição do valor e = 0 no 
vetor. No caso, o elemento zero está na posição 0. 
Resposta : 0 
https://simulado.estacio.br/bdq_simulados_exercicio_preview.asp?cod_prova=4106908257&cod_hist_prova=205790006&pag_voltar=otacka
https://simulado.estacio.br/bdq_simulados_exercicio_preview.asp?cod_prova=4106908257&cod_hist_prova=205790006&pag_voltar=otacka
 
 
 
6 
 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. 
 
 
5 e 5 
 
6 e 2 
 
7 e 1 
 
6 e 4 
 
6 e 1 
Respondido em 21/09/2020 19:11:13 
 
 
Gabarito 
Comentado 
 
 
 
 
 
7 
 Questão 
 
 
 
 
 
if(vet[j-1] > vet[j] ) 
 { 
 aux=vet[j]; 
 vet[j]= vet[j-1]; 
 vet[j-1]=aux; 
 } 
https://simulado.estacio.br/bdq_simulados_exercicio_preview.asp?cod_prova=4106908257&cod_hist_prova=205790006&pag_voltar=otacka
https://simulado.estacio.br/bdq_simulados_exercicio_preview.asp?cod_prova=4106908257&cod_hist_prova=205790006&pag_voltar=otacka
 
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]< 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; 
 } 
Respondido em 21/09/2020 19:19:02 
 
 
 
8 
 Questão 
 
 
O seguinte trecho de programa abaixo representa qual tipo de estrutura de ordenação? 
void ordenar(float v[], int n) // n é o no. de elementos em v 
{ 
 int i , // índice 
 aux, // auxiliar para troca 
trocou = true, 
fim = n - 1; 
while (trocou) 
{ 
 trocou = false; // sinaliza que é falso que trocou 
 for (i = 0; i < fim; i++) 
 { 
 if (v[i] > v[i+1]) 
 { 
 aux = v[i]; 
 v[i] = v[i+1]; 
 v[i+1] = aux; 
 // sinaliza que é verdadeiro que trocou 
 trocou = true; 
 } // fim if 
 } // fim for 
 fim--; // decrementa o fim 
} // fim while 
} // fim da função 
 
 
Quicksort 
 
Bublesort 
 
Mergesort 
 
Heapsort 
 
Shellsort 
Respondido em 21/09/2020 19:20:02 
 
 
Gabarito 
Comentado 
 
 
 
 
 
 
 
 
https://simulado.estacio.br/bdq_simulados_exercicio_preview.asp?cod_prova=4106908257&cod_hist_prova=205790006&pag_voltar=otacka
https://simulado.estacio.br/bdq_simulados_exercicio_preview.asp?cod_prova=4106908257&cod_hist_prova=205790006&pag_voltar=otacka
javascript:abre_colabore('38403','205790006','4106908257');