Prévia do material em texto

Pontuação deste teste: 30 de 30
Enviado 4 out em 20:10
Esta tentativa levou 70 minutos.
3 / 3 ptsPergunta 1
No desenvolvimento de um sistema de análise financeira, um programador utilizou um algoritmo cuja
complexidade de tempo, no pior caso, é igual a O(n).
Outro programador aponta um algoritmo de melhor complexidade igual a:
 O(n!) 
 O(n )2
 O(log n) Correto!Correto!
 O(2 )n
3 / 3 ptsPergunta 2
Considere dois vetores ordenados com n elementos cada. 
Considere então o processo de união entre os vetores, gerando assim um terceiro vetor de tamanho 2n
elementos, que também será ordenado.
Qual vai ser a complexidade de tempo do processo de união dos vetores?
 A complexidade é O(1), porque é necessário apenas realizar uma cópia simples de cada elemento do vetor. 
 
A complexidade é O(log n), porque é necessário realizar a busca binária para identificar qual será o elemento
copiado para o vetor destino.
 
A complexidade é O(n), porque é necessário copiar cada elemento original, tendo que percorrer cada vetor de
 origem.
Correto!Correto!
 
A complexidade é O(nlog n), ),porque é necessário realizar a busca de cada elemento para depois adicionar o
mesmo no vetor destino.
 
A complexidade é O(n2 ), porque há dois vetores, sendo necessário então fazer dois laços de forma aninhada
(um dentro do outro), originando uma multiplicação das quantidades de elementos.
3 / 3 ptsPergunta 3
Para uma entrada n e um tempo T, melhorias substanciais podem ser obtidas ao utilizarmos diferentes
algoritmos.
Assinale a alternativa correta com relação ao tempo de execução, para uma mesma entrada (n), porém
utilizando algoritmos diferentes.
Considere as seguintes ordens de complexidade no tempo:
T1(n) = n
T2(n) = nlogn
T3(n) = n² 
T4(n) = 2n
 T1 > T2 
 T1 > T4 
 T3 < T1 
 T4 < T3 
 T2 < T3 Correto!Correto!
3 / 3 ptsPergunta 4
Analise as afirmativas a seguir sobre complexidade de algoritmos:
I. Algoritmos de complexidade O(n log n) resolvem um problema quebrando-o em problemas menores,
resolvendo cada um deles independentemente e depois ajuntando as soluções.
II. Algoritmos de complexidade O(1) são chamados de complexidade linear, onde um pequeno trabalho é
realizado sobre cada elemento de entrada.
III. Algoritmos de complexidade O(n) são chamados de complexidade constante, onde o tempo de execução
cresce na mesma proporção do crescimento da estrutura de dados.
Estão CORRETAS as afirmativas:
 I, apenas. Correto!Correto!
 I e II, apenas. 
 I, II e III. 
 II e III, apenas. 
3 / 3 ptsPergunta 5
De acordo com Ziviani (2004) a pesquisa binária é um algoritmo de busca em vetores ordenados que segue
o paradigma de divisão e conquista.
Sobre o algoritmo de busca binária é correto afirmar:
I. No melhor caso tem complexidade O(n). 
II. No melhor caso tem complexidade O(log n). 
III. No pior caso tem complexidade O(log n). 
IV. No caso médio tem complexidade O(1).
Está correto o que se afirma em:
 
 
 
 Apenas I 
 Apenas I, II e IV 
 Apenas III Correto!Correto!
 Apenas I e III 
 Apenas II e IV 
3 / 3 ptsPergunta 6
Considere o seguinte código em português estruturado:
Qual a ordem de complexidade do pior caso desse algoritmo?
 n*n Correto!Correto!
 n 
 4*n 
 n*log n 
 3*n 
3 / 3 ptsPergunta 7
A seguir são apresentados alguns resultados do cálculo da complexidade de alguns algoritmos conhecidos
para ordenação de vetores.
Qual entre eles apresenta um bom fator de complexidade em sua execução e deve ser utilizado?
 O(2 )n
 O(n )2
 O(n) Correto!Correto!
 O(n )3
3 / 3 ptsPergunta 8
Analise o algoritmo abaixo que apresenta uma estrutura de repetição:
O algoritmo irá gerar como saída, o seguinte valor para a variável x: 
 
 3 Correto!Correto!
 2 
 1 
 4 
3 / 3 ptsPergunta 9
Analise o algoritmo abaixo que apresenta uma estrutura de repetição:
Quantas vezes o bloco de repetição (linha 6 a linha 10) vai ser executado?
 1 
 3 
 4 
 2 Correto!Correto!
3 / 3 ptsPergunta 10
Faça o teste de mesa do algoritmo abaixo:
De acordo com o resultado impresso no código acima, avalie as afirmações abaixo:
I. Os valores impressos para a variável i serão: 2, 3, 4, 5. 
II. O único valor impresso para a variável j será o 13. 
III. O único valor impresso para a variável i será o 5. 
IV. A estrutura de repetição vai ser executada 4 vezes. 
V. A estrutura de repetição vai ser executada 5 vezes.
Marque a resposta correta abaixo:
 As afirmativas II e IV estão corretas 
 As afirmativas II e III estão corretas 
 As afirmativas III e V estão corretas 
 As afirmativas I e V estão corretas 
 As afirmativas I e IV estão corretas Correto!Correto!
Pontuação do teste: 30 de 30