TESTE DE CONHECIMENTO AULA 04 - ESTRUTURA DE DADOS

Prévia do material em texto

ESTRUTURA DE DADOS
AULA 04
		1.
		Nos métodos de ordenação interna, quais são aqueles classificados como tipo método simples?
	
	
	
	Insert Sort, Bubble Sort e Quick Sort
	
	
	Shell Sort, Quick Sort e Heap Sort
	
	
	Selection Sort, Insert Sort e Bubble Sort
	
	
	Insert Sort, Bubble Sort e Shell Sort
	
	
	Selection Sort, Shell Sort e Bubble Sort
		
	Gabarito
Comentado
	
	
		
	Gabarito
Comentado
	
	
		
	Gabarito
Comentado
	
	
	
	
	 
		
	
		2.
		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 binária
	
	
	pesquisa cadeias indexada
	
	
	pesquisa de cadeias
	
	
	pesquisa sequencial
	
	
	pesquisa indexada
		
	Gabarito
Comentado
	
	
	
	
	 
		
	
		3.
		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 2
	
	
	6 e 4
	
	
	7 e 1
	
	
	6 e 1
	
	
	5 e 5
		
	Gabarito
Comentado
	
	
	
	
	 
		
	
		4.
		Em uma pesquisa sequencial a lista deve estar?
	
	
	
	ordenada ou desordenada.
	
	
	ordenada somente do início até a metade da lista.
	
	
	ordenada somente o primeiro da lista.
	
	
	desordenada somente da metade da lista até o final.
	
	
	sempre desordenada.
	
Explicação:
A busca sequencial pode se usada para listas ordenadas ou não ordenadas, não havendo qualquer restrição a parte ou à  totalidade da lista na ordenação.  Já a busca binária só pode ser usada para listas ordenadas.
		
	Gabarito
Comentado
	
	
	
	
	 
		
	
		5.
		Qual a importância de se entender a "ordenação" de dados ?
	
	
	
	A ordenação é a base na qual, muitos sistemas são construídos. Entendendo a ordenação, tem-se conhecimento para manter outros problemas.
	
	
	A ordenação é a base na qual, muitos algoritmos são construídos. Entendendo a ordenação, tem-se conhecimento para manter outros problemas.
	
	
	A ordenação é a base na qual, muitos sistemas são construídos. Entendendo a ordenação, tem-se conhecimento para resolver outros problemas.
	
	
	A ordenação é a base na qual, muitos algoritmos são construídos. Entendendo a ordenação, tem-se conhecimento para resolver outros problemas.
	
	
	A ordenação é a base na qual, muitos programas são construídos. Entendendo a ordenação, tem-se conhecimento para manter outros problemas.
		
	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:
	
	
	
	binária.
	
	
	randômica.
	
	
	por contagem.
	
	
	por comparação.
	
	
	linear.
		
	Gabarito
Comentado
	
	
	
	
	 
		
	
		7.
		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
	
	
	
	Bublesort
	
	
	Mergesort
	
	
	Quicksort
	
	
	Shellsort
	
	
	Heapsort
		
	Gabarito
Comentado
	
	
	
	
	 
		
	
		8.
		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 III e IV são corretas.
	
	
	Somente as afirmativas I e III 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.