[Exercícios] Algoritmos de ordenação

1) Quais destes algoritmos de ordenação têm a classe de complexidade assintótica, no pior caso, em O(n.log n) ?
(A) QuickSort, MergeSort, e HeapSort
(B) QuickSort e SelectionSort
(C) MergeSort e HeapSort
(D) QuickSort e BubbleSort
(E) QuickSort, MergeSort e SelectionSort

2) Analise o seguinte programa descrito na forma de pseudocódigo:

1. algoritmo
2. declare X[10], n, i, aux, flag numérico
3. para i ← 1 até 10 faça
4. leia X[i]
5. n ← 1
6. flag ← 1
7. enquanto (n ≤ 10 E flag = 1) faça
8. inicio
9. flag ← 0
10. para i ← 1 até 9 faça
11. inicio
12. se (X[i] < X[i+1]) então
13. inicio
14. flag ← 1
15. aux ← X[i]
16. X[i] ← X[i+1]
17. X[i+1] ← aux
18. fim_se
19. fim_para
20. n ← n + 1
21. fim_enquanto
22. para i ← 1 até 10 faça
23. escreva X[i]
24. fim_algoritmo

Esse programa realiza a ordenação decrescente de um vetor de números inteiros, que implementa o algoritmo de
(A) ordenação rápida.
(B) ordenação por troca.
(C) ordenação por seleção.
(D) ordenação por inserção.
(E) ordenação por intercalação

3) Sobre o comportamento assintótico do algoritmo de ordenação Merge Sort, assinale a alternativa que

MERGESORT(V, i, j)
(1) Se (i<j) então
(2) m = (i+j)/2;
(3) MERGESORT(v, i, m);
(4) MERGESORT(v, m+1, j);
(5) MESCLAR(v, i, m, j);
(6) Fim;

apresenta, corretamente, sua complexidade.
a) O(log n)
b) O(n log n)
c) O(n2)
d) O(n3)
e) O(2n)

4) Sobre a escolha adequada para um algoritmo de ordenação, considere as afirmativas a seguir.
I. Quando os cenários de pior caso for a preocupação, o algoritmo ideal é o Heap Sort.
II. Quando o vetor apresenta a maioria dos elementos ordenados, o algoritmo ideal é o Insertion Sort.
III. Quando o interesse for um bom resultado para o médio caso, o algoritmo ideal é o Quick Sort.
IV. Quando o interesse é o melhor caso e o pior caso de mesma complexidade, o algoritmo ideal é o
Bubble Sort.
Assinale a alternativa correta.
a) Somente as afirmativas I e II são corretas.
b) Somente as afirmativas I e IV são corretas.
c) Somente as afirmativas III e IV são corretas.
d) Somente as afirmativas I, II e III são corretas.
e) Somente as afirmativas II, III e IV são corretas.


5) Seja V um vetor de n inteiros não negativos, tal que o maior valor encontrado em V é m > 0.
Com relação à ordenação de V , considere as afirmativas a seguir.
I. O tempo de execução dos algoritmos Quicksort e Mergesort para ordenar V é 
(n lg n) para qualquer
valor de m.
II. Quando m = O(n), é possível ordenar V em tempo de execução O(n) no pior caso.
III. O tempo de execução de pior caso do Quicksort para ordenar V é O(n lg n) quando m = O(n).
IV. Para instâncias onde n = O(m), o algoritmo Countingsort é mais eficiente que o Mergesort, em função
de n.
Assinale a alternativa correta.
a) Somente as afirmativas I e II são corretas.
b) Somente as afirmativas I e IV são corretas.
c) Somente as afirmativas III e IV são corretas.
d) Somente as afirmativas I, II e III são corretas.
e) Somente as afirmativas II, III e IV são corretas.


Para responder às questões 6 e 7, considere a seguinte variante do algoritmo quicksort para ordenação de uma lista de inteiros x1, . . . , xn:

6) Seja Φ(x1, ..., xn) o número total de permutações de dois elementos durante a execução do algoritmo
QS, inclusive durante as chamadas recursivas. Seja Φmax(n) o maior valor de Φ(x1, . . . , xn) para todas as listas possíveis de comprimento n.
Sabendo que
a) Φmax(n) = n − 1.
b) Φmax(n) está em o(n).
c) Φmax(n) está em O(n log(n)), mas não em O(n).
d) Φmax(n) está em O(n2), mas não em O(n log n).
e) Φmax(n) > 2n.

7) Assinale a alternativa correta.
a) O tempo de execução do algoritmo QS, no pior caso, para entradas de tamanho n, é de Φ(n log2(n)).
b) O tempo de execução total do algoritmo para a entrada x1, . . . , xn é sempre de O(Φ(x1, . . . , xn)).
c) O tempo de execução total do algoritmo QS para a entrada x1, . . . , xn não é proporcional à soma das vezes que cada uma das linhas foi executada.
d) O tempo de execução do algoritmo QS, no pior caso, para entradas de tamanho n, é de Φ(n2).
e) O número total de comparações do algoritmo QS, incluindo as chamadas recursivas, é de O(Φmax(n)) no pior caso.

8) Relacione as colunas

(I) Inserção
(II) Seleção
(III) QuickSort
(IV) ShellSort
(V) MergeSort (ou ordenação
por fusão)

(A) Encontra o menor elemento e o troca com a primeira posição, depois o segundo menor com a segunda posição e assim sucessivamente (n-1 vezes).
(B) As comparações e trocas são feitas baseadas em uma distância determinada (por exemplo: distância 4, onde o primeiro seria comparado com o quinto elemento, o segundo com o sexto, e assim sucessivamente), depois a distância é reduzida. Este processo se repete até que a distância seja 1 e as últimas comparações e trocas sejam efetuadas.
(C) A partir do segundo elemento, este deve ser colocado na sua posição correspondente
(entre os elementos já analisados, como ao se organizarem as cartas de baralho na mão do jogador). Repete-se o procedimento até o último elemento.
(D) Escolhe-se um ponto de referência (pivô) e separam-se os elementos em 2 partes: à esquerda, ficam os elementos menores que o pivô, e à direita, os maiores. Repete-se este processo para os grupos de elementos formados (esquerda e direita) até que todos os elementos estejam ordenados.
(E) Divide-se o grupo de elementos ao meio, repete-se a divisão para cada um dos subgrupos, até que cada subgrupo tenha apenas 1 elemento. Nesse ponto, faz-se o reagrupamento dos subgrupos comparando os elementos e trocando, se necessário, para que eles fiquem ordenados. Repete-se este procedimento até restar um só grupo de elementos.


Assinale a alternativa que contém a associação correta.
a) I-A, II-D, III-B, IV-C, V-E.
b) I-B, II-A, III-C, IV-E, V-D.
c) I-B, II-A, III-E, IV-D, V-C.
d) I-C, II-A, III-D, IV-B, V-E.
e) I-D, II-E, III-B, IV-A, V-C.

9) Considere o problema de ordenação onde os vetores a serem ordenados, de tamanho n > 0, possuem [n/2] valores iguais a um número real x e [n=2] valores iguais a um outro número real y. Considere que os números reais x e y são conhecidos e fixos, porém estão distribuídos aleatoriamente no vetor a ser ordenado.
Neste caso, é correto afirmar:
a) Podemos ordenar estes vetores a um custo O(n).
b) No caso médio, o Quicksort será o algoritmo mais eficiente para este problema, com um custo O(n log n).
c) O algoritmo de ordenação por inserção sempre opera no melhor caso com um custo O(n).
d) O limite inferior para esta classe de problema é Ω(n²) .
e) O limite inferior para esta classe de problema é Ω(n logn).

10) Os fragmentos de programas abaixo, enumerados 1, 2 e 3, são implementações para o
problema de ordenação usando o algoritmo quicksort.


Assinale a alternativa que enumera os paradigmas das linguagens com as quais os
programas 1, 2 e 3 foram respectivamente implementados.
A) Lógico, imperativo e funcional
B) Imperativo, funcional e lógico
C) Funcional, lógico e imperativo
D) Lógico, funcional e imperativo
E) Funcional, funcional e imperativo


Respostas:
1) C
2) B
3) B
4) D
5) A
6) C
7) D
8) D
9) A
10) D

[Exercícios] Algoritmos de ordenação [Exercícios] Algoritmos de ordenação Reviewed by Vinicius dos Santos on 07:18:00 Rating: 5

Nenhum comentário

Escreve ai sua opinião!