simulado 1 - Algoritmos e complexidade

Prévia do material em texto

Meus
Simulados
Teste seu conhecimento acumulado
Disc.: ALGORITMOS E COMPLEXIDADE   
Aluno(a): JANNE LIS HEGUEDUSCH DE SANTIS 202203634811
Acertos: 10,0 de 10,0 03/06/2023
Acerto: 1,0  / 1,0
Analise as seguintes a�rmações relacionadas a conceitos básicos sobre Programação: 
 
I. Um procedimento é um conjunto de comandos para uma tarefa especí�ca referenciada por um nome
no algoritmo principal, retornando um determinado valor no seu próprio nome. 
II. Podem-se inserir módulos em um algoritmo. Para isso, pode-se utilizar "Procedimentos" ou
"Funções". As ações das "Funções" e dos "Procedimentos" são hierarquicamente subordinadas a um
módulo principal. 
III. Cada "Função" ou "Procedimento" pode utilizar constantes ou variáveis do módulo principal ou
de�nir suas próprias constantes ou variáveis. 
IV. Uma variável global indica o endereço onde um valor é armazenado na memória do
computador, enquanto um ponteiro representa um valor numérico real. 
 
Indique a opção que contenha todas as a�rmações verdadeiras. 
I e III. 
 II e III. 
III e IV. 
I e II. 
II e IV. 
Respondido em 03/06/2023 15:12:26
Explicação:
Os procedimentos não retornam valores. Variáveis globais não indicam endereços. Ponteiro não
representa um valor numérico real, eles representam endereços. 
Acerto: 1,0  / 1,0
Considere o algoritmo em pseudocódigo, descrito a seguir.  
 Questão1
a
 Questão2
a
https://simulado.estacio.br/alunos/inicio.asp
javascript:voltar();
Calcule a complexidade do algoritmo, sabendo que a função f tem complexidade igual a O(n ).  
O(n log(n))  
O(n log (n)) 
O(n )
 O(n log(n)) 
O(n ) 
Respondido em 03/06/2023 15:11:31
Explicação:
Vamos analisar o código simpli�cado abaixo:
J=1
Enquanto j < n
J = 2xj
Para k = 0 ate j
Operação elementar
Para facilitar, vamos fazer n = 2k
J = 1 à j = 2, com 3 (21+1) iterações
J = 2 à j = 4 com 5 (22+1 )iterações
J= 4 à j = 8 com 9 (23+1)  iterações
J = 8 à j = 16 com 17 (24+1) iterações
J = 2k à j = (2k+1 + 1) iterações
O total de iterações é a soma , porém 2k=n, assim a
complexidade do código é n log n. Considerando OP com complexidade constante. Como OP é
quadrática, temos que o código analisado é n3log n.
O for mais externo se repete n vezes, assim a complexidade total do algoritmo é n4log n
Acerto: 1,0  / 1,0
2
3
2 2
5
4
3
∑
logn
i=1 (2
i + 1) < 2k ∑
logn
j=1 1 = 2
klogn
 Questão3
a
Ano: 2019 Banca: UFSC Órgão: UFSC Prova: UFSC - 2019 - UFSC - Técnico de Tecnologia da Informação
A respeito de um algoritmo recursivo, analise as a�rmativas abaixo e assinale a alternativa correta.
I. Deve conter pelo menos uma estrutura de repetição.
II. Deve conter pelo menos uma estrutura de seleção.
III. Deve invocar a si mesmo pelo menos uma vez ao ser executado.
Somente as a�rmativas II e III estão corretas.
 Somente a a�rmativa II está correta.
Somente a a�rmativa I está correta.
Todas as a�rmativas estão corretas.
Somente as a�rmativas I e II estão corretas.
Respondido em 03/06/2023 15:11:51
Explicação:
Respsota correta: Somente a a�rmativa II está correta
Acerto: 1,0  / 1,0
O código abaixo é uma implementação:
 
public class Misterio {
public static long Misterio(long x) {
if (x == 1)
return 1;
else
return x * Misterio(x-1);
}
}
Iterativa da exponenciação
Recursiva da exponenciação
 Recursiva do fatorial
Recursiva da série de Fibonacci
Iterativa da série de Fibonacci
Respondido em 03/06/2023 15:12:47
Explicação:
Resposta correta: Recursiva do fatorial
Acerto: 1,0  / 1,0
 Questão4
a
 Questão5
a
Assinale a alternativa correta a respeito dos algoritmos de ordenação bubble sort e quick sort: 
O quick sort tem um tempo de execução logarítmico no pior caso. 
O bubble sort é um algoritmo recursivo que efetua, a cada passo, o particionamento da lista que
será ordenada em duas sublistas - uma com os elementos maiores que um elemento escolhido
como pivô, e outra com os elementos maiores que este. 
O bubble sort tem um tempo de execução logarítmico em média. 
O quick sort efetua a ordenação da lista, realizando trocas de ordem sucessivas de elementos
subsequentes. 
 O bubble sort e o quick sort têm um tempo de execução quadrático no pior caso. 
Respondido em 03/06/2023 15:13:23
Explicação:
A resposta correta é: O bubble sort e o quick sort têm um tempo de execução quadrático no pior
caso. 
Acerto: 1,0  / 1,0
Em relação aos algoritmos de ordenação, avalie se as a�rmativas a seguir são verdadeiras (V) ou falsas
(F): 
 
I. O algoritmo quick sort é muito e�ciente quando há uma quantidade pequena de elementos a ordenar.  
II. O algoritmo shell sort utiliza intensamente a inserção direta.  
III. No algoritmo bubble sort, o número de variáveis envolvidas é pequeno. 
 
As a�rmativas I, II e III são, respectivamente: 
V, F e V 
F, F e V 
 F, V e V 
V, F e F 
V, V e V 
Respondido em 03/06/2023 15:13:46
Explicação:
A resposta correta é: F, V e V 
Acerto: 1,0  / 1,0
Árvores binárias podem ser usadas para representar expressões aritméticas. Como um exemplo de
expressão, podemos ter: a * b + f sen - h * j com os elementos enumerados "Em-ordem". Nesse caso, a
árvore binária terá como raiz: 
o átomo a. 
 Questão6
a
 Questão7
a
o átomo sen. 
o átomo j. 
o átomo *. 
 o átomo +. 
Respondido em 03/06/2023 15:14:40
Explicação:
A resposta correta é: o átomo +. 
Acerto: 1,0  / 1,0
Analise a seguinte árvore binária e assinale a alternativa correta.
 
"A" é �lho de todos. 
"B" e "C" são caules da árvore. 
Com exceção do nó "A", que é raiz, os demais nós são conhecido como folhas. 
 TA é a subárvore enraizada em "A", portanto toda a árvore. 
"B" tem grau de saída 3 e "C" grau 2. 
Respondido em 03/06/2023 15:15:24
Explicação:
A resposta correta é: TA é a subárvore enraizada em "A", portanto toda a árvore. 
Acerto: 1,0  / 1,0
(CESPE/CEBRASPE - IFF - Professor - Engenharia da Computação - 2018)
 Questão8
a
 Questão9
a
Considerando o grafo precedente, assinale a opção correta:
O nó 5 é adjacente a si mesmo.
 O grafo não pode ser classi�cado como conexo.
Os nós 1 e 4 são adjacentes.
Os arcos a1 e a2 são arcos irmãos.
Os nós 2 e 3 têm grau 3.
Respondido em 03/06/2023 15:16:19
Explicação:
Resposta correta: O grafo não pode ser classi�cado como conexo.
Acerto: 1,0  / 1,0
(CS-UFG - Fundação Unirg - Analista de Sistemas - 2017)
Seja S o grafo de �uxo de controle de um programa P. Se o teste que aplica um conjunto de dados de teste
satisfaz o critério todos os ramos de S, então pode-se concluir que esse conjunto também irá satisfazer o
critério:
Todas as classes de P.
Todos os caminhos de P.
Todas as respostas de P.
 Todos os comandos de P.
Todos os predicados de P.
Respondido em 03/06/2023 15:16:39
Explicação:
Resposta correta: Todos os comandos de P.
 Questão10
a