Projeto de Algorítmos - Semana 5 Univesp Atividades 10pt

Prévia do material em texto

25/09/2019 Teste: Atividade para avaliação - Semana 5
https://cursos.univesp.br/courses/2629/quizzes/8328/take 1/4
2 ptsPergunta 1
Assinale verdadeiro ou falso:
Verdadeiro 1. Um algoritmo de ordenação estável mantém a ordem relativa de dados
idênticos presente na sequência desordenada fornecida como entrada.
Falso 2. Para o Input=[(“Adriana”,20),(“Alice”,15), (“Amanda”,20),(”Carlos”,15),
(“Pedro”,15)], em que (<nome>, <idade>), um algoritmo de ordenação estável aplicado para
ordenar as idades retornaria: Output= (Alice,”15”), (“Adriana”,20),(“Amanda”,20)(“Carlos”,15),
(“Pedro,15”)].
Falso 3. Quick-sort, insertion-sort e counting-sort são algoritmos de ordenação
estáveis.
Verdadeiro 4. Um algoritmo de ordenação instável pode se tornar estável simplesmente
considerando-se o índice de cada elemento na ordenação original ao se comparar os
elementos com valores idênticos na ordenação atual.
2 ptsPergunta 2
Considere o algoritmo a seguir:
O_q_Faço_?(V[1,...TAM], TAM)
 j ← 1
 ENQUANTO(j<TAM+1)
 i ← Tam
 ENQUANTO(i >j+1)
 IF(V[i] < V[i-1])
 temp = V[i-1];
 V[i-1] = V[i];
 V[i] = temp;
 FIM-SE
 i ← i-1
 FIM-ENQUANTO
25/09/2019 Teste: Atividade para avaliação - Semana 5
https://cursos.univesp.br/courses/2629/quizzes/8328/take 2/4
É verdadeira apenas a afirmativa II.
É verdadeira apenas a afirmativa III.
São verdadeiras apenas as afirmativas I e III.
Nenhuma das afirmativas é verdadeira.
São verdadeiras apenas as afirmativas I e II.
 j ← j+1
 FIM-ENQUANTO
 
Analise as seguintes afirmativas:
I – Trata-se de um algoritmo de ordenação que aplica a abordagem divisão e conquista.
II – Sendo V=[87, 62, 21, 33, 52] e TAM=5, o algoritmo executa 1 comparação e 4 trocas de
valores.
III – O algoritmo apresenta complexidade O(n ).2
Agora responda:
2 ptsPergunta 3
São verdadeiras apenas as afirmativas I e III.
São verdadeiras apenas as afirmativas II e III.
São verdadeiras todas as afirmativas.
São verdadeiras apenas as afirmativas I e II.
Nenhuma das afirmativas é verdadeira.
Considere as sentenças a seguir:
I – Um algoritmo chamado “in-place” necessita de uma estrutura de dados auxiliar para aplicar
uma transformação sobre os dados de entrada.
II – Quick-sort e Heap-sort são algoritmos “in-place”.
III – Counting-sort não é um algoritmo “in-place”.
Agora responda:
2 ptsPergunta 4
25/09/2019 Teste: Atividade para avaliação - Semana 5
https://cursos.univesp.br/courses/2629/quizzes/8328/take 3/4
São verdadeiras todas as afirmativas.
Nenhuma das afirmativas é verdadeira.
São verdadeiras apenas as afirmativas II e III.
São verdadeiras apenas as afirmativas I e III.
São verdadeiras apenas as afirmativas I e II.
O algoritmo de Coppersmith e Winograd realiza a multiplicação de matrizes com
complexidades O(n ) e 𝛀(n ) para uma entrada de tamanho n. Considere as afirmações a
seguir:
2.375 2
I – A cota superior é O(n ) e a cota inferior é 𝛀(n ).2.375 2
II – O algoritmo é assintoticamente ótimo.
III – A cota superior ainda pode ser melhorada.
Agora responda:
2 ptsPergunta 5
1ª ordenação: [131,312,572,713,243,724,124,245,437,457]
2ª ordenação: [312,713,124,724,131,437,243,245,457,572]
3ª ordenação: [124,131,243,245,312,437,457,572,713,724]
1ª ordenação: [131,312,572,713,243,124,724,245,457,437]
2ª ordenação: [713, 312,724,124,437,131,245,243,572,457]
3ª ordenação: [124,131,243,245,312,437,457,572,713,724]
1ª ordenação: [312,131,572,243,713,124,724,245,437,457]
2ª ordenação: [312,713,724,124,437,131,243,245,457,572]
3ª ordenação: [124,131,243,245,312,437,457,572,713,724]
1ª ordenação: [131,312,572,713,243,124,724,245,457,437]
2ª ordenação: [131,124,243,,245,312,457,437,572,713,724]
3ª ordenação: [124,131,243,245,312,437,457,572,713,724]
Considerando como entrada A=[713,131,312,124,245,457,572,724,243,437], qual sequência
de resultados o algoritmo radix-sort retornará?
25/09/2019 Teste: Atividade para avaliação - Semana 5
https://cursos.univesp.br/courses/2629/quizzes/8328/take 4/4
Salvo em 1:15 
1ª ordenação: [131,312,572,713,243,124,724,245,457,437]
2ª ordenação: [312,713,124,724,131,437,243,245,457,572]
3ª ordenação: [124,131,243,245,312,437,457,572,713,724]
Enviar teste