Algoritmos de Busca e Ordenação

Prévia do material em texto

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:
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.
Sobre o funcionamento da busca binária, é correto afirmar que dividindo seu vetor em duas metades.
ESTRUTURA DE DADOS
 CCT0753_A4_201701030284_V1 
 
 
Lupa Calc.
 
 
Vídeo
 
PPT
 
MP3
 
Aluno: TIAGO LUIZ CHAVES Matrícula: 201701030284
Disciplina: CCT0753 - ESTRUTURA DE DADOS Período Acad.: 2018.1 EAD (GT) / EX
 
 
Prezado (a) Aluno(a),
 
Você fará agora seu EXERCÍCIO DE FIXAÇÃO! Lembre-se que este exercício é opcional, mas não valerá ponto para sua avaliação. O mesmo será composto de
questões de múltipla escolha (3).
Após a finalização do exercício, você terá acesso ao gabarito. Aproveite para se familiarizar com este modelo de questões que será usado na sua AV e AVS.
 
1.
Tabela Hash
 Pesquisa de seleção
Pesquisa sequêncial
Pesquisa ordenada
 Pesquisa binária
 
Gabarito Coment.
 
2.
Quicksort
 Inserção
Heapsort
 Bolha
Seleção
 
Gabarito Coment.
 
3.
 Se o item for menor que o item que está na metade do vetor, procure na segunda metade, ou seja, a da direita.
Se o item for menor que o item que está na metade do vetor, o item foi encontrado.
"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 :
Nos métodos de ordenação interna, quais são aqueles classificados como tipo método simples?
Seja a seguinte função de ordenação:
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;
 }
 }
Pode-se dizer que é uma função de ordenaçã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)
 
 Se o item for igual ao 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 maior que o item que está na metade do vetor procure na primeira metade, ou seja, a da direita.
 
Gabarito Coment.
 
4.
MergeSort
SelectionSort
 BubbleSort
InsertionSort
QuickSort
 
 
5.
Shell Sort, Quick Sort e Heap Sort
Insert Sort, Bubble Sort e Shell Sort
Insert Sort, Bubble Sort e Quick Sort
Selection Sort, Shell Sort e Bubble Sort
 Selection Sort, Insert Sort e Bubble Sort
 
Gabarito Coment. Gabarito Coment. Gabarito Coment.
 
6.
 Que utiliza o método inserção e realiza uma ordenação decrescente nos elementos do vetor v.
Que utiliza o método seleção e realiza uma ordenação crescente nos elementos do vetor v.
 Que utiliza o método inserção e realiza uma ordenação crescente nos elementos do vetor v.
Que utiliza o método bolha e realiza uma ordenação crescente nos elementos do vetor v.
Que utiliza o método seleção e realiza uma ordenação decrescente nos elementos do vetor v.
 
 
7.
 cout<<"\n....: "< < outroVetor[meio]<else 
 cout<<"\nDado nao encontrado\n";
Pode-se afirmar que:
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".
trata-se da implementação do algortimo de ordenação por seleção.
trata-se da implementação do algortimo de busca sequencial
trata-se da implementação do algortimo de ordenação por inserção.
 trata-se da implementação do algortimo de busca binária.
trata-se da implementação do algortimo de ordenação bolha.
 
Gabarito Coment.
 
8.
QuickSort
Seleção
Bolha
MergeSort
 Inserção