CienciaComputacao_Enade

Prévia do material em texto

eBOOK: QUESTÕES DO ENADE COMENTADAS 
 
 
 
Curso: 
CIÊNCIAS DA COMPUTAÇÃO 
 
 
Organizador(es): Sibelius Lellis Vieira 
 
 
 
SUMÁRIO 
QUESTÃO DISCURSIVA Nº 3 
Autor(a): Anibal Jukemura 
QUESTÃO DISCURSIVA Nº 4 
Autor(a): Joriver Canedo e Sibelius Lellis Vieira 
QUESTÃO DISCURSIVA Nº 5 
Autor(a): Sibelius Lellis Vieira 
QUESTÃO Nº 9 
Autor(a): André Luiz Alves e Sibelius Lellis Vieira 
QUESTÃO Nº 10 
Autor(a): André Luiz Alves e Sibelius Lellis Vieira 
QUESTÃO Nº 11 
Autor(a): Sibelius Lellis Vieira 
QUESTÃO Nº 12 
Autor(a): Sibelius Lellis Vieira 
QUESTÃO Nº 13 
Autor(a): Cármen Cecília Centeno 
QUESTÃO Nº 14 
Autor(a): Sibelius Lellis Vieira 
QUESTÃO Nº 15 
Autor(a): Cármen Cecília Centeno 
QUESTÃO Nº 16 
Autor(a): Sibelius Lellis Vieira 
QUESTÃO Nº 17 
Autor(a): André Luiz Alves, Ronaldo Lopes de Oliveira e Sibelius Lellis Vieira 
QUESTÃO Nº 18 
Autor(a): Sibelius Lellis Vieira 
QUESTÃO Nº 19 
Autor(a): Fábio Gomes Barbosa 
QUESTÃO Nº 20 
Autor(a): Sibelius Lellis Vieira 
QUESTÃO Nº 21 
Autor(a): Sibelius Lellis Vieira 
QUESTÃO Nº 22 
Autor(a): Cármen Cecília Centeno 
QUESTÃO Nº 23 
Autor(a): Sibelius Lellis Vieira 
QUESTÃO Nº 24 
Autor(a): André Luiz Alves e Ronaldo Lopes de Oliveira 
QUESTÃO Nº 25 
Autor(a): Cármen Cecília Centeno 
QUESTÃO Nº 26 
Autor(a): Sibelius Lellis Vieira 
QUESTÃO Nº 27 
Autor(a): Cármen Cecília Centeno e Sibelius Lellis Vieira 
QUESTÃO Nº 28 
Autor(a): Anibal Jukemura e Sibelius Lellis Vieira 
QUESTÃO Nº 29 
Autor(a): Cármen Cecília Centeno e Sibelius Lellis Vieira 
QUESTÃO Nº 30 
Autor(a): Cármen Cecília Centeno e Sibelius Lellis Vieira 
QUESTÃO Nº 31 
Autor(a): Sibelius Lellis Vieira 
QUESTÃO Nº 32 
Autor(a): Cármen Cecília Centeno 
QUESTÃO Nº 33 
Autor(a): Sibelius Lellis Vieira 
QUESTÃO Nº 34 
Autor(a): Sibelius Lellis Vieira 
QUESTÃO Nº 35 
Autor(a): Wilmar Oliveira de Queiroz 
QUESTÃO DISCURSIVA Nº 3 
O jogo Sudoku consiste em uma matriz 9x9 dividida em 9 sub-matrizes 3x3, como mostrado 
na figura a seguir. 
 
 
 
 
 
 
 
 
 
 
 
 
 
Disponível em <http://www.en-wikipedia.org>. Acesso em 26 jul 2014 (adaptado). 
A matriz está parcialmente preenchida com números de 1 a 9, e o objetivo do jogo é 
completar a matriz, de forma que cada linha, coluna e sub-matriz contenham todos os 
números de 1 a o. 
A partir dessas informações, escreva um algoritmo recursivo baseado em retrocesso 
(backtracking) para resolver o jogo. A matriz fio transformada em um vetor V de 81 posições, 
contendo zeros nas posições que faltam para serem preenchidas. 
Considere que existem duas funções implementadas. A primeira função, NaoHaViolacao (x, i, 
V), retorna verdadeiro se a inserção do número x na posição i do vetor V não causa violação 
das restrições do jogo (número repetido em linha, coluna ou sub-matriz). A segunda função, 
Imprime (V) , realiza a impressão do vetor V. 
Considere, ainda, que o algoritmo deve imprimir o vetor V com a solução encontrada, se esta 
existir. (valor: 10,0 pontos) 
 
 
Conteúdo avaliado: Algoritmos 
 
Autor: Anibal Jukemura 
 
 
Comentário: 
 
Foi usada uma notação em português estruturado, de forma imperativa. 
1 Sudoku (i,V) 
2 Se i > 81 então Imprime(V) e termine; /* solução encontrada */ 
3 Senão se V[i]=0 então /* posição a preencher */ 
4 Repita para x=1 até 9 
5 Se NaoHaViolacao(x,i,V) então /* registra e avança */ 
6 V[i]=x 
7 Sudoku(i+1,V) 
8 Fim se 
9 Fim repita 
10 V[i]=0 /* apaga solução anterior */ 
11 Senão Sudoku(i+1,V) /* pula posição já preenchida */ 
12 Fim 
 
A análise do algoritmo Sudoku(i,V) segue da seguinte forma: 
 
O algoritmo faz a análise da matriz como sendo um vetor. Considere i o índice 
(posição) do número a ser avaliado começando em 1. Como é uma matriz 9x9, temos 
81 posições. Na linha 2 o vetor será impresso quando todas as 81 posições forem 
avaliadas e calculadas (preenchidas). Caso contrário, o algoritmo verifica se a 
posição corrente em i deve ser preenchida (V[i]=0, na linha 2). Se não for o caso, o 
algoritmo continua na linha 11 e pula-se a posição já preenchida chamando a função 
Sudoku na posição i+1 (próxima posição). 
 
As linhas 4-9 tratam o caso do preenchimento da posição corrente (V[i]=0) testando 
todos os nove valores de x (1 a 9) para cada posição a ser preenchida (lembre-se: 
certamente um destes valores podem ser utilizados na posição corrente). A 
verificação da posição i, neste caso, inicia-se com a função NaoHaViolacao(x,i,V) 
que, se retornar "VERDADEIRO", o valor corrente de x poderá ser inserido na posição 
e o algoritmo continua na próxima posição (chamada recursiva na linha 7). 
 
Repare que, se não há preenchimento para os nove valores de x na posição corrente, 
ou seja, a função NaoHaViolacao(x,i,V) retorna "FALSO" para posição corrente i, o 
algoritmo segue na linha 10 e apaga a solução anterior aplicada "voltando" na 
aplicação recursiva daquele valor, desde a primeira chamada. 
 
Para ilustrar o funcionamento do algoritmo, neste exemplo, se aplicarmos o algoritmo, 
a primeira tentativa será preencher os espaços vazios da primeira linha com os 
valores 1,2,4,8,9. Quando o algoritmo tenta preencher a posição 9 da primeira linha, a 
função NaoHaViolacao(x,i,V) retornará FALSO para todos os valores tentados de x. 
Assim, o algoritmo vai à linha 10 e todo um processo de retorno das chamadas 
recursivas vão executando a linha 10 e apagando a solução até então tentada. Ao 
retornar das chamadas recursivas, a linha 4 é executada novamente, agora com uma 
nova tentativa para o valor de x e o processo é reiniciado. 
 
 
QUESTÃO DISCURSIVA Nº 4 
Muitas aplicações utilizam o sistema de localização (GPS) do dispositivo móvel do usuário para 
descobrir qual o melhor caminho a seguir. Algumas aplicações também permitem que o 
usuário notifique a ocorrência de eventos que ele presencia durante seu percurso, tais como 
acidentes ou trânsito lento. Em um possível cenário, esta notificação é enviada para um 
servidor centralizado, o qual é responsável por disseminar a notificação para os demais 
usuários do aplicativo. Uma equipe de desenvolvimento criou uma aplicação desse tipo 
utilizando uma base de dados relacional para o armazenamento de dados referentes aos 
usuários, eventos e notificações enviadas. A modelagem conceitual foi feita utilizando o 
diagrama entidade-relacionamento conforme apresentado na figura a seguir. 
 
A equipe de desenvolvimento deseja adicionar as seguintes características ao modelo: 
• Cada notificação deve ter data e hora; 
• O grupo de usuários para o qual uma notificação é enviada deve ser restrito. Cada 
usuário deve ter um grupo com um número arbitrário de amigos, que também são 
usuários da aplicação, e as notificações enviadas por um usuário devem ser enviadas 
somente a seus amigos. Também se deseja armazenar informações sobre quais 
notificações foram enviadas para quais usuários. 
Nessa situação, adapte o diagrama ER da figura para atender os novos requisitos. (valor: 10,0 
pontos) 
 
 
 
Conteúdo avaliado: Banco de dados 
 
Autor: Joriver Canedo 
 
Comentário: 
 
1) Forma gráfica: 
 
Diagrama ER abaixo. 
Observação: 
 
 
Nesta representação pode-se substituir o relacionamento amizade pela 
entidade “Grupo” com as consequentes alterações de cardinalidade. 
 
2) Forma escrita: 
��Para a notificação ter data e hora, adicionar o atributo do tipo 
timestamp; 
��Para restringir o acesso da notificação para amigos do Usuário: 
o criar uma relação n para n de Usuário para Usuário chamada 
amizade; ou 
o criar uma entidade “Grupo” com uma relação 1 para n de 
Usuário para grupo. 
��Para guardar as notificações enviadas para cada usuário, criar uma 
relação n para n entre notificação e Usuário chamada notificações 
enviadas. Neste caso, o relacionamento entre EVENTO e NOTIFICAÇÃOserá 1xN e o 
relacionamento entre NOTIFICAÇÃO e USUÁRIO seria retirado e substituído pelo 
relacionamento ENVIO (NxN). 
 
 
 
QUESTÃO DISCURSIVA Nº 5 
As técnicas de projeto de algoritmos são essenciais para que os desenvolvedores possam 
implementar software de qualidade. Essas técnicas descrevem os princípios que devem ser 
adotados para se projetar soluções algorítmicas para um dado problema. Entre as principais 
técnicas, destacam-se os projetos de algoritmos por tentativa e erro, divisão e conquista, 
programação dinâmica e algoritmos gulosos. 
Nesse contexto, faça o que se pede nos itens a seguir. 
a) Descreva o que caracteriza o projeto de algoritmos por divisão e conquista. (valor: 6,0 
pontos) 
b) Apresente uma situação de uso da técnica de projeto de algoritmos por divisão e 
conquista. (valor: 4,0 pontos) 
 
 
 
Conteúdo avaliado: Algoritmos e estrutura de dados 
 
Autor: Sibelius Lellis Vieira 
 
Comentário: a) Muitos algoritmos úteis são recursivos em sua estrutura: para resolver 
um dado problema, eles evocam a si mesmo recursivamente uma ou mais vezes para 
lidar com subproblemas correlatos. Tais algoritmos seguem uma abordagem de dividir 
e conquistar: eles quebram ou dividem o problema em vários problemas menores que 
são similares ao problema principal, mas menores em tamanho, e resolvem os 
subproblemas recursivamente, ou seja, quebrando sucessivamente os subproblemas, 
até alcançar um ponto em que o subproblema possa ser solucionado diretamente, e a 
partir das soluções dos menores subproblemas, estas são combinadas até criar uma 
solução completa para o problema original. 
 
O paradigma de dividir e conquistar envolve 3 passos em cada nível da recursão: 
Dividir o problema em um número de subproblemas que são instâncias menores do 
mesmo problema; 
Conquistar os subproblemas via sua solução de forma recursiva. Os subproblemas 
são divididos até que atinjam um tamanho que possibilita a sua solução diretamente, 
sem nova divisão. 
Combinar as soluções dos subproblemas de tal forma a obter a solução do problema 
original. 
 
b) Neste ponto, ilustra-se a utilização prática do uso da técnica de divisão e conquista 
no projeto de algoritmos, em uma situação simples, como por exemplo, os algoritmos 
de ordenação quicksort e mergesort. No caso, será usado o algoritmo mergesort. O 
algoritmo de mergesort segue de forma muito próxima o paradigma de dividir e 
conquistar. Intuitivamente, opera da maneira como se segue: 
 
• Divisão: dividir uma sequência de n elementos que devem ser ordenador em 
duas subsequências, cada uma com n/2 elementos, aproximadamente. 
 
• Conquista: ordenar as duas subsequências, e caso sejam ainda muito 
grandes, dividir novamente as duas, de forma a obter quatro subsequências 
do problema original. Continuar a divisão até atingir subsequências de 
tamanho adequado para uma ordenação direta. 
 
• Combinação: juntar as subsequências para produzir as respostas ordenadas. 
 
A recursão para quando a sequência a ser ordenada tem tamanho 2 ou 1, e aí o 
processo termina e os resultados intermediários são combinados para formar o 
resultado final, ou seja, a sequência ordenada. 
 
 
QUESTÃO Nº 9 
 
A figura a seguir apresenta duas telas de um sistema de venda de passagens aéreas de uma 
empresa. Na tela 1, o usuário selecionou sua origem, seu destino, e, logo em seguida, sua data 
de ida. Ao mudar o foco para o campo de preenchimento da data de retorno, a ferramenta de 
calendário apresentou automaticamente a data do dia da compra (01/09/2014), conforme 
exibido na tela 2. 
 
 
Com base nas telas apresentadas e em dimensões de qualidade, tais como facilidade de 
aprendizagem, prevenção de erros, eficiência, memorização e satisfação subjetiva, avalie as 
afirmações a seguir. 
I. O botão “Ir” apresenta uma metáfora adequada com o mundo real, facilitando a 
aprendizagem. 
II. Na tela 1, o uso do calendário clicável não auxilia na prevenção de erros, visto que 
a entrada de datas pode ser realizada manualmente pelos usuários. 
III. Na tela 2, o fato de o calendário selecionar a data da compra prejudica a eficiência 
da interface, já que a data preenchida é anterior à data de ida. 
IV. A memorização é prejudicada pois a interface apresenta elementos gráficos em 
demasia. 
É correto apenas o que se afirma em 
A. I e II 
B. I e III 
C. II e IV 
D. I, III e IV 
E. II, III e IV 
 
 
 
Gabarito: B 
 
Tipo de questão: Fácil 
 
Conteúdo avaliado: Engenharia de Software e Interação Humano-Computador 
 
Autor(a): André Luiz Alves e Sibelius Lellis Vieira 
 
Comentário: A afirmação I está correta, visto que o botão “Ir” indica uma metáfora 
adequada, pois trata-se de uma situação de prosseguimento de um processo. A 
afirmação II está incorreta, uma vez que o calendário clicável facilita a prevenção de 
erros, uma vez que as entradas não precisam ser efetuadas manualmente. A 
afirmação III está correta, pois a interface da tela 2 pode prejudicar a eficiência da 
interface uma vez que o usuário terá que necessariamente corrigir a data de retorno 
que foi automaticamente preenchida pelo sistema quando a data da ida for maior que 
a data da compra, sob pena de o sistema recusar a transação e ele ter que submetê-
la novamente. A interface não apresenta elementos gráficos além dos necessários, o 
que implica que a afirmação IV está incorreta. 
 
 
Referências: 
 
OLIVEIRA NETTO, A. A. Interação humano computador. Florianópolis: Visual 
Books, 2004. 
 
SHNEIDER, Pen. et al. Designing the user interface: strategies for effective 
human-computer interaction. 5. ed. New York: Addison Wesley, 2009. 
 
 
QUESTÃO Nº 10 
O gerenciamento de um projeto inclui atividades com o objetivo de garantir que todos os 
produtos definidos no seu escopo sejam entregues no prazo estimado. Nesse contexto, avalie 
as afirmações a seguir. 
I. Técnicas como PERT e COM são utilizadas para obtenção de estimativas de esforço e 
como apoio para definição de atividades. 
II. Séries históricas, quando utilizadas para obter estimativas de esforço no 
desenvolvimento de um sistema, levam à obtenção de estimativas consistentes, 
independentemente do domínio de aplicação dos sistemas que deram origem às 
séries históricas. 
III. No caso de atraso da execução do cronograma, a contratação de novos 
desenvolvedores assegura que o produto será entregue de acordo com o cronograma 
inicialmente proposto. 
É correto o que se afirma em 
A. I, apenas 
B. II, apenas 
C. I e III, apenas 
D. II e III, apenas 
E. I, II e III 
 
 
 
 
Gabarito: A 
 
Tipo de questão: Fácil 
 
Conteúdo avaliado: Engenharia de Software e Interação Humano-Computador 
 
Autor(a): André Luiz Alves e Sibelius Lellis Vieira 
 
Comentário: Afirma-se que o gerenciamento de projeto tem o objetivo de garantir que 
os produtos do seu escopo sejam entregues no prazo estimado, e é solicitado que 
sejam avaliadas 3 afirmações: a afirmação I apresenta as técnicas de PERT (Program 
Evaluation and Review Technique) que tem o propósito de avaliar o progresso no 
tempo com base em revisões, e CPM (Critical Path Method) que identifica o caminho 
crítico, ou seja, as atividades que definem o tempo total do projeto como úteis para a 
obtenção dos objetivos do gerenciamento. A afirmação II indica que as séries 
históricas levam à obtenção de estimativas consistentes, independentemente do 
domínio de aplicação que deu origem às series, o que não pode ser afirmado porque 
séries históricas apenas dão uma diretriz e dependem do contexto ou domínio a 
aplicação. A afirmação III diz que, no caso de atraso, a contratação de mais 
empregados por si só assegura que o produto será entregue de acordo com o 
cronograma, ignorando que o atraso pode advir de outras situações. As afirmaçõesII 
e III são muito gerais, podendo não se aplicar a todos os casos, e são, portanto, 
falsas. A única alternativa possível é a letra A, que indica apenas a afirmação I como 
verdadeira. 
 
 
Referências: 
MEREDITH, Jack R. Administração de projetos: uma abordagem gerencial. 4. ed. 
Rio de Janeiro: LTC, 2003. 
CLELAND, David I. Gerenciamento de projetos. 2. ed. Rio de Janeiro: LTC, 2007. 
KERZNER, Harold. Project management: a systems approach to planning, 
scheduling, and controlling, 10. ed. New Jersey: Wiley, 2009. 
 
 
QUESTÃO Nº 11 
Considere um esquema de gerência de memória por paginação simples, onde a memória 
física é dividida em quadros (frames) de 1 Kbyte e endereçada por byte. Os espaços de 
endereçamento dos processos são múltiplo de 1Kbyte. A tabela de página para um 
determinado processo P é apresentado a seguir, em que o primeiro bit (BV) mostra se a 
página é válida (1) ou inválida (0). 
BV Quadro(frame) 
0 1 0010 
1 1 0100 
2 1 0001 
3 1 0111 
4 1 0000 
5 1 1101 
6 0 1111 
7 0 0110 
 
 
Com base na tabela apresentada, avalie as afirmações a seguir. 
I. O endereço físico é composto por 13 bits. 
II. O esquema de gerência de memória apresentado reduz a fragmentação externa. 
III. A tradução do endereço lógico 0110000000110 para endereço físico causa exceção. 
É correto o que se afirma em 
A. I, apenas 
B. II, apenas 
C. I e III, apenas 
D. II e III, apenas 
E. I, II e III 
 
 
 
 
Gabarito: B 
 
Tipo de questão: Difícil 
 
Conteúdo avaliado: Sistemas Operacionais e Arquitetura de Computadores 
 
Autor(a): Sibelius Lellis Vieira 
 
Comentário: Com base na tabela de paginação e na informação que a memória é 
dividida em quadros de 1 Kbyte e endereçada por byte, existem 1024 endereços por 
quadro, sendo necessário 10 bits para indicar o endereço no quadro, portanto 
(210=1024). Portanto, como a tabela de páginas indica que cada quadro é identificado 
por 4 bits, tem-se 14 bits de endereço físico e 13 bits de endereço lógico. 
Logo, a afirmação I é falsa. O esquema apresentado reduz a fragmentação externa, 
vez que qualquer área da memória pode ser usada com paginação, sendo esta uma 
característica da paginação, e implicando que a afirmação II é verdadeira. Para 
encontrar o endereço físico correspondente ao endereço lógico 0110000000110, 
observa-se que tal endereço deve mapear a página 011 (3) para a moldura 0111 (7), 
e o bit é valido, não resultando em exceção. A afirmação III é incorreta, o que 
resultada na alternativa B. 
 
Referências: 
SILBERSCHATZ, A.; GAVIN B. P.; GAGNE G. Fundamentos de sistemas 
operacionais. 8. ed. Rio de Janeiro: Elsevier/Campus, 2013. 
TANENBAUM, Andrew S. Sistemas operacionais modernos. 3. ed. São Paulo: 
Prentice-Hall, 2010. 
 
 
QUESTÃO Nº 12 
 
Analise o custo computacional dos algoritmos a seguir, que calculam o valor de um polinômio 
de grau n, da forma: P(x) = anx
n+an-1 x
n-1+ ... +a1x + a0, onde os coeficientes são números de 
ponto flutuante armazenados no vetor a[0..n], e o valor de n é maior que zero. Todos os 
coeficientes podem assumir qualquer valor, exceto o coeficiente an que é diferente de zero. 
Algoritmo 1: 
soma = a[0] 
Repita para i = 1 até n 
 Se a[i] ≠ 0.0 então 
 potencia = x 
 Repita para j = 2 até i 
 potencia = potência * x 
 Fim repita 
 soma = soma + a[i] * potencia 
 Fim se 
Fim repita 
Imprima (soma) 
 
Algoritmo 2: 
soma = a[n] 
Repita para i = n-1 até 0 passo -1 
 soma = soma * x + a[i] 
Fim repita 
Imprima (soma) 
 
Com base nos algoritmos 1 e 2, avalie as asserções a seguir e a relação proposta entre elas. 
 
I. Os algoritmos possuem a mesma complexidade assintótica. 
PORQUE 
II. Para o melhor caso, ambos os algoritmos possuem complexidade O(n). 
 
A respeito dessas asserções, assinale a opção correta. 
A. As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I. 
B. As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa correta 
da I. 
C. A asserção I é uma proposição verdadeira, e a II é uma proposição falsa. 
D. A asserção I é uma proposição falsa, e a II é uma proposição verdadeira. 
E. As asserções I e II são proposições falsas. 
 
 
 
Gabarito: D 
 
Tipo de questão: Difícil 
 
Conteúdo avaliado: Teoria da Computabiidade e Complexidade 
 
Autor(a): Sibelius Lellis Vieira 
 
Comentário: Observa-se que o algoritmo 1 contêm dois laços, um externo e um 
interno, e o algoritmo 1 apresenta 1 laço. O laço externo do algoritmo 1 e o laço do 
algoritmo 2 tem a mesma complexidade, mas a existência de 2 laços no algoritmo 1 
invalida a asserção I. O algoritmo 1 não necessariamente executa o laço interno, 
sendo que, no melhor caso, não executa o laço interno vez alguma. Portanto, a 
asserção II está correta, e a alternativa D indica esta situação. Pode-se verificar que a 
questão não exige que se verifique detalhadamente se os algoritmos realmente 
calculam o valor do polinômio, apenas que se analise a complexidade dos algoritmos, 
o que se reduz a analisar o possível número de iterações dos mesmos. 
 
 
Referências: 
CORMEN, Thomas H. et al. Algoritmos: teoria e prática. 3. ed. Rio de Janeiro: 
Campus, 2012. 
 
SZWARCFITER, Jayme Luiz, MARKEZAON, Lilian. Estrutura de Dados e seus 
Algoritmos. RJ, Editora LTC. 1994. 
ZIVIANI, Nivio. Projeto de algoritmos com implementações em Java e C++. São 
Paulo: Cengage Learning, 2006. 
 
 
 
QUESTÃO Nº 13 
A figura a seguir apresenta uma árvore binária de pesquisa, que mantém a seguinte 
propriedade fundamental: o valor associado à raiz é sempre menor do que o valor de todos os 
nós da subárvore à direita e sempre maior do que o valor de todos os nós da subávore à 
esquerda. 
 
 
 
 
 
 
 
 
15 
20 
17 25 
10 
13 7 
14 
 
 
Em relação à árvore apresentada na figura, avalie as afirmações a seguir. 
I. A árvore possui a vantagem de realizar a busca de elementos de forma eficiente, 
como a busca binária em um vetor. 
II. A árvore está desbalanceada, pois a subárvore da esquerda possui um número de nós 
maior do que a subárvore da direita. 
III. Quando a árvore é percorrida utilizando o método de caminhamento pós-ordem, os 
valores são encontrados em ordem decrescente. 
IV. O número de comparações realizadas em função do número n de elementos na 
árvore em uma busca binária realizada com sucesso é O(log n). 
 
É correto apenas o que se afirma em 
A. I e III 
B. I e IV 
C. II e III 
D. I, II e IV 
E. II, III e IV 
 
 
 
 
Gabarito: B 
 
Tipo de questão: Difícil 
 
Conteúdo avaliado: Algoritmos e Estrutura de Dados 
 
Autor(a): Cármen Cecília Centeno 
 
Comentário: Inicialmente, pode ser observado que a figura representa uma arvore 
binária completa. Percebemos que todos os seus níveis estão completos, exceto o 
último. Sendo assim, a árvore tem uma altura mínima e com certeza está balanceada, 
o que exclui a afirmação II, logo as letras C, D e E estão incorretas. 
Analisando as alternativas, concluímos que I está correta. A alternativa III está 
incorreta, pois em um percurso de pós ordem se percorre a árvore da esquerda 
depois da direita e a partir daí se imprime a raiz. Logo, o resultado seria 7,14,13,10, 
17,25,20,15. A afirmação IV está correta, pois basta verificar se o valor buscado está 
do lado esquerdo ou direito da árvore, procedendo da mesma forma com as 
subárvores. Desta forma, a busca olha sempre metade, da metade, da metade, ... dos 
nós (idem a busca binária mencionada em I), implicando em um tempo de busca de 
O(log n). 
 
 
Referências: 
 
CORMEN, Thomas H. et al. Algoritmos: teoria e prática. 3. ed. Rio de Janeiro: 
Campus, 2012. 
 
SZWARCFITER, Jayme Luiz, MARKEZAON, Lilian. Estrutura de Dadose seus 
Algoritmos. RJ, Editora LTC. 1994. 
 
 
QUESTÃO Nº 14 
 
Seja o universo U={10,20,30,40} e o conjunto dos números naturais N. com base no 
conhecimento sobre lógica de predicados, avalie as afirmações a seguir. 
I. H = (∀x ∈ N)(∃y ∈ U)(x<y) é válida. 
II. H = (∀x ∈ N)(∃y ∈ N)(y<x) é válida. 
III. H = (∀x ∈ U)(∃y ∈ U)(x>y) é inválida, sendo x=10 um contra-exemplo. 
 
É correto o que se afirma em 
A. I, apenas 
B. III, apenas 
C. I e II, apenas 
D. II e III, apenas 
E. I, II e III 
 
 
 
Gabarito: B 
 
Tipo de questão: Difícil 
 
Conteúdo avaliado: Lógica e Matemática Discreta 
 
Autor(a): Sibelius Lellis Vieira 
 
Comentário: Três afirmações devem ser avaliadas. Normalmente, começar pela que 
apresenta um contra-exemplo pode ser mais adequada, pois o contra-exemplo pode 
ser avaliado sem necessidade de generalização. A afirmativa III indica que para 
qualquer x (elemento) pertencente à U, existe y (também elemento de U) tal que x > y 
é invalido, ou seja, existe x em U tal que não existe um y menor que x e x=10 é este 
contra-exemplo. De fato, a afirmativa III é verdadeira, pois esta afirmação é realmente 
inválida. Diante disto, a análise da afirmativa II pode revelar a resposta correta, pois 
se II for falsa, a resposta correta é B. A afirmativa II é similar à afirmativa III, sendo 
que os elementos avaliados são do conjunto de números naturais. O conjunto de 
números naturais é infinito, tendo como elementos 0, 1, 2, e assim por diante. A 
afirmativa diz que é válida a situação na qual, para qualquer elemento de N, existe um 
elemento menor do que o primeiro. Pode-se observar que para o elemento 0 isto não 
é verdade. Portanto, II é falsa e a resposta é B. Como o conjunto U está contido no 
conjunto N, fica fácil verificar que a afirmação I é falsa, pois é similar à afirmação II, e 
mais restritiva ainda. 
 
 
Referências: 
 
SOUZA, João Nunes da Silva. Lógica para ciência da computação: uma introdução 
concisa. 2. ed. Rio de Janeiro: Elsevier, 2008. 
 
SILVA, Flávio Correa da. Lógica para computação. São Paulo: Thomson Learning, 
2006. 
 
 
QUESTÃO Nº 15 
Considere as seguintes expressões regulares cujo alfabeto é {a,b}. 
 R1 = a(a ∪ b)* 
 R2 = b(a ∪ b)* 
Se L(R) é uma linguagem associada a uma expressão regular R, é correto afirmar que 
A. L(R1) = L(r2) 
B. L(R2) = {w | w termina com b} 
C. Existe um autômato finito determinístico cuja linguagem é igual a L(R1) ∪ L(R2). 
D. Se R3 é uma expressão regular tal que L(R3) = L(R1) ∩ L(R2), então L(R3) é uma 
linguagem infinita. 
E. Um autômato finito não determinístico que reconheça L(R1) ∪ L(R2) tem, pelo 
menos, quatro estados. 
 
 
 
 
Gabarito: C 
 
Tipo de questão: Difícil 
 
Conteúdo avaliado: Linguagens Formais, Autômatos e Compiladores 
 
Autor(a): Cármen Cecília Centeno 
 
Comentário: A linguagem L(R1) é composta das palavras ou sequências que iniciam 
com “a” e a linguagem L(R2) é composta das palavras ou sequências que iniciam 
com “b”. Note que a expressão regular (a ∪ b)* gera qualquer sequência de a´s e b´s. 
Logo, L(R2) não termina com b necessariamente. Sabemos ainda que a união de 
L(R1) e L(R2) são todas as palavras que comecem com “a” ou com “b”, ou seja 
qualquer palavra sobre o alfabeto, exceto a palavra vazia. Este AFD pode ser 
representado com dois estados apenas. Portanto, resta apenas a alternativa C, e 
como afirmado anteriormente, um AFD de dois estados reconhece L(R1) ∪ L(R2). 
 
 
 
 
 
Referências: 
 
HOPCROFT, John; MOTWANI, Rajeev; ULLMAN, Jeffrey D. Introduction to 
automata theory, languages, and computation. 3. ed. New Jersey: Prentice Hall, 
2006. 
 
MENEZES, Paulo Blauth. Linguagens Formais e Autômatos. RS. Editora Sagra 
Luzzatto. 2002 
SIPSER, Michael. Introdução a teoria da computação. 2. ed. São Paulo: Thomson 
Learning, 2007. 
 
 
 
QUESTÃO Nº 16 
 
Uma pilha é uma estrutura de dados que armazena uma coleção de itens de dados 
relacionados e que garante o seguinte funcionamento: o último elemento a ser inserido é o 
primeiro a ser removido. É comum na literatura utilizar os nome push e pop para as 
operações de inserção e remoção de um elemento em uma pilha, respectivamente. O 
seguinte trecho de código em linguagem C define uma estrutura de dados pilha utilizando um 
vetor de inteiros, bem como algumas funções para sua manipulação. 
 
#include <stdlib.h> 
#include <stdio.h> 
typedef struct { 
 int elementos[100]; 
 int topo; 
}pilha; 
 
pilha * cria_pilha () { 
 pilha * p = malloc (sizeof(pilha)); 
 p ->topo = -1; 
a,b 
a,b 
 return pilha; 
} 
 
void push (pilha *p, int element) { 
 if (p ->topo >= 99) 
 return; 
 p->elementos[++p->topo] = element; 
} 
 
int pop(pilha *p) { 
 int a = p->elementos[p->topo]; 
 p->topo--; 
 return a; 
} 
 
O programa a seguir utiliza uma pilha 
 
int main(){ 
 pilha * p = cria_pilha( ); 
 push(p, 2); 
 push(p, 3); 
 push(p, 4); 
 pop(p); 
 push(p, 2); 
 int a = pop(p) + pop(p); 
 push(p, a); 
 a += pop(p); 
 printf(“ %d”, a); 
 return 0; 
} 
 
A esse respeito, avalie as afirmações a seguir. 
I. A complexidade computacional de ambas as funções push e pop e O(1). 
II. O valor exibido pelo programa seria o mesmo caso a instrução a += pop(p); fosse 
trocada por a += a; 
III. Em relação ao vazamento de memória (memory leak), é opcional chamar a função 
free(p), pois o vetor usado pela pilha é alocado estaticamente. 
 
É correto o que se afirma em 
A. I, apenas 
B. III, apenas 
C. I e II, apenas 
D. II e III, apenas 
E. I, II e III 
 
 
 
Gabarito: C 
 
Tipo de questão: Difícil 
 
Conteúdo avaliado: Algoritmos e Estrutura de Dados 
 
Autor(a): Sibelius Lellis Vieira 
 
Comentário: As funções push e pop empilham e desempilham um elemento da pilha, 
realizando uma operação única. Tem complexidade O(1), indicando que a afirmação I 
é verdadeira. A execução do programa inicia empilhando 2, 3 e 4, na ordem, e depois 
desempilhando 4 e empilhando 2. Posteriormente, desempilha 2 e 3, realiza a adição 
destes (a=2+3=5) e empilha este valor (5). A seguir, desempilha este valor e soma 
com o valor de a, que acabou de ser empilhado (5). Portanto, empilhar 5 e somar com 
o que foi empilhado é equivalente a somar a variável a consigo mesmo e colocar o 
resultado em a. Portanto, II está correta. A afirmação III está incorreta, pois uma 
alocação de memória foi feita via chamada à malloc, pois embora a pilha seja definida 
como um vetor de elementos e um topo, a variável que a representa é dinâmica, e 
pode ser alocada e desalocada por free. Logo, não é opcional invocar free(p) para 
liberar memória. Logo, as afirmativas I e II estão corretas e a letra adequada é C. 
 
 
Referências: 
 
CORMEN, Thomas H. et al. Algoritmos: teoria e prática. 3. ed. Rio de Janeiro: 
Campus, 2012. 
DROZDEK, Adam. Estruturas de dados e algoritmos em C++. São Paulo: Cengage 
Learning, 2002. 
ZIVIANI, Nivio. Projeto de algoritmos com implementações em Java e C++. São 
Paulo: Cengage Learning, 2006. 
 
 
 
QUESTÃO Nº 17 
Considerando que o gerente de qualidade é o responsável por definir os meios necessários 
para se obter um produto com a qualidade desejada, bem como por estabelecer técnicas para 
aferir a qualidade do produto, avalie as afirmações a seguir. 
I. O uso de processos de desenvolvimento padronizados, sem adaptações, 
independente do tipo de software a ser desenvolvido, assegura que o produto terá a 
qualidade desejada. 
II. O controle de qualidade pode ser realizado por meio de revisões, incluindo inspeções 
de programas, e de artefatos de projetos. 
III. Fatores de qualidade de software estão diretamente relacionados a um único atributo 
interno de software. 
É correto o que se afirma em 
A. II, apenas 
B.III, apenas 
C. I e II, apenas 
D. I e III, apenas 
E. I, II e III 
 
 
 
 
Gabarito: A 
 
Tipo de questão: Fácil 
 
Conteúdo avaliado: Engenharia de Software e Interação Humano-Computador 
 
Autor(a): André Luiz Alves, Ronaldo Lopes de Oliveira e Sibelius Lellis Vieira 
 
Comentário: A afirmação I está incorreta, pois os processos precisam ser adaptados 
ao contexto do desenvolvimento, considerando o tipo de software que vai ser 
desenvolvido, tecnologias envolvidas, recursos disponíveis e cultura organizacional. 
Por exemplo, software de tempo real tem características próprias que devem ser 
consideradas para acrescentar algumas atividades de desenho e também de garantia 
de qualidade. A afirmação III também está incorreta, pois a qualidade de software é 
multidimensional, sendo avaliada por vários fatores internos e externos. Alguns 
exemplos desses fatores são funcionalidade, usabilidade, manutenibilidade, 
eficiência, portabilidade e confiabilidade. A afirmação II está correta, pois a qualidade 
deve ser garantida durante todo o ciclo de vida, através de revisões e outras técnicas 
nos artefatos produzidos e também pelos testes no software construído. 
 
 
Referências: 
 
KOSCIANSKI, Andre; SOARES, Michel dos Santos. Qualidade de Software. 2. Ed. 
São Paulo: Novatec, 2007. 
 
SOMMERVILLE, Ian. Engenharia de Software. 8. ed. São Paulo: Pearson Education 
do Brasil, 2007. 
 
 
QUESTÃO Nº 18 
 
Em relação à aplicação adequada das técnicas de Inteligência Artificial, avalie as afirmações a 
seguir. 
I. Indução em Árvore de Decisão é utilizada para identificação de fraudes em cartões de 
crédito. 
II. Redes Neurais Artificiais são utilizadas no desenvolvimento de sistemas de análise de 
risco em aplicações financeiras. 
III. Sistemas Especialistas baseados em regras são utilizados no desenvolvimento de 
sistemas de diagnóstico de falhas em hardware. 
 
É correto o que se afirma em 
A. I, apenas 
B. III, apenas 
C. I e II, apenas 
D. II e III, apenas 
E. I, II e III 
 
 
 
Gabarito: E 
 
Tipo de questão: Difícil 
 
Conteúdo avaliado: Inteligência Artificial e Computacional 
 
Autor(a): Sibelius Lellis Vieira 
 
Comentário: As três afirmações são verdadeiras: árvores de decisão são usadas para 
a tarefa de classificação em mineração de dados, e identificação de padrões, bem 
como redes neurais artificiais, que podem ser utilizadas para sistemas de análise de 
risco, classificando o risco em alto ou baixo. Já sistemas especialistas são usados 
para simular o comportamento de um especialista, que pode fazer diagnósticos, tais 
como diagnósticos médicos. Está correta a letra E. 
 
 
Referências: 
 
RUSSEL, Stuart.; NORVIG, Peter. Inteligência artificial. 2. ed. Rio de Janeiro: 
Elsevier, 2004. 
 
LUGER, George F. Inteligência artificial. 4. ed. Porto Alegre: Bookman, 2004. 
 
 
 
QUESTÃO Nº 19 
O algoritmo de traçado de raios (ray-tracing) é considerado um marco no desenvolvimento de 
técnicas de computação gráfica para a geração de imagens realistas. 
 
 
Imagem 1 
Disponível em: <http://wikipedia.org> 
 
 
Imagem 2 
Disponível em: <http://www.colegioweb.com.br> 
 
 
Imagem 3 
Disponível em: <http://www.cgw.com> 
 
A partir da análise das imagens apresentadas, conclui-se que a técnica de traçado de raios foi 
utilizada para a geração 
A. Apenas da imagem 1. 
B. Apenas da imagem 2. 
C. Apenas das imagens 1 e 3. 
D. Apenas das imagens 2 e 3. 
E. Das imagens 1, 2 e 3. 
 
 
 
 
Gabarito: A 
 
Tipo de questão: Muito difícil 
 
Conteúdo avaliado: Computação Gráfica e Processamento de Imagem 
 
Autor(a): Fábio Gomes Barbosa 
 
Comentário: O Ray-Tracing é um algoritmo recursivo que, para cada pixel da projeção 
(imagem), projeta um raio (vetor) traçado a partir do observador em direção aos 
objetos constituintes da cena, os interceptando, conforme a distância e usando esta 
informação para determinar quais os objetos mais próximos e os mais distantes. 
Desta forma, é possível calcular qual a cor será atribuída ao pixel. Porém é preciso 
lembrar que principal característica é: este raio torna-se a fonte de luz, revelando 
assim apenas a luz visível para ser processada. Para tal, observa-se a incidência das 
fontes de luz (ambiente) no ponto interceptado: são consideradas as componentes de 
luz refletida, refratada e também de sombra e o mais importante: qual a contribuição 
(peso) de cada uma no referido ponto de intersecção. Observa-se que as 3 imagens 
apresentadas se originam de uma projeção ancorada a partir do ponto de vista do 
observador e que esta é uma das características do Ray-Tracing. Entretanto, a 
Imagem 1 apresenta em sua composição diversos objetos transparentes, feitos de 
vidro colorido. Algumas das características do vidro são transparência, refração e a 
reflexão de luz. Neste contexto, outra característica do Ray-Tracing facilmente 
observada na Imagem 1 é que a técnica considera o redirecionamento dos raios (por 
meio de uma árvore), assim é possível produzir os reflexos na superfície dos vidros 
de forma realista. Na imagem 2, um raio, o ponto de vista do observador exerce 
pouca influência na constituição da imagem, uma vez que um raio é sua própria fonte 
de luz. A imagem 3 apenas o sol age como fonte de luz, demonstrando pouca (ou 
quase nenhuma) característica de transparência, reflexão e refração nos objetos 
constituintes. 
 
 
Referências: 
 
AZEVEDO, Eduardo e CONCI, Aura. Computação Gráfica – Teoria e Prática. 
Editora Campus, 2003. 
 
SHIRLEY, Peter H. Fundamentals of computer graphics. Massachusetts: 
AK Peters, 2005. 
 
QUESTÃO Nº 20 
 
Um processo tem um ou mais fluxos de execução, normalmente denominado apenas por 
threads. 
 
 
A partir das figuras 1 e 2 apresentadas, avalie as afirmações 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çamento 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 independente uma das outras. 
 
É correto apenas o que se afirma em 
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 
 
 
 
Gabarito: E 
 
Tipo de questão: Fácil 
 
Conteúdo avaliado: Sistemas Operacionais e Arquitetura de Computadores 
 
Autor(a): Sibelius Lellis Vieira 
 
Comentário:De acordo com o enunciado, na Figura 1 existem 3 threads, uma para 
cada processo e na figura 2 existem 3 threads em um único processo. Como cada 
processo tem seu próprio espaço de endereçamento, a afirmação I e a afirmação II 
estão incorretas, o que indica que a alternativa correta é a letra E. Nesta alternativa, 
III, IV e V estão corretas. A afirmação III diz que na Figura 2 existe um único espaço 
de endereçamento e 3 threads de controle. Como cada processo tem seu próprio 
espaço de endereçamento, está correta. A afirmação IV diz que na figura 2 existem 3 
processos, cada um com seu espaço de endereçamento e uma thread, o que está 
correto. A afirmação V diz que as threads permitem que várias execuções ocorram no 
mesmo ambiente de processo de forma independente umas das outras, o que está 
correto. 
 
 
Referências: 
SILBERSCHATZ, A.; GAVIN B. P.; GAGNE G. Fundamentos de sistemas 
operacionais. 8. ed. Rio de Janeiro: Elsevier/Campus, 2013. 
TANENBAUM, Andrew S. Sistemas operacionais modernos. 3. ed. São Paulo: 
Prentice-Hall,2010. 
 
 
QUESTÃO Nº 21 
O fragmento de código a seguir, escrito em Java, descreve duas implementações para um 
lock. Ambas possuem um método denominado acquire e um método denominado release. 
 
class LockA { 
 private int turn = 0 
 public void acquire (int tid) { 
 while (turn == (1-tid)); 
 } 
 public void release(int tid) { 
 turn = (1 – tid); 
 } 
} 
 
class LockB { 
 public void acquire ( ) { 
 disableInterrupts ( ) ; 
 } 
 public void release ( ) { 
 enableInterrupts( ); 
 } 
} 
 
Considera-se que: 
• As duas implementações de lock são utilizadas por aplicações com, no máximo, duas 
threads; 
• Uma aplicação que utilizar qualquer uma destas implementações invocará o método 
acquire antes de entrar em sua seção crítica e o método release após deixar a 
seção crítica; 
• Tanto o método acquire quanto o método release são operações atômicas nas 
duas implementações de lock; 
• Para a implemetanção que requer um tid (thread id), assume-se que ele sempre será 
0 ou 1; 
• Os métodos disableInterrupts e enableInterrupts são utilizados para desabilitar 
e habilitar respectivamente as interrupções do processador onde o código for 
executado. O código desses dois métodos foi desenvolvido para ser utilizado em uma 
máquina com um ou dois processadores. 
 
A partir das informações apresentadas, avalie as afirmações a seguir. 
I. A implementação de LockA garante progresso. 
II. A implementação de LockB garante progresso. 
III. A implementação de LockA garante exclusão mútua. 
IV. A implementação de LockB garante exclusão mútua 
 
 
É correto apenas o que se afirma em 
A. I e II 
B. II e III 
C. III e IV 
D. I, II e IV 
E. I, III e IV 
 
 
 
 
Gabarito: B 
 
Tipo de questão: Difícil 
 
Conteúdo avaliado: Sistemas Operacionais e Arquitetura de Computadores 
 
Autor(a): Sibelius Lelllis Vieira 
 
Comentário: No fragmento do código apresentado existem duas formas de proteger a 
seção crítica de acesso concorrente em um sistema com um ou dois processadores. 
Na primeira, da classe LockA, uma variável turn é utilizada para controlar o acesso, e 
só acessa a seção aquele processo ou thread para o qual a variável turn indica. No 
segundo fragmento, da classe LockB, o processo que desabilitar a interrupção acessa 
a seção crítica e posteriormente libera o acesso, liberando a interrupção. No 
enunciado, duas threads no máximo, acessam a seção crítica. O acesso é efetivado 
invocando o método acquire, e após o retorno do método, a seção crítica é utilizada e 
o método release é invocado, na sequência. A implementação de LockA garante que 
apenas uma thread acessa a seção crítica, pois apenas uma delas será apontada 
(valor de turn é único, 0 ou 1) por turn em um dado momento, mas não garante 
progresso, pois se uma thread que pode acessar a seção crítica não quiser, a outra 
não vai poder. Portanto, alternativas corretas podem ser B ou C. A implementação de 
LockB garante progresso, mas não a exclusão mútua, no caso de existirem dois 
processadores. Portanto, a alternativa correta é a B. 
 
 
Referências: 
SILBERSCHATZ, A.; GAVIN B. P.; GAGNE G. Fundamentos de sistemas operacionais. 8. 
ed. Rio de Janeiro: Elsevier/Campus, 2013. 
TANENBAUM, Andrew S. Sistemas operacionais modernos. 3. ed. São Paulo: 
Prentice-Hall, 2010. 
 
 
QUESTÃO Nº 22 
Considere o processo de fabricação de um produto siderúrgico que necessita passar por n 
tratamentos térmicos e químicos para ficar pronto. Cada uma das n etapas de tratamento é 
realizada uma única vez na mesma caldeira. Além do custo próprio de cada etapa do 
tratamento, existe o custo de se passar de uma etapa para a outra, uma vez que, dependendo 
da sequência escolhida, pode ser necessário alterar a temperatura da caldeira e limpá-la para 
evitar a reação entre os produtos químicos utilizados. Assuma que o processo de fabricação 
inicia e termina com a caldeira limpa. Deseja-se projetar um algoritmo para indicar a 
sequência de tratamentos que possibilite fabricar o produto com o menor custo total. Nesta 
situação, conclui-se que 
 
A. A solução do problema é obtida em tempo de ordem O(nlogn), utilizando um 
algoritmo ótimo de ordenação. 
B. Uma heurística para a solução do problema de coloração de grafos solucionará o 
problema em tempo polinomial. 
C. O problema se reduz a encontrar a árvore geradora mínima para o conjunto de etapas 
do processo, requerendo tempo de ordem polinomial para ser solucionado. 
D. A utilização do algoritmo de Dijkstra para se determinar o caminho de custo mínimo 
entre o estado inicial e o final soluciona o problema em tempo polinomial. 
E. Qualquer algoritmo conhecido para a solução do problema descrito possui ordem de 
complexidade de tempo não-polinomial, uma vez que o problema do caixeiro viajante 
se reduz a ele. 
 
 
 
Gabarito: E 
 
Tipo de questão: Difícil 
 
Conteúdo avaliado: Teoria dos Grafos 
 
Autor(a): Cármen Cecília Centeno 
 
Comentário: Para modelar este problema utilizando grafos se usa um grafo completo 
com n+1 vértices representando cada uma das etapas e a etapa inicial caldeira limpa. 
As arestas contêm pesos que representam o custo de se passar de uma etapa para a 
outra. Deseja se sair do vértice que representa a caldeira limpa passar por todos os 
vértices uma única vez e retornar ao vértice caldeira limpa de forma que o custo seja 
mínimo. O problema não pode ser resolvido através de uma arvore geradora mínima, 
pois temos que encontrar um ciclo (exclui C). Não podemos aplicar Dijkstra, pois 
temos que garantir que todos os vértices sejam visitados (exclui D). O problema de 
coloração determina conjuntos de tarefas e não uma ordem de tarefas (exclui B). Não 
é suficiente fazer uma ordenação dos valores pois isso não garante que os vértices 
serão todos visitados uma única vez de forma mínima. Se colocarmos todas as 
etapas com o mesmo custo como garantir que será encontrado um ciclo que visite 
todas os vértices. O problema em questão corresponde ao problema do Caixeiro 
Viajante ou Ciclo Hamiltoniano, que é NP-Completo. 
 
 
Referências: 
 
CORMEN, Thomas H. et al. Algoritmos: teoria e prática. 3. ed. Rio de Janeiro: 
Campus, 2012. 
 
SZWARCFITER, Jayme Luiz, MARKEZAON, Lilian. Estrutura de Dados e seus 
Algoritmos. RJ, Editora LTC. 1994. 
 
 
QUESTÃO Nº 23 
Qual o valor de retorno da função a seguir, caso n=27? 
 
int recursao (int n) { 
 if (n <=10) { 
 return n * 2; 
 } 
 else { 
 return recursao (recursao (n/3)); 
 } 
} 
 
A. 8. 
B. 9. 
C. 12. 
D. 16. 
E. 18. 
 
 
 
 
Gabarito: D 
 
Tipo de questão: Difícil 
 
Conteúdo avaliado: Fundamentos e Técnicas de Programação 
 
Autor(a): Sibelius Lellis Vieira 
 
Comentário: No caso de n=27, a função recursao(27) retorna 
recursao(recursal(27/3))=recursao(recursao(9)); recursao(9) retorna 18. Portanto, 
recursao(18) é avaliada; recursao(18) retorna 
recursao(recursao(18/3)=recursao(recursao(6)); recursao(6) retorna 12, logo, deve-se 
avaliar recursao(12) e esta, por sua vez, retorna 
recursao(recursao(12/3))=recursao(recursao(4); recursao(4) retorna 8 e recursao(8), 
por sua vez, retorna 16. Portanto, a alternativa correta é D. 
 
 
Referências: 
FARREL, Joyce. Lógica e design de programação: introdução. São Paulo: 
Cengage Learning, 2010. 
FARRER, Harry. et al. Programação estruturada de computadores: algoritmos 
estruturados. 3. ed. Rio de Janeiro: LTC, 1999. 
LOPES, Anita; GUTO, G. Introdução à programação. Rio de Janeiro: Campus, 
2002. 
 
 
QUESTÃO Nº 24 
 
Considere as seguintes tabelas de um banco de dados: 
1. Fornecedor (cod_fornec, nome_fornec, telefone, cidade, UF) 
2. Estado (UF, nome_estado) 
A expressão SQL que obtém os nomes dos estados para os quais não há fornecedores 
cadastrados é. 
A.SELECT E.UF 
FROM Estado AS E 
WHERE E.nome_estado NOT IN ( 
 SELECT F.UF 
 FROM Fornecedor AS F); 
 
B. SELECT E.nome_estado 
FROM Estado AS E, FROM 
Forncedor AS F 
WHERE E.UF = F.UF; 
 
C. SELECT E. nome_estado 
FROM Estado AS E 
WHERE E.UF NOT IN ( 
 SELECT F.UF 
 FROM Fornecedor AS F); 
 
D. SELECT E.nome_estado 
FROM Estado AS E, FROM 
Forncedor AS F 
WHERE E.nome_estado = F.UF; 
 
E. SELECT E. nome_estado 
FROM Estado AS E 
WHERE E.UF IN ( 
 SELECT F.UF 
 FROM Fornecedor AS F); 
 
 
 
Gabarito: C 
 
Tipo de questão: Fácil 
 
Conteúdo avaliado: Banco de Dados 
 
Autor(a): André Luiz Alves e Ronaldo Lopes de Oliveira 
 
Comentário: O enunciado da questão afirma que existem duas tabelas: uma tabela 
FORNECEDOR em que cada tupla (linha da tabela) representa um fornecedor 
cadastrado e uma tabela ESTADO em que cada tupla (linha da tabela) representa um 
Estado da Federação (também conhecido como Unidade da Federação ou UF). A 
tabela FORNECEDOR contém para cada fornecedor a sigla da UF em que ele está 
situado. A tabela ESTADO contém para cada estado a sua sigla e o seu nome. 
Observando a definição das tabelas pode-se concluir que os Estados que não tem 
fornecedores são aqueles cuja sigla não aparecem na tabela FORNECEDOR. Uma 
expressão de linguagem de consulta SQL que pode ser usada para obter o nome dos 
estados que não tem fornecedores é baseada em uma construção usando consultas 
aninhadas com a opção NOT IN para selecionar as tuplas da tabela ESTADO cujo 
valor do atributo UF não estão no conjunto de valores de UF contidos na tabela 
FORNECEDOR. A opção que segue esse raciocínio são apenas as das alternativas A 
e C. Entretanto, a alternativa A tem dois erros: seleciona a sigla, mas o que se quer é 
o nome e compara valor de nome com sigla. Algumas observações adicionais: a letra 
B e D apresentam sintaxe SQL errada na cláusula FROM e a letra E lista o nome dos 
estados que tem fornecedores cadastrados porque usa a cláusula IN ao invés de 
NOT IN. 
 
 
Referências: 
 
KORTH, Henry; SILBERSCHATZ, Abraham. Sistema de banco de dados. 6. ed. Rio 
de Janeiro: Campus, 2012. 
 
ELMASRI, Ramez. Sistemas de banco de dados. 6. ed. São Paulo: Pearson 
Addison Wesley, 2012. 
 
 
QUESTÃO Nº 25 
 
Uma gramática livre de contexto (GLC) é um modelo computacional geralmente utilizado para 
definir linguagens de programação e, quando está de acordo com a Forma de Backus-Naur 
(BNF), permite que alguns operadores sejam utilizados no lado direito de suas produções, 
como o operador | (pipe) que indica seleção, o operador [ ] que indica que o operando em 
questão é opcional, e o operador * que indica repetição de 0 ou mais vezes. 
Projetar um compilador para uma determinada linguagem envolve, entre outras coisas, 
especificar quais são os símbolos válidos nesta linguagem, bem como quais são as regras 
sintáticas que a definem. 
A linguagem de programação Java é uma linguagem com suporte à orientação a objetos que 
não permite herança múltipla e que permite que uma classe implemente múltiplas interfaces. 
A seguir, exibem-se trechos de código sintaticamente válidos na linguagem Java. 
Trecho 1: 
class A extends B { } 
Trecho 2: 
class F implements C { } 
Trecho 3: 
class J extends A implements C, D { } 
No trecho 1, cria-se uma classe chamada A que herda de uma classe chamada B. No trecho 2, 
cria-se uma classe F que implementa uma interface chamada C. No trecho 3, cria-se uma 
classe chamada J que herda de uma classe chamada A e implementa duas interfaces C e D. 
Considere que: 
• <classdecl> é um não terminal cujo intuito é dar origem a declarações de classes; 
• <classbody> é um não terminal cujo intuito é dar origem ao corpo de classes; 
• Os terminais aparecem entre aspas duplas; 
• “ id” é um símbolo que representa identificador válido, como nomes de classes ou 
variáveis. 
A gramática que especifica uma linguagem que não permita herança múltipla e que 
implemente zero ou mais interfaces é 
A. <classdecl> “class” “id” [“ extends”] “id” <classbody> 
B. <classdecl> “class” “id” (“ extends” “id”)* <classbody> 
C. <classdecl> “class” “id” [“ extends”] “id” [“implements” (, | “id”)*]<classbody> 
D. <classdecl> “class” “id” [“ extends” “id”] [“implements” “id” (“,” “id”)*]<classbody> 
E. <classdecl> “class” “id” [“ extends” “id”] “implements” “id” (“,” “id”)*<classbody> 
 
 
 
 
 
Gabarito: D 
 
Tipo de questão: Médio 
 
Conteúdo avaliado: Linguagens Formais, Autômatos e Compiladores 
 
Autor(a): Cármen Cecília Centeno 
 
Comentário: Como indicado na questão o operador [ ] indica que o operando é 
opcional. Observando os exemplos vemos que “ class” “ id” acontece em todos, estes 
podem ser seguidos pelos terminais “ extends” (trecho 1 e 3) ou “ implements” 
(trecho 2) o que indica que podemos escolher entre “ extends” ou “ implements” , o 
que exclui letras A e B. 
A seguir note a diferença de [“ extends” ] “ id” e [“ extends” “ id”], no primeiro ocorre 
um id sem o terminal “ extends”, no segundo os dois estão ligados, como pode ser 
observado nos exemplos, excluímos assim letra C. A diferença entre as letras D e E 
é que na segunda o terminal “ implements” é obrigatório e em D é opcional pois está 
entre [ ]. Como dito anteriormente tanto “ implements” quanto “ extends” são 
elementos opcionais, logo letra D é a opção correta. 
 
 
Referências: 
 
HOPCROFT, John; MOTWANI, Rajeev; ULLMAN, Jeffrey D. Introduction to 
automata theory, languages, and computation. 3. ed. New Jersey: Prentice Hall, 
2006. 
 
MENEZES, Paulo Blauth. Linguagens Formais e Autômatos. RS. Editora Sagra 
Luzzatto. 2002 
 
 
QUESTÃO Nº 26 
Um conjunto indutivo S é definido de acordo com os seguintes passos: 
[Base] Declaração dos elementos iniciais, atômicos. 
[Indução] Definição de regras que constroem expressões a partir de elementos já existentes 
em S. 
[Fecho] Uma declaração de que nada mais está em S a não ser os elementos construídos 
pelos passos Base e Indução. 
 
Os operadores que constroem as expressões nos passos Base e Indução são chamados de 
construtores do conjunto S. Como um exemplo, a definição abaixo especifica um conjunto 
indutivo Prop, das proposições booleanas formadas pelos construtores V (valor verdadeiro), 
F(valor falso), ! (para negação de expressões) e and (para a conjunção de expressões). 
1. [Base] V,F estão em Prop. 
2. [Indução] Se B está em Prop, então (! B) está em Prop. 
3. [Indução] Se B1 e B2 estão em Prop, então (and B1 B2) está em Prop. 
4. [Fecho] Nada mais está em Prop, a não ser o especificado em Base e Indução. 
 
Expressões (termos) em Prop incluem V, F, !F, !V, (and V F), (and (! V) (! F)) e assim por 
diante. De forma análoga, linguagens funcionais permitem a declaração de tipos indutivos 
com seus respectivos construtores. 
Neste contexto, avalie as seguintes afirmações. 
I. Conjuntos indutivos são conjuntos enumeráveis. 
II. Conjuntos infinitos não podem ser especificados por meio de definições indutivas. 
III. Para estender a linguagem Prop de tal forma a considerar expressões para disjunção e 
implicação de proposição, é necessário acrescentar mais dois construtores à definição 
de Prop anterior. 
 
É correto o que se afirma em 
A. I, apenas 
B. II, apenas 
C. I e III, apenas 
D. II e III, apenas 
E. I, II e III 
 
 
 
 
Gabarito: C 
 
Tipo de questão: Difícil 
 
Conteúdo avaliado: Lógica e Matemática Discreta 
 
Autor(a): Sibelius Lellis Vieira 
 
Comentário: Trata-se de uma questão de matemática discreta, que apresenta uma 
série de definições em relação à formação de um conjunto indutivo S. A questão 
apresenta as seguintes afirmações, que podem ser deduzidas do contexto da 
questão: I. Conjuntos indutivos são enumeráveis.Formalmente, um conjunto é 
enumerável ou infinitamente contável se existe uma bijeção entre este conjunto e um 
subconjunto infinito de número naturais ou N. Intuitivamente, pode-se compreender 
um conjunto enumerável como sendo aquele para o qual seus elementos podem ser 
discriminados, um a um, em uma ordem. No caso, o conjunto indutivo é enumerável, 
uma vez que os elementos deste conjunto podem ser adicionados a ele em uma 
sequência de indução, um após o outro. A afirmação II indica que conjuntos infinitos 
não podem ser especificados por meio de definições indutivas. Não há esta limitação, 
visto que conjuntos de números tais como os naturais podem ser definidos de forma 
indutiva e são infinitos. De fato, conjuntos enumeráveis são infinitamente contáveis, 
visto que se forem finitos, serão apenas conjuntos contáveis. A afirmação III diz que 
se considerarmos expressões para disjunção e implicação de proposição, teríamos 
que acrescentar mais dois construtores à definição de Prop. Uma vez que prop já tem 
definido elementos que são a conjunção e a negação, nas definições de indução 2 e 
3, deve-se acrescentar expressões como as propostas para disjunção e implicação. 
Portanto, I e III estão corretas, tendo como gabarito a letra C. 
 
Referências: 
 
ROSEN, Kenneth H. Matemática discreta e suas aplicações. 6. ed. São Paulo: 
McGraw-Hill, 2009. 
MENEZES, P. B. Matemática Discreta para Computação e Informática. 2ª Edião. 
Editora Sagra Luzzatto, 2005. 
 
 
QUESTÃO Nº 27 
Considere o seguinte argumento: 
1 – Se existe fogo, então existe oxigênio. 
2 – Não há oxigênio. 
3 – Então não há fogo. 
A regra de inferência que justifica a validade do argumento acima é 
 
A. P →Q , ¬P 
 ¬Q 
 
B. P →Q , ¬Q 
 ¬P 
C. P →Q , Q 
 P 
D. P →Q , ¬Q 
 ¬¬P 
E. P →Q , P 
 Q 
 
 
 
 
Gabarito: B 
 
Tipo de questão: Fácil 
 
Conteúdo avaliado: Lógica e Matemática Discreta 
 
Autor(a): Cármen Cecília Centeno e Sibelius Lellis Vieira 
 
Comentário: Pelo enunciado, se P corresponde à existe fogo, e Q corresponde à 
existe oxigênio, então a afirmação 1 equivale à P → Q , a afirmação 2 equivale à ┐Q 
e a afirmação 3 equivale à ┐P. Observe que como há negação, as alternativas C e E 
são incorretas, e a afirmativa D nega duas vezes, o que também indica inexatidão. A 
alternativa correta é B, modus tollens, que a partir de P → Q e ┐Q implicam que ┐P. 
Além disso sabemos que somente nas alternativas A e E temos regras de inferências 
válidas, sendo que A representa a regra Modus Tollens e E representa a regra Modus 
Ponens. 
 
 
Referências: 
 
ALENCAR FILHO, Edgar. Iniciação à Lógica Matemática. Nobel.2013 SP. 
 
ROSEN, Kenneth H. Matemática discreta e suas aplicações. 6. ed. São Paulo: 
McGraw-Hill, 2009. 
 
SILVA, Flávio Correa da. Lógica para computação. São Paulo: Thomson Learning, 
2006. 
 
SOUZA, João Nunes da Silva. Lógica para ciência da computação: uma introdução 
concisa. 2. ed. Rio de Janeiro: Elsevier, 2008. 
 
 
 
QUESTÃO Nº 28 
Um cientista afirma ter encontrado uma redução polinomial de um problema NP-Completo 
para um problema pertencente à classe P. Considerando que esta afirmação tem implicações 
importantes no que diz respeito à complexidade computacional, avalie as seguintes asserções 
e a relação proposta entre elas. 
 
I. A descoberta do cientista implica que P = NP 
PORQUE 
II. A descoberta do cientista implica na existência de algoritmos polinomiais para 
todos os problemas NP-Completos. 
 
A respeito dessas asserções, assinale a opção correta. 
A. As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I. 
B. As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa correta 
da I. 
C. A asserção I é uma proposição verdadeira, e a II é uma proposição falsa. 
D. A asserção I é uma proposição falsa, e a II é uma proposição verdadeira. 
E. As asserções I e II são proposições falsas. 
 
 
 
 
Gabarito: A 
 
Tipo de questão: Difícil 
 
Conteúdo avaliado: Teoria da Computabilidade e Complexidade 
 
Autor(a): Aníbal Jukemura e Sibelius Lellis Vieira 
 
Comentário: Uma redução polinomial de um problema NP-completo para um 
problema pertencente à classe P implica que P=NP, pois se qualquer problema NP-
completo pode ser resolvido em tempo polinomial, então P=NP, um problema 
aberto e fundamental na teoria da computação. Logo, a asserção I está correta. Por 
outro lado, quando um problema pertence à classe NP-Completo, o mesmo pode ser 
reduzido, em tempo polinomial, a um outro problema da classe NP-Completo. Por 
isso, ao solucionar um problema em tempo polinomial, todos podem ser solucionados 
da mesma forma. Logo, a alternativa A é a correta. 
 
 
Referências: 
CORMEN, Thomas H. et al. Algoritmos: teoria e prática. 3. ed. Rio de Janeiro: 
Campus, 2012. 
SIPSER, Michael. Introdução a teoria da computação. 2. ed. São Paulo: Thomson 
Learning, 2007. 
 
 
QUESTÃO Nº 29 
Diferentes implementações da linguagem de programação PROLOG permitem predicados 
com parâmetros, aceitam as operações de conjunção e disjunção lógica, utilizando os 
símbolos vírgula (conjunção) e ponto e vírgula (disjunção), e a negação lógica com o predicado 
not. 
Considere que um programador propôs as cláusulas mostradas a seguir, definidas em uma 
linguagem de programação como o PROLOG, como parte da verificação de critérios para 
seleção de candidatos a uma chapa de presidente e vice-presidente de uma empresa. Estas 
cláusulas apresentam as premissas para chegar às conclusões selecionadas, desconsiderados 
e descartados, a partir da possibilidade da existência de fatos ou regras com o identificador 
superior. 
superior (jorge). 
superior (ana). 
selecionados (P,Q) :- superior(P), superior(Q). 
desconsiderados (P,Q) :- not(superior(P)); not(superior(Q)). 
descartado (P) :- not(superior(P)). 
Considerando apenas as colocações e cláusulas acima e a hipótese de mundo fechado (closed 
world assumption), avalie as afirmações a seguir. 
I. Para todos valores dos parâmetros P e Q, o predicado selecionados retornará um 
valor lógico falso. 
II. Para todos os valores de P e Q, os predicados selecionados e desconsiderados 
retornarão valores lógicos diferentes. 
III. A conjunção dos predicados selecionados e desconsiderados, para quaisquer 
valores de P e Q, retornará um valor lógico verdadeiro. 
IV. Para qualquer valor de parâmetro P, o predicado descartado retornará um valor 
verdadeiro. 
V. A disjunção dos predicados selecionados e desconsiderados, para quaisquer 
valores de P e Q, retornará um valor lógico verdadeiro. 
É correto apenas o que se afirma em 
A. I e II 
B. I e III 
C. II e V 
D. III e IV 
E. IV e V 
 
 
 
 
Gabarito: C 
 
Tipo de questão: Médio 
 
Conteúdo avaliado: Paradigmas e Linguagens de Programação; Lógica e Matemática 
Discreta 
 
Autor(a): Cármen Cecília Centeno e Sibelius Lellis Vieira 
 
Comentário: Para solucionar a questão não é necessário o conhecimento de 
PROLOG, basta analisar o que é considerado em cada uma das situações: 
 
candidatos selecionados corresponde à expressão lógica P e Q; candidatos 
desconsiderados corresponde a ~P ou ~Q (~denota não) e candidatos descartados 
corresponde a ~P. 
 
Para facilitar a análise das afirmações vamos aplicar a lei de equivalência de De 
Morgan (~(P e Q) ≡ ~P ou ~Q. 
 
Resumindo: 
Selecionados: P e Q 
Desconsiderados: ~(P e Q) 
Descartado: ~P 
 
Análise das alternativas: 
 
I. Falso. V(P) = V e V(Q) = V retorna verdadeiro 
II. Verdadeiro, após a aplicação da lei de De Morgan fica claro que um é o 
oposto do outro. 
III. Falso. (P e Q) e ~(P e Q), a conjunção de uma proposição e sua negação 
é sempre falso. 
IV. Falso. V(P)= V então V(~P) = F 
V. Verdadeiro. (P e Q) ou ~(P e Q), a disjunção de uma proposição e sua 
negação é sempre verdadeiro. 
 
Portanto, II e V são verdadeiros, sendo correto o que se afirma na letra C. 
 
 
Referências: 
 
ROSEN, Kenneth H. Matemática discreta e suas aplicações. 6. ed. São Paulo: 
McGraw-Hill, 2009. 
 
RUSSEL, Stuart.; NORVIG, Peter. Inteligência artificial. 2. ed. Rio de Janeiro: 
Elsevier, 2004. 
 
SOUZA, João Nunes da Silva. Lógica para ciência da computação: uma introdução 
concisa. 2. ed. Rio de Janeiro: Elsevier, 2008. 
 
 
QUESTÃO Nº 30 
Uma fazenda possui um único poço artesiano que deve abastecer n bebedouros para o gado. 
Deseja-se determinar um projeto de ligação entre esses n+1 pontos através de encanamento 
com a menor extensão total. Um algoritmo proposto para a solução do problema executa os 
seguintes passos: 
1. Crie n+1 conjuntos unitários, cada um contendo um dos pontos a serem ligados entre 
si e insira esses conjuntos em um conjunto C. 
2. Crie um conjunto D contendo um registro para cada combinação possível de dois 
pontos distintos a serem ligados. Cada registro deve conter os campos ci, cj e d, em 
que ci e cj são dois pontos a serem ligados e d é a distância entre eles. 
3. Enquanto D não estiver vazio faça: 
3.1. Remova o registro de D com o menor valor de distância d. 
3.2. Se os valores de ci e cj do registro removido pertencerem a conjuntos distintos de 
C, então: 
3.2.1. Substitua estes dois conjuntos pela união entre eles. 
3.2.2. Guarde o registro removido em um conjunto-solução. 
 
Com base na descrição do problema e do algoritmo proposto, conclui-se que: 
A. O problema exemplifica a obtenção de uma árvore geradora mínima, portanto está 
no conjunto P. 
B. O algoritmo é uma heurística para o Problema do Caixeiro Viajante, logo apresenta 
complexidade polinomial. 
C. O problema descrito é de otimização, logo pertence ao conjunto NP-difícil, mas não 
ao conjunto NP-completo. 
D. Uma alternativa para a solução do problema é usar o algoritmo de Dijkstra para 
obtenção do caminho mínimo entra dois pontos. 
E. O passo de maior custo do algoritmo é a criação do conjunto D com as combinações 
de pontos, apresentando complexidade computacional O(n!). 
 
 
 
 
Gabarito: A 
 
Tipo de questão: Difícil 
 
Conteúdo avaliado: Teoria dos Grafos; Teoria da Computabilidade e Complexidade 
 
Autor(a): Cármen Cecília Centeno e Sibelius Lellis Vieira 
 
Comentário: É solicitado que um conjunto de n+1 pontos sejam conectados, em 
qualquer ordem. Qualquer ponto deve estar conectado a algum outro ponto. Portanto, 
não é um problema de caminho mínimo, pois todos os pontos devem ser incluídos, ou 
seja, o algoritmo de Dijkstra não é adequado, pois este acha o menor caminho que 
não necessariamente passa por todos os vértices. Também não é um problema de 
caixeiro viajante, pois um ponto pode ser conectado a outro já cheio de conexões e 
não é necessário voltar ao ponto de partida. Isto exclui as letras B e D. 
Analisando o algoritmo vemos que em 1 é criado um conjunto de vértices, e que cada 
vértice ocorre uma única vez no conjunto. Em 2 é criado um conjunto de arestas com 
pesos, é criado todas as possíveis arestas originado um grafo completo. Note que o 
algoritmo é um algoritmo guloso, sempre retira a aresta de menor peso. Uma vez 
encontrada a aresta é removido os vértices do conjunto C, sendo assim a solução 
encontrada não terá ciclos, o que gera uma arvore, como é sempre escolhida a aresta 
de menor peso é encontrada uma arvore geradora mínima. 
 
O exame ainda mostra que se trata de um algoritmo polinomial, pois tanto o conjunto 
C quanto o conjunto D têm cardinalidade n2, pois para a criação do conjunto D basta 
combinar cada vértice com todos os outros. Portanto, a alternativa E é excluída. Ao 
final, o item 3.2 do algoritmo testa se cada elemento de D tem valores ci e cj que 
pertencem à conjuntos disjuntos de C. Para realizar este exame, é necessário 
examinar os conjuntos de C dois a dois. Como o conjunto C se inicia com 
cardinalidade n e esta cardinalidade não aumenta, este teste também pode ser 
realizado em tempo polinomial. Logo, a letra C está incorreta. Trata-se, portanto, de 
um algoritmo que possibilita a formação de uma árvore geradora mínima em tempo 
polinomial, estando correta a letra A. 
 
 
 
Referências: 
CORMEN, Thomas H. et al. Algoritmos: teoria e prática. 3. ed. Rio de Janeiro: 
Campus, 2012. 
 
SZWARCFITER, Jayme Luiz, MARKEZAON, Lilian. Estrutura de Dados e seus 
Algoritmos. RJ, Editora LTC. 1994. 
 
 
QUESTÃO Nº 31 
 
Na transmissão de dados em sistemas computacionais, o dispositivo de verificação de erros 
conhecido como bit de paridade consiste da adição de um bit extra durante a transmissão. O 
valor associado a esse bit é uma função da quantidade de bits de dados iguais a 1 a serem 
transmitidos. 
Nesse contexto, considere a transmissão de 7 bits de dados, com um bit extra de paridade, 
em um sistema de comunicação no qual a probabilidade de transmitir um bit de forma 
incorreta é igual a 10 -6 e independe de outros erros ocorridos. O bit de paridade também 
pode sofrer erros. 
A probabilidade da ocorrência de transmissão de 2 bits errados, que seria erroneamente 
detectada como uma transmissão sem erros, é 
A. 1,0 x 10-12. 
B. 2,0 x 10-12. 
C. 2,8 x 10-11. 
D. 2,0 x 10-6. 
E. 2,8 x 10-5. 
 
 
 
Gabarito: C 
 
Tipo de questão: Muito difícil 
 
Conteúdo avaliado: Redes de Computadores e Sistemas Distribuídos; Probabilidade e 
Estatística 
 
Autor(a): Sibelius Lellis Vieira 
 
Comentário: No caso em comento, oito bits são transmitidos, e a probabilidade de que 
um deles qualquer seja transmitido incorretamente é de 10-6. A probabilidade de que 
exista um bit errado é 10-6 multiplicado por 8 (número de bits que podem estar 
errados). Caso possam existir dois bits errados, então pode ser o bit 1 e 2, o bit 1 e 3, 
etc. Desta forma, existem 28 combinações de dois bits errados. Logo, a probabilidade 
de se transmitir dois bits errados é 28. 10-6.10-6, ou seja, 2,8.10-11. A alternativa 
correta é a letra C. 
 
 
Referências: 
 
FOROUZAN, Behrouz. Comunicação de dados e redes de Computadores. 4. ed. 
Porto Alegre: McGraw Hill, 2008. 
 
TANENBAUM, Andrew; WETHERHALL, David. Redes de computadores. 5. ed. São 
Paulo: Campus, 2011. 
MONTGOMERY, Douglas C. Probabilidade aplicada à engenharia. 4. ed. Rio de 
Janeiro: LTC, 2011. 
 
 
QUESTÃO Nº 32 
Considere as proposições lógicas simples P,Q,R: 
P: o programador lê a literatura técnica 
Q: o programador conhece o idioma inglês 
R: o programador será selecionado 
Pretende-se demonstrar a validade ou invalidade do seguinte argumento: 
Se o programador lê a literatura técnica, então ele conhece inglês. 
Se o programador conhece o idioma inglês, então ele será selecionado. 
O programador não será selecionado ou ele lê a literatura técnica. 
Logo, o programador lê a literatura técnica se e somente se conhece o idioma inglês. 
Considerando as colocações acima, avalie as afirmações a seguir. 
I. As premissas do argumento podem ser expressas na forma: P � Q, Q � R e ¬R v P. A 
conclusão do argumento pode ser expressa na forma: P ↔ Q. 
II. A validade do argumento se demonstra com os passos: ¬Q v P (equivalente de uma 
premissa), P �R (transitividade da implicação a partir das premissas) e conclusão Q 
↔ R (conjunção de duas proposições condicionais e transformação em bicondicional) 
III. A validade do argumento se demonstra com os passos: R � P (equivalente de uma 
premissa), Q �P (transitividade da implicação), chegamos à conclusão Q ↔ R 
(conjunção de duas proposições condicionais e transformação em bicondicional). 
IV. As premissas do argumento podem ser expressas na forma: P�Q, Q�R e ¬R � P e a 
conclusãodo argumento acima pode ser expressa na forma: P�Q. 
V. A invalidade do argumento acima se demonstra desta forma: a proposição lógica 
P↔Q é diferente das premissas P�Q, Q�R e ¬R v P. 
 
É correto apenas o que se afirma em 
A. I e III 
B. II e IV 
C. I, III e V 
D. I, II, IV e V 
E. II, III, IV e V 
 
 
 
 
Gabarito: A 
 
Tipo de questão: Médio 
 
Conteúdo avaliado: Lógica e Matemática Discreta 
 
Autor(a): Cármen Cecília Centeno 
 
Comentário: Considerando as premissas P, Q, R a tradução do argumento é imediata: 
P�Q, Q ↔R, ¬R v P e a conclusão P ↔ Q, com isso concluímos que I é verdadeira e 
IV é falsa, o que exclui as letras B, D e E. Resta apenas A.( I e III) e C. (I, III e V). 
sendo assim podemos concluir que III é verdadeiro. Se III é verdadeiro então o 
argumento é válido o que torna V falsa pois esta afirma que o argumento é inválido. 
 
 
 
Referências: 
 
ALENCAR FILHO, Edgar. Iniciação à Lógica Matemática. Nobel.2013 SP. 
 
ROSEN, Kenneth H. Matemática discreta e suas aplicações. 6. ed. São Paulo: 
McGraw-Hill, 2009. 
 
SOUZA, João Nunes da Silva. Lógica para ciência da computação: uma introdução 
concisa. 2. ed. Rio de Janeiro: Elsevier, 2008. 
 
 
 
QUESTÃO Nº 33 
 
A seguinte sequência de instruções lógicas e aritméticas será executada por um processador 
em pipeline de 5 estágios: busca da instrução, leitura de registradores, execução, acesso à 
memória e escrita de dados. 
 
and R5, R4, R3 
or R6, R4, R2 
add R1, R2, R2 
mul R3, R2, R1 
sub R1, R1, R4 
 
O pipeline foi implementado sem hardware adicional para a resolução de conflitos, mas os 
valores dos registradores podem ser escritos na primeira metade do ciclo e lidos na segunda 
metade. Sabendo-se que o primeiro operando das instruções é o registrador destino, avalie as 
afirmações a seguir. 
I. A troca de posição entre as instruções or e add soluciona o conflito de dados. 
II. A troca de posição entre as instruções add e and soluciona o conflito de dados. 
III. A inserção de uma operação nop (sem operação) entre add e mul soluciona o conflito 
de dados. 
É correto o que se afirma em 
A. I, apenas 
B. II, apenas 
C. I e II, apenas 
D. II e III apenas 
E. I, II e III 
 
 
 
Gabarito: B 
 
Tipo de questão: Difícil 
 
Conteúdo avaliado: Sistemas Operacionais e Arquitetura de Computadores 
 
Autor(a): Sibelius Lellis Vieira 
 
Comentário: Segundo o enunciado, 5 instruções são executadas em sequência, por 
um processador com pipeline em 5 estágios, sendo o estágio de leitura o segundo e o 
estágio de escrita o quinto. Existe um conflito de dados entre a instrução add 
R1,R2,R2 que escreve no registrador R1 e a instrução mul R3,R2,R1 lê o registrador 
R1 logo em seguida, uma vez que o enunciado indica que o primeiro operando é o 
registrador destino (a ser escrito). Esta leitura deve esperar por um tempo que 
permita que a escrita da instrução anterior seja efetivada. Como o pipeline não tem 
hardware para a resolução de conflitos, é necessário ao programador modificar o 
código para evitá-lo. Supõe-se que cada estágio tem o mesmo tempo de ciclo. Para 
prevenir o conflito RAW (leitura após escrita) de R1, a escrita deve anteceder a leitura 
em pelo menos, 3 ciclos (diferença do estágio de leitura e escrita em cada instrução). 
A diferença de 3 ciclos entre a instrução add e a instrução mul só é conseguida se 
add trocar de posição com a instrução and. Neste caso, supondo que a execução 
inicia-se no ciclo 0 e cada estágio dura um ciclo, a escrita de R1 é feita no ciclo 4 (0, 
1, 2, 3, e 4 são os estágio da instrução add, a primeira a executar). A instrução mul é 
a quarta, iniciando em sua execução no ciclo 3, e a leitura de R1 é feita no ciclo 4 
também. Como o enunciado afirma que os registradores são escritos na primeira 
metade de ciclo, a escrita de R1 no ciclo 4 é efetivada antes da leitura de R1 no ciclo 
4. Portanto, a alternativa B é a correta. 
 
 
Referências: 
 
HENNESSY, John L.; PATTERSON, David. A. Organização e projeto de 
computadores: a interface hardware/software. 3. ed. Rio de Janeiro: Campus, 2005. 
 
STALLINGS, William. Arquitetura e organização de computadores. 8. ed. São 
Paulo: Pearson, 2010. 
 
 
 
 
QUESTÃO Nº 34 
 
Considere a implementação de um compilador em que as etapas de análise léxica e sintática 
possam compartilhar o mesmo processador de forma concorrente. Considere, ainda, uma 
solução para o problema, cujo pseudocódigo é mostrado abaixo. O analisador léxico lê os 
lexemas e identifica os respectivos tokens do arquivo-fonte por meio da chamada ao 
procedimento Leia. O analisador sintático verifica a sequencia dos tokens por meio da 
chamada ao procedimento Case. Os dois processos compartilham a constante N e as 
variáveis buffer, vez e cont. 
constante N = 10; 
inteiro buffer[N], vez = 0, cont = 0; 
Analisador_Lexico: 
01 inteiro token, in = 0; 
02 enquanto verdadeiro faça 
03 Leia(token); 
04 enquanto cont = N-1 aguarde; 
05 enquanto vez = 1 aguarde; 
06 buffer[in] = token; 
07 cont = cont + 1; 
08 vez = 1; 
09 in = (in + 1) mod N; 
10 fim enquanto 
 
Analisador_Sintatico 
11 inteiro token, out = 0; 
12 enquanto verdadeiro faça 
13 enquanto cont = 0 aguarde; 
14 enquanto vez = 0 aguarde; 
15 token buffer[out]; 
16 cont = cont-1; 
17 vez = 0; 
18 out = (out + 1) mod N; 
19 Case(token); 
20 fim enquanto 
 
 
A partir da análise da solução, avalie as asserções a seguir e a relação proposta entre elas. 
 
I. A eliminação da variável cont e das linhas 4,7,13 e 16 causa erro de sincronismo 
entre os processos. 
PORQUE 
II. A variável cont é responsável pelo controle do acesso à seção crítica do código. 
 
A respeito dessas asserções, assinale a opção correta. 
A. As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I. 
B. As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa correta 
da I. 
C. A asserção I é uma proposição verdadeira, e a II é uma proposição falsa. 
D. A asserção I é uma proposição falsa, e a II é uma proposição verdadeira. 
E. As asserções I e II são proposições falsas. 
 
 
 
Gabarito: E 
 
Tipo de questão: Muito difícil 
 
Conteúdo avaliado: Fundamentos e Técnicas de Programação; Sistemas 
Operacionais e Arquitetura de Computadores 
 
Autor(a): Sibelius Lellis Vieira 
 
Comentário: No caso em comento, um processo que executa um analisador léxico 
utiliza a variável cont para indicar se pode colocar um token no buffer no caso dele 
estar cheio e a variável vez para indicar se é a vez do processo executar. Outro 
processo, executando concorrentemente, também utiliza a variável cont para não ler 
os token do buffer caso este esteja vazio e usa variável vez para verificar se é a sua 
vez. Portanto, a variável vez é usada pelo controle de acesso à seção crítica do 
código, e a variável cont para indicar quantos elementos existem no buffer. Trata-se 
de um caso clássico de problema do produtor versus consumidor, compartilhando um 
buffer de memória e variáveis de controle para acesso ao buffer. É correta a 
alternativa E, pois a eliminação da variável cont, para o caso do problema, não afeta o 
processo, dado que a variável vez alterna a execução dos processos. 
 
 
Referências: 
 
SILBERSCHATZ, A.; GAVIN B. P.; GAGNE G. Fundamentos de sistemas operacionais. 8. 
ed. Rio de Janeiro: Elsevier/Campus, 2013. 
TANENBAUM, Andrew S. Sistemas operacionais modernos. 3. ed. São Paulo: 
Prentice-Hall, 2010. 
 
 
 
QUESTÃO Nº 35 
Um prédio de 4 andares, sendo o primeiro andar térreo, é servido por 2 elevadores. Por 
motivo de economia de energia, o elevador 2 só é acionado se for solicitado em mais de 2 
andares. Considere um circuito proposto para habilitar o acionamento do elevador2 
conforme é mostrado a seguir. Ele utiliza um multiplexador 4x1, cuja saída é selecionada 
através da composição dos sinais A e B, que indicam se os andares 1 e 2 solicitaram o serviço 
do elevador. Assim o valor AB=10(2) indica que o primeiro andar solicitou elevador, mas não o 
segundo. Os sinais C e D indicam se os andares 3 e 4 solicitaram o serviço, respectivamente. 
 
 
 
 
Com base na análise do circuito proposto para o problema, avalie as seguintes asserções e a 
relação proposta entre elas. 
 
I. O circuito não atende às especificações do projeto. 
PORQUE 
II. A entrada superior do multiplexador com valor constante 0 indica que a saída 
será 0 independentemente dos valores dos sinais A,B, C e D. 
 
A respeito dessas asserções, assinale a opção correta. 
A. As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I. 
B. As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa correta 
da I. 
C. A asserção I é uma proposição verdadeira, e a II é uma proposição falsa. 
D. A asserção I é uma proposição falsa, e a II é uma proposição verdadeira. 
E. As asserções I e II são proposições falsas. 
 
 
Gabarito: E 
 
Tipo de questão: Difícil 
 
Conteúdo avaliado: Sistemas Digitais 
 
Autor(a): Wilmar Oliveira de Queiroz 
 
Comentário: A condição para acionar o elevador 2 é que seja solicitado por mais de 2 
andares, isto é, 3 ou 4 andares. 
As entradas de endereçamento AB do MUX selecionam qual das 4 entradas vai para a 
saída S (habilita o elevador 2), portanto: 
 
A B S 
0 0 habilita a 1ª entrada, que é 0, então a saída é 0. 
0 1 habilita a 2ª entrada que depende da saída da porta AND (entradas C e 
D) 
1 0 habilita a 3ª entrada que depende da saída da porta AND (entradas C e 
D) 
1 1 habilita a 4ª entrada que depende da saída da porta OR (entradas C ou 
D) 
 
Analisando as entradas C e D nas portas AND e OR: 
 
C D AND OR 
0 0 0 0 
0 1 0 1 
1 0 0 1 
1 1 1 1 
 
Juntando as 4 entradas em uma Tabela Verdade a saída será 1 quando pelo menos 
três entradas estiverem em 1: 
 
A B C D S SAÍDA 
0 0 0 0 0 1ª entrada do MUX, S=0 
0 0 0 1 0 1ª entrada do MUX, S=0 
0 0 1 0 0 1ª entrada do MUX, S=0 
0 0 1 1 0 1ª entrada do MUX, S=0 
0 1 0 0 0 2ª entrada do MUX, S=0 (S=1 somente se C=D=1) 
0 1 0 1 0 2ª entrada do MUX, S=0 (S=1 somente se C=D=1) 
0 1 1 0 0 2ª entrada do MUX, S=0 (S=1 somente se C=D=1) 
0 1 1 1 1 2ª entrada do MUX, S=1 (três entradas em 1) 
1 0 0 0 0 3ª entrada do MUX, S=0 (S=1 somente se C=D=1) 
1 0 0 1 0 3ª entrada do MUX, S=0 (S=1 somente se C=D=1) 
1 0 1 0 0 3ª entrada do MUX, S=0 (S=1 somente se C=D=1) 
1 0 1 1 1 3ª entrada do MUX, S=1 (três entradas em 1) 
1 1 0 0 0 4ª entrada do MUX, S=0 (S=1 somente se C=D=1, ou C ou 
D=1) 
1 1 0 1 1 4ª entrada do MUX, S=1 (três entradas em 1) 
1 1 1 0 1 4ª entrada do MUX, S=1 (três entradas em 1) 
1 1 1 1 1 4ª entrada do MUX, S=1 (três entradas em 1) 
 
Conclusão: 
Asserção I é falsa, pois o circuito atende às especificações. 
Asserção II: é falsa, pois a saída do MUX depende dos valores de A, B, C e D e será 1 
quando 3 ou 4 delas forem 1. 
Então resposta é a opção E. 
 
 
Referências: 
IDOETA, Ivan V.; CAPUANO, Francisco G. Elementos de eletrônica digital. 41. 
ed. São Pulo: Érica, 2012. 
TOCCI, Ronald J.; WIDMER, Neal S. Sistemas digitais: princípios e aplicações. 
11. ed. Rio de Janeiro: Pearson Prentice Hall, 2011.