TC A4.3 ED

Prévia do material em texto

ESTRUTURA DE DADOS
CCT0260_A4_201702472027_V3
	
		
	 
	Lupa
	 
	 
	
Vídeo
	
PPT
	
MP3
	 
	Aluno: 
	Matrícula: 
	Disciplina: CCT0260 - ESTRUT.DE DADOS 
	Período Acad.: 2017.3 EAD (G) / 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.
		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
	
	
	5 e 5
	
	
	6 e 1
	
	 
	6 e 2
	
	
	
		2.
		Marque a afirmativa correta para a "Busca ou pesquisa binária".
		
	
	
	
	 
	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 adicionar um valor no vetor, mantendo a ordem existente e ajustando o total de elementos.
	
	
	É o processo pelo qual um conjunto de dados é colocado em uma ordem crescente ou decrescente.
	
	 
	Consiste em adicionar um valor no vetor, alterando a ordem existente e ajustando o total de elementos.
	
	
	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.
	 Gabarito Comentado
	
	
		3.
		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.
		
	
	
	
	
	Bolha
	
	
	Seleção
	
	
	Quicksort
	
	
	Heapsort
	
	 
	Inserção
	 Gabarito Comentado
	
	
		4.
		É correto afirmar sobre o funcionamento da busca sequencial.
		
	
	
	
	 
	Os elementos são pesquisados de acordo com o índice. Pior caso: o elemento está no último índice do meu vetor.
	
	
	Os elementos são pesquisados de acordo com o índice. Melhor caso: o elemento está no último índice do meu vetor.
	
	
	Os elementos são pesquisados de acordo com o índice. Pior caso: o elemento está no primeiro índice do meu vetor.
	
	
	Os elementos são pesquisados aleatoriamente. Pior caso: o elemento está no último índice do meu vetor.
	
	
	Os elementos são pesquisados de acordo com o índice. Melhor caso: o elemento está no meio do meu vetor.
	 Gabarito Comentado
	
	
		5.
		Nos métodos de ordenação interna, quais são aqueles classificados como tipo método simples?
		
	
	
	
	 
	Selection Sort, Insert Sort e Bubble Sort
	
	
	Selection Sort, Shell Sort e Bubble Sort
	
	
	Insert Sort, Bubble Sort e Shell Sort
	
	
	Insert Sort, Bubble Sort e Quick Sort
	
	
	Shell Sort, Quick Sort e Heap Sort
	 Gabarito Comentado
	 Gabarito Comentado
	 Gabarito Comentado
	
	
		6.
		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 número de inscrição, o nome e a nota obtida pelo candidato. Este vetor está ordenado pelo número de inscrição. Para realização de uma consulta que, dado um número de inscrição, apresenta o nome e nota do candidato, um programador utilizou um algoritmo de busca que realiza sucessivas divisões no vetor, comparando o número de inscrição procurado com o número de inscrição do candidato posicionado no meio do vetor. Se o candidato posicionado do meio do vetor tiver o número de inscrição igual ao número de inscrição procurado, a busca termina com sucesso. Caso contrário, se candidato posicionado do meio do vetor tiver número de inscrição menor que o procurado, então a busca continua na metade posterior do vetor. E finalmente, se candidato posicionado do meio do vetor tiver número de inscrição maior que o procurado, a busca continua na metade anterior do vetor. O algoritmo utilizado pelo programador trata-se do método denominado busca:
		
	
	
	
	
	linear.
	
	
	por comparação.
	
	
	randômica.
	
	
	por contagem.
	
	 
	binária.
	 Gabarito Comentado
	
	
		7.
		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:
		
	
	
	
	 
	Seleção
	
	
	Inserção
	
	
	Quicksort
	
	
	Bolha
	
	
	Heapsort
	 Gabarito Comentado
	
	
		8.
		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
		
	
	
	
	
	Mergesort
	
	 
	Bublesort
	
	
	Heapsort
	
	
	Shellsort
	
	
	Quicksort
	 Gabarito Comentado