1. (IADES 2018) Quando dois elementos estão fora de ordem, há uma inversão, e esses
dois elementos são trocados de posição, ficando em ordem correta. Assim, o
primeiro elemento é comparado com o segundo. Se uma inversão for encontrada, a
troca é feita. Em seguida, independentemente de se houve ou não troca após a
primeira comparação, o segundo elemento é comparado com o terceiro, e, caso uma
inversão seja encontrada, a troca é feita. O processo continua até que o
penúltimo elemento seja comparado com o último. Com esse processo, garante-se
que o elemento de maior valor do vetor seja levado para a última posição. A
ordenação continua com o posicionamento do segundo maior elemento, do terceiro
etc., até que todo o vetor esteja ordenado.
CELES, W.; CERQUEIRA, R.; RANGEL, J. L.
Introdução a Estruturas de Dados . Rio de Janeiro: Elsevier, 2004, com
adaptações.
Em relação ao algoritmo descrito, é correto
afirmar que a respectiva ordem de complexidade, no pior caso, é
A) O(log(n))
B) O(n)
C) O(nⁿ)
D) O(n*log(n))
E) O(n²)
2. (IFB 2017) Leia as afirmativas a seguir a respeito das principais classes de
comportamento assintótico.
I) A complexidade logarítmica é típica de
algoritmos que resolvem problemas, transformando-os em problemas menores e
depois agrupando as soluções dos problemas menores.
II) A complexidade quadrática é típica de
algoritmos onde os dados são processados aos pares muitas vezes com um anel
dentro de outro.
III) Um algoritmo com complexidade
exponencial é mais rápido que um algoritmo linear.
IV) Um algoritmo com complexidade n! (n
fatorial) apresenta um comportamento pior que um algoritmo com complexidade 2
n.
V) A complexidade do algoritmo de pesquisa
binária é logarítmica.
Assinale a alternativa que apresenta somente
as afirmativas CORRETAS.
A) I, II, IV, V.
B) I, II, III,
IV.
C) I, II, III, V.
D) II, III, IV,
V.
E) II, IV, V.
3. (FCC 2017) Um Analista, estudando a complexidade de algoritmos de busca linear (ou
sequencial), concluiu corretamente que no pior caso, considerando um vetor de n
elementos, este tipo de algoritmo tem complexidade
A) O(n).
B) O(log 2 n-1).
C) O(√n).
D) O(log2n).
E) O(log 2 n 2
).
4. (IFB 2017) Na análise de algoritmos para resolver certos problemas, é necessário
avaliar não só o tamanho dos dados de entrada, mas os diferentes cenários para
esses dados de entrada. Estes cenários são:
A) cenário
complexo, cenário de entrada única e cenário constante;
B) caso
constante, caso polinomial e caso exponencial;
C) pior caso, caso médio, melhor caso;
D) cenário
inicial, cenário de valores intermediários e cenário assintótico;
E) caso mediano,
caso preferencial e caso particular.
5. (FCC 2017) O algoritmo QuickSort usa uma técnica conhecida por divisão e
conquista, onde problemas complexos são reduzidos em problemas menores para se
tentar chegar a uma solução. A complexidade média deste algoritmo em sua
implementação padrão e a complexidade de pior caso são, respectivamente,
A) O(n-1) e
Ο(n³).
B) Ο(n²) e Ο(n
log n²).
C) O(n²) e
O(n³).
D) Ο(n) e Ο(n²).
E) Ο(n log n) e Ο(n²).
GABARITO
1:E - 2:C - 3:A - 4:C - 5:E
0 Comentários