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?

1. Apenas a afirmação I está correta
2. Apenas as afirmações I e II estão corretas
3. As afirmações I e III estão corretas
4. Apenas as afirmações II e III estão corretas
5. 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?

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

1. Todos os algoritmos considerados têm pior caso Θ(n lg n).
2. O pior caso por inserção e o melhor caso por intercalação é Θ(n²).
3. O pior caso por seleção e inserção é Θ(n²).
4. O melhor caso por seleção e intercalação é Θ(n lg n).
5. 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:

1. Todas as afirmações são verdadeiras.
2. Apenas as afirmações I e II são verdadeiras.
3. Apenas as afirmações I e III são verdadeiras.
4. Apenas as afirmações II e III são verdadeiras.
5. 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:

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

1. Instruções são executadas uma após a outra, sem operações concorrentes.
2. Modela hierarquia de memória (caches e memória virtual).
3. O tamanho de cada palavra de dados (word) é ilimitado.
4. Toda instrução gasta tempo de ordem polinomial com grau maior que zero.
5. 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:

1. Calcular o tempo de execução de um algoritmo
2. Planejar uma bateria de testes para um algoritmo
3. Ordenar os elementos de um vetor
4. Provar a corretude de um algoritmo
5. NDA

Ideia original de: Pedro Henrique Del Bianco Hokama