MO417 - Questão para a prova oral

Número:

Enunciado: João, professor da escolinha "Criança Feliz", resolveu presentear o seu terceiro aluno mais novo da turma de 20 alunos com um DVD de suas músicas. Para saber qual pupilo satisfazia esta condição, escolheu um deles ao acaso e disse:
- Tiago, em qual dia você nasceu?
Sabendo sua data de nascimento, falou aos alunos restantes:
- Crianças, quem nasceu antes do Tiago, fique à sua frente. Quem nasceu depois, atrás.
Dito isto, notou que Tiago era o sétimo da fila. Tendo pouco tempo devido a um compromisso, qual deveria ser a próxima decisão do professor João - quem tem como hobby o estudo de algoritmos (especialmente os de busca em tempo linear) - para descobrir o aluno a ganhar o presente?

a. Escolher um entre os treze alunos atrás de Tiago e reordenar a fila a partir dele;

b. Escolher um entre os seis alunos à frente de Tiago e reordenar a fila a partir dele;

c. Escolher outro aluno ao acaso e reordenar a fila a partir dele;

d. Dar o presente para o terceiro aluno à frente de Tiago;

e. NDA

Ideia original de: Adriano Ricardo Ruggero 

MO417 - Questão para a prova oral

Número:

Enunciado: O algoritmo de ordenação Quick Sort é considerado NÃO ESTÁVEL porque:

A) Pode ordenar elementos de mesmo valor fora da ordem original do arranjo.
B) Faz a ordenação dos elementos in-place.
C) Pode produzir um particionamento não balanceado.
D) Pode escolher como pivô um elemento do início/final do arranjo.
E) NDA

Ideia original de: Adriano Ricardo Ruggero

MO417 - Questão para a prova oral

Número:

Enunciado: Indique, dentre as opções abaixo, qual NÃO É uma característica do algoritmo de ordenação HeapSort:

A)  Sua complexidade no pior caso é O(n log n).
B)  É mais eficiente para pequenos vetores de entrada.
C)  Baseia-se na ordenação por árvores.
D)  Faz a ordenação dos elementos in-place.
E)  NDA

Ideia original de: Adriano Ricardo Ruggero

Número: 2013-001

Enunciado: Suponha uma função iterativa para cálculo do módulo de um número inteiro positivo. Qual a ordem de crescimento de tal função?

A) n 

B) n log n 

C) log n 

D) n^2 

E) N.D.A.

Ideia original de:  Adriano Ricardo Ruggero

Teste de postagem no blog da disciplina MO417 - Complexidade de Algoritmos, professor João Meidanis.