Ex. Aula 4 ESTRUTURA DE DADOS ORDENAÇÃO E PESQUISA

Prévia do material em texto

09/04/2019 EPS
estacio.webaula.com.br/Classroom/index.html?id=2294224&classId=1132751&topicId=2652356&p0=03c7c0ace395d80182db07ae2c30f034&en… 1/4
CCT0753_EX_A4_201802216618_V1
 
 
 
 ESTRUTURA DE DADOS 4a aula
 Lupa 
Vídeo
 
PPT
 
MP3
 
 
Exercício: CCT0753_EX_A4_201802216618_V1 11/03/2019 (Finaliz.)
Aluno(a): WALDIR DE SOUZA PINTO 2019.1 EAD
Disciplina: CCT0753 - ESTRUTURA DE DADOS 201802216618
 
 1a Questão
Em relação à classificação do método de ordenação, assinale abaixo aquele que, durante o processo de ordenação, só usa a
memória principal:
Ordenação Simples
 Ordenação Interna
Ordenação Simples Externa
Ordenação Externa
Ordenação Eficiente
Gabarito
 Coment.
Gabarito
 Coment.
Gabarito
 Coment.
 
 
 2a 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
2
 0
1
-2
-1
 
 
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
09/04/2019 EPS
estacio.webaula.com.br/Classroom/index.html?id=2294224&classId=1132751&topicId=2652356&p0=03c7c0ace395d80182db07ae2c30f034&en… 2/4
 
 
 3a Questão
"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 :
InsertionSort
MergeSort
QuickSort
SelectionSort
 BubbleSort
 
 
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ô.
 
 
 4a Questão
Qual papel do for mais interno na função ordena abaixo ?
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 maior valor de x que deve ser inserido em v[0..j-1].
Encontrar o menor valor v[j] 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
Gabarito
 Coment.
 
 
 5a Questão
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
 Inserção
Seleção
Gabarito
 Coment.
 
 
 6a Questão
09/04/2019 EPS
estacio.webaula.com.br/Classroom/index.html?id=2294224&classId=1132751&topicId=2652356&p0=03c7c0ace395d80182db07ae2c30f034&en… 3/4
O resultado do concurso para o cargo de uma empresa está armazenado em um vetor, que contém
em cada um de seus elementos o nome e a nota obtida pelo candidato. Deseja-se que este vetor
seja ordenado pela nota, em ordem decrescente. Sendo o vetor pequeno (poucos elementos), o
programador responsável por desenvolver este algoritmo, escolheu um método de ordenação que
executa os seguintes passos:
Selecione candidato com maior nota entre todos e troque-o com o candidato que está na
primeira posição do vetor;
Selecione o segundo maior e troque-o com o candidato que está na segunda posição;
Os passos descritos anteriormente são seguidos para a terceira nota, quarta nota e assim por
diante até que reste apenas um candidato.
O algoritmo utilizado pelo programador trata-se do método de ordenação denominado:
Inserção
Heapsort
Bolha
 Seleção
Quicksort
Gabarito
 Coment.
 
 
 7a Questão
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 a posição de v se o valor vl foi encontrado.
Retorna o valor de vl se o valor n foi encontrado.
Resulta em erro, se o valor de vl não estiver dentro de v.
Retorna -1 se o valor de vl estiver dentro de v.
Retorna -1 se o valor de n foi encontrado.
 
 
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
 Coment.
 
 
 8a 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];
09/04/2019 EPS
estacio.webaula.com.br/Classroom/index.html?id=2294224&classId=1132751&topicId=2652356&p0=03c7c0ace395d80182db07ae2c30f034&en… 4/4
v[i-1] = v[i];
v[i] = aux;
}
}
...
Assinale o método ao qual o trecho de algoritmo pertence.
 Inserção
Heapsort
Seleção
Quicksort
Bolha
Gabarito
 Coment.