Programacao e Estrutura de Dados AOL 04

Prévia do material em texto

Programação e Estrutura de Dados 
Avaliação On-Line 4 (AOL 4) - 
1. Question	1	
/	1	
A	busca	binária,	é	uma	busca	que	tem	por	objetivo	receber	uma	estrutura	ordenada	e	fazer	uma	
comparação	parcial	do	dado	que	é	tratado	com	o	tamanho	da	metade	da	sua	estrutura,	caso	o	
dado	seja	maior	que	a	metade	da	estrutura	o	algoritmo	faz	um	loop	na	segunda	metade	da	
estrutura,	caso	seja	menor	faz	um	loop	na	metade	da	estrutura,	esse	formato	elimina	de	um	total	
de	valores	praticamente	metade	de	comparações,	tendo	como	tamanho	O(n/2),	pois	
independente	de	ter	o	dado	ou	não	na	estrutura	somente	vai	percorrer	uma	metade.	
Agora,	leia	o	código-fonte	a	seguir:	
public	static	boolean	buscaBinaria(int[]	vetor,	int	pesquisar)	{if	(	…	)	{for	(int	pos	=	0;	pos	<	
vetor.length;	pos++)	{if	(pesquisar	==	vetor[pos])	{System.out.println("Localizado");return	
true;}}}	else	{for	(int	pos	=	vetor.length;	pos	>	0;	pos--)	{if	(pesquisar	==	vetor[pos])	
{System.out.println("Localizado");return	true;}}}return	false;}	
Considerando	essas	informações	e	o	conteúdo	estudado,	a	alternativa	que	corresponde	ao	
comando	IF	do	código	acima	é:	
Hide	answer	choices		
1. pesquisar	>=	vetor[(int)	(vetor.length)].	
2. pesquisar	==	vetor[(int)	(vetor.length	/	2)].	
3. pesquisar	>=	vetor[(int)	(vetor.length	/	2)].	
Correct	answer	
4. pesquisar	!=	vetor[(int)	(vetor.length)].	
5. pesquisar	<=	vetor[(int)	(vetor.length)].	
2. Question	2	
/	1	
Uma	das	formas	de	navegar	no	grafo	é	através	da	lista	de	adjacência,	que	possui	dois	atributos:	o	
vértice	e	a	lista	de	vizinhos.	Em	vez	de	armazenar	as	arestas,	armazena	os	vizinhos.	
Uma	das	vantagens	da	lista	de	adjacência	é	que	ela	não	utiliza	uma	matriz	como	base	e,	portanto,	
pode	ter	tamanho	indefinido.	
Analise	a	situação	a	seguir:	
public	ArrayList	buscarVizinhos	(Vertice	noaux){returnnew	ArrayList	<>	(arestas	
[noaux.getIndice	()	]);}	
No	código-fonte	acima,	há	uma	criação	estática,	ou	seja,	com	quantidades	fixas	de	vértices.	Foi	
utilizado	um	vetor	de	arestas	para	poder	alocar	os	vizinhos.	Com	base	nessas	informações	e	no	
conteúdo	estudado,	podemos	dizer	que	o	comando	utilizado	para	buscar	o	vizinho	de	um	nó	é:	
Hide	answer	choices		
1. buscarVizinhos	(new	Grafo	(1));	
2. buscarVizinhos	(1);		
3. buscarVizinhos	(new	int	[1]	[1]);		
4. buscarVizinhos	(new	Aresta	(1));	
5. buscarVizinhos	(new	Vertice	("A",1));		
Correct	answer	
3. Question	3	
/	1	
Os	vértices	ou	“nós”	são	os	componentes	de	um	grafo	que	designam	o	sentido	de	uma	aresta.	Se	
um	grafo	não	possui	vértices,	ele	não	possui	arestas.	Os	vértices,	na	programação,	são	classes	
que	não	se	referenciam,	porém	possuem	algumas	propriedades	que	designam	rótulo,	focando	
em	alguns	algoritmos,	no	índice	ou	Ids.	Em	programação	orientada	a	objetos,	temos	o	
encapsulamento	que,	como	o	nome	diz,	encapsula	essas	propriedades	em	métodos	getters	e	
setters,	para	cada	propriedade,	que	em	classe	se	torna	um	atributo.		
Analise	a	situação	a	seguir:	
class	Vertice	{private	static	int	indice;private	static	String	nome;boolean	static	visitado=false;}	
Com	base	nessas	informações	e	no	conteúdo	estudado,	podemos	dizer	que	o	encapsulamento	do	
atributo	índice	corresponde	a:	
Hide	answer	choices		
1. public	void	getID	(int	aux)	{...}	public	int	setID	()	{...}			
2. public	void	setID	(int	aux)	{...}	public	void	setIndice	(int	aux)	{...}	
3. public	void	getIndice	(int	aux)	{...}	public	int	setIndice	()	{...}		
4. public	void	setID	(int	aux)	{...}	public	int	getID	()	{...}		
5. public	void	setIndice	(int	aux)	{...}	public	int	getIndice	()	{...}		
Correct	answer	
4. Question	4	
/	1	
Existem	muitas	formas	de	navegação	dentro	de	um	grafo.	Uma	das	mais	comuns	é	a	matriz	de	
adjacência,	uma	matriz	que	possui	o	mesmo	número	de	linhas	e	de	colunas	–	ou	seja,	quadrada	–	
e	sua	quantidade	de	elementos,	tanto	linhas	quanto	colunas,	é	o	total	de	vértices	do	grafo.	Nesse	
sentido,	toda	matriz	de	adjacência	sempre	será	bidimensional.	
Essa	é	uma	das	principais	formas	de	visualização	de	grafos	dentro	dos	algoritmos,	onde	estes	
recebem	a	matriz	e	fazem	o	processamento	pelas	ligações	dos	vértices.	
Analise	a	situação	a	seguir:	
ESTRUT DADOS QUEST 04 UNID 4_v1.PNG 
Com	base	nessas	informações	e	no	conteúdo	estudado,	dizemos	que	o	grafo	que	corresponde	a	
essa	matriz	é:	
Hide	answer	choices		
1. F-X	e	G	isolado.	
2. F-X-G.	
Correct	answer	
3. G-F-X.	
4. F-G-X.	
5. X-F-G.	
5. Question	5	
/	1	
As	tabelas	hash	podem	ser	desenvolvidas	à	mão,	porém,	no	Java	existe	a	chamada	API	Collection,	
que	auxilia	na	aplicação	desta	estrutura	sem	necessariamente	precisar	criar	do	zero,	através	da	
interface	SET<T>	com	a	instanciação	da	classe	HashSet<T>	().	
Embora	esteja	usando	a	interface	SET,	os	comandos	para	inserir,	editar,	pesquisar	e	remover	
possuem,	basicamente,	a	mesma	sintaxe	para	quase	todas	as	coleções.	
Analise	a	situação	a	seguir:	
import	java.util.HashSet;	
import	java.util.Set;	
public	class	Prj_Hash	{public	static	void	main(String	args[]){Set<Integer>	hasht=new	
HashSet<Integer>();					hasht.add(100);					System.out.println("remover:"+hasht.remove(100));S
ystem.out.println("contains:"+	hasht.contains(100));}			}	
Assim,	considerando	as	informações	apresentadas	e	os	conteúdos	estudados,	analise	as	
operações	a	seguir	e	associe-as	às	suas	respectivas	características:	
1)	add	
2)	remove	
3)	contains	
4)	iterator	
5)	isEmpty	
I.	(	)	Remove	elementos	da	estrutura	
	
II.	(	)	Retorna	um	objeto	navegável	através	de	um	padrão	de	projeto	
	
III.	(	)	Retorna	se	contém	elementos	na	estrutura	ou	não	
	
IV.	(	)	Busca	elementos	na	estrutura	
	
V.	(	)	Insere	elementos	na	estrutura	
Agora,	assinale	a	alternativa	que	apresenta	a	sequência	correta:	
Hide	answer	choices		
1. 2,	4,	5,	3,	1.	
Correct	answer	
2. 5,	4,	2,	3,	1.		
3. 2,	5,	4,	3,	1.	
4. 2,	4,	5,	1,	3.	
5. 1,	2,	4,	3,	5.	
6. Question	6	
/	1	
As	estruturas	de	dados	homogêneas	são	estruturas	que	possuem	indexação	por	profundidade,	
porém	com	apenas	uma	tipagem.	No	caso	de	matrizes	e	vetores,	independentemente	do	
tamanho	“N”	que	possuam,	eles	sempre	terão	a	mesma	tipagem.	
Por	isso,	existem	diversas	aplicações	para	essas	estruturas,	sendo	uma	delas	na	forma	
computacional	de	manipular	um	grafo.	Na	classe	grafo,	temos	os	vértices	e	a	matriz	de	
adjacência,	que	deve	ser	populada	para	possuir	as	arestas.	Porém,	o	grafo	em	si	é	iniciado	ao	
executar	o	construtor,	pois	este	define	os	tamanhos	da	matriz	da	classe.	
Analise	a	situação	a	seguir:	
class	Grafo{private	Vertice	nos	[];private	int	matriz	[]	[];	
public	Grafo	(Vertice	nosaux	[]){...}}	
Com	base	nessas	informações	e	no	conteúdo	estudado,	podemos	dizer	que	a	linha	que	
corresponde	ao	comando	do	construtor	do	código	acima	é:	
Hide	answer	choices		
1. nosaux	=	nosaux;	matriz	=	new	int	[nosaux.length]	[nosaux.length];	
2. nos	=	nos;	matriz	=	new	int	[nos.length]	[nos.length];	
3. noaux	=	nos;	matriz	=	new	int	[nos.length]	[nos.length];	
4. nos	=	nosaux;	matriz	=	new	int	[nosaux.length]	[nosaux.length];	
Correct	answer	
5. nos	=	nosaux;	matriz	=	new	int	[10]	[10];	
7. Question	7	
/	1	
Uma	das	principais	aplicações	de	grafos	em	um	problema	de	logística	é	achar	o	menor	caminho	
para	várias	entregas.	No	caso,	cada	ponto	de	entrega	seria	um	vértice	e	cada	rua,	avenida	ou	
caminho,	seriam	as	arestas.	Por	ser	um	problema	recorrente	em	grafos,	existem	diversos	
algoritmos	para	isso.	Um	deles	se	destaca	por	ser	um	dos	mais	simples	para	resolver	este	
problema.	Trata-se	da	árvore	geradora	mínima	ou	MST	(Minimum	Spanning	Tree),	que	percorre	
os	vizinhos	até	o	fim	e	verifica	se	algum	deles	possui	uma	conectividade	com	os	nós	do	grafo.	
Com	base	nessas	informações	e	no	conteúdo	estudado,	podemos	dizer	que	o	algoritmo	usado	no	
MST	como	forma	de	criar	uma	árvore	geradora	mínima	é:	
Hide	answer	choices		
1. BFS	ou	busca	por	largura.	
2. matriz	de	adjacência.	
3. DFS	ou	busca	por	profundidade.	
Correct	answer	
4. matriz	de	incidência.	
5. lista	de	adjacência.	
8. Question	8	
/	1	
O	HashMap	é	uma	estrutura	hash	diferenciada,	pois	nela	você	é	obrigadoa	setar	o	valor	junto	
com	sua	posição	de	memória,	no	entanto	ao	instanciar	um	hashmap,	deve-se	passar	via	parâtro	
da	declaração	a	tipagem	do	índice	e	a	tipagem	do	valor,	no	caso	do	exemplo	abaixo,	o	índice	é	
integer	e	o	dado	também,	podendo	assumir	diversos	tipos	inclusive	um	objeto	tanto	como	
índice	como	quanto	valor.	
Por	conta	da	particularidade	da	inserção	do	índice	junto	com	o	valor	a	add,	no	hashmap	não	é	
usado	e	sim	o	put(indice,valor)	para	poder	alocar,	e	o	uso	do	constains	é	diferenciado	pois	pode-
se	buscar	tanto	por	chave	usando	a	containsKey	quanto	por	valor	containsValue.Por	este	motivo	
o	hashmap	é	democrático	pois	você	pode	criar	as	posições	que	desejar	e	assim	trazer	mais	
agilidade	ao	programa	caso	necessite	
Analise	a	situação	a	seguir:	
import	java.util.HashMap;	
import	java.util.Map;	
public	class	Prj_HashMap		{public	static	void	main(String	args[]){Map<Integer,Integer>	
mapa=new	HashMap<Integer,Integer>();	
mapa.put(1,	100);	
mapa.put(2,	200);		
System.out.println("remover:"+mapa.remove(2));	
System.out.println("contains	por	chave:"+	mapa.get(1));	
System.out.println("contains	por	chave:"+	mapa.containsKey(1));	
System.out.println("contains	por	valor:"+	mapa.containsValue(100));	
for(Integer	aux:	mapa.keySet()	){System.out.println(aux	+	"-"	+	aux.hashCode()	+	"-"+	
mapa.get(aux)	);}					}	}	
Com	base	nessas	informações	e	no	conteúdo	estudado,	analise	as	afirmativas	a	seguir	e	
identifique	qual	dela(s)	corresponde(m)	ao	padrão	iterator	na	navegação	da	estrutura	Mapa.	
I.	Integer	aux:	mapa.keySet()	
II.	new	HashMap<Integer,Integer>();.	
III.	mapa.	
IV.	mapa.get(aux).	
V.	mapa.getClass().	
Está	correto	apenas	o	que	se	afirma	em:	
Hide	answer	choices		
1. IV	e	II.	
2. II	e	I.	
3. V	e	III.	
4. III	e	IV.	
5. I	e	IV.	
Correct	answer	
9. Question	9	
/	1	
A	estrutura	hash	possui	um	dos	melhores	desempenhos	dentro	de	uma	grande	estrutura	de	
dados,	pois	sua	notação	de	big	O(1)	é	uma	constante.	Ou	seja,	para	N	dados,	temos	apenas	um	
conjunto	de	instruções	a	se	buscar.	Porém,	com	a	grande	quantidade	de	dados,	surge	o	problema	
da	colisão,	quando	dados	diferentes	assumem	o	mesmo	valor	de	hash.	Existem	formas	de	
trabalhar	o	hashing	para	que	isso	não	ocorra,	porém,	é	preciso	usar	uma	outra	estrutura	de	
dados	para	poder	considerar	um	hash	repetido	de	dados	distintos.	Uma	das	estruturas	possíveis	
é	a	linkedlist,	que	faz	a	alocação	do	dado	repetido	ou	aproximado	dentro	de	um	mesmo	hash.	
Com	base	nessas	informações	e	no	conteúdo	estudado,	podemos	dizer	que	a	técnica	utilizada	
para	a	colisão	é:	
Hide	answer	choices		
1. o	encadeamento	separado.	
Correct	answer	
2. o	rerash.	
3. o	load	factor.	
4. o	new	LinkedList.	
5. o	linear	probing.	
10. Question	10	
/	1	
A	pilha	é	uma	estrutura	de	dados	homogênea,	que	se	comporta	mais	ou	menos	da	mesma	forma	
que	uma	pilha	do	mundo	real,	tendo	seus	dados	organizados	na	estrutura	LIFO	(Last	in	First	
Out).	
Uma	das	aplicações	das	pilhas	é	no	algoritmo	de	busca	de	grafos,	no	DFS	que	busca	por	
profundidade,	onde	sua	busca	aplica-se	em	receber	um	vértice	e	retornar	todos	os	caminhos	
atrelados	a	partir	dele.	
Analise	a	situação	a	seguir:	
public	void	buscaDFS(Grafo_MA	adj)	{	/*Grafo_MA	adj	é	matriz	de	
adjacência*/this.resetar(adj);Stack<Vertice>	pilha	=	new	Stack<>();	
adj.getNo(0).setVisitado(true);	
pilha.add(adj.getNo(0));	
System.out.print(adj.getNo(0).getNome());	
while	(!pilha.isEmpty())	{/*chamada	da	função	getIDVizinhos	com	argumentos	de	matriz	de	
adjacência	e	o	índice	do	topo	da	pilha*/	
DECLARAÇÃO	IDVIZINHOif	(idVizinho	==	-1)	{pilha.pop();}	else	
{adj.getNo(idVizinho).setVisitado(true);pilha.push(adj.getNo(idVizinho));System.out.print(","	+	
adj.getNo(idVizinho).getNome());	
}}}	
Com	base	nessas	informações	e	no	conteúdo	estudado,	o	código	que	corresponde	à	declaração	
de	idVizinho	no	DFS	é:	
Hide	answer	choices		
1. int	idVizinho	=	this.getVertices	(adj,pilha.peek	().getIndice	());	
2. int	Vizinho	=	this.getIDVizinhos	(0,	pilha.peek	().getIndice	());	
3. int	idVizinho	=	this.getIDVizinhos	(pilha.peek	().getIndice	(),pilha.peek	
().getIndice	());	
4. int	idVizinho	=	this.getIDVizinhos	(adj,	pilha.peek	().getIndice	());	
Correct	answer	
5. int	idVizinho	=	this.getVertices	(pilha.peek	().getIndice	(),	pilha.peek	().getIndice	
());