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

Prévia do material em texto

24/05/2021 EPS 
 ESTRUTURA DE DADOS 
a Lupa 
4 aula 
 
Exercício: CCT0826_EX_A4_ 01/05/2021 
Aluno(a): 2021.1 EAD 
Disciplina: CCT0826 - ESTRUTURA DE DADOS 
 
Existem vários tipos de algoritmos para realizar a ordenação dos elementos, onde um algoritmo de ordenação deve 
rearranjar o vetor de forma a estabelecer uma ordem entre os elementos. Marque a alternativa correta que cita o 
algoritmo cuja descrição é: "considera cada elemento uma vez inserindo-o em seu lugar correto entre os elementos que 
já estão em ordem". E o seu passo a passo pode ser descrito como: "o elemento é inserido entre os ordenados movendo- 
se os elementos maiores que ele uma posição para a direita e posteriormente inserindo-o na posição vaga". 
QuickSort 
MergeSort 
Bolha 
Seleção 
 Inserção 
Respondido em 01/05/2021 22:11:19 
Gabarito 
Comentado 
 
 
Existem vários algoritmos de busca em estruturas de dados, um destes realiza a busca em vetores, e requer acesso 
aleatório aos elementos desta estrutura e parte do pressuposto de que os dados do vetor estejam ordenados e utiliza a 
técnica de divisão e conquista comparando o elemento desejado com o elemento do meio do vetor. Esta técnica ainda 
verifica se o elemento do meio do vetor for o desejado, a busca termina. Caso contrário, se o elemento do meio vier 
antes do elemento buscado, então a busca continua na metade posterior do vetor. E se o elemento do meio vier depois da 
chave, a busca continua na metade anterior do vetor. O algoritmo que utiliza esta metodologia é: 
Pesquisa sequencial 
Seleção 
Bolha 
Inserção 
 Pesquisa binária 
Respondido em 01/05/2021 22:11:54 
Gabarito 
Comentado 
 
 
Qual papel do for mais interno na função ordena abaixo ? 
1/4 
 
24/05/2021 EPS 
void ordena( int n, int v[]) 
{ 
int i, j, x; 
for (j = 1; j < n; ++j) { 
x = v[j]; 
for (i = j-1; i >= 0 && v[i] > x; --i) 
v[i+1] = v[i]; 
v[i+1] = x; 
} 
} 
Encontrar o menor valor v[j] que deve ser inserido em v[0..j-1]. 
Encontrar o maior valor de x que deve ser inserido em v[0..j-1]. 
Encontrar o valor de v[j] deve em v[0..j-1]. 
 Encontrar o ponto onde v[j] deve ser inserido em v[0..j-1]. 
Encontrar o elmento a ser eliminado do vetor 
Respondido em 01/05/2021 22:12:52 
Gabarito 
Comentado 
 
 
Com a utilização das estruturas de dados e seus tipos, em algumas situações é imprescindível a criação de funções que 
façam determinada verificação ou ação nestas estruturas. Dessa forma, analise a função abaixo e marque corretamente a 
alternativa que descreve as funcionalidades desta. 
int funcao(float v[], float vl, int n) 
{ 
for (int i = 0; i < n; i++) 
if (v[i] == vl) 
return i; 
return -1; 
} 
Retorna -1 se o valor de vl estiver dentro de v. 
 Retorna a posição de v se o valor vl foi encontrado. 
Resulta em erro, se o valor de vl não estiver dentro de v. 
Retorna o valor de vl se o valor n foi encontrado. 
 Retorna -1 se o valor de n foi encontrado. 
Respondido em 01/05/2021 22:14:52 
 
 
Explicação: 
A função apresentada é a busca sequencial. Note que ela retorna o índice do elemento vl, quando o valor vl é 
encontrado e ela retorna -1 caso o valor vl não for encontrado. 
Gabarito 
Comentado 
 
 
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: 
Tabela Hash 
Pesquisa de seleção 
Pesquisa ordenada 
Pesquisa sequêncial 
 Pesquisa binária 
Respondido em 01/05/2021 22:15:54 
 
 
Explicação: 
O enunciado descreve a busca binária. 
A busca sequencial trabalha sequencialmente testando elemento a elemento. 
2/4 
 
24/05/2021 EPS 
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. 
Gabarito 
Comentado 
 
 
Considere a seguinte função busca escrita em linguagem C++ : 
bool busca(int vetor[ ], int n, int tam) 
{ 
int ini=0, mid; 
while (ini <= tam) 
{ 
cout << " x "; 
mid = (ini + tam)/2; 
if (vetor[mid] == n) 
return true; 
else if (n > vetor[mid]) 
ini = mid+1; 
else 
tam = mid-1; 
} 
return false; 
} 
Qual a quantidade total de impressões da letra x nas buscas pelos números n = 4, n = 2 e n = 0 no vetor 
[1,2,3,4,5,6,7,8], sendo tam = 7 ? 
int vetor[] = {1,2,3,4,5,6,7,8}; 
busca(vetor, 4, 7); 
busca(vetor, 2, 7); 
busca(vetor, 0, 7); 
5 
 4 
 6 
8 
9 
Respondido em 01/05/2021 22:16:36 
 
 
Explicação: 
Na 1a. execução da busca... para n = 4 temos impresso : x 
Na 2a. execução da busca ... para n = 2 temos impresso : x x 
Na 3a. execução da busca ... para n = 0 temos impresso : x x x 
Total de impressões da letra x : 6 
 
 
É 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. 
randômica. 
3/4 
 
24/05/2021 EPS 
por comparação. 
 binária. 
Respondido em 01/05/2021 22:17:06 
Gabarito 
Comentado 
 
 
Sobre o funcionamento da busca binária, é correto afirmar que dividindo seu vetor em duas metades. 
 Se o item for igual ao item que está na metade do vetor, o item foi encontrado. 
Se o item for maior que o item que está na metade do vetor procure na primeira metade, ou seja, a da direita. 
Se o item for menor que o item que está na metade do vetor, o item foi encontrado. 
Se o item for igual ao item que está na metade do vetor, o item não foi encontrado. 
Se o item for menor que o item que está na metade do vetor, procure na segunda metade, ou seja, a da direita. 
Respondido em 01/05/2021 22:17:25 
 
 
Explicação: 
Neste tipo de busca, o vetor deve estar ordenado. 
Divide-se o conjunto de dados ao meio e procura-se no meio do vetor. Se achou, retorna a posição do dado do meio. SE 
não achou, verifica-se se o valor procurado vem antes do valor do meio. Se for verdade, redefine-se o fim do vetor, 
voltando a realizar a busca à esquerda do meio. Se o valor procurado vier depois do valor do meio do vetor, então 
redefine-se o início e segue-se para a busca na parte à direita do meio do vetor. 
Gabarito 
Comentado 
 
 
 
4/4