Questões sobre Complexidade de Algoritmos: março 2013

segunda-feira, 25 de março de 2013

MO417 - Questão para a prova oral

Número: 2009-049

Enunciado: O comandante de um pelotão de 10 soldados precisou atribuir uma missão ao sexto homem mais velho de sua equipe. Sem saber as idades dos soldados, escolheu um deles ao acaso e lhe perguntou sua data de nascimento: "Zero-dois, em que dia o senhor nasceu?" O soldado, em alto e bom tom, respondeu: "03 de abril de 1989, senhor!"

O comandante, então, lembrando-se de seu intenso treinamento em Algoritmos, deu a seguinte ordem ao pelotão: "Organizem uma fila da seguinte forma: quem nasceu antes do soldado Zero-dois, que se posicione à frente dele; quem nasceu depois, que se posicione atrás dele." Após o pelotão ter se organizado, o comandante notou que o soldado Zero-dois era apenas o quarto da fila, e percebeu que teria de continuar sua busca. Para chegar mais rápido à resposta, o próximo passo do comandante, então, deveria ser:

Continuar procurando somente entre os 3 soldados mais velhos, mas agora buscando o segundo mais velho dentre eles.
Continuar procurando somente entre os 6 soldados mais novos, mas agora buscando o segundo mais velho dentre eles.
Continuar procurando somente entre os 6 soldados mais novos, mas agora buscando o segundo mais novo dentre eles.
Continuar procurando o sexto homem mais velho entre os 10 soldados, mas escolhendo outro soldado ao acaso.
NDA

Ideia original de: Fábio de Souza Azevedo

MO417 - Questão para a prova oral

Número: 2003-060

Enunciado:
Sobre árvores de decisão, NÃO é correto afirmar que:

A) Não há uma mesma árvore para todo algoritmo de ordenacao por comparação, mas a árvore é unica para um determinado algoritmo.
B) O comprimento do caminho mais longo da raiz de uma árvore de decisão até qualquer de suas folhas acessíveis representa o número de comparações do pior caso que o algoritmo de ordenação correspondente executa para qualquer entrada de um tamanho dado.
C) Toda árvore de decisão de qualquer algoritmo de ordenação correto conterá todas as possíveis permutações dos n elementos de entrada em suas folhas, onde cada permutação estará contida em uma única folha acessível.
D) Uma árvore de decisão é uma árvore binária cheia que representa as comparações executadas por um algoritmo de ordenação quando ele opera sobre uma entrada de tamanho dado.
E) NDA

Ideia original de: Ivan Brunetto

domingo, 24 de março de 2013

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-025

Enunciado: Dado o algoritmo de COUNTING-SORTING a seguir, que ordena o vetor A no vetor B:

COUNTING-SORTING (A,B,k)
1 let C[0..k] be a new array
2 for i=0 to k
3 C[i]=0
4 for j=1 to A.length
5 C[A[j]]=C[A[j]]+1
6 //C[i] now contains the number of elements equal to i.
7 for i=1 to k
8 C[i]=C[i]+C[i-1]
9 // C[i] now contains the number of elements equal to i.
10 for j=A.length downto 1
11 B[C[A[j]]]=A[j]
12 C[A[j]]=C[A[j]]-1

O que acontece quando a linha 10 é substituída por: for j=1 to A.length

a. a complexidade aumenta
b. o algoritmo não é mais estável
c. o algoritmo não é mais correto
d. não produz nenhuma diferença
e. NDA

Ideia original de: Vladimir Jaime Rocca Layza

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-024

Qual das afirmações é INCORRETA:

O algoritmo HEAP-SORT é assintoticamente ótimo segundo o modelo computacional de árvore de decisão.
O algoritmo COUNTING-SORT é um algoritmo de ordenação estável.
Para implementar o algoritmo RADIX-SORT, pode-se utilizar qualquer algoritmo de ordenação para realizar as ordenações intermediárias.
O tempo de execução de pior caso do algoritmo QUICK-SORT é O(n^2).
NDA

Ideia original de: Daniel Vidal

MO417 - Questão para a prova oral

Número: 2013-023

Enunciado: Considere o algoritmo do quicksort ligeiramente modificado para sempre eleger um elemento aproximadamente do meio para ser o pivô. Mais especificamente, no subproblema em A[p,...,r] o elemento A[⌈(r+p)/2⌉] é eleito pivô. Desta forma, é correto afirmar que:

a) Quando e entrada A está em ordem decrescente, o tempo de execução do quicksort é T(n)=Θ(n lg n), refletindo o pior caso.

b) Quando a entrada A está em ordem crescente, o tempo de execução do quicksort é T(n)=Θ(n), refletindo o melhor caso.

c) Quando a entrada A está em ordem crescente ou decrescente, no final de cada procedimento de partição, o pivô sempre começa e termina na mesma posição.

d) Quando a entrada A está em ordem crescente ou decrescente, o tempo de execução do quicksort é T(n)=Θ(n lg n), refletindo o melhor caso.

e) NDA

Ideia original de: Jacqueline Midlej do Espírito Santo

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-021

Enunciado: Durante o desenvolvimento de uma aplicação qualquer, um programador deparou-se com a necessidade de ordenar uma sequência de n números naturais, pertencentes ao intervalo [0, 1000]. Para escolher o algoritmo mais adequado, ele resolveu adotar três critérios:

1. O algoritmo deve ser estável.
2. O algoritmo deve trabalhar inplace.
3. O algoritmo deve possuir complexidade de tempo no pior caso de O(n lg n).

Segundo estes critérios, assinale o algoritmo que ele poderá escolher:

MERGESORT
HEAPSORT
QUICKSORT
COUNTING SORT
N.D.A.

Ideia original de: Daniel Henriques Moreira

sábado, 23 de março de 2013

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-019

Enunciado: Observe a ilustração das etapas de ordenação de um arranjo de 6 números inteiros de 3 dígitos, através do algoritmo radix sort, utilizando um algoritmo intermediário que deveria ser estável para ordenar cada dígito:

Analisando a figura, é correto afirmar que:

a. O arranjo se encontra ordenado, porém o algoritmo de ordenação intermediário falhou da etapa (c) para a (d).
b. O arranjo se encontra desordenado, e o algoritmo de ordenação intermediário funcionou corretamente em todas as etapas.
c. O arranjo se encontra desordenado, e o algoritmo de ordenação intermediário funcionou corretamente das etapas de (a) até (c).
d. O arranjo se encontra desordenado, pois o algoritmo de ordenação intermediário falhou da etapa (b) para a (c).
e. NDA

Ideia original de: Wallace Felipe Francisco Cardoso

quarta-feira, 20 de março de 2013

MO417 - Questão para a prova oral

Número: 2010-027

Enunciado: Temos um vetor de tamanho n para ser ordenado, onde cada elemento é um inteiro pertencente ao intervalo [0,k). Seja f o custo de ordenação de tal vetor através do Counting Sort, em função de n e k. Marque a alternativa INCORRETA:

Se k for ω(n) então f é Ω(n), mas não é Θ(n)
Se k for Ω(n) então f é Θ(n)
Se n for ω(k) então f é Θ(n)
Se n for Ω(k) então f é Θ(n)
NDA

Ideia original de: Daniel Cason

MO417 - Questão para a prova oral

Número: 2010-026

Enunciado: Na prova do limite inferior para ordenações por comparação são usadas árvores binárias cheias para mostrar que todo algoritmo de ordenação por comparação vai usar Ω(n lg n) comparações. As árvores usadas tem as seguintes características:

Para cada algoritmo existe uma árvore, que é a mesma para todos os tamanhos de entrada, e cada caminho da raiz até uma folha é uma execuçãs diferente do algoritmo.
Para cada entrada de tamanho n existe uma árvore, que é compartilhada por todos os algoritmos, e cada algoritmo faz um caminho próprio nela.
Para cada tamanho n e para cada algoritmo existe uma árvore, e cada caminho da raiz até uma folha é uma execuçãs diferente do algoritmo.
Existe uma única árvore para qualquer tamanho de entrada e para qualquer algoritmo, e o caminho feito nessa árvore vai depender do algoritmo e do tamanho da entrada.
NDA

Ideia original de: Alexandre Tachard Passos

MO417 - Questão para a prova oral

Número: 2010-025

Enunciado: O que aconteceria com o BUCKET SORT se para ordenar cada balde usassemos um algoritmo de ordenação que é Θ(n^3)?

O tempo de execução esperado seria Θ(n)
O tempo de execução esperado seria Θ(n^3)
O tempo no pior caso seria Θ(n)
O tempo no pior caso seria Θ(n^2)
NDA

Ideia original de: Pedro Henrique Del Bianco Hokama

MO417 - Questão para a prova oral

Número: 2010-024

Enunciado: É correto afirmar que:

Bucket Sort só ordena números inteiros.
Counting Sort não é estável.
Radix Sort se utiliza de uma subrotina de ordenação estável.
Radix Sort só ordena números entre 0 e 1.
NDA

Ideia original de: Alexandre Toshio Hirata

MO417 - Questão para a prova oral

Número: 2009-045

Enunciado: Qual algoritmo é ao mesmo tempo estável, local e roda em tempo O(n lg n) no pior caso?

Insertion sort
Quicksort
Heapsort
Merge sort
NDA

Ideia original de: Milton Aparecido Soares Junior

MO417 - Questão para a prova oral

Número: 2009-043

Enunciado: Considere o seguinte algoritmo COUNTING SORT modificado, que recebe como parâmetros um vetor A a ser ordenado, que deve conter valores inteiros no intervalo de 1..k, e o próprio k:

COUNTING-SORT-Modificado (A, k) 
1. for i := 0 to k 
2.      do C[i] := 0 
3. for j := 1 to comprimento[A] 
4.      do C[A[j]] := C[A[j]] +1 
5. j := 1 
6. for i := 1 to k 
7.     for cont := 1 to C[i] 
8.            A[j] := i 
9.            j := j + 1

Sobre este algoritmo é CORRETO afirmar:

É estável como o COUNTING-SORT original.
O vetor auxiliar C deve ter tamanho mínimo n.
Sua complexidade de tempo no pior caso é Θ(n²).
Ordena A corretamente no próprio vetor A, sem utilizar um vetor de SAÍDA auxiliar B.
NDA

Ideia original de: Renato Hirata

MO417 - Questão para a prova oral

Número: 2009-042

Enunciado: Considere a ordenação radix sort sobre a lista abaixo. Qual é a disposição dos elementos após a ordenação do segundo dígito?

429
832
423
132
611
133
101

101
611
423
429
132
832
133

101
132
133
423
429
611
832

101
611
423
429
832
132
133

101
132
133
429
423
611
832

Ideia original de: Ana Carolina Correia Rézio

segunda-feira, 18 de março de 2013

MO417 - Questão para a prova oral

Número: 2003-072

Enunciado: Sobre os algoritmos de ordenação vistos, é correto afirmar que:

A) Com a existência de algoritmos em tempo linear, deduz-se que é possível um aperfeiçoamento do QuickSort a fim dele proporcionar uma ordenação O(n).
B) O CountingSort, é um bom algoritmo para ordenação em tempo linear que não necessita de espaço adicional, e por isso é estável.
C) O BucketSort também é um algoritmo de ordenação em tempo linear, isto é, para qualquer entrada, ele ordena em O(n).
D) O RadixSort ordena um dígito de cada vez (do menos ao mais significativo) e, para ordenar cada dígito, pode utilizar, por exemplo, o InsertionSort, embora esta escolha possa prejudicar sua performance.
E) n.d.a.

Ideia original de: Patrick Henrique da Silva Brito

MO417 - Questão para a prova oral

Número: 2003-059

Enunciado: Sobre o algoritmo Radix Sort, NÃO é válida a seguinte afirmação:

A) seu tempo de execução é proporcional ao número de elementos a ordenar, se cada elemento não utilizar mais de d dígitos decimais, onde d é uma constante fixa;
B) é necessário um algoritmo de ordenação estável para ordenar sobre o dígito i;
C) para os d dígitos dos elementos de entrada, a ordenação necessariamente deve se dar do dígito menos significativo para o mais significativo;
D) não é um algoritmo de ordenação por comparação ;
E) NDA

Ideia original de: Alexandro Baldassin

MO417 - Questão para a prova oral

Número: 2003-069

Enunciado: Sobre o COUNTING-SORT é correto afirmar que:

A) Se os inteiros a serem ordenados estão no intervalo de 1 a n, tem ordem de crescimento Θ(n). Escapa do limite inferior de Ω(n lg n) porque não realiza ordenação por comparação.

B) É estável porque utiliza ordenação local, ou seja, utiliza espaço adicional constante.

C) Realiza ordenação sobre cada dígito dos elementos, assim como era usado antigamente na ordenação de cartões perfurados.

D) Divide o intervalo [0, 1) em n subintervalos de igual tamanho e depois distribui os n elementos de entrada entre os subintervalos. Então conta-se o número de elementos em cada subintervalo e redistribui os elementos no arranjo de forma ordenada.

E) NDA

Ideia original de: Fabio Batista Gomes

MO417 - Questão para a prova oral

Número: 2003-065

Enunciado: É correto afirmar que:

A) Um algoritmo de ordenação é estável quando chaves com o mesmo valor aparecem no arranjo de saída na mesma ordem em que estavam no arranjo de entrada. O counting sort é um exemplo de tal algoritmo.
B) O bucket sort tem tempo Θ(n), desde que seus elementos pertençam ao intervalo [0,1).
C) O limite assintótico inferior para o problema de ordenação é Ω(n lg n).
D) O algoritmo SELECT para seleção em tempo linear fica mais eficiente quando são usados grupos de 3 elementos no lugar de 5, pois o insertion sort empregado na ordenação do grupo é mais rápido para n menor.
E) N.D.A.

Ideia original de: Bruno Cedraz Brandão

MO417 - Questão para a prova oral

Número: 2003-062

Enunciado: Abaixo encontram-se duas versões do algoritmo "Bubble Sort".

BUBBLE-SORT1(A)                          BUBBLE-SORT2(A)
1 for i := length[A]-1 downto 1          1 for i := length[A]-1 downto 1 
2   for j := 1 to i                      2   for j := 1 to i
3     if (A[j] > A[j+1])                 3     if (A[j] >= A[j+1])
4       troca A[j] <-> A[j+1]            4       troca A[j] <-> A[j+1]

Note que a única diferença entre as duas versões é a comparação na linha 3. Qual destas duas versões pode ser usada na implementação do algoritmo "Radix Sort" para obtermos complexidade de tempo linear no número de elementos?

A) Ambas as versões podem ser usadas na implementação do "Radix Sort".
B) Somente a versão "Bubble-Sort1" pode ser usada na implementação do "Radix Sort".
C) Somente a versão "Bubble-Sort2" pode ser usada na implementação do "Radix Sort".
D) Nenhuma das versões pode ser usada na implementação do "Radix Sort".
E) NDA

Ideia original de: José Augusto Amgarten Quitzau

MO417 - Questão para a prova oral

Número: 2003-044

Enunciado: Com relação aos algoritmos de ordenação heapsort e quicksort, assinale a alternativa INCORRETA:

A) O heapsort é superior ao quicksort, se considerarmos o pior caso.
B) O heapsort não é muito competitivo para um arranjo de entrada (array) pequeno, devido à sobrecarga da criação do heap inicial e do cálculo da posição de pais e filhos.
C) O quicksort possui a propriedade conta-intuitiva de funcionar melhor para arranjos de entrada (arrays) que estejam em ordem aleatória e pior para os que já estão totalmente ordenados.
D) No quicksort, o pivô somente pode ser o último elemento do arranjo de entrada (array).
E) NDA.

Ideia original de: Eduardo Akira Yonekura

domingo, 17 de março de 2013

MO417 - Questão para a prova oral

Número: 2013-017

Enunciado: Suponha que o tempo total de um algoritmo é dado pela recorrência

T(n)=8T(⌊n2⌋)+n2.

Assinale a afirmativa que representa a complexidade do algoritmo.

a.

θ(n2 log n)
b.

θ(n2)

θ(n log n)

θ(n3 log n)
e. NDA

Ideia original de: Osvaldo Andrade Neto

MO417 - Questão para a prova oral

Número: 2013-016

Enunciado: Suponha que a função f satisfaz a relação de recorrência

f(n) = 2 f(n^1/2) + 1.

Dê uma estimativa assintótica correta da função f(n).

(a) Θ(log n)
(b) Θ(n)
(c) Θ(n log n)
(d) Θ(n²)
(e) NDA

Ideia original de: Marcelo Palma Salas

MO417 - Questão para a prova oral

Número: 2013-015

Enunciado: Sejam a ≥ 1 e b > 1 constantes, seja f(n) uma função e T(n) definida sobre os números inteiros não negativos pela recorrência

T(n) = aT(n/b) + f(n)

É INCORRETO afirmar que:

Se a = b e f(n) = n então T(n) = Θ(n lg n)
Se a = b²e f(n) = n então T(n) = Θ(n²)
Se a = b e f(n) = n²então T(n) = Θ(n²)
Se a = b² e f(n) = n² então T(n) = Θ(n lg n)
NDA

Ideia original de: Anderson Carlos Sousa e Santos

MO417 - Questão para a prova oral

Número: 2013-014

Enunciado : Qual a ordem de crescimento das soluções para a recorrência abaixo:

T( n ) = T( n^1/2 ) + n

Como sempre, supõem-se valores constantes para n pequeno e arrendondamento da raiz para cima ou para baixo.

a) Θ ( n )

b) Θ ( n² )

c) Θ ( n log log n )

d) Θ ( n log n )

e) N.D.A.

Ideia original de: Erick Aguiar Donato

MO417 - Questão para a prova oral

Número: 2013-013

Enunciado: Se T(n) = 9T(n/3)+n², T(0) = T(1) = 1, qual das seguintes afirmações NÃO é correta.

a) T(n) = O(n³)
b) T(n) = Θ(n² log n)
c) T(n) = Ω(n²)
d) T(n) = Ω(n³)
e) NDA

Ideia original de: John Edgar Vargas Muñoz

MO417 - Questão para a porva oral

Número: 2013-012

Enunciado: Dada a seguinte função recursiva:

Function (n)

if (n ≤ 1)

PARAR

else

Ativar processo X

Function (n/2)

Sendo T(n) o número de ativações do processo X, a fórmula de recorrência que representa esta função é:

T(n) = 1 + T(n/2), n>1
T(1) = 0

Podemos afirmar que:

a) A recorrência não pode ser resolvida pelo método mestre, pois não existe a constante “a”.

b) O processo x será ativado lg n vezes.

c) O processo x será ativado n lg n vezes.

d) O processo x será ativado 2ⁿ vezes.

e) NDA

Ideia original de: Lucas Oliveira Batista

MO417 - Questão para a prova oral

Número: 2013-011

Enunciado: Considere o algoritmo abaixo para a resolução do problema Torre de Hanoi.

Algoritmo Hanoi (n, ori, des, aux)
se n = 1
      então “move pino” de ori para des
senão Hanoi (n − 1, ori, aux, des)
      “move pino” de ori para des
      Hanoi (n − 1, aux, des, ori)

A seguir, considere a recorrência para este problema:

T(n)=1                 para n=1
T(n)=2T(n-1)+1   para n>1

É correto afirmar que:

a. T(n)=Θ(2ⁿ)
b. T(n)=Θ(n²)
c. T(n)=Θ(n lg n)
d. T(n)=Θ(n² lg n)
e. NDA

Ideia original de: Jacqueline Midlej do Espírito Santo

MO417 - Questão para a prova oral

Número: 2013-010

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. Heapsort

II. Insertion Sort

III. Merge Sort

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

sábado, 16 de março de 2013

MO417 - Questão para a prova oral

Número: 2013-009

Enunciado: Assinale a alternativa na qual a recorrência descrita pode ser resolvida pelo método mestre:

A) T(n) = T(n/4) - n
B) T(n) = nT(n/2) + n
C) T(n) = 2T(n/4) + n
D) T(n) = 3T(n/3) + n lg n
E) N.D.A.

Ideia original de: Félix Carvalho Rodrigues

MO417 - Questão para a prova oral

Número: 2013-008

Enunciado: Qual das seguintes recorrências NÃO pode ser resolvida pelo teorema mestre?

a. T(n) = 0,5T(n/2) + n
b. T(n) = 3T(n/3) + 1/n
c. T(n) = T(n/2) + sqrt(n)
d. T(n) = 2T(n/3) + n lg n
e. NDA

Ideia original de: Jorge Augusto Hongo

MO417 - Questão para a prova oral

Número: 2013-007

Enunciado: Dadas as seguintes recorrências, assinale a alternativa correta:

T₁(n) = 5T(n/6) + n²
T₂(n) = 5T(n/2) + n^{lg 5}
T₃(n) = 5T(n/2) + n²

a. T₁(n) possui uma ordem de crescimento maior do que T₂(n)
b. T₂(n) possui uma ordem de crescimento maior do que T₃(n)
c. T₃(n) = Θ(n^{lg 5} lg n)
d. T₁(n) = Θ(n^{log₆ 5})
e. NDA

Ideia original de: Anderson Coelho Weller

MO417 - Questão para a prova oral

Número: 2013-006

Enunciado: O tempo de execucão de um algoritmo A é descrito por T(n) = 7T(n/2) + n². Outro algoritmo A' tem complexidade de tempo T'(n) = aT'(n/4) + n². Qual é o maior inteiro a tal A' é assintoticamente mais rápido que A?

a) 26
b) 35
c) 48
d) 50
e) NDA.

Ideia original de: Carlos Eduardo Alfaro Morales

MO417 - Questão para a prova oral

Número: 2013-005

Enunciado: Dadas as recorrências abaixo, qual NÃO pode ser resolvida pelo método Mestre?

T(n) = 9T(n/3) + n
T(n) = T(2n/3) + 1
T(n) = 3T(n/4) + n lg n
T(n) = 2T(n/2) + n lg n
N.D.A.

Ideia original de: Tiago Pedroso da Cruz de Andrade

terça-feira, 12 de março de 2013

MO417 - Questão para a prova oral

Número: 2010-023

Enunciado: No algoritmo quicksort, suponha que o algoritmo de particionamento sempre produza uma divisão desequilibrada de 200 para 1 em todos os níveis de recursão. Seu tempo de execução será dado então pela solução da seguinte recorrência

T(n) = T(200n/201) + T(n/201) + n

e pode ser descrito como:

Θ(lg n)
Θ(n²)
O(n)
O(n lg n)
NDA

Ideia original de: Maikon Cismoski dos Santos

MO417 - Questão para a prova oral

Número: 2010-022

Enunciado: Sobre o algoritmo Quicksort, podemos afirmar que:

No caso médio o quicksort executa com tempo O(lg n).
No pior caso o quicksort tem desempenho tão ruim quanto o mergesort.
Seu caso médio é tão bom quanto o melhor caso, ambos com tempo O(n lg n).
Seu pior caso ocorre quando a entrada já está ordenada, sendo o tempo de execução O(n lg n).
NDA.

Ideia original de: Rodrigo Tripodi Calumby

MO417 - Questão para a prova oral

Número: 2010-021

Enunciado: Um algoritmo de ordenação é denominado local se a memória adicional utilizada por ele possui tamanho constante, ou seja, independe do tamanho do vetor a ser ordenado.

Qual dos algoritmos de ordenação abaixo NÃO é local?

Heapsort
Insertionsort
Mergesort
Quicksort
NDA

Ideia original de: Marcos Vinícius Mussel Cirne

MO417 - Questão para a prova oral

Número: 2010-020

Enunciado: Assinale a alternativa incorreta:

O Heapsort possui tempo de execução O(n log n) apenas para arranjos ordenados em ordem decrescente, já que a estrutura do heap está praticamente "montada".
O Quicksort e o Insertion-Sort possuem complexidade O(n²) para o pior caso.
O Quicksort se mostra mais eficiente que o Insertion-Sort pois seu tempo de execução no caso médio é Θ(n log n).
Se os sucessivos particionamentos do arranjo são balanceados, o Quicksort é executado assintoticamente tão rápido quanto a ordenação por intercalação.
NDA

Ideia original de: Matheus Silva Mota

MO417 - Questão para a prova oral

Número: 2010-019

Enunciado: Um dos paradigmas para a solução eficiente de problemas é a divisão e conquista. Qual das alternativas abaixos apresenta dois algoritmos que utilizam a divisão e conquista?

Heapsort e Insertion-sort
Insertion-sort e Merge-sort
Merge-sort e Quicksort
Quicksort e Heapsort
NDA

Ideia original de: Pedro Henrique Del Bianco Hokama

MO417 - Questão para a prova oral

Número: 2010-018

Enunciado: Nas afirmações a seguir sobre algoritmos de ordenação, interprete "é igual a" como significando "tem mesma ordem de crescimento assintótico".

1. O tempo de excecução do pior caso do quicksort é igual ao tempo de excecução do pior caso do insertion sort.
2. O tempo de excecução do caso médio do quicksort é igual ao tempo de excecução do caso médio do heapsort.
3. O tempo de excecução do pior caso do heapsort é igual ao tempo de excecução do pior caso do selection sort.

As afirmações corretas são:

1, 2 e 3.
1 e 2.
1 e 3.
2 e 3.
NDA

Ideia original de: Anderson Francisco Talon

MO417 - Questão para a prova oral

Número: 2010-017

Enunciado: Em relação ao Heapsort, podemos afirmar que:

O algoritmo é local.
O algoritmo é estável.
No pior caso, o algoritmo tem complexidade temporal de O(n lg n).

As alternativas verdadeiras são:

1, 2 e 3.
1 e 3.
2 e 3.
Apenas 3.
NDA.

Ideia original de: Carlos Eduardo Seo

MO417 - Questão para a prova oral

Número: 2009-035

Enunciado: Qual dos vetores abaixo não é um max-heap?

[52, 45, 27, 60, 20, 10, 9]
[66, 9, 40, 1, 5, 30, 35]
[80, 30, 60, 12, 20, 50, 55]
[100, 66, 55, 30, 17, 40, 12]
NDA

Ideia original de: Guilherme Moraes Armigliatto

MO417 - Questão para a prova oral

Número: 2009-033

Enunciado: A altura de um heap é o número de arestas no caminho da raiz até uma das folhas mais distantes. Qual das alternativas abaixo é um possível número de elementos de um heap quando a altura deste é h ≥ 2?

2^h-1 + 1
2^h - 1
2^h+1
2^h+1 - 1
NDA

Ideia original de: José Vieira Maciel Borges

MO417 - Questão para a prova oral

Número: 2009-030

Enunciado: Dado o seguinte vetor organizado como um heap [16, 14, 10, 8, 7, 9, 3, 2, 4, 1] é incorreto afirmar que:

As folhas do heap são os elementos 7, 9, 3, 2, 4 e 1.
Os filhos à esquerda e à direita do elemento "10" são "9" e "3", respectivamente.
O heap apresentado é um heap máximo.
O pai do elemento "2" é o elemento "8"
NDA

Ideia original de: Danilo Brandão Gonçalves

MO417 - Questão para a prova oral

Número: 2009-029

Enunciado: Dado um heap H com 19 elementos distintos cujo maior elemento encontra-se na raiz, em quantos nós de H pode estar o seu segundo menor elemento?

Ideia original de: Ana Carolina Correia Rézio

MO417 - Questão para a prova oral

Número: 2003-056

Enunciado: Sobre os algoritmos de ordenação heapsort e quicksort, assinale a alternativa incorreta:

A) Tanto o heapsort quanto o quicksort realizam uma ordenação local.
B) O tempo de execução do heapsort é O(n lg n).
C) O heapsort se baseia no paradigma de dividir e conquistar.
D) O comportamento do quicksort para o pior caso leva a um tempo de execução equivalente ao do insertion-sort.
E) N.D.A.

Ideia original de: Guilherme Mundim Torres

MO417 - Questão para a prova oral

Número: 2013-004

Enunciado: Qual das seguintes afirmações NÃO é correta?

a) 256nⁿ = o(nⁿ⁺¹).
b) n lg n^a + b n + c = O(n lg n), se a, b e c são constantes.
c) O tempo de execução do Merge Sort no caso médio é o(n²).
d) Se S(n) é a complexidade de pior caso do Selection Sort e B(n) é a complexidade de pior caso do Bubblesort, então S(n) = o(B(n)).
e) NDA.

Ideia original de: Carlos Eduardo Alfaro Morales

segunda-feira, 11 de março de 2013

MO417 - Questão para a prova oral

Número: 2003-053

Enunciado: Considere o heap A=[12,10,6,8,9,1,4,7,2,3,5]. Após a execução do procedimento MAX_HEAP_INSERT(A,11), o heap A será:

A) A=[12,10,11,8,9,6,4,7,2,3,5,1]
B) A=[12,10,6,8,9,1,4,7,2,3,5,11]
C) A=[12,11,10,8,9,6,4,7,2,3,5,1]
D) A=[12,10,6,8,9,11,4,7,2,3,5,1]
E) N.D.A.

Ideia original de: Daniele Constant

MO417 - Questão para a Prova Oral

Número: 2003-052

Enunciado: Qual é o tempo de execução do QuickSort, tomando sempre o primeiro elemento como pivô, quando todos os elementos do arranjo a ser ordenado são distintos e estão ordenados em ordem decrescente?

A) Θ(lg n);
B) Θ(n lg n);
C) Θ(n);
D) Θ(n²);
E) N.D.A.

Ideia original de: Marcelo Fantinato

MO417 - Questão para a Prova Oral

Número: 2003-050

Enunciado: Sobre o Heapsort, o Quicksort, e suas estruturas subjacentes podemos afirmar que:

A) Em um HEAP máximo S podemos executar INSERÇÃO(S,x), DELEÇÃO(S,i), MÁXIMO(S) e MÍNIMO(S) em tempo O(lg n), onde x é um elemento a ser inserido e i é um índice válido no arranjo do HEAP.
B) No algoritmo Quicksort, o pior caso ocorre apenas quando todos os valores do vetor são iguais.
C) Mesmo no pior caso, o Quicksort tem desempenho melhor que o Heapsort, para qualquer n.
D) Em um HEAP máximo, todos os valores do nível h são obrigatoriamente maiores que qualquer valor do nível h+1, com h crescendo da raiz em direção às folhas.
E) N.D.A.

Ideia original de: Bruno Cedraz Brandão

MO417 - Questão para a Prova Oral

Número: 2003-047

Enunciado: Considere um arranjo A de tamanho n, onde todos os elementos são iguais. O que podemos afirmar com relação à complexidade dos algoritmos HeapSort e QuickSort para este caso:

A) HeapSort leva Θ( n lg n ) e QuickSort leva Θ( n² )
B) HeapSort leva Θ( lg n ) e QuickSort leva Θ( n lg n )
C) HeapSort leva Θ( n ) e QuickSort leva Θ( n² )
D) HeapSort leva Θ( n lg n ) e QuickSort leva Θ( n lg n )
E) n.d.a.

Ideia original de: Nielsen Cassiano Simões

MO417 - Questão para a prova oral

Número: 2003-043

Enunciado: Qual das seguintes recorrências NÃO pode ser resolvida pelo método mestre:

A) T(n) = 2T(n/4) + sqrt(n)
B) T(n) = T(n/2) + lg n
C) T(n) = 5T(n/2) + n²
D) T(n) = 16T(n/4) + n
E) N.D.A.

Obs. sqrt(x) é raíz quadrada de 'x'

Ideia original de: Thiago Alves da Silva

MO417 - Questão para a prova oral

Número: 2003-040

Enunciado: A solução para a recorrência

T(n) = T( n/sqrt(2) ) + 1

é:

A) Θ(n)
B) Θ(log n)
C) Θ(n log n)
D) Θ(n²)
E) n.d.a.

Obs.: considere sqrt(x) como sendo a raiz quadrada de x

Ideia original de: Ricardo Luís Lachi

MO417 - Questão para a Prova Oral

Número: 2003-039

Enunciado: Assinale entre as alternativas abaixo a solução para a seguinte recorrência:

T(1) = 0, se n = 1;

T(n) = 2T(n - 1) + 1, se n > 1.

A) O(n lg n);
B) O(n²);
C) O(n³);
D) O(2ⁿ);
E) N.D.A.

Ideia original de: Marcelo Fantinato

MO417 - Questão para a Prova Oral

Número: 2003-035

Enunciado: Considere a seguinte equação de recorrência:

T(n) = 1, se n ≤ 2
T(n) = 2T(sqrt(n)) + lg n, se n > 2

É correto afirmar que esta recorrência tem solução:

a) impossível de ser resolvida
b) O(lg n lg lg n)
c) Θ(n lg n)
d) O(lg lg n)
e) NDA

Ideia original de: Augusto Jun Devegili

MO417 - Questão para a Prova Oral

Número: 2003-033

Enuncioado: Para T(n) = 2T(n/2) + n lg n, a solução é:

A) Θ(n lg n);
B) O(n lg n));
C) Ω(n lg n);
D) o(n lg n);
E) n.d.a.

Ideia original de: Carlos R. Senna

MO417 - Questão para a prova oral

Número: 2003-032

Enunciado: A solução da recorrência T(n) = 2T(n/2) + n é:

A) O(n)
B) O(lg n)
C) Ω(n^2)
D) Θ(lg n)
E) NDA

Ideia original de: Alexandro Baldassin

domingo, 10 de março de 2013

MO417 - Questão para a prova oral

Número: 2013-003

Enunciado: Sobre as seguintes afirmações, NÃO é correto afirmar que:

a. o(g(n)) ⊂ O(g(n))
b. o(g(n)) ∩ O(g(n)) = Θ(g(n))
c. o(g(n)) ∩ Θ(g(n)) = ∅
d. O(g(n)) ∩ Ω(g(n)) = Θ(g(n))
e. NDA

Ideia original de: Jacqueline Midlej do Espírito Santo

sábado, 9 de março de 2013

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-002

Enunciado: Assinale a alternativa abaixo que contém funções que NÃO pertencem a o(n^n) e a ω(n^(1/2)) simultaneamente:

n , n^2 , n^e
n! , n^10 , n^(6/5)
n^(ln e) , n^(lg (n!)) , n^(10!)
lg (n!) , n^(2+sin n) , n lg n
N.D.A.

Ideia Original de: Félix Carvalho Rodrigues

MO417 - Questão para a prova oral

Número: 2013-001

Enunciado:

I – O algoritmo MergeSort possui complexidade Ω (n.log(n)) para o melhor caso.

II – O algoritmo InsertionSort possui complexidade Ω (n) para o melhor caso.

III – O algoritmo InsertionSort possui complexidade O(n²) para o pior caso.

De acordo com as afirmações acima, marque a alternativa correta:

a) Apenas a afirmativa I está correta.

b) Apenas a afirmativa II está correta.

c) Apenas a afirmativa III está correta.

d) Todas as afirmações estão corretas.

e) N.D.A.

Ideia original de: Erick Aguiar Donato

segunda-feira, 4 de março de 2013

MO417 - Questão para a prova oral

Número: 2010-014

Enunciado: Dadas as funções f(n), g(n) e h(n), assinale a alternativa que contém a assertiva INCORRETA:

se f(n)=O(g(n)) e g(n)=Θ(h(n)) então f(n)=O(h(n))
se f(n)=Ω(g(n)) e g(n)=Θ(h(n)) então f(n)=Ω(h(n))
se f(n)=O(g(n)) e g(n)=O(f(n)) então f(n)=Θ(g(n))
se f(n)=Θ(g(n)) e h(n)=Θ(g(n)) então f(n)=Θ(h(n))
NDA

Ideia original de: Alisson Pontes

MO417 - Questão para a prova oral

Número: 2010-012

Enunciado: Dadas as seguintes afirmações:

I. (1.52)ⁿ = o((1.53)ⁿ), para todo valor positivo de n,
II. Se f(n) = Ω(g(n)), então f(f(n)) = Ω(g(n)), para quaisquer f(n) e g(n) positivas,
III. f(g(n)) = Θ(g(f(n)), para quaisquer f(n) e g(n) positivas,

assinale a alternativa correta:

Apenas a afirmação I é verdadeira.
Apenas a afirmação II é verdadeira.
Apenas a afirmação III é verdadeira.
Existem pelo menos duas afirmações verdadeiras.
NDA

Ideia original de: Marcos Vinícius Mussel Cirne

MO417 - Questão para a prova oral

Número: 2010-010

O seguinte pseudo código descreve qual função?

FUNCAO(n)
    i <-- 0
    while n > 1
        n <-- lg(n)
        i <-- i + 1
    return i

ln n
lgⁿ n
lg^* n
lg ( lg n)
NDA

Ideia original de: Fabian van 't Hooft

MO417 - Questão para a prova oral

Número: 2010-009

Enunciado: Considerando duas funções f(n) e g(n), quais das seguintes afirmações são corretas?

I. Se f(n) = 29n² + Θ(n) então f(n) = O(n²)
II. Temos que n! = o( nⁿ)
III. Temos que n² = o(n²)
IV. Temos que 13n = o(n²)
V. Temos que log n = O(1/n)

Apenas I, II e IV são corretas
Apenas III é incorreta
Apenas V é incorreta
Todas as alternativas são corretas
NDA

Ideia original de: Priscila Tiemi Maeda Saito

MO417 - Questão para a prova oral

Número: 2009-026

Enunciado: Sobre as afirmações abaixo:

I - Se f(n) = O(g(n)) então f(n) = o(g(n))
II - Se f(n) = o(g(n)) então f(n) = O(g(n))
III - f(n)=Θ(g(n)) se, e somente se, existem c > 0, e n₀ > 0 tais que 0 ≤ g(n)/c ≤ f(n) ≤ c g(n) para todo n > n₀

podemos afirmar que:

II e III são corretas
I e III são corretas
Apenas II é correta
Apenas I é correta
NDA

Ideia original de: Fernando José Vieira da Silva

MO417 - Questão para a prova oral

Número: 2009-025

Enunciado: Qual das alternativas abaixo é falsa:

27 n² + Θ(n) = O(n²)
n! = o(nⁿ)
f(n) = Θ(g(n)) se e somente se g(n) = Θ(f(n))
f(n) = O(g(n)) implica que f(n) = o(g(n))
NDA

Ideia original de: Rafael Navarro

MO417 - Questão para a prova oral

Número: 2009-024

Enunciado: Considere a seguinte recorrência:

 T(n) = 5   para n ≤ 3
 T(n) = 3T(piso(n/4)) + n para n ≥ 4

Podemos dizer que T(n) tem ordem de crescimento:

Θ(n)
Θ(nlg(n))
Θ(n²)
Θ(n³)
NDA

Ideia original de: Jonathas Campi Costa

MO417 - Questão para a prova oral

Número: 2009-023

Enunciado: Considerando três funções f(n), g(n) e h(n) crescentes quaisquer, o que é verdadeiro:

Se f (n) = O (g (n)) então f (n) = o (g (n))
Se g (n) = ω (f (n)) e f (n) = O (h (n)), é possível que g (n) = Θ (h (n))
É possível que f (n) = o (g (n)) e f (n) = ω (g (n))
Se f (n) = O (g (n)) e g (n) = Θ (h (n)) então f (n) = Θ (h (n))
NDA

Ideia original de: Luiz Augusto Muniz de Paula

MO417 - Questão para a prova oral

Número: 2009-021

Enunciado: Assinale a alternativa correta.

10n = o(n²)
n² = o(n²)
5n² = ω(n²)
lg(n) = O(1/n)
NDA

Ideia original de: Robson Roberto Souza Peixoto

MO417 - Questões para a prova oral

Número: 2009-020

Enunciado: Considere o pseudo-código abaixo que retorna o índice do elemento mínimo do vetor v = (v[i], . . . , v[f]), onde i ≤ f:

minimo (v, i, f)
1.   if i = f
2.     then return i
3.   p ← minimo (v, i, (i+f)/2)
4.   q ← minimo (v, (i+f)/2+1, f)
5.   if v[p] ≤ v[q]
6.     then return p
7.   return q

Considerando n = f - i + 1, o número de comparações entre elementos de v numa execução de minimo ( v, i, f) é?

n log n
n - 1
n/2
log n
NDA

Ideia original de: Ana Carolina Correia Rézio

MO417 - Questão para a prova oral

Número: 2009-019

Enunciado: Assinale a alternativa INCORRETA:

f(n) = Θ(g(n)) implica f(n) = O(g(n))
f(n) = o(g(n)) implica f(n) = O(g(n))
f(n) = O(g(n)) implica f(n) = Θ(g(n))
f(n) = ω(g(n)) implica f(n) = Ω(g(n))
NDA

Ideia original de: Jefferson Luiz Moisés da Silveira

domingo, 3 de março de 2013

MO417 - Questão para a prova oral

Número: 2003-031

Enunciado: Considere a seguinte função de recorrência:

        /  1, se n = 1;
T(n) = |      
       |          
        \  2 * T(n/2), para n > 1.
               

A solução para esta recorrência é:

A) O( lg n )
B) Θ( n )
C) O( 2^(n/2) )
D) Θ( n lg n )
E) n.d.a.

Ideia original de: Nielsen Cassiano Simões

MO417 - Questão para a prova oral

Número: 2003-029

Enunciado: Sobre o crescimento de funções, NÃO podemos afirmar que:

A) O(n lg n) ⊆ O(n²⁰⁰³) ⊆ O(n!)
B) Se f(n) = 4ⁿ e g(n) = n², então f(n) = O(g(n)) e g(n) = Ω(f(n))
C) f(n) = o(g(n)) se e somente se g(n) = ω(f(n)).
D) n = O(2ⁿ)
E) N.D.A.

Ideia Original de: Bruno Cedraz Brandão

MO417 - Questão para a prova oral

Número: 2003-027

Enunciado : Considerando o gráfico, assinale a afirmativa correta.

A) f(x) = o(h(x))
B) h(x) = ω(g(x))
C) g(x) = Ω(h(x))
D) f(x) = O(g(x))
E) N.D.A.

Ideia original de: Camila Ribeiro Rocha

MO417 - Questão para a prova oral

Número: 2003-025

Enunciado: Qual das alternativas a seguir está correta?

A) Se f(n) = O(g(n)) então g(n) = O(f(n)).
B) Se f(n) = Ω(g(n)) então g(n) = Ω(f(n)).
C) Se f(n) = Θ(g(n)) então g(n) = Θ(f(n)).
D) Se f(n) = o(g(n)) e f(n) = ω(g(n)) então f(n) = Θ(g(n)).
E) NDA

Ideia original de: Patrick Henrique

MO417 - Questão para a prova oral

Número: 2003-024

Enunciado: Considere uma função f(n) que satisfaz:
f(n) = O(n^2)
f(n) = ω(lg(n))
Qual alternativa contém duas funções que poderiam ser f(n)?

A) n! e n^2
B) (lg(n))! e n^n
C) n^(lg(lg(sqrt(64)))) e lg(n) * lg(n)
D) não existe nenhuma função conhecida que possa ser f(n)
E) n.d.a.

Obs.: sqrt(x) é a raiz quadrada de x

Ideia original de: Ricardo Luís Lachi

MO417 - Questão para a prova oral

Número: 2003-021

Enunciado: Assinale a alternativa em que as funções estão enumeradas em ordem, da menor para a maior:

a) lg n, log₁₀ n, ln n, lg* n
b) lg* n, log₁₀ n, lg n, ln n
c) lg* n, log₁₀ n, ln n, lg n
d) lg n, ln n, log₁₀ n, lg* n
e) NDA

Ideia original de: Augusto Jun Devegili

MO417 - Questão para a prova oral

Número: 2003-020

Enunciado: Quando escrevemos f(n) = O(g(n)), intuitivamente esta notação quer dizer que:

A) f(n) sempre tem ordem de crescimento maior ou igual à de g(n), podendo até ter uma ordem de crescimento bem maior.
B) g(n) tem ordem de crescimento praticamente igual à de f(n), podendo ter uma ordem de crescimento um pouco maior ou um pouco menor.
C) f(n) não tem ordem de crescimento maior do que a de g(n), podendo até ter uma ordem de crescimento bem menor.
D) g(n) não tem ordem de crescimento maior do que a de f(n), podendo até ter uma ordem de crescimento bem menor.
E) N.D.A.

Ideia original de: Marcelo Fantinato

MO417 - Questão para a prova oral

Número: 2003-016

Enunciado: Considere um função f(n) tal que f(n) = Θ(n^2). Então, NÃO podemos afirmar que:

A) f(n) = o(n^3) e f(n) = ω(n)
B) f(n) = O(n^2) e f(n) = Ω(n^2)
C) f(n) = O(n^2) e f(n) = ω(lg(n))
D) f(n) = O(n) e f(n) = Ω(n^2)
E) NDA

Ideia original de: Alexandro Baldassin

MO417 - Questão para a prova oral

Número: 2010-008

Enunciado:
I - O Insertion-Sort nunca faz mais do que 2n trocas para ordenar um arranjo de n elementos.
II - Para uma entrada A com n elementos, o Merge-Sort sempre será mais rápido que o Insertion-Sort, isto porque possuem complexidades de pior caso O(n²) e O(n lg n), respectivamente.
III - O Bubble-Sort e o Insertion-Sort possuem complexidade de pior caso de mesma ordem.

Considerando as afirmações I, II e III, qual das alternativas abaixo está correta?

Apenas a afirmação I está correta
Apenas as afirmações I e II estão corretas
As afirmações I e III estão corretas
Apenas as afirmações II e III estão corretas
NDA

Ideia original de: Matheus Silva Mota

MO417 - Questão para a prova oral

Número: 2010-007

Enunciado: Com o intuito de melhorar o desempenho do algoritmo Merge-Sort, foi proposto um novo algoritmo que ao invés de subdividir o problema inicial em 2 subproblemas de igual tamanho entre si (e assim sucessivamente), subdivide o problema inicial em 3 subproblemas de igual tamanho entre si (e assim sucessivamente). Este novo algoritmo possui um tempo de execução da ordem de?

Θ(n)
Θ(nlog n)
Θ(n²)
Θ(n²log n)
NDA

Ideia original de: Leonardo Scanferla Amaral

MO417 - Questão para a prova oral

Número: 2010-006

Enunciado: Considerando os algoritmos de ordenação por inserção, seleção e intercalação, é CORRETO afirmar que:

Todos os algoritmos considerados têm pior caso Θ(n lg n).
O pior caso por inserção e o melhor caso por intercalação é Θ(n²).
O pior caso por seleção e inserção é Θ(n²).
O melhor caso por seleção e intercalação é Θ(n lg n).
NDA

Ideia original de: Fábio Augusto Faria

MO417 - Questão para a prova oral

Número: 2010-005

Enunciado: Dadas as seguintes afirmações:

I. O tempo de execução do algoritmo INSERTION-SORT, no melhor caso, é Θ(n), onde n é o número de elementos do vetor a ser ordenado.
II. O número de trocas realizadas durante a execução do algoritmo SELECTION-SORT, no pior caso, é Θ(n), onde n é o número de elementos do vetor a ser ordenado.
III. O MERGE-SORT é um algoritmo estável, ou seja, ele não altera as posições relativas de elementos de mesmo valor no vetor ordenado.

Assinale a alternativa correta:

Todas as afirmações são verdadeiras.
Apenas as afirmações I e II são verdadeiras.
Apenas as afirmações I e III são verdadeiras.
Apenas as afirmações II e III são verdadeiras.
NDA

Ideia original de: Marcos Vinícius Mussel Cirne

MO417 - Questão para a prova oral

Número: 2010-004

Enunciado: Considere os seguintes tempos de execução para um conjunto de algoritmos quaisquer:
i) T(n) = 5n³ + 40n - 1/n²
ii) T(n) = (n² + 2n - 15)/(n - 3)
iii) T(n) = 256
iv) T(n) = lg 2ⁿ + 300n
É correto afirmar que em notação Θ os tempos de execução são, respectivamente:

Θ(n³), Θ(n²), Θ(256), Θ(lg n)
Θ(n³), Θ(n²), Θ(256), Θ(n)
Θ(n³), Θ(n), Θ(1), Θ(n)
Θ(n³), Θ(n), Θ(1), Θ(lg n)
NDA

Ideia original de: Ewerton Almeida Silva

MO417 - Questão para a prova oral

Número: 2010-003

Enunciado: Sobre o modelo RAM, é CORRETO afirmar que:

Instruções são executadas uma após a outra, sem operações concorrentes.
Modela hierarquia de memória (caches e memória virtual).
O tamanho de cada palavra de dados (word) é ilimitado.
Toda instrução gasta tempo de ordem polinomial com grau maior que zero.
NDA

Ideia original de: Alexandre Toshio Hirata

MO417 - Questão para a prova oral

Número: 2010-002

Enunciado: Invariantes de laço são normalmente utilizadas para:

Calcular o tempo de execução de um algoritmo
Planejar uma bateria de testes para um algoritmo
Ordenar os elementos de um vetor
Provar a corretude de um algoritmo
NDA

Ideia original de: Pedro Henrique Del Bianco Hokama

MO417 - Questão para a prova oral

Número: 2009-013

Enunciado: Dados dois algoritmos recursivos Alg₁ e Alg₂, sabe-se que suas relações de recorrência são dadas respectivamente por T₁(n) = 2T₁(n/2) + c₁n e T₂(n) = 4T₂(n/4) + c₂n para entradas de tamanho n > 1. Para entradas de tamanho n = 1, temos T₁(1) = c₁ e T₂(1) = c₂. Assinale a alternativa incorreta:

T₁(n)/T₂(n) = O(n).
Se c₁ = c₂ o algoritmo Alg₂ é mais rápido, embora não assintoticamente.
Alg₁ possui complexidade Θ(n lg(n)).
Alg₂ possui complexidade Θ(n^2).
NDA

Ideia original de: Ricardo Dutra da Silva

MO417 - Questão para a prova oral

Número: 2009-008

Enunciado: A busca binária é um algoritmo de busca em vetor bastante eficiente, porém, requer que este vetor esteja ordenado. Por isso, em alguns casos, dependendo do número de buscas que serão realizadas, é mais interessante utilizar a busca sequencial. Considerando isso, em qual dos seguintes casos, em um vetor com n elementos não necessariamente ordenados, é preferível utilizar a busca sequêncial a ordená-lo e utilizar a busca binária?

Quando o número de buscas é inferior a log n
Quando o número de buscas é proporcional a n
Quando o número de buscas é proporcional a n²
Quando o número de buscas é proporcional a n³
NDA

Ideia original de: Raoni Florentino da Silva Teixeira

MO417 - Questão para a prova oral

Número: 2009-005

Enunciado: Considere a relação de recorrência:

T(n) = { c, se n = 1

T(n/2) + c, se n > 1,

onde c é uma constante positiva. A solução para esta relação pertence a qual ordem de crescimento?

Θ(log n)
Θ(n)
Θ(n log n)
Θ(n²)
NDA

Ideia original de: Ana Carolina Correia Rézio

MO417 - Questão para a prova oral

Número: 2009-003

Enunciado: Sobre o algoritmo de ordenação por inserção ("insertion sort") é INCORRETO afirmar que:

No melhor caso seu tempo de execução em função do número de elementos da entrada é linear.
No pior caso seu tempo de execução em função do número de elementos da entrada é quadrático.
No caso médio seu tempo de execução em função do número de elementos da entrada é Θ(n lg n).
É um algoritmo eficiente para ordernar um número pequeno de elementos.
NDA

Ideia original de: Renato Hirata

MO417 - Questão para a prova oral

Número: 2009-001

Enunciado: Sobre o algoritmo de ordenação Merge-Sort recursivo, é INCORRETO afirmar que:

Seu tempo de execução pode ser descrito por uma equação de recorrência.
A etapa de dividir o problema em subproblemas tem tempo de execução linear (Θ(n)).
Considerando a complexidade de pior caso, é assintoticamente mais eficiente que o Insertion-Sort (ordenação por inserção).
Podemos usar ferramentas matemáticas para resolver sua equação de recorrência e estabelecer limites sobre o desempenho do algoritmo.
NDA

Ideia original de: Renato Hirata

MO417 - Questão para a prova oral

Número: 2003-011

Enunciado: Por que o algoritmo de ordenação Quick sort, se mostra na prática, mais rápido que o Insertion Sort?:

A) Porque sua razão de crescimento no pior caso é O(n3)- ene ao cubo.
B) Porque apesar de possuir razão de crescimento no pior caso O(n2), seu caso médio é O(n lg n).
C) Porque sua razão de crescimento no pior caso é O(n lg n).
D) A razão de crescimento não influencia na velocidade de execução de um algoritmo.
E) N.D.A.

Ideia original de: Patrick Henrique da Silva Brito

MO417 - Questão para a prova oral

Número: 2003-008

Enunciado:Com relação ao algoritmo de ordenação por inserção (insertion sort), assinale a alternativa INCORRETA:

A) Se o vetor de entrada estiver em ordem inversa à desejada, a ordenação levará tempo O(n²).
B) Quanto mais próxima a entrada estiver da ordem desejada, mais eficiente será a ordenação por inserção (insertion sort).
C) As exigências de espaço extra para este algoritmo consistem em armazenamento apenas para algumas variáveis temporárias.
D) A ordenação por inserção (insertion sort) geralmente é pior do que a ordenação por bolha (bubblesort).
E) NDA.

Ideia original de: Eduardo Akira Yonekura