Algoritmos de Ordenação e Busca

Prévia do material em texto

1.
		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 Externa
	
	
	Ordenação Externa
	
	 
	Ordenação Interna
	
	
	Ordenação Eficiente
	
	
	Ordenação Simples
	
	
	
		2.
		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.
	
	
	
	
	
	5 e 5
	
	
	7 e 1
	
	
	6 e 4
	
	
	6 e 1
	
	 
	6 e 2
	
	
	
		3.
		Suponha uma listagem, contendo número de inscrição e pontuação (ordenada pelo número de inscrição) dos candidatos para o cargo de Analista de Sistemas de uma grande empresa pública. São 1024 candidatos inscritos e o sistema implementado para consulta do resultado, permite busca binária ou busca sequencial pelo número de inscrição. O número máximo de comparações executadas se fosse utilizada a busca binária e se fosse utilizada busca sequencial, respectivamente, seria de:
	
	
	
	
	
	9 e 9
	
	
	1024 e 512
	
	
	9 e 10
	
	 
	512 e 1024
	
	
	10 e 10
	 Gabarito Comentado
	
	
		4.
		Marque a afirmativa correta para a "Busca ou pesquisa binária".
	
	
	
	
	
	É o processo pelo qual um conjunto de dados é colocado em uma ordem crescente ou decrescente.
	
	
	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.
	
	
	Consiste em adicionar um valor no vetor, mantendo a ordem existente e ajustando o total de elementos.
	
	
	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 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.
	 Gabarito Comentado
	
	
		5.
		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.
	
	
	por comparação.
	
	
	linear.
	
	
	randômica.
	
	
	por contagem.
	 Gabarito Comentado
	
	
		6.
		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:
	
	
	
	
	
	Pesquisa ordenada
	
	
	Tabela Hash
	
	 
	Pesquisa binária
	
	
	Pesquisa sequêncial
	
	
	Pesquisa de seleção
	 Gabarito Comentado