Classificação: RESTRITA
Questão 1 Considere o seguinte algoritmo descrito em pseudo-código não
estruturado:
a) O(n);
Questão 2: Permutação simples é o tipo de agrupamento ordenado, sem
repetição, em que entram todos os elementos em cada grupo. Considere o
seguinte problema: quantas permutações de n símbolos distintos podem ser
formadas? Trata-se de um problema:
d) O(n!)
Questão 3: O seguinte pseudo-código (Gersting, J.) apresenta o algoritmo de
busca sequencial de elemento x em uma lista com n itens.
a) O(n);
Questão 4: Assinale a alternativa que apresenta em ordem crescente as
complexidades:
b) 10000; nlog2n; n7 ; 3n ; n!
Questão 5: O problema da acessibilidade pode ser enunciado como se segue:
“Dado um grafo orientado G V V, onde V é o conjunto de nós e dois nós
quaisquer vi e vj V, existe um caminho de vi para vj?” A solução a este problema
é dada pelo algoritmo de Warshall, conforme descrito no pseudo-código abaixo:
b) Polinomial O(n3 ).
6-Dado um grafo orientado G V V, onde V é o conjunto de nós e dois nós
quaisquer vi e vj V, existe um caminho de vi para vj? Este problema é conhecido
como
b) Problema da Acessibilidade.
Questão 7: Considere o seguinte trecho de código: Para i de 1 até n faça {grau [i] =
0} Impar=0; Para i de 1 até n faça { Para j de 1 até n faça {Se A[i, j] == 1, então grau[i]
= grau[i] + 1} } Para i de 1 até n faça { Se grau(i) %2 <>0 Impar++}
c) Apenas I e II;
Questão 8: Considere-se o seguinte enunciado: Dado um conjunto S de números
inteiros, determine se há algum sub-conjunto não-vazio de S, cujos elementos são
tais que quando somados apresentam total igual a zero
e) NP
Questão 9: Assinale a alternativa que diz respeito a um problema que apresenta
desempenho polinomial:
e) Detecção de um caminho Euleriano em um Grafo;
Classificação: RESTRITA
Questão 10: Considere o grafo G=(V, A, g), onde: V = {1, 2, 3, 4, 5, 6, 7, 8} são os
vértices
c) Apenas I e II;
Questão 11: (Fundamentada na questão 36 de ENADE 2011) “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
d) Apenas I, II e III;
Questão 12: “O estudo da complexidade computacional destina-se a estabelecer
uma classificação quantitativa das linguagens decidíveis, de acordo com a
quantidade de esforço que a máquina de Turing deve dispender para processar
suas cadeias de entrada” (Neto J, J.)
e) Apenas III
Questão 13: Em uma determinada edificação, onde o esquema de segurança é
crucial, deseja-se cobrir todas as áreas de circulação e ao mesmo tempo
minimizar o número de pontos de monitoração. Sabe-se que o número de salas
deste lugar é 30 e o número de corredores é 15. A fim de se obter exatamente o
menor número de pontos de monitoração de forma a cobrir todos os corredores,
deveriam ser realizados cálculos de complexidade:
a) fatorial;
Questão 14: É possível classificar os problemas com base na computabilidade de
suas soluções utilizando-se a Máquina de Turing como referencial. Considere as
demais afirmações a respeito da Máquina de Turing:
d) Apenas II e IV
Questão 15: O problema do caixeiro viajante (Travelling Salesman Problem – TSP) é
de natureza combinatória e é uma referência para diversas aplicações, tais como
projeto de circuitos integrados, roteamento de veículos, programação de
produção, robótica, etc. Em sua forma mais simples, no
c) I, II e III;
Questão 16: Considere os seguintes problemas: I – O problema da mochila pode
ser definido como: Dado um conjunto S = {a1, a2, ..., an} de números inteiros não
negativos, todos representados em binário, há um subconjunto P de S tal que a
soma de todos os elementos de P é igual a K?
d) I, II, III, IV e V;
Questão 17: Considere as seguintes afirmações I - Encontrar o maior subconjunto
C de vértices, tal que todos os pares de vértices distintos, formados a partir dos
Classificação: RESTRITA
elementos do conjunto C sejam adjacentes (ou seja, são interligados por uma
aresta) é um problema da classe NP;
d) apenas I;
Questão 18: Considere as seguintes afirmações e assinale a alternativa correta. I –
Se qualquer problema NP – completo pode ser resolvido em tempo polinomial,
então P = NP.
b) São verdadeiras apenas as afirmações II e III.
Questão 19: Considere as seguintes questões: I – Dado um conjunto S = {a1, a2,
..., an} de números inteiros não negativos, todos representados em binário, há um
subconjunto P S tal que ai = K? A busca pela resposta a este problema é NP-
completo;
d) Apenas I e III;
Questão 20: Assinale a alternativa que representa um problema NP-Completo:
e) Problema do Ciclo Hamiltoniano