MO417 - Questão para a prova oral

Número: 2003-007

Enunciado : Sobre a RAM (Random access machine) e modelos de computação em geral, pode-se afirmar:  

1. A RAM é um modelo de computação cujo acesso à memória é feito de forma seqüencial.
2. Um modelo de computação facilita a análise do tempo de execução ou espaço de memória intrínsecos de um algoritmo, ao considerar todos os detalhes da implementação do hardware.
3. O modelo RAM tem poder computacional maior que o modelo da Máquina de Turing.
4. O modelo RAM é um modelo de computação no qual tanto algoritmos sequenciais quanto paralelos podem ser executados.
5. N.D.A. 

Ideia original de:  Bruno Cedraz Brandão

MO417 - Questão para a prova oral

Número: 2003-006

Enunciado: Em geral, a análise de algoritmos é realizada focando no “pior caso”. Qual das seguintes alternativas não representa uma razão para esta tendência?

1. O “pior caso” ocorre com bastante freqüência durante a execução de alguns algoritmos.
2. O tempo de execução de um algoritmo no “pior caso” pode ser considerado um limite superior para o tempo de execução padrão.
3. Freqüentemente, o “caso médio” é quase tão ruim quanto o pior caso.
4. Por não precisar de suposições sobre a distribuição probabilística das entradas, a análise do “pior caso” é geralmente mais fácil de ser realizada do que a do “caso médio”.
5. N.D.A.

Ideia original de:  Marcelo Fantinato

MO417 - Questão para a prova oral

Número: 2003-005

Enunciado: Dado um vetor de tamanho n ordenado em ordem decrescente, qual o custo de se aplicar o algoritmo insertion-sort para ordená-lo em ordem crescente?

A) n log n
B) n
C) n^2
D) log n
E) N.D.A.

Ideia original de:  Daniele Constant

MO417 - Questão para a prova oral

Número: 2003-004

Enunciado: Considere o algoritmo insertion sort representado abaixo como um programa escrito em C:

void insertsort(int x[], int n)
{
   int i, k, y;
   for (k = 1; k < n; k++)
   {
      y = x[k];
      for (i = k-1; i >= 0 && y < x[i]; i--)
         x[i+1] = x[i];
      x[i+1] = y;
   }
}
 
onde  x[]  é um vetor de inteiros quaisquer e  n é o número de elementos desse vetor, com  n >= 0 . Quanto à sua eficiência, podemos afirmar que:

1. o melhor caso ocorre quando o vetor  x[]  está ordenado em ordem decrescente.
2. o melhor caso ocorre quando o vetor  x[]  está ordenado em ordem crescente.
3. o melhor caso ocorre quando o vetor  x[]  não está ordenado.
4. independentemente do estado de ordenação em que se encontra o vetor  x[] , o algoritmo executa sempre o mesmo número de operações.
5. NDA 

Ideia original de:  Alexandro Baldassin

MO417 - Questão para a prova oral

Número: 2003-003

Enunciado: Qual o tempo de execução de pior caso para um algoritmo que inverte a ordem dos elementos de um vetor de tamanho n?

Entrada: Um vetor de n elementos (a₁, a₂, ..., a_n)
Saída: O vetor de entrada na ordem inversa: (a_n, a_n-1, ..., a₁)

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

Ideia original de:  Thiago Alves da Silva

MO417 - Questão para a prova oral

Número: 2003-002

Enunciado: Dado um vetor ordenado com n elementos, qual o menor custo com o qual é possível encontrar um elemento nesse vetor (no pior caso)?

A) 1
B) n
C) log n
D) n log n
E) n.d.a.

Ideia original de:  Nielsen Cassiano Simões

MO417 - Questão para a prova oral

Número: 2003-001

Enunciado: Dado um vetor com n inteiros quaisquer, qual das funções abaixo melhor reflete o tempo de execução para calcular de forma correta e eficiente o número de vezes que cada um dos inteiros aparece no vetor? 

A) log n
B) n log n
C) n
D) n^2
E) N.D.A.

Ideia original de:  Ricardo Luís Lachi