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

MO417 - QUESTÃO PARA A PROVA ORAL


Número:


Enunciado: Assinale a alternativa INCORRETA sobre os algoritmos de ordenação.

a) Radix Sort é mais vantajoso que Merge Sort quando d < lgn, isto é, o número de dígitos for menor que lgn.
b) QuickSort e HeapSort são métodos de ordenação *in-place. Já Merge Sort e Counting Sort não são.
c) Os elementos do Bucket Sort são números reais uniformente distribuídos no intervalo [0..1).
d) Para que Radix Sort funcione adequadamente, este deve utilizar um método de ordenação estável, por exemplo, Quick Sort.
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

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Um algoritmo de ordenação é estável, se a ordem relativa dos itens com elementos iguais não é alterada após a ordenação. Dados os algoritmos de ordenação abaixo, qual(is) dele(s) é(são) estável(is)?

I. Insertion Sort

II. Merge Sort

III. Heapsort

a) Apenas I é correta

b) Apenas II é correta

c) I e II são corretas

d) II e III são corretas

e) NDA

Ideia original de: Ademar Takeo Akabane

MO417 - QUESTÃO PARA PROVA ORAL

Número:

Enunciado: Dadas as seguintes afirmações:

I. f(n)= 5n³+7 e g(n) = 2ⁿ, então g(n) Є Ω f(n).
II. Se f(n) Є O(g(n)), então f(n) cresce no máximo tão rapidamente quanto g(n).
III. Se f(n) = 4 ^logn e g(n) (3/2)ⁿ, então, f(n) = Ω(g(n)).

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

Ideia original de: Ademar Takeo Akabane