Logo Passei Direto
Buscar

AV1 - Complexidade de Algoritmos_GABARITO

Ferramentas de estudo

Questões resolvidas

Considerando as funções de complexidade abaixo para os algoritmos numerados de 1 a 6 dadas por (1) f ( n ) = 100 n + 2000 log n (2) f ( n ) = 100 n log (n+1) (3) f ( n ) = 400 n + 300 n + 200 (4) f ( n ) = 1000 log n +20000 (5) f ( n ) = 2n (6) f ( n ) = 3000 log n + 3001 para n "grande" qual seria a ordenação destes algoritmos em ordem crescente de eficiência (do menos eficiente ao mais eficiente)?
Escolha uma opção:
a. 1-2-3-4-5-6
b. 5-3-2-1-4-6
c. 5-3-1-2-4-6
d. 6-4-1-2-3-5
e. 6-4-1-2-5-3

Considere os seguintes Problemas Computacionais (1) Somar Duas Matrizes de tamanho m x m (2) Multiplicar duas matrizes m x m e as afirmacoes abaixo I Os tamanhos de entrada dos dois Problemas Computacionais são iguais II Se uma Instância do Problema (1) tiver a mesma entrada que uma instância do Problema (2) ambas as instâncias terão a mesma saída III O Problema (1) terá como saída uma matriz e o Problema (2) terá como saída um número IV Para a instância do Problema (1) onde as matrizes são A = [ ]5 2 4 1 B = [ ]3 1 2 0 a saída será C = [ ]8 3 6 1 V Os algoritmos para resolução dos Problemas Computacionais (1) e (2) são iguais as que estão corretas são
Escolha uma opção:
a. IV e V
b. II e III
c. I e II
d. I e III
e. I e IV

Considere os seguintes Problemas Computacionais (1) Somar dois vetores de m componentes (2) Resolver o sistema Ax=b onde A é uma matriz mxm e b é um vetor de m componentes e as afirmações abaixo I Se uma instância do Problema (1) tiver a mesma entrada que uma instância do Problema (2) ambas as instâncias terão a mesma saída II Os tamanhos das entradas dos dois Problemas são iguais III O Algoritmo de Gauss que serve para resolver o Problema(2) é viável computacionalmente para uma matriz 20 x 20 IV Para a instância do Problema (2) onde as matrizes são A = [ ]2 0 0 1 b = [ ]4 2 x = [ ]2 2 a saída será V O Algoritmo de Cramer que serve para resolver o Problema(2) é viável computacionalmente para uma matriz 20 x 20 as que estão corretas são
Escolha uma opção:
a. III e V
b. I e II
c. IV e V
d. I e III
e. III e IV

No Algoritmo abaixo as Complexidades de Pior Caso e Melhor caso são dadas RESPECTIVAMENTE por Para i de 1 até log n faça Se vetor[i]>0 então Para j de 1 até n faça resultado=resultado+i*j+4 Fim Para Fim Se Fim Para
Escolha uma opção:
a. O( n ) e O( n log n )
b. O( n ) e O( log n )
c. O( n ) e O( n )
d. O( log n) e O( n )
e. O( n log n ) e O( log n )

Para o Algoritmo abaixo Calcule o número total de operações f somaquad:=0; Para i=1 até n faça Para j= 1 até n faça quadrado:=somaquad+j; Fim Para Fim Para Escreva(quadrado);
Escolha uma opção:
a. 2n² + 4n + 4
b. 4n²
c. 4n² + 4n + 4
d. 6n² +4n + 4
e. n+5n²+2

Considere os seguintes Problemas Computacionais (1) Resolução do Sistema Linear Ax = b onde A é m x m e b tem m componentes (2) Ordenação de um vetor de m componentes e as afirmações abaixo I Para qualquer instância do Problema (1) a saída terá tamanho menor que a entrada II O Problema(2) possui só um algoritmo para sua resolução III A saída do Problema (1) será um vetor e a do Problema (2) um número IV Uma instância que não é válida do Problema (2) é aquela de vetor de entrada V A saída do Problema (2) é sempre igual a sua entrada se o vetor de entrada já estiver ordenado as que estão corretas são
Escolha uma opção:
a. III e IV
b. I e V
c. IV e V
d. II e III
e. I e II

A Função de Complexidade de Caso Médio para a Busca Sequencial num vetor de tamanho 9 com 50 % de possibilidade de não achar o número no vetor e 50% de possibilidade de achar o número no vetor dividida igualmente para cada componente do vetor dará o seguinte resultado
Escolha uma opção:
a. 6
b. 3
c. 5
d. 7
e. 4

Para o algoritmo dado por Para i de n até 2 faça Para j de i-1 até n faça Comando; Fim Para Fim Para quantas vezes será repetido Comando?
Escolha uma opção:
a. (n +1)(n-1)/2
b. n /2
c. (n +2)(n-1)/2
d. n(n-1)/2
e. (n +1)n/2

Material
páginas com resultados encontrados.
páginas com resultados encontrados.

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Questões resolvidas

Considerando as funções de complexidade abaixo para os algoritmos numerados de 1 a 6 dadas por (1) f ( n ) = 100 n + 2000 log n (2) f ( n ) = 100 n log (n+1) (3) f ( n ) = 400 n + 300 n + 200 (4) f ( n ) = 1000 log n +20000 (5) f ( n ) = 2n (6) f ( n ) = 3000 log n + 3001 para n "grande" qual seria a ordenação destes algoritmos em ordem crescente de eficiência (do menos eficiente ao mais eficiente)?
Escolha uma opção:
a. 1-2-3-4-5-6
b. 5-3-2-1-4-6
c. 5-3-1-2-4-6
d. 6-4-1-2-3-5
e. 6-4-1-2-5-3

Considere os seguintes Problemas Computacionais (1) Somar Duas Matrizes de tamanho m x m (2) Multiplicar duas matrizes m x m e as afirmacoes abaixo I Os tamanhos de entrada dos dois Problemas Computacionais são iguais II Se uma Instância do Problema (1) tiver a mesma entrada que uma instância do Problema (2) ambas as instâncias terão a mesma saída III O Problema (1) terá como saída uma matriz e o Problema (2) terá como saída um número IV Para a instância do Problema (1) onde as matrizes são A = [ ]5 2 4 1 B = [ ]3 1 2 0 a saída será C = [ ]8 3 6 1 V Os algoritmos para resolução dos Problemas Computacionais (1) e (2) são iguais as que estão corretas são
Escolha uma opção:
a. IV e V
b. II e III
c. I e II
d. I e III
e. I e IV

Considere os seguintes Problemas Computacionais (1) Somar dois vetores de m componentes (2) Resolver o sistema Ax=b onde A é uma matriz mxm e b é um vetor de m componentes e as afirmações abaixo I Se uma instância do Problema (1) tiver a mesma entrada que uma instância do Problema (2) ambas as instâncias terão a mesma saída II Os tamanhos das entradas dos dois Problemas são iguais III O Algoritmo de Gauss que serve para resolver o Problema(2) é viável computacionalmente para uma matriz 20 x 20 IV Para a instância do Problema (2) onde as matrizes são A = [ ]2 0 0 1 b = [ ]4 2 x = [ ]2 2 a saída será V O Algoritmo de Cramer que serve para resolver o Problema(2) é viável computacionalmente para uma matriz 20 x 20 as que estão corretas são
Escolha uma opção:
a. III e V
b. I e II
c. IV e V
d. I e III
e. III e IV

No Algoritmo abaixo as Complexidades de Pior Caso e Melhor caso são dadas RESPECTIVAMENTE por Para i de 1 até log n faça Se vetor[i]>0 então Para j de 1 até n faça resultado=resultado+i*j+4 Fim Para Fim Se Fim Para
Escolha uma opção:
a. O( n ) e O( n log n )
b. O( n ) e O( log n )
c. O( n ) e O( n )
d. O( log n) e O( n )
e. O( n log n ) e O( log n )

Para o Algoritmo abaixo Calcule o número total de operações f somaquad:=0; Para i=1 até n faça Para j= 1 até n faça quadrado:=somaquad+j; Fim Para Fim Para Escreva(quadrado);
Escolha uma opção:
a. 2n² + 4n + 4
b. 4n²
c. 4n² + 4n + 4
d. 6n² +4n + 4
e. n+5n²+2

Considere os seguintes Problemas Computacionais (1) Resolução do Sistema Linear Ax = b onde A é m x m e b tem m componentes (2) Ordenação de um vetor de m componentes e as afirmações abaixo I Para qualquer instância do Problema (1) a saída terá tamanho menor que a entrada II O Problema(2) possui só um algoritmo para sua resolução III A saída do Problema (1) será um vetor e a do Problema (2) um número IV Uma instância que não é válida do Problema (2) é aquela de vetor de entrada V A saída do Problema (2) é sempre igual a sua entrada se o vetor de entrada já estiver ordenado as que estão corretas são
Escolha uma opção:
a. III e IV
b. I e V
c. IV e V
d. II e III
e. I e II

A Função de Complexidade de Caso Médio para a Busca Sequencial num vetor de tamanho 9 com 50 % de possibilidade de não achar o número no vetor e 50% de possibilidade de achar o número no vetor dividida igualmente para cada componente do vetor dará o seguinte resultado
Escolha uma opção:
a. 6
b. 3
c. 5
d. 7
e. 4

Para o algoritmo dado por Para i de n até 2 faça Para j de i-1 até n faça Comando; Fim Para Fim Para quantas vezes será repetido Comando?
Escolha uma opção:
a. (n +1)(n-1)/2
b. n /2
c. (n +2)(n-1)/2
d. n(n-1)/2
e. (n +1)n/2

Prévia do material em texto

05/04/2022 19:03 Questionário AV1 - 121R - Complexidade de Algoritmos: Revisão da tentativa
https://ava.unicarioca.edu.br/graduacao/mod/quiz/review.php?attempt=2655780&cmid=841500 1/6
Página inicial / Minha disciplinas / 121R-71680 / Espaço para AV1 / Questionário AV1 - 121R - Complexidade de Algoritmos
Questão 1
Correto
Atingiu 0,60 de
0,60
Iniciado em terça, 5 Abr 2022, 01:44
Estado Finalizada
Concluída em terça, 5 Abr 2022, 02:24
Tempo
empregado
40 minutos 1 segundo
Avaliar 5,40 de um máximo de 6,00(90%)
Considerando as funções de complexidade abaixo para os algoritmos numerados de 1 a 6 dadas por
(1) f ( n ) = 100 n + 2000 log n
(2) f ( n ) = 100 n log (n+1)
(3) f ( n ) = 400 n + 300 n + 200
(4) f ( n ) = 1000 log n +20000
(5) f ( n ) = 2n 
(6) f ( n ) = 3000 log n + 3001
para n "grande" qual seria a ordenação destes algoritmos em ordem crescente de eficiência (do menos eficiente ao
mais eficiente)?
 
 
Escolha uma opção:
a. 1-2-3-4-5-6
b. 5-3-2-1-4-6 
c. 5-3-1-2-4-6
d. 6-4-1-2-3-5
e. 6-4-1-2-5-3
2
2
3 
https://ava.unicarioca.edu.br/graduacao/
https://ava.unicarioca.edu.br/graduacao/course/view.php?id=21506
https://ava.unicarioca.edu.br/graduacao/course/view.php?id=21506&sectionid=217896
https://ava.unicarioca.edu.br/graduacao/mod/quiz/view.php?id=841500
05/04/2022 19:03 Questionário AV1 - 121R - Complexidade de Algoritmos: Revisão da tentativa
https://ava.unicarioca.edu.br/graduacao/mod/quiz/review.php?attempt=2655780&cmid=841500 2/6
Questão 2
Correto
Atingiu 0,60 de
0,60
Considere os seguintes Problemas Computacionais
 (1) Somar Duas Matrizes de tamanho m x m
 (2) Multiplicar duas matrizes m x m 
e as afirmações abaixo 
I Os tamanhos de entrada dos dois Problemas Computacionais são iguais 
II Se uma Instância do Problema (1) tiver a mesma entrada que uma instância do Problema (2) ambas as instâncias
terão a mesma saída 
III O Problema (1) terá como saída uma matriz e o Problema (2) terá como saída um número 
 
IV Para a instância do Problema (1) onde as matrizes são e a saída será 
V Os algoritmos para resolução dos Problemas Computacionais (1) e (2) são iguais
as que estão corretas são 
 
 
 
 
 
 
 
 
 
Escolha uma opção:
a. IV e V
b. II e III
c. I e II
d. I e III
e. I e IV 
A = [ ]5
2
4
1
B = [ ]3
1
2
0
C = [ ]8
3
6
1
05/04/2022 19:03 Questionário AV1 - 121R - Complexidade de Algoritmos: Revisão da tentativa
https://ava.unicarioca.edu.br/graduacao/mod/quiz/review.php?attempt=2655780&cmid=841500 3/6
Questão 3
Correto
Atingiu 0,60 de
0,60
Questão 4
Incorreto
Atingiu 0,00 de
0,60
Considere os seguintes Problemas Computacionais
 (1) Somar dois vetores de m componentes
 (2) Resolver o sistema Ax=b onde A é uma matriz mxm e b é um vetor de m componentes
e as afirmações abaixo 
I Se uma instância do Problema (1) tiver a mesma entrada que uma instância do Problema (2) ambas as instâncias
terão a mesma saída 
II Os tamanhos das entradas dos dois Problemas são iguais
III O Algoritmo de Gauss que serve para resolver o Problema(2) é viável computacionalmente para uma matriz 20 x
20 
IV Para a instância do Problema (2) onde as matrizes são e a saída será 
V O Algoritmo de Cramer que serve para resolver o Problema(2) é viável computacionalmente para uma matriz 20 x
20 
 
as que estão corretas são
 
 
 
 
 
 
 
 
 
Escolha uma opção:
a. III e V
b. I e II
c. IV e V
d. I e III
e. III e IV 
A = [ ]2
0
0
1
b = [ ]4
2
x = [ ]2
2
No Algoritmo abaixo as Complexidades de Pior Caso e Melhor caso são dadas RESPECTIVAMENTE por
Para i de 1 até log n faça
Se vetor[i]>0 então
Para j de 1 até n faça
resultado=resultado+i*j+4
Fim Para
Fim Se
Fim Para
Escolha uma opção:
a. O( n ) e O( n log n ) 
b. O( n ) e O( log n )
c. O( n ) e O( n )
d. O( log n) e O( n )
e. O( n log n ) e O( log n )
2 
2 
2 
2 
2 
05/04/2022 19:03 Questionário AV1 - 121R - Complexidade de Algoritmos: Revisão da tentativa
https://ava.unicarioca.edu.br/graduacao/mod/quiz/review.php?attempt=2655780&cmid=841500 4/6
Questão 5
Correto
Atingiu 0,60 de
0,60
Questão 6
Correto
Atingiu 0,60 de
0,60
Para o Algoritmo abaixo Calcule o número total de operações f 
 
somaquad:=0;
Para i=1 até n faça
Para j= 1 até n faça
quadrado:=somaquad+j;
Fim Para
Fim Para
Escreva(quadrado);
Escolha uma opção:
a. 2n² + 4n + 4
b. 4n²
c. 4n² + 4n + 4 
d. 6n² +4n + 4
e. n+5n²+2 
Considere os seguintes Problemas Computacionais
 (1) Resolução do Sistema Linear Ax = b onde A é m x m e b tem m componentes
 (2) Ordenação de um vetor de m componentes
e as afirmações abaixo
I Para qualquer instância do Problema (1) a saída terá tamanho menor que a entrada
II O Problema(2) possui só um algoritmo para sua resolução 
III A saída do Problema (1) será um vetor e a do Problema (2) um número 
IV Uma instância que não é válida do Problema (2) é aquela de vetor de entrada 
V A saída do Problema (2) é sempre igual a sua entrada se o vetor de entrada já estiver ordenado
 
as que estão corretas são
 
 
 
 
 
 
 
 
 
Escolha uma opção:
a. III e IV
b. I e V 
c. IV e V
d. II e III
e. I e II
v = [ ]4
1
05/04/2022 19:03 Questionário AV1 - 121R - Complexidade de Algoritmos: Revisão da tentativa
https://ava.unicarioca.edu.br/graduacao/mod/quiz/review.php?attempt=2655780&cmid=841500 5/6
Questão 7
Correto
Atingiu 0,60 de
0,60
Questão 8
Correto
Atingiu 0,60 de
0,60
Questão 9
Correto
Atingiu 0,60 de
0,60
Considerando as funções de complexidade abaixo para os algoritmos numerados de 1 a 6 dadas por
(1) f( n ) = 100 n + 2000 log n
(2) f( n ) = 100 n log n + 8000
(3) f( n ) = 30 log n - 45
(4) f( n ) = 2 +20
(5) f( n ) = 2000000000
(6) f( n ) = n + 3001
para n "grande" qual seria a ordenação destes algoritmos em ordem crescente de eficiência (do menos eficiente ao
mais eficiente)?
 
 
 
Escolha uma opção:
a. 6-4-1-2-3-5 
b. 5-3-2-1-4-6
c. 1-2-3-4-5-6
d. 6-4-1-2-5-3
e. 5-3-1-2-4-6
4
n
n
A Função de Complexidade de Caso Médio para a Busca Sequencial num vetor de tamanho 9 com 50 % de
possibilidade de não achar o número no vetor e 50% de possibilidade de achar o número no vetor dividida
igualmente para cada componente do vetor dará o seguinte resultado 
Escolha uma opção:
a. 6
b. 3
c. 5
d. 7 
e. 4
Para o vetor v=(9 ,1, 8, 2, 15, 20) utilizou-se os Algoritmos I,II e III dados por
I InsertionSort 
II BubbleSort 
III SelectionSort.
dando respectivamente X trocas de posições,Y trocas de posições e Z trocas de posições
a soma de X+Y+Z é igual a 
Escolha uma opção:
a. 10 
b. 4
c. 7
d. 6
e. 5
05/04/2022 19:03 Questionário AV1 - 121R - Complexidade de Algoritmos: Revisão da tentativa
https://ava.unicarioca.edu.br/graduacao/mod/quiz/review.php?attempt=2655780&cmid=841500 6/6
Questão 10
Correto
Atingiu 0,60 de
0,60
Para o algoritmo dado por 
 
Para i de n até 2 faça 
 Para j de i-1 até n faça 
 Comando; 
Fim Para 
Fim Para 
 
quantas vezes será repetido Comando? 
Escolha uma opção:
a. (n +1)(n-1)/2
b. n /2
c. (n +2)(n-1)/2 
d. n(n-1)/2
e. (n +1)n/2
2
◄ APS TEMA 5 NOTAS (NOTA 
MÁXIMA 0,8)
Seguir para...
APS TEMA 6 - NOTAS (MÁXIMO 0,8) 
►
Rio Comprido
Av. Paulo de Frontin, 568 Rio Comprido, Rio de Janeiro, RJ
Méier
Rua Venceslau, 315 Méier, Rio de Janeiro, RJ
 Central de atendimento: (21) 2563-1919
© 2018 UniCarioca | Todos os direitos reservados.
https://ava.unicarioca.edu.br/graduacao/mod/assign/view.php?id=841499&forceview=1
https://ava.unicarioca.edu.br/graduacao/mod/assign/view.php?id=841532&forceview=1

Mais conteúdos dessa disciplina