Simulado 2 - Aula 4

Prévia do material em texto

1a 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 menor valor v[j] que deve ser inserido 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 
 
Encontrar o valor de v[j] deve em v[0..j-1]. 
 
Encontrar o maior valor de x que deve ser inserido em v[0..j-1]. 
6 
 
 
 
 
 
 2a Questão 
 
 
Marque a afirmativa correta para a "Ordenação em Listas Lineares Sequenciais". 
 
 
Consiste em adicionar um valor no vetor, alterando a ordem existente e ajustando o total de 
elementos. 
 
Consiste em adicionar um valor no vetor, mantendo a ordem existente e ajustando o total de 
elementos. 
 Consiste em fazer uma busca em um vetor já ordenado, dividindo o espaço de busca ao meio e 
verificando se o dado está no meio ou, antes do meio ou depois do meio. 
 
Consiste em fazer uma busca em um vetor desordenado, dividindo o espaço de busca ao meio e 
verificando se o dado está no meio ou, antes do meio ou depois do meio. 
 É o processo pelo qual um conjunto de dados é colocado em uma ordem crescente ou decrescente. 
 
 
 
 
 
 
 3a Questão 
 
 
Considere as afirmativas a seguir. 
I. Uma forma muito simples de fazer uma busca em um vetor consiste em percorrer o vetor, elemento 
a elemento, para verificar se o elemento procurado é igual a um dos elementos do vetor. 
II. A pesquisa sequencial é extremamente simples e eficiente quando o número de elementos 
do vetor for muito grande. 
III. Na pesquisa binária, a cada interação do algoritmo o tamanho do vetor é dividido ao meio. 
IV. A pesquisa binária funciona corretamente quanto o conjunto de dados estiver desordenado. 
Assinale a alternativa correta. 
 
 
Somente as afirmativas I e IV são corretas. 
 
Somente as afirmativas I e II são corretas. 
 
Somente as afirmativas II, III e IV são corretas. 
 Somente as afirmativas I e III são corretas. 
 
Somente as afirmativas III e IV são corretas. 
 
 
 
Explicação: 
Analisando cada afirmativa : 
I. Uma forma muito simples de fazer uma busca em um vetor consiste em percorrer o vetor, elemento a 
elemento, para verificar se o elemento procurado é igual a um dos elementos do vetor. 
Correto. SEria uma busca sequencial. 
II. A pesquisa sequencial é extremamente simples e eficiente quando o número de elementos 
do vetor for muito grande. 
Falso. Se tivermos que procurar um elemento que está no fim do vetor ou que não seja encontrado, o 
tempo de execução será proporcional ao número de elementos. Então, quanto maior a lista, mais tempo 
levaremos. 
III. Na pesquisa binária, a cada interação do algoritmo o tamanho do vetor é dividido ao meio. 
Correto. 
IV. A pesquisa binária funciona corretamente quanto o conjunto de dados estiver desordenado. 
Falso. Por definição, a busca binária só pode atuar em listas ordenadas. 
Logo, apenas as afirmativas I e III estão corretas. 
 
 
 
 
 4a 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 4 
 6 e 2 
 
5 e 5 
 
6 e 1 
 
7 e 1 
 
 
 
 
 
 
 5a Questão 
 
 
Para consultarmos uma estrutura de dados, normalmente, empregamos um tipo de pesquisa de dados. O 
trecho de programa a seguir refere-se a uma pesquisa por um elemento único (sua primeira ocorrência), 
em um conjunto de elementos de dados armazenado em uma estrutura de acesso indexado e aleatório. 
Selecione a opção correspondente ao algoritmo utilizado, no programa, para a referida pesquisa: 
int busca(float v[], float valor, int n) { 
int ini = 0, fim = n -1, meio; 
while (ini <= fim) { 
meio = (ini + fim)/2; 
if (v[meio] == valor) return meio; 
if (valor < v[meio]) fim = meio -1; 
 else ini = meio+1; 
} 
return -1; 
} 
 
 pesquisa sequencial 
 
pesquisa cadeias indexada 
 
pesquisa de cadeias 
 pesquisa binária 
 
pesquisa indexada 
 
 
 
 
 
 
 6a 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: 
v[10] = {0, 2, 4, 6, 8, 10, 20, 100} 
tam = 8 
e = -6 
É sabido que a mesma retornaria o valor -1, porque: 
 
 
Seria o retorno do segundo if 
 
É a posição do elemento e no vetor v 
 
Seria o retorno do while 
 Porque ele não achou o elemento na coleção 
 
É o módulo do valor de e 
 
 
 
Explicação: 
 Veja que para retornar -1 o return m; não foi executado. E para o return m; não poder ser 
executado, o teste if ( v[m] == e ) foi sempre falso. Logo, retornar -1 é o caso do elemento e = -6 não 
ser encontrado no vetor v. 
 
 
 
 
 
 7a 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 4 
 
7 e 1 
 
6 e 1 
 6 e 2 
 5 e 5 
 
 
 
 
 
 8a 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 ? 
 
 
 
5 10 20 30 
 10 20 30 40 
 
10 20 40 30 
 
10 30 40 20 
 
10 30 20 40