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:

1. Continuar procurando somente entre os 3 soldados mais velhos, mas agora buscando o segundo mais velho dentre eles.
2. Continuar procurando somente entre os 6 soldados mais novos, mas agora buscando o segundo mais velho dentre eles.
3. Continuar procurando somente entre os 6 soldados mais novos, mas agora buscando o segundo mais novo dentre eles.
4. Continuar procurando o sexto homem mais velho entre os 10 soldados, mas escolhendo outro soldado ao acaso.
5. 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

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:

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

Ideia original de: Daniel Vidal

MO417 - Questão para a prova oral

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

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:

1. MERGESORT
2. HEAPSORT
3. QUICKSORT
4. COUNTING SORT
5. N.D.A.

Ideia original de: Daniel Henriques Moreira

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