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:

1. T₁(n)/T₂(n) = O(n).
2. Se c₁ = c₂ o algoritmo Alg₂ é mais rápido, embora não assintoticamente.
3. Alg₁ possui complexidade Θ(n lg(n)).
4. Alg₂ possui complexidade Θ(n^2).
5. 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?

1. Quando o número de buscas é inferior a log n
2. Quando o número de buscas é proporcional a n
3. Quando o número de buscas é proporcional a n²
4. Quando o número de buscas é proporcional a n³
5. 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?

1. Θ(log n)
2. Θ(n)
3. Θ(n log n)
4. Θ(n²)
5. 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:

1. No melhor caso seu tempo de execução em função do número de elementos da entrada é linear.
2. No pior caso seu tempo de execução em função do número de elementos da entrada é quadrático.
3. No caso médio seu tempo de execução em função do número de elementos da entrada é Θ(n lg n).
4. É um algoritmo eficiente para ordernar um número pequeno de elementos.
5. 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:

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