MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-052

Enunciado: Suponha que a sequência de números 5,8,2,6,1,7 é inserida na ordem dada em uma árvore binária de busca A vazia, sem qualquer procedimento de balanceamento. Logo após, o nó com chave 6 é removido da árvore.

Qual a alternativa correta sobre a árvore resultante?

A) A árvore terá altura 3 e nó 8 terá profundidade 2;
B) A árvore terá altura 2 e nó 2 terá profundidade 1;
C) A árvore terá altura 3 e nó 5 terá profundidade 0;
D) A árvore terá altura 2 e nó 1 terá profundidade 1;
E) NDA

Ideia original de: Félix Carvalho Rodrigues

MO417 - Questão para a prova oral

Número: 2013-051

Enunciado: Em um grafo não orientado, com n vértices, determine a quantidade mínima e máxima, respectivamente, de arestas que pode haver para obtermos k componentes conexas.  Considere que não há mais de uma aresta entre dois vértices e que não há laços (um laço seria uma arestas com vértices idênticos nas extremidades).

a) n+k e n^k
b) n e (n-k)²
c) n-k e n(n-1)/2
d) n-k  e (n-k+1)(n-k)/2
e) NDA

Ideia original de: Jacqueline Midlej do Espírito Santo

MO417 - Questão para a prova oral

Número: 2013-046

Enunciado: Considere as seguintes cidades em uma árvore de busca binária, de altura 3:

Belém	Fortaleza	Recife
Belo Horizonte	Goiânia	Rio de Janeiro
Brasília	Guarulhos	Salvador
Campinas	Manaus	São Luís
Curitiba	Porto Alegre	São Paulo

 

Qual é a sequência correta de busca nesta árvore, se procuramos a cidade Natal?

1. Guarulhos, Campinas, Fortaleza, Goiânia.
2. Guarulhos, Rio de Janeiro, Porto Alegre, Manaus.
3. Guarulhos, Rio de Janeiro, Porto Alegre, Recife.
4. Guarulhos, Rio de Janeiro, São Luis, Salvador.
5. NDA 

Ideia original de: Julián Esteban Gutiérrez Posada

MO417 - Questão para a prova oral

Número: 2013-050

Enunciado: Árvores rubro-negras podem ser implementadas sem o apontador para o pai nos nós. Isso economiza ϴ(n) de espaço na estrutura de dados. Qual das seguintes operações NÃO poderá ser realizada em tempo O(lg n) numa árvore assim?

a)  Inserção.
b)  Sucessor.
c)  Busca.
d)  Deleção.
e)  N.D.A.

Ideia original de:  René du Raymond Sacramento

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-049

Enunciado: Qual dos nós da árvore abaixo, se tiver o valor ou a cor alterados, faz com que a árvore obedeça todas as propriedades de uma árvore rubro-negra?

a) 4
b) 10
c) 12
d) 14
e) NDA

Ideia original de: Raphael Azzolini

MO417 - Questão para a prova oral

MO417 - Questão para a prova oral

Número: 2013-048

Enunciado: O seguinte algoritmo insere o nó z numa árvore binária de busca T.

TREE-INSERT(T,z)
1   y = NIL
2   x = T.root
3   while x <> NIL
4   y  = x
5 if z.key < y.key
6 x = x.left
7  else x = x.right
8   z.p = y
9   if y == NIL
10 T.root = z // tree T was empty
11 elseif z.key < y.key
12     y.left = z
13 else y.right = z

Depois de inserir os seguintes elementos (nessa ordem): 4, 6, 1, 2, 5, 9, 7 numa árvore vazia T, qual chave não fica numa folha de T?

a) 9
b) 7
c) 5
d) 2
e) NDA

Ideia original de: John Edgar Vargas Muñoz

MO417 - QUESTÃO PARA PROVA ORAL

Número: 2013-047


Enunciado: O conjunto de chaves { 3, 7, 5, 19, 18, 15, 25, 20, 10} exibe o percurso em pós-ordem de uma árvore de pesquisa binária. Qual alternativa exibe a chave e a altura ou profundidade correta de um nó desta árvore? Nota: a altura de um nó x é o número de arestas no caminho de x ao seu descendente mais distante; e a profundidade de um nó x é o número de arestas no caminho de x ao seu ascendente mais distante.

1. chave=7, profundidade=1
2. chave=15, altura=3
3. chave=19, profundidade=4
4. chave=20, altura=2
5. NDA.

Ideia original de: Laurindo de Sousa Britto Neto

MO417 - QUESTÃO PARA A PROVA ORAL

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-045

Enunciado: Suponha que um algoritmo de Huffman tenha sido projetado para codificar sequências de DNA em arquivos binários. A figura abaixo contém a árvore binária que representa a montagem de códigos livres de prefixos para os nucleotídeos A, T, G e C. Nesta árvore, cada nó interno é rotulado com a soma das frequências das folhas de suas sub-árvores.

Selecione a alternativa cujo conteúdo preenche corretamente as folhas w, x, y e z, nesta ordem, com o nucleotídeo e sua respectiva frequência, bem como contém o código correspondente à sequência AATGGC:

1. w = C : 40; x = T : 35, y = G : 10; z = A : 15; 1011011001000
2. w = G : 40; x = C : 35, y = A : 15; z = T : 10; 100100101001
3. w = A : 40; x = G : 35, y = T : 10; z = C : 15; 0010011110101
4. w = C : 40; x = A : 35, y = G : 15; z = T : 10; 11111011001000
5. N.D.A.

Ideia original de: Daniel Henriques Moreira

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-044

Enunciado: Para um conjunto finito de possíveis valores de moedas, deseja-se resolver o problema: "Encontrar o menor número de moedas para compor o troco de uma compra".  Uma abordagem plausível é utilizar o seguinte algoritmo guloso:

1. Escolhe-se a moeda de maior valor possivel que seja menor ou igual ao troco
2. Resolve-se o problema novamente descontando do troco inicial o valor da moeda escolhida no passo 1.

Qual dos conjuntos de valores de moedas faz com que o algoritmo acima retorne sempre uma solução ótima? Suponha que exista um estoque infinito de moedas de cada valor.

1. {1, 2, 10, 15, 30}
2. {1, 5, 10, 25, 50} 
3. {1, 2, 10, 25, 50}
4. O algoritmo guloso acima sempre retorna soluções ótimas
5. NDA

Ideia original de: Daniel Vidal

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-043

Enunciado: Usando código de Huffman, qual seria uma codificação ótima para os caracteres a, b, c, d, e, f, respectivamente, que aparecem com frequências 40, 20, 15, 10, 10, 5, respectivamente?

A) 0, 10, 101, 110, 1110, 1111
B) 0, 10, 110, 1110, 11110, 11111
C) 0, 100, 101, 110, 1110, 1111
D) 1, 10, 110, 1110, 11110, 11111
E) NDA

Ideia original de: Fabrício Matheus Gonçalves

MO417 - Questão para a prova oral

Número: 2013-042

Enunciado: Seja F={a:45, b:13, c:12, d:16, e:9, f:5} um conjunto de caracteres e suas respectivas frequências, e o seguinte algoritmo de Huffman:

HUFFMAN(C)
1   n = |C|
2   Q = C
3   for i = 1 to n-1
4       allocate a new node z
5       z.right = x = EXTRACT-MIN(Q)
6       z.left = y = EXTRACT-MIN(Q)
7       z.freq = x.freq + y.freq
8       INSERT(Q,z)
9   return EXTRACT-MIN(Q)

A chamada HUFFMAN(F) gera qual árvore:

a)

b)

c)

 
d)

 
e) NDA.


Ideia original de: Carlos Eduardo Alfaro Morales

MO417 - QUESTÃO PARA A PROVA ORAL

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-041

Enunciado: Um ladrão entrou em um estabelecimento que vende produtos em pó para roubar ouro. Ele consegue carregar 5 kg, mas o estabelecimento só tinha 2kg de ouro em estoque. O ladrão então resolveu levar outros produtos, até completar o peso máximo que ele aguenta.  Considerando a quantidade em estoque e os valores dos produtos mostrados na tabela abaixo, quais produtos o ladrão irá levar se ele quiser maximizar o valor total dos produtos levados?

Produto	Quantidade em Estoque	Preço Total do Estoque
Ouro	2 kg	R$ 200.000
Leite em pó	150 kg	R$ 150
Areia	20 kg	R$ 40
Minério de ferro	1 kg	R$ 100
Pó de serra	2.000 toneladas	R$ 20.000

1. Ouro, leite em pó e areia.
2. Ouro, leite em pó e minério de ferro.
3. Ouro, pó de serra e areia.
4. Ouro, areia e minério de ferro.
5. N. D. A.

Ideia original de: Hilário Seibel Júnior

MO417 - Questao para a prova oral

Número: 2013-040

Enunciado: Algoritmos gulosos fornecem um método elegante e simples para selecionar um conjunto de tamanho máximo de atividades mutuamente compatíveis, auxiliando a solução eficaz de vários problemas. Considere o conjunto S de atividades (onde si é o momento de início e fi é o momento de término da atividade ai):



Analisando o conjunto acima, utilizando algoritmos gulosos, pode-se afirmar que um subconjunto mutuamente compatível de tamanho máximo é:

a. {a1, a4, a8, a11}
b. {a2, a4, a5, a9}
c. {a3, a5, a9, a11}
d. {a3, a9, a7, a11}
e. NDA

Ideia original de: Ederlon Barbosa

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-039

Enunciado: Um arquivo bitmap, contendo um conjunto de 100 pixels, foi compactado através do algoritmo de Huffman. Seguindo a quantidade de pixels por cor apresentada abaixo, responda: qual é o tamanho (em bits) deste arquivo de pixels após a compactação?

COR	Red	Green	Blue	Black	White	TOTAL
Número de Pixels	5	10	15	20	50	100

a. 165
b. 175
c. 185
d. 195
e. NDA

Ideia original de: Anderson Coelho Weller

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-038

Enunciado: Suponha que uma sequência de DNA tenha sido transcrita para um arquivo X onde cada molécula A,C,G,T é representada por 2 bits. Deseja-se diminuir o tamanho desse arquivo, alterando a representação das moléculas, e para isso será utilizado o algoritmo de Huffman.

Dado que as frequências dos caracteres A,C,G,T no arquivo X são respectivamente: 11%, 22%, 43%, e 24%, assinale a alternativa na qual a representação descrita poderia ser obtida pelo algoritmo de Huffman:

A) O algoritmo retorna a seguinte representação: A=110, C=111, G=0, T=10
B) O algoritmo retorna a seguinte representação: A=000, C=101, G=1, T=01
C) O algoritmo retorna a seguinte representação: A=11, C=101, G=100, T=0
D) O algoritmo retorna a seguinte representação: A=00, C=01, G=11, T=10
E) NDA

Ideia original de: Félix Carvalho Rodrigues

MO417 - Questão para a prova oral

Número: 2010-042

Enunciado: No problema de seleção de atividades, considere o conjunto de atividades ilustrado na tabela abaixo, onde i é o índice de uma atividade, s_i é um tempo de início e f_i é um tempo de término, ambos medidos em horas. Qual o número mínimo de salas que seriam necessárias para acomodar todas as atividades, levando em conta que são gastos 5 minutos para limpeza e preparação entre atividades consecutivas que ocorrem numa mesma sala?

i	1	2	3	4	5
si	1	3	4	5	6
fi	4	5	6	7	8

1. 2 salas.
2. 3 salas.
3. 4 salas.
4. 5 salas.
5. NDA

Ideia original de: Maikon Cismoski dos Santos

MO417 - Questão para a prova oral

Número: 2010-038

Enunciado: Qual das seguintes entradas produz uma codificação de Huffman na qual todos os caracteres são representados com o mesmo número de bits?

1. char.	a	b	c	d
   freq.	3	5	8	13

2. char.	a	b	c	d
   freq.	14	15	3	4

3. char.	a	b	c	d
   freq.	16	20	19	15

4. char.	a	b	c	d
   freq.	34	46	11	23

5. NDA

Ideia original de: Marcos Vinícius Mussel Cirne

MO417 - Questão para a prova oral

Número: 2010-033

Enunciado: Qual das alternativas não é uma subsequência comum às cadeias "ACCAGGTCGAG" e "GTACGTTCGGA"?

1. ACGTGA
2. AGTCAG
3. CGTCGA
4. GGTCGG
5. NDA

Ideia original de: Alisson Pontes

MO417 - Questão para a prova oral

Número: 2009-080

Enunciado: Usando o algoritmo de Huffman e adotando que quem sai do heap primeiro ganha o bit 0, qual é o código para a seguinte entrada?

	a	b	c
f	40	20	30

1. a	b	c
   0	10	11

2. a	b	c
   1	00	01

3. a	b	c
   1	01	00

4. a	b	c
   0	11	10

5. NDA

Ideia original de: Robson Roberto Souza Peixoto

MO417 - Questão para a prova oral

Número: 2009-077

Enunciado: Suponha um arquivo com 100 mil caracteres (a, b, c, d, e, f), com as seguintes frequências de aparecimento de cada caractere no arquivo, e palavras de código de comprimento fixo e variável dadas pela seguinte tabela:

Caracteres do arquivo	a	b	c	d	e	f
Frequência	30.000	25.000	15.000	12.000	11.000	7.000
Códigos de comprimento fixo	000	001	010	011	100	101
Códigos de comprimento variável	11	01	101	100	001	000

Obs: Códigos de prefixo são códigos nos quais nenhuma palavra de código é prefixo de outra.
Assinale a alternativa INCORRETA:

1. A representação por códigos de comprimento fixo ocupa um espaço de 300.000 bits para codificar este arquivo.
2. É possível economizar espaço para codificar este arquivo, utilizando apenas 245.000 bits com o código de comprimento variável.
3. Podemos representar a palavra "cabe" utilizando o código de prefixo de comprimento variável da seguinte forma: 1011101001.
4. A cadeia 0101101 representa "bbc" no código de prefixo de comprimento variável.
5. NDA

Ideia original de: Ivo Kenji Koga

MO417 - Questão para a prova oral

Número: 2009-072

Enunciado: Considere o algoritmo abaixo, concebido para selecionar as moedas que devem ser devolvidas a um cliente como troco numa máquina do tipo Vending para cafés e bebidas quentes. O algoritmo deve escolher o menor número de moedas possível, para manter sempre uma quantia de moedas razoável no "caixa" da máquina. Caso não haja nenhuma combinação de moedas para o troco, o algoritmo deve retornar uma mensagem avisando ao cliente.  As moedas disponíveis no caixa da máquina estão em ordem decrescente (esta ordem é mantida por outro módulo da máquina). Nomeamos o conjunto de moedas no caixa como C, e seus valores pertencem ao conjunto { 0.01, 0.05, 0.10, 0.25, 0.50 }.  A idéia foi escrever um algoritmo guloso onde cada moeda m escolhida seria a de maior valor em C, ainda não escolhida, que acrescentada à soma dos valores das moedas já escolhidas não ultrapassasse o valor desejado para o troco:

   MONTA-TROCO(C,t)
    M ← {∅}
    soma_M ← 0
    i ← 1
    n ← comprimento[C]
    while (soma_M < t) and (i < n)
     do m ← C[i]
        if (soma_M + m) ≤ t
      then M ← M U {m}
           soma_M ← soma_M + m
        i ← i + 1
    if soma_M = t
     then return M
     else return "Troco não disponível!"
    

onde C é o conjunto de moedas atualmente no caixa da máquina e t é o valor do troco que se deseja compor.

Dentre as características abaixo, quais são as que se aplicam ao algoritmo proposto:

I - Pode retornar um troco de valor diferente do correto;
II - Pode retornar uma quantidade de moedas maior do que o mínimo possível (considerando as moedas disponíveis no "caixa" da máquina);
III - Pode dizer ao cliente que não há troco quando na verdade haveria uma combinação de moedas possível para aquele troco.

1. apenas I
2. apenas I e II
3. apenas II e III
4. apenas III
5. NDA

Ideia original de: Fernando José Vieira da Silva

MO417 - Questão para a Prova Oral

Número: 2003-112

Enunciado: Considere as seguintes freqüências:

A: 15

B: 13

C: 12

D: 6

E: 25

F: 7

Utilizando o algoritmo de Huffman podemos obter qual dos seguintes códigos de prefixo para cada caractere:

A) A:01; B: 00; C: 100; D: 1010; E: 11; F: 1011
B) A:0; B: 0101; C: 0100; D: 0110; E: 011; F: 10
C) A:01; B: 11; C: 0000; D: 0001; E: 001; F: 10110
D) A:011; B: 0101; C: 0100; D: 010; E: 00; F: 01000
E) N.D.A.
 
Ideia original de: Camila Ribeiro Rocha

MO417 - Questão para a prova oral

Número: 2003-104

Enunciado: Sobre códigos de Huffman, podemos afirmar que:

A) é um código de prefixo ótimo, pois utiliza códigos de comprimento fixo
B) quanto maior a frequência de um caracter, maior será o número de bits a ele atribuido
C) pode sempre ser representado por uma árvore binária cheia (full binary tree), construída de baixo para cima através do agrupamento das menores frequências dos caracteres
D) é um código de prefixo ótimo que só pode ser construído utilizando-se a abordagem de programação dinâmica, já que a abordagem gulosa não fornece uma solução ótima
E) NDA

Ideia original de: Alexandro Baldassin

MO417 - Questão para a prova oral

Número: 2003-098

Enunciado: Assuma que você tenha um problema cujas soluções possuam um valor associado "c". Suponha que você queira achar uma solução que maximize o valor de "c". Lendo artigos sobre o assunto, você descobriu que existe um algoritmo que utiliza programação dinâmica para encontrar esta solução. O artigo onde você encontrou este algoritmo provava formalmente que o algoritmo está correto, mas você tem a impressão que um algoritmo guloso poderia ser muito mais eficitente, embora você saiba que provar a corretude do algoritmo guloso não será fácil. Você resolve  implementar ambos os algoritmos e comparar algumas soluções para ver se a abordagem gulosa não falha logo de cara. Que tipo de resultado mostraria que o guloso NÃO funciona?

A) Tanto as soluções encontradas pelos algoritmos quanto os valores de "c" para estas soluções são diferentes para uma mesma entrada.
B) Tanto as soluções encontradas pelos algoritmos quanto os valores de "c" para estas soluções são iguais para uma mesma entrada.
C) Tanto as soluções encontradas pelos algoritmos quanto os valores de "c" para estas soluções são iguais para uma mesma entrada, mas o algoritmo guloso não resolve todos os subproblemas que o algoritmo de programação dinâmica resolve.
D) As soluções encontradas pelos algoritmos podem ser diferentes, mas os valores de "c" para as soluções sempres são iguais para uma mesma entrada.
E) NDA

Ideia original de: José Augusto Amgarten Quitzau

MO417 - Questão para a prova oral

Número: 2003-078

Enunciado:
Suponha que você tenha usado duas seqüências "A" e "B" como dados de entrada para um algoritmo de programação dinâmica que resolve o problema da maior subseqüência comum entre duas seqüências. Como resultado, você obteve a seqüência "C". Neste contexto, é correto afirmar que

A) Certamente não há outra subseqüência comum a "A" e "B" com o mesmo comprimento que "C".
B) Certamente não há subseqüência comum a "A" e "B" com comprimento menor que "C".
C) Pode haver uma subseqüência comum a "A" e "B" com comprimento maior que "C", mas somente "C" é uma subseqüência de comprimento ótimo.
D) Dependendo de "A" e "B", pode haver outras seqüências com o mesmo comprimento que "C".
E) NDA

Ideia original de: José Augusto Amgarten Quitzau

MO417 - Questão para a prova oral 

Número: 2003-075

Enunciado: A programação dinâmica em geral é aplicada a problemas:

A) de otimização
B) de busca linear
C) de ordenação
D) que não envolvam repetição de subproblemas
E) NDA

Ideia original de: Alexandro Baldassin

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-037

Enunciado: Considere o problema de encontrar a rota máxima do topo até a base de um triangulo usando apenas elementos adjacentes, sendo um de cada linha.  Por exemplo, x+y+d+c, marcada em vermelho na figura,  seria uma rota possível no triangulo a seguir:

x

y   z

a   d   e

b   c   f   g

Para um triângulo com n elementos, NÃO seria correto afirmar que:

A) Com uma estratégia de programação dinâmica bottom-up podemos conseguir complexidade assintótica menor do que com uma estratégia de programação dinâmica top-down.
B) a = a + max(b, c) seria parte de uma estratégia de programação dinâmica bottom-up para resolver o problema.
C) f = f + max(d, e) seria parte de uma estratégia de programação dinâmica top down para resolver o problema.
D) Existe um algoritimo O(2^h) que usa forca bruta para calcular todas as possíveis somas, onde h é a altura do triângulo.
E) NDA

Ideia original de: Fabrício Matheus Gonçalves

MO417 - Questão para a prova oral

MO417 - Questão para a prova oral

Número: 2013-036

Enunciado: Considere a seguinte versão do algoritmo para calcular números de Fibonacci:

FIBONACCI(n)
1 Criar arranjo Fib[1..n]
2 for i=1 to n
3    do Fib[i]=-1
4 Fib[1]=1
5 Fib[2]=1
6 return LOOKUP-FIB(Fib,n)

LOOKUP-FIB(Fib,n)
1 if (Fib[n]>0)
2   then return Fib[n]
3   else
4       return Fib[n]=LOOKUP-FIB(Fib,n-1) + LOOKUP-FIB(Fib,n-2)

Podemos AFIRMAR que:

a) Trata-se um algoritmo memoizado com tempo de execução O(n)
b) Não é um algoritmo memoizado mas seu tempo de execução é O(lg n)
c) Somente é um algoritmo recursivo com tempo de execução O(2^n)
d) É um algoritmo memoizado com tempo de execução O (lg n)
e) NDA

Ideia original de: Marleny Luque Carbajal

MO417 - Questão para a prova oral

Número: 2013-035

Enunciado: Considere as sequências S₁= MVIVSMV e S₂= VSIMVM.
Assinale a alternativa correta.

a) Existe uma única subsequência comum mais longa entre S1 e S2
b) Existem duas subsequências comuns mais longas entre S1 e S2
c) Existem três subsequências comuns mais longas entre S1 e S2
d) Existem quatro subsequências comuns mais longas entre S1 e S2
e) N.D.A

Ideia original de: Danielle Furtado dos Santos Dias

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-034

Enunciado: Seja A(n) o seguinte algoritmo:

    A(n):
        for i in 1..n:
            X[i] = -1
        return R(X,n)
    R(X,n):
        if X[n] >= 0:
            return X[n]
        else:
            if n <= 2:
                x = 1
            else:
                x = R(X,n-1)+R(X,n-2)
            X[n] = x
            return x

e B(n) o seguinte algoritmo:

    B(n):
        for i in 1..n:
            if i<=2:
                X[i] = 1
            else:
                X[i] = X[i-1] + X[i-2]
        return X[n]

Qual afirmação NÃO é verdadeira?

A) Ambos os algoritmos levam O(n) passos no pior caso.

B) O algoritmo A é uma versão memoizada do algoritmo recursivo de Fibonacci.

C) O algoritmo B é uma versão do algoritmo de Fibonacci que utiliza programação dinâmica.

D) Ambos os algoritmos retornam o n-ésimo número de Fibonacci para qualquer natural n.

E) NDA

 Ideia original de: Félix Carvalho Rodrigues

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-033

Enunciado: Considere o problema de encontrar a Subcadeia Comum mais Longa (LCS), definindo como LCS(A,B) o tamanho da subcadeia comum mais longa entre as strings A e B. Tomando A="ALFABETO" e B="HABITAT" e o subproblema A'="ALFA" e B'="HABI", podemos afirmar que:

a) LCS(A',B') + LCS(A-A',B-B') = LCS(A,B) - 1
b) LCS(A',B') + LCS(A-A',B-B') = LCS(A,B)
c) LCS(A',B') + LCS(A-A',B-B') = LCS(A,B) + 1
d) LCS(A',B') + LCS(A-A',B-B') = LCS(A,B) + 2
e) NDA.

Ideia original de: Lucas Miguel de Carvalho

MO417 - Questão para a prova oral

MO417 - Questão para a prova oral

Número: 2013-031

Enunciado: Considere o algoritmo SELECT a seguir, que retorna o i-ésimo menor elemento de um arranjo de entrada de tamanho n:

1: Dividir os n elementos do arranjo de entrada em grupos de 5 elementos cada e no máximo um grupo formado pelos n mod 5 elementos restantes.

2: Encontrar a mediana de cada um dos ceil(n/5) grupos, através da ordenação por inserção dos elementos de cada grupo (nos quais existem 5 elementos, no máximo), e posterior escolha do elemento do meio (se houver, dois, tomar o menor).

3: Usar SELECT recursivamente para encontrar a mediana x das ceil(n/5) medianas localizadas na Etapa 2. Se celi(n/5) for par, então x será a mediana inferior.

4: Particionar o arranjo de entrada em torno da mediana de medianas x, em tempo linear. Seja k uma unidade maior que o número de elementos no lado baixo da partição, de forma que x seja o k-ésimo menor elemento e existam n - k elementos no lado alto da partição.

5: Se i = k, então retornar x. Caso contrário, usar SELECT recursivamente para encontrar o i-ésimo menor elemento no lado baixo se i < k, ou então o (i - k)-ésimo menor elemento no lado alto, se i>k.

No processo de obter o 2° menor elemento do arranjo:

 <3,1,2,6,9,10,15,4,5,8,7,13,12>,

indique quais são as medianas encontradas na Etapa 2, depois da primeira chamada recursiva do algoritmo SELECT na Etapa 5:

a) 4 e 2

b) 5 e 3

c) 6 e 2

d) 8 e 3

e) NDA

Ideia original de: Marleny Luque Carbajal

MO417 - QUESTÃO PARA A PROVA ORAL

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-030

Enunciado: Leonardo prestou um concurso público com 30 vagas e está tentando descobrir sua classificação final. Entretanto, foi divulgada apenas uma lista na qual cada elemento possui o número de inscrição de um candidato e sua respectiva nota final. Infelizmente, a lista está ordenada pelo número de inscrição e não pela nota. Para saber se foi aprovado, Leonardo precisa comparar sua nota com a do candidato que ficou em 30o. lugar.

Considerando o estado da arte em teoria de algoritmos, o que podemos oferecer a pessoas que queiram obter o 30o. elemento numa lista de tamanho n?

1. Os melhores algoritmos conhecidos para este problema gastam Ω(n lg n) unidades de tempo.
2. É possível conseguir a resposta desejada em tempo linear em n.
3. Exsitem algoritmos que resolvem tais problemas em tempo O(lg n).
4. Nenhum algoritmo para este problema usa menos do que tempo Ω(n²).
5. N. D. A.

Ideia original de: Hilário Seibel Júnior

MO417 - QUESTÃO PARA A PROVA ORAL

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-029


Enunciado: Tomando-se o algoritmo abaixo, que seleciona o i-ésimo menor elemento de um arranjo a, desde que i esteja entre 1 e o tamanho de a, auxiliado pelo algoritmo PARTICIONA:

01. SELECIONA(a: arranjo, i)
02.    se a.tamanho > 0
03.       inicio = 1
04.       fim = a.tamanho
05.       enquanto inicio < fim
06.          q = PARTICIONA(a, inicio, fim)      
07.          k = q - inicio + 1
08.          se i == k
09.             retorna a[q]
10.          senão se i < k
11.             fim = q - 1
12.          senão
13.             inicio = q + 1
14.             i = i - k
15.       retorna a[inicio]
16.    senão retorna NULO

01. PARTICIONA(a: arranjo, p, r)
02.    x = a[r]
03.    i = p - 1
04.    para j = p até r - 1
05.       se a[j] <= x
06.          i = i + 1
07.          troca a[i] com a[j]
08.    troca a[i + 1] com a[r]
09.    retorna i + 1

Sobre o algoritmo SELECIONA(a: array, i), é INCORRETO afirmar que:

1. Um pior caso ocorre para entradas ordenadas crescentemente, desejando-se saber o menor elemento.
2. Um melhor caso ocorre para entradas ordenadas crescentemente, desejando-se saber o maior elemento.
3. Um melhor caso ocorre para entradas ordenadas decrescentemente, desejando-se saber o maior elemento.
4. As complexidades de tempo esperada e no pior caso são O(n) e Θ(n²), respectivamente, para entradas de tamanho n.
5. N.D.A.

Ideia original de: Daniel Henriques Moreira

MO417 - QUESTÃO PARA A PROVA ORAL 

Número: 2013-027

Enunciado: Sobre as afirmações 

I. O Insertion Sort em uma implementação estável utiliza, além do vetor original, um espaço de armazenamento = Θ(1).

II. Os algoritmos de ordenação em tempo linear se diferenciam dos algoritmos de ordenação O(n lg n) convencionais por precisarem de uma característica específica de entrada.

III. O pior caso do Quicksort ocorre quando a entrada já está ordenada, sendo o tempo de execução O(n lg n).

Podemos afirmar que:

a) Todas são verdadeiras.
b) I e II são verdadeiras.
c) I e III  são verdadeiras.
d) II e III são verdadeiras.
e) NDA

Ideia original de: Lucas Miguel de Carvalho

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-026

Enunciado: Sobre o algoritmo de busca binária iterativa a seguir:

BINARY-SEARCH(A, x)

1  if x < A[1] then
2     return 0
3  if x ≥ A[n] then
4     return n
5  // aqui A[1] ≤ x < A[n]
6  start ← 1
7  end ← n
8  // invariante: A[start] ≤ x < A[end]
9  while start + 1 < end do
10    middle ← (start + end)/2
11    if A[middle] ≤ x then
12       start ← middle
13    else
14       end ← middle
15 return start

é correto afirmar que, se A[1] ≤ x < A[n], a comparação da linha 11 é executada pelo menos:

a) ⌊lg (n-1)⌋  vezes, para n ≥ 2
b) ⌊lg n⌋  vezes, para n ≥ 1
c) ⌈lg n⌉  vezes, para n ≥ 1
d) lg n + 1  vezes, para n ≥ 1
e) NDA

Ideia original de: Lucas Miguel de Carvalho