Estudos Disciplinares XIV Questionário Unidade I

Prévia do material em texto

· Pergunta 1
0,5 em 0,5 pontos
	
	
	
	Um programador deve propor um algoritmo para determinar o resultado de uma eleição. Sabe-se que o número n de eleitores é tão grande que o armazenamento do vetor de eleitores em memória, ou em arquivo, torna-se inviável. O número de candidatos, no pior caso, pode ser igual ao de eleitores. Além disso, as cédulas de eleição podem ser reinseridas no sistema de contagem tantas vezes quantas forem necessárias. Nessa eleição, o candidato somente será eleito por maioria absoluta e cada eleitor votará uma única vez. Caso não exista um candidato eleito, a eleição será anulada. Apenas duas variáveis inteiras devem ser utilizadas no algoritmo para determinar o resultado da eleição: uma para armazenamento do número do candidato vitorioso e a outra, a critério do programador. O algoritmo ótimo para a solução desse problema tem complexidade:
	
	
	
	
		Resposta Selecionada:
	c. 
O(n).
	Respostas:
	a. 
O(1).
	
	b. 
O(log n).
	
	c. 
O(n).
	
	d. 
O(n log n).
	
	e. 
O(n2).
	Comentário da resposta:
	Resposta: C
Comentário:
A – Alternativa incorreta. JUSTIFICATIVA. A função f(n)=O(1) refere-se a algoritmos de complexidade constante, nos quais o uso do algoritmo independe do tamanho de n. As instruções do algoritmo são executadas em um número fixo de vezes. A questão indica que as células de eleição podem ser reinseridas no sistema de contagem tantas vezes quantas forem necessárias, portanto, poderá ocorrer um número indeterminado de execuções.
B – Alternativa incorreta. JUSTIFICATIVA. A função f(n)=O(log n) refere-se a algoritmos de complexidade logarítmica, nos quais o tempo de execução ocorre em algoritmos que resolvem um problema transformando-o em problemas menores, o que não é o caso da questão.
C – Alternativa correta.
JUSTIFICATIVA. A função f(n)=O(n) refere-se a algoritmos de complexidade linear, nos quais, em geral, os elementos de entrada recebem algum tipo de tratamento. Essa é a melhor situação possível para um algoritmo que deve processar n elementos de entrada (número de votos) ou produzir n elementos de saída (número de candidatos eleitos).
D – Alternativa incorreta. JUSTIFICATIVA. A função f(n)=O(n log n) refere-se a algoritmos que dividem o problema em problemas menores, porém juntando, posteriormente, a solução dos problemas menores.
E – Alternativa incorreta. JUSTIFICATIVA. A função f(n)=O(n²) refere-se a algoritmos de complexidade quadrática, que ocorrem quando os itens de dados são processados aos pares, geralmente um loop dentro do outro.
	
	
	
· Pergunta 2
0,5 em 0,5 pontos
	
	
	
	Seja A um conjunto e seja ~ uma relação entre pares de elementos de A. Diz-se que ~ é uma relação de equivalência entre pares de elementos de A se as seguintes propriedades são verificadas, para quaisquer elementos a, a’ e a”
de A:
(i) a ~ a;
(ii) se a ~ a’, então a’ ~ a;
(iii) se a ~ a’ e a’ ~ a’’, então a ~ a’’.
Uma classe de equivalência do elemento a de A com respeito à relação ~ é o conjunto:
O conjunto quociente de A pela relação de equivalência ~ é o conjunto de todas as classes de equivalência relativamente à relação ~, definido e denotado como a seguir:
A função  é chamada projeção canônica e é definida como:
Considerando as definições acima, avalie as afirmativas a seguir.
I - A relação de equivalência ~ no conjunto A particiona o conjunto A em subconjuntos disjuntos: as classes de equivalência.
II - A união das classes de equivalência da relação de equivalência ~ no conjunto A resulta no conjunto das partes de A.
III -  As três relações seguintes
 
são relações de equivalência no conjunto dos números inteiros Ζ.
IV - Qualquer relação de equivalência no conjunto A é proveniente de sua projeção canônica.
É correto apenas o que se afirma em:
	
	
	
	
		Resposta Selecionada:
	d. 
I e IV.
	Respostas:
	a. 
II.
	
	b. 
III.
	
	c. 
I e III.
	
	d. 
I e IV.
	
	e. 
II e IV.
	Comentário da resposta:
	Resposta: D
Comentário:
I – Afirmativa correta.
JUSTIFICATIVA. Uma relação de equivalência ~ entre pares de elementos de um conjunto A divide (particiona) o conjunto A em subconjuntos mutuamente exclusivos (disjuntos) em suas classes de equivalência.
II – Afirmativa incorreta. JUSTIFICATIVA. A união das classes de equivalência da relação de equivalência ~ no conjunto A não resulta no conjunto das partes de A. O conjunto das partes de A é a coleção de todos os subconjuntos de A.
III – Afirmativa incorreta JUSTIFICATIVA. A relação de equivalência deve satisfazer às propriedades de reflexividade, simetria e transitividade. A relação  não é uma relação de equivalência em Z, pois não é simétrica: por exemplo, 2  1, mas 1 não é  2.
IV – Afirmativa correta. JUSTIFICATIVA. Como , para cada elemento , podemos associar um elemento de , pois existe uma função de  e suas classes de equivalência são consideradas projeções canônicas.
	
	
	
· Pergunta 3
0,5 em 0,5 pontos
	
	
	
	O problema P versus NP é um problema ainda não resolvido e um dos mais estudados em computação. Em linhas gerais, deseja-se saber se todo problema cuja solução pode ser eficientemente verificada por um computador, também pode ser eficientemente obtida por um computador. Por “eficientemente” ou “eficiente” significa “em tempo polinomial”. A classe dos problemas cujas soluções podem ser eficientemente obtidas por um computador é chamada de classe P. Os algoritmos que solucionam os problemas dessa classe têm complexidade de pior caso polinomial no tamanho das suas entradas. Para alguns problemas computacionais, não se conhece solução eficiente, isto é, não se conhece algoritmo eficiente
para resolvê-los. No entanto, se para uma dada solução de um problema é possível verificá-la eficientemente, então o problema é dito estar em NP. Dessa forma, a classe de problemas para os quais suas soluções podem ser eficientemente verificadas é chamada de classe NP. Um problema é dito ser NP-completo se pertence à classe NP e, além disso, se qualquer outro problema na classe NP pode ser eficientemente transformado nesse problema. Essa transformação eficiente envolve as entradas e saídas dos problemas. Considerando as noções de complexidade computacional apresentadas, avalie as afirmativas a seguir.
I. Existem problemas na classe P que não estão na classe NP.
II. Se o problema A pode ser eficientemente transformado no problema B e B está na classe P, então A está na classe P.
III. Se P = NP, então um problema NP-completo pode ser solucionado eficientemente.
IV. Se P é diferente de NP, então existem problemas na classe P que são NP-completos.
É correto apenas o que se afirma em:
	
	
	
	
		Resposta Selecionada:
	d. 
II e III.
	Respostas:
	a. 
I.
	
	b. 
IV.
	
	c. 
I e III.
	
	d. 
II e III.
	
	e. 
II e IV.
	Comentário da resposta:
	Resposta: D
Comentário:
I – Afirmativa incorreta. JUSTIFICATIVA. Problemas na classe P também podem ser verificados em tempo polinomial, e, portanto, também estão na classe NP.
 
II – Afirmativa correta. JUSTIFICATIVA. Se soubermos resolver o problema B de forma eficiente, e tivermos um algoritmo eficiente capaz de transformar o problema A no problema B, então temos uma forma eficiente de resolver o problema A. Basta aplicarmos o algoritmo de conversão de A para B. Dessa forma, podemos dizer que ambos os problemas pertencem à mesma classe.
 
III – Afirmativa correta.
JUSTIFICATIVA. Dizer que P=NP significa dizer que todos os problemas na classe NP podem ser resolvidos por um algoritmo polinomial, que é muito mais rápido do que um algoritmo exponencial. Teoricamente, isso significa que esses problemas podem ser resolvidos de forma eficiente. Contudo, devemos ter em mente que, se trabalharmos com polinômios de ordem elevada, podemos ter um tempo de execução potencialmente elevado. De qualquer forma, o crescimento de uma função polinomial é bem menor do que de uma função exponencial.
 
IV – Afirmativa incorreta. JUSTIFICATIVA. Se considerarmos que P≠NP (o que ainda não foi provado, mas pode ser adotado como uma suposição), um problema NP-completo certamente não poderia pertencerà classe P.
	
	
	
· Pergunta 4
0,5 em 0,5 pontos
	
	
	
	Um processo tem um ou mais fluxos de execução, normalmente denominados apenas threads.
TANENBAUM, A.D. Sistemas operacionais modernos. 3. ed. São Paulo: Pearson Prentice Hall. 2010 (com adaptações).
 
A partir das figuras 1 e 2 apresentadas, avalie as afirmativas a seguir.
I - Tanto na figura 1 quanto na figura 2, existem três threads que utilizam o mesmo espaço de endereçamento.
II - Tanto na figura 1 quanto na figura 2, existem três threads que utilizam três espaços de endereçamentos distintos.
III - Na figura 2, existe um processo com um único espaço de endereçamento e três threads de controle.
IV - Na figura 1, existem três processos tradicionais, cada qual tem seu espaço de endereçamento e uma única thread de controle.
V - As threads permitem que várias execuções ocorram no mesmo ambiente de processo de forma paralela umas às outras.
É correto apenas o que se afirma em:
	
	
	
	
		Resposta Selecionada:
	e. 
III, IV e V.
	Respostas:
	a. 
I, II e III.
	
	b. 
I, II e IV.
	
	c. 
I, III e V.
	
	d. 
II, IV e V.
	
	e. 
III, IV e V.
	Comentário da resposta:
	Resposta: E
Comentário:
I – Afirmativa incorreta. JUSTIFICATIVA. Na figura I, temos três threads e três processos. Cada thread pertence a um dos respectivos processos. Como processos separados não compartilham memória (pelo menos não normalmente, na maioria dos sistemas operacionais modernos e em condições de execução padrão), não podemos afirmar que as threads utilizam o mesmo espaço de endereçamento.
II – Afirmativa incorreta. JUSTIFICATIVA. Na figura II, temos apenas um processo com três threads. Como essas três threads pertencem ao mesmo processo, elas compartilham o mesmo espaço de endereçamento.
III – Afirmativa correta.
JUSTIFICATIVA. Quando temos threads de um mesmo processo, elas compartilham o mesmo espaço de endereçamento, como indicado na figura II, na qual as threads estão desenhadas no mesmo círculo (que representa um único processo).
IV – Afirmativa correta.
JUSTIFICATIVA. Na maioria dos sistemas operacionais modernos, cada processo tem pelo menos uma thread associada. Novas threads podem ser disparadas pelo processo, se necessário. De forma similar, um processo também pode criar outros novos processos. Cada processo tem o seu próprio espaço de endereçamento, que é utilizado pela(s) thread(s) do respectivo processo.
V – Afirmativa correta.
JUSTIFICATIVA. Tanto threads quanto processos permitem que o sistema operacional execute operações em paralelo ou que, pelo menos, simule essa execução, no caso de máquinas com apenas um processador e um núcleo. Contudo, threads que executam dentro de um mesmo processo podem facilmente compartilhar dados, pois todas existem no mesmo espaço de endereçamento e podem compartilhar o acesso às suas variáveis, por exemplo.
	
	
	
· Pergunta 5
0,5 em 0,5 pontos
	
	
	
	Considere o arranjo computacional apresentado a seguir.
A característica fundamental esperada para tais sistemas de modo a ter o menor impacto sobre a experiência do usuário final é:
	
	
	
	
		Resposta Selecionada:
	a. 
A transparência entre as entidades do sistema.
	Respostas:
	a. 
A transparência entre as entidades do sistema.
	
	b. 
A linguagem de programação orientada a eventos.
	
	c. 
O hardware com elevada taxa de processamento de dados.
	
	d. 
A base de dados deve estar localizada no mesmo espaço fixo.
	
	e. 
A independência quanto à disponibilidade de conexão à rede de comunicação de dados.
	Comentário da resposta:
	Resposta: A
Comentário:
A – Alternativa correta.
JUSTIFICATIVA. Em um sistema distribuído, no qual diferentes aplicações e bases de dados comunicam-se de forma complexa, é importante que existam interfaces bem definidas entre as diversas entidades do sistema. Além disso, essas interfaces precisam ser transparentes, ou seja, devem permitir que as entidades se comuniquem sem expor a implementação interna. Dessa forma, a realização de alterações internas nessas entidades, como a correção de defeitos ou a execução de melhorias, não afetam a interface de acesso e fazem com que as aplicações que dependam dessas entidades continuem funcionando normalmente.
B – Alternativa incorreta.
JUSTIFICATIVA. Ainda que o uso de uma linguagem orientada a eventos seja útil na construção desse tipo de sistema, sua simples utilização não garante que o usuário final tenha a experiência adequada.
 C – Alternativa incorreta.
JUSTIFICATIVA. Uma vez que as aplicações rodem em um sistema distribuído e se comuniquem por meio de uma rede pública, provavelmente há um ambiente bastante heterogêneo com relação ao hardware utilizado. Ainda há a influência da velocidade da rede pública, que está fora do controle da aplicação.
D – Alternativa incorreta.
JUSTIFICATIVA. A base de dados não precisa estar fisicamente próxima do local em que as aplicações são executadas, uma vez que elas podem ser acessadas remotamente pela rede.
E – Alternativa incorreta.
JUSTIFICATIVA. Um sistema distribuído, como o apresentado na figura do enunciado, certamente depende do acesso à rede para o seu funcionamento, uma vez que as aplicações rodam em diferentes máquinas e em diferentes locais (mas acessíveis pela rede pública).
	
	
	
· Pergunta 6
0,5 em 0,5 pontos
	
	
	
	Suponha que, para armazenar exatamente 999999 chaves de um índice, um profissional da área da computação tenha escolhido a estrutura de uma árvore B, de grau mínimo 5, com todos os nós completos. Nessa situação, a profundidade dessa árvore é igual a:
	
	
	
	
		Resposta Selecionada:
	b. 
5.
	Respostas:
	a. 
4.
	
	b. 
5.
	
	c. 
6.
	
	d. 
7.
	
	e. 
8.
	Comentário da resposta:
	Resposta: B
Comentário: Para uma árvore B de grau mínimo 5, temos no máximo 10 chaves por nó. O número de registros por nó é de 10-1=9 registros. Com base nessas informações, construímos a figura 1 a seguir.
Figura. Exemplo de árvore B.
No nível zero dessa árvore (a raiz), temos um nó com 9 registros e 10 chaves. No primeiro nível, temos, para cada uma das chaves, 9 registros e 10 chaves, com um total de 100 chaves e 90 registros. No segundo nível, temos 100 nós e 900 registros. No terceiro nível, temos 1000 nós e 9000 registros. No quarto nível, temos 10000 nós e 90000 registros. No quinto nível, temos 100000 nós e 900000 registros. Somando o total de registros, obtemos o valor 999999, que é o total indicado no enunciado. Logo, essa árvore apresenta profundidade 5.
	
	
	
· Pergunta 7
0,5 em 0,5 pontos
	
	
	
	Leia o texto a seguir.
Uma árvore AVL é um tipo de árvore binária balanceada na qual a diferença entre as alturas de suas subárvores da esquerda e da direita não pode ser maior do que 1 para qualquer nó. Após a inserção de um nó em uma AVL, a raiz da subárvore de nível mais baixo no qual o novo nó foi inserido é marcada. Se a altura de seus filhos diferir em mais de uma unidade, é realizada uma rotação simples ou uma rotação dupla para igualar suas alturas.
LAFORE, R. Data strutures & algorithms in Java. Indianapolis: Sams Publishing, 2003 (com adaptações).
A seguir, é apresentado um exemplo de árvore AVL.
Pelo exposto no texto acima, após a inserção de um nó com valor 3 na árvore AVL exemplificada, ela ficará com a seguinte configuração:
	
	
	
	
		Resposta Selecionada:
	a. 
	Respostas:
	a. 
	
	b. 
	
	c. 
	
	d. 
	
	e. 
	Comentário da resposta:
	Resposta: A
Comentário:
Figura. Árvore após inserção do valor 3. Ao lado das circunferências, anotamos as alturas dos nós. Enade, 2017.
 
A – Alternativa correta.
JUSTIFICATIVA. Observamos que a árvore do enunciado está desbalanceada no nó que contém o valor 10. Logo, devemos fazer uma rotação para balancearmos a árvore. Executando uma rotação simples à direita, obtemos a árvore ilustrada na alternativa.
B – Alternativa incorreta.
JUSTIFICATIVA. Essa árvore corresponde simplesmente à árvore após a inserção do valor 3, sem nenhum procedimento de balanceamento. Portanto, não se trata de uma árvore AVL.
C e E – Alternativas incorretas.
JUSTIFICATIVA. As árvores estão incorretas,pois o valor 15 encontra-se do lado errado do nó com o valor 13 (como ele é “maior”, deveria estar no lado direito). Nesses casos, as árvores mostradas não são árvores binárias de busca e, muito menos, árvores do tipo AVL.
D – Alternativa incorreta. JUSTIFICATIVA. Ainda que a árvore obtida esteja balanceada, a rotação não foi feita no nó correto, uma vez que ela deve ser executada no primeiro nó em que ocorre o desbalanceamento: no caso, trata-se do nó que contém o valor 10 (considerando como referência a figura mostrada acima).
	
	
	
· Pergunta 8
0,5 em 0,5 pontos
	
	
	
	Ao longo de todo o desenvolvimento do software, devem ser aplicadas atividades de garantia e qualidade de software (GQS), entre as quais se encontra a atividade de teste. Um dos critérios de teste utilizados para gerar casos de teste é o denominado critério dos caminhos básicos, cujo número de caminhos pode ser determinado com base na complexidade ciclomática. Considerando-se o grafo de fluxo de controle apresentado na figura a seguir, no qual os nós representam os blocos de comandos e as arestas representam a transferência de controle, qual a quantidade de caminhos básicos que devem ser testados no programa associado a esse grafo de fluxo de controle, sabendo-se que essa quantidade é igual à complexidade ciclomática mais um?
 
	
	
	
	
		Resposta Selecionada:
	c. 
4.
	Respostas:
	a. 
1.
	
	b. 
3.
	
	c. 
4.
	
	d. 
7.
	
	e. 
8.
	Comentário da resposta:
	Resposta: C
Comentário:
Vimos que o número ciclomático V(G) de um grafo é dado por:
 
V(G) = E – N + P
 
Um componente de um grafo é um conjunto de nodos conectados. Nesse caso, todo grafo de programa terá número de componentes P igual a 1 (P = 1), pois os nodos não conectados correspondem a comandos que nunca serão executados.
Da figura do enunciado, o número de arestas E vale 9 e o número N de nodos vale 7- . Logo: V(G) = 9 – 7 + 1 = 3
O método dos caminhos básicos de McCabe acrescenta que, quando os grafos de um programa não forem fortemente conexos, é necessário adicionar uma aresta conectando o último nodo ao primeiro. Ou seja, para se obter o resultado correto da questão, deve-se somar 1 ao cálculo V(G). Como V(G) = 3, o resultado será 3 + 1 = 4.
	
	
	
· Pergunta 9
0,5 em 0,5 pontos
	
	
	
	Considere a relação EMPREGADO (NumeroEmp, RG, nome, sobrenome, salario, endereço), em que o atributo grifado corresponde à chave primária da relação. Suponha que se deseje realizar as seguintes consultas:
1- Listar o nome dos empregados com sobrenome Silva;
2- Listar o nome dos empregados em ordem crescente de seus sobrenomes.
Em relação à definição de um índice sobre o atributo sobrenome para melhorar o desempenho das consultas acima, julgue os itens a seguir.
I - Um índice que implemente Árvore-B+ será adequado para melhorar o desempenho da consulta 1.
II - Um índice que implemente Árvore-B+ será adequado para melhorar o desempenho da consulta 2.
III - Um índice que implemente uma função hash será adequado para melhorar o desempenho da consulta 1.
IV - Um índice que implemente uma função hash será adequado para melhorar o desempenho da consulta 2.
Assinale a opção correta.
	
	
	
	
		Resposta Selecionada:
	d. 
Apenas os itens I, II e III estão corretos.
	Respostas:
	a. 
Apenas um item está correto.
	
	b. 
Apenas os itens I e II estão corretos.
	
	c. 
Apenas os itens III e IV estão corretos.
	
	d. 
Apenas os itens I, II e III estão corretos.
	
	e. 
Todos os itens estão corretos.
	Comentário da resposta:
	Resposta: D
Comentário:
I – Afirmativa correta.
JUSTIFICATIVA. A consulta utiliza um filtro de igualdade e as Árvores-B são indicadas para esse tipo de consulta, conforme mostramos a seguir.
 SELECT  Nome
 FROM   Empregado
 WHERE  Sobrenome = ‘Silva’;
II – Afirmativa correta.
JUSTIFICATIVA. A consulta utiliza um filtro de ordenação e as Árvores-B são indicadas para esse tipo de consulta, conforme mostramos a seguir.
 SELECT  Nome
 FROM   Empregado
 ORDER BY  Sobrenome  ASC;
III – Afirmativa correta.
JUSTIFICATIVA. A consulta utiliza um filtro de igualdade e as funções hash são indicadas para esse tipo de consulta.
IV – Afirmativa incorreta.
JUSTIFICATIVA. A consulta utiliza um filtro de ordenação e as funções hash não são indicadas para esse tipo de consulta.
	
	
	
· Pergunta 10
0,5 em 0,5 pontos
	
	
	
	Uma empresa, no Brasil, recebeu o número IP 204.145.121.0 para endereçar sua rede, respeitando a RFC 1812. Nessa configuração de endereço base,
	
	
	
	
		Resposta Selecionada:
	e. 
se for necessário dividir a rede em oito sub-redes, então o endereço da máscara de rede será 255.255.255.224.
	Respostas:
	a. 
o endereço de broadcast é 204.145.121.1.
	
	b. 
o endereço recebido pertence à classe B.
	
	c. 
o número máximo de hosts endereçáveis é 256.
	
	d. 
se for necessário dividir a rede em quatro sub-redes, então o número máximo de hosts endereçáveis é 254.
	
	e. 
se for necessário dividir a rede em oito sub-redes, então o endereço da máscara de rede será 255.255.255.224.
	Comentário da resposta:
	Resposta: E
Comentário:
A – Alternativa incorreta.
JUSTIFICATIVA. O IP 204.145.121.1 corresponde ao primeiro IP válido normalmente utilizado para gateway. No caso do RFC 1812, o broadcast seria representado pelo IP 204.145.121.255.
B – Alternativa incorreta.
JUSTIFICATIVA. O endereço recebido pertence à classe C, pois encontra-se na faixa de IP compreendida entre 192.0.0.0 a 223.255.255.0
C – Alternativa incorreta.
JUSTIFICATIVA. O número máximo de hosts endereçáveis é 254, pois existem dois valores reservados.
D – Alternativa incorreta.
 JUSTIFICATIVA. Para quatro sub-redes, o número máximo de hosts endereçáveis é 62, conforme mostrado no quadro a seguir.
E – Alternativa correta.
JUSTIFICATIVA. Para oito sub-redes, o número máximo de hosts endereçáveis será 224, conforme mostrado no quadro a seguir. 
	
	
	
image1.gif
image2.gif