MO417 - QUESTÃO PARA A PROVA ORAL


Número:


Enunciado: Dada as seguintes afirmações abaixo, assinale a alternativa correta.

I. Se A é redutível em tempo polinomial a B e B é redutível em tempo polinomial a C, então A é redutível em tempo polinomial a C.

II. Cobertura de Vértice, Clique e Ciclo Hamiltoniano são problemas da classe NP-Completo.

III. Se A é redutível polinomialmente a B e se B ∈ P, então A ∈ P.

a) Somente I e II estão corretas
b) Somente I e III estão corretas
c) Somente II e III estão corretas
d) Todas estão corretas
e) NDA



Ideia original de: Ademar Takeo Akabane

MO417 - QUESTÃO PARA A PROVA ORAL


Número:


Enunciado: A matriz de peso abaixo, representa o grafo G=( V, E) acíclico orientado ponderado. Em cada célula dessa matriz, representada pela linha u e coluna v, é armazenado o peso w da aresta (u,v).

\	R	S	T	U	V
R	∞	1	2	∞	-1
S	∞	∞	∞	-3	-1
T	∞	-2	∞	-1	∞
U	∞	∞	∞	∞	1
V	∞	∞	∞	∞	∞

OBS: w = ∞, significa que  (u,v) ∉ E.

Denotamos por δ(u, v) o caminho mais curto a partir do vértice u até o vértice v no grafo.
Assinale a alternativa correta:

a) δ( R, V) = -2
b) δ( R, S) = 1
c) δ( T, V) = 0
d) δ( R, U) = 1
e) NDA


Ideia original de: Ademar Takeo Akabane

MO417 - QUESTÃO PARA A PROVA ORAL


Número:


Enunciado: Considere o grafo abaixo, execute uma busca em profundidade. Suponha que as listas de adjacências estejam em ordem alfabética. Toda vez que for reiniciá-lo, pegue o primeiro vértice em ordem alfabética que ainda não foi visitado.
Com base na classificação das arestas da busca em profundidade, pode-se dizer que o algoritmo encontrará durante o percurso:

Lembrete: 

I) Arestas de Árvore: faz parte de uma árvore de busca em profundidade;

II) Aresta de Retorno: liga um descendente a um ancestral;

III) Arestas Diretas: liga um ancestral a um descendentes;

IV) Arestas Cruzadas: as demais.

a) 7 Arestas de Árvore e 2 Arestas de Retorno
b) 2 Arestas de Diretas e 2 Arestas de Cruzadas
c) 8 Arestas de Árvore e 1 Arestas de Retorno
d) 2 Arestas de Diretas e 3 Arestas de Cruzadas
e) NDA 

Ideia original de: Ademar Takeo Akabane

MO417 - QUESTÃO PARA A PROVA ORAL


Número:


Enunciado: Cada alternativa abaixo (exceto a alternativa e) exibe um conjunto de chaves em percurso de pós-ordem de uma árvore. Qual das alternativas obedece a propriedade de árvore de pesquisa binária?

a) { 1, 4, 7, 5, 3, 9, 12, 18, 16, 11, 8 }
b) { 1, 4, 3, 5, 7, 9, 12, 18, 16, 11, 8 }
c) { 1, 4, 7, 5, 3, 9, 12, 11, 16, 18, 8 }
d) { 1, 4, 3, 5, 7, 9, 16, 18, 12, 11, 8 }
e) NDA



Ideia original de: Ademar Takeo Akabane

MO417 - QUESTÃO PARA A PROVA ORAL


Número:


Enunciado: Dado o algoritmo abaixo:

ACTIVITY_SELECTOR( s,f )
1  n <- comprimento[s]
2  A <- {a_n}
3  K <- n
4  for m <- n-1 to 1 do
5     if s[m] >= f[k] then
6         A <- A U {a_m}
7         k <- m
8  return A

Assinale a alternativa correta:

a) O subconjunto maior de atividades mutuamente compatível será no caso, em que a entrada dos dados forem colocados monotonicamente descrescente de tempo de término.

b) O subconjunto maior de atividades mutuamente compatível será no caso, em que a entrada dos dados forem colocados monotonicamente crescente de tempo de término.

c) O subconjunto maior de atividades mutuamente compatível será no caso, em que a entrada dos dados forem colocados monotonicamente descrescente de tempo de início.

d) O subconjunto maior de atividades mutuamente compatível será no caso, em que a entrada dos dados forem colocados monotonicamente crescente de tempo de início.

e) NDA




Ideia original de: Ademar Takeo Akabane

MO417 - QUESTÃO PARA A PROVA ORAL


Número:


Enunciado: Com base na matriz de programação dinâmica abaixo, assinale a alternativa que possui uma subsequência comum mais longa (LCS-Length) entre as sequências X=(PIONNER) e Y=(SPRINGTIME).

\	Yi	S	P	R	I	N	G	T	I	M	E
Xi	0	0	0	0	0	0	0	0	0	0	0
P	0	0	1	1	1	1	1	1	1	1	1
I	0	0	1	1	2	2	2	2	2	2	2
O	0	0	1	1	2	2	2	2	2	2	2
N	0	0	1	1	2	3	3	3	3	3	3
N	0	0	1	1	2	3	3	3	3	3	3
E	0	0	1	1	2	3	3	3	3	3	4
R	0	0	1	1	2	3	3	3	3	3	3

a) P O N E
b) I O E R
c) I N E R
d) P I N E
e) NDA


Ideia original de: Ademar Takeo Akabane

MO417 - QUESTÃO PARA A PROVA ORAL


Número:


Enunciado: Dadas as seguintes afirmações:

I. Radix Sort é mais vantajoso que Merge Sort quando d < lgn, isto é, o número de dígitos for menor que lgn.
II. QuickSort e HeapSort são métodos de ordenação *in-place. Já Merge Sort e Counting Sort não são.
III. O algoritmo de seleção (SELECT), tempo de execução O(n) no pior caso, localiza o elemento desejado particionando recursivamente o arranjo de entrada. Sabe-se que o algoritmo de particionamento utilizado é o PARTITION do Quick Sort modificado.

a) Apenas I é correta
b) Apenas II é correta
c) I e II são corretas
d) II e III são corretas
e) NDA

*Um algoritmo de ordenação é in-place se a memória adicional requerida não depende do tamanho do vetor que está sendo ordenado.


Ideia original de: Ademar Takeo Akabane