2 ALGORITMOS E COMPLEXIDADE

Prévia do material em texto

21/11/2023, 08:38 EPS
https://simulado.estacio.br/alunos/ 1/6
Disc.: ALGORITMOS E COMPLEXIDADE Turma: 3002
Aluno: FELIPE ANDERSON SILVA DE ANDRADE Matr.: 201703344936
Prof.: JEAN PIERRE HASHIMOTO BARROS Nota:  1,60 pts.
6679746955 04/11/2023 19:27:27
 1. Ref.: 3990627
Considere o algoritmo em pseudocódigo, descrito a seguir.  
Calcule a complexidade do algoritmo, sabendo que a função f tem complexidade igual a O(n ).  
O(n ) 
O(n log (n)) 
 O(n log(n)) 
O(n )
O(n log(n))  
Respondido em 04/11/2023 20:06:01
 2. Ref.: 3990629
Considere os algoritmos a seguir e as suas correspondentes complexidades indicadas:  
Estão corretas apenas as complexidades indicadas para os algoritmos: 
II, III, IV e V.
II, III e V.
2
3
2 2
4
5
3
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3990627.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3990627.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3990629.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3990629.');
21/11/2023, 08:38 EPS
https://simulado.estacio.br/alunos/ 2/6
I, II e IV.
 I, II e III.
I, III, IV e V.
Respondido em 04/11/2023 20:06:12
 3. Ref.: 3992613
Sobre o conceito de Algoritmos Recursivos, analise as a�rmações abaixo e, a seguir, assinale a alternativa correta.
I. Um programa tem um número limitado de procedimentos recursivos.
II. Recursividade é utilizada exclusivamente quando não se sabe solucionar um problema de maneira imediata, então
é realizada a divisão em problemas menores para alcançar o resultado desejado.
III. Todos os problemas computacionais resolvidos de maneira iterativa gastam mais memória que se resolvidos de
forma recursiva.
Somente a a�rmação III está correta
 Nenhuma das a�rmações está correta
Somente a a�rmação II está correta
As a�rmações I e II estão corretas
Somente a a�rmação I está correta
Respondido em 04/11/2023 20:06:17
 4. Ref.: 3992578
Ano: 2020 Banca: FAPEC Órgão: UFMS Prova: FAPEC - 2020 - UFMS - Técnico de Tecnologia da Informação
Considere a seguinte função recursiva: funcao recursiva(x : inteiro): inteiro início
 
se x = 1 então
 
    retorne -x
 
senão
 
      retorne -5 * recursiva(x - 1) + x
 
�mse
 
�mfuncao
 
Qual é o valor retornado pela função se ela for chamada com x = 4?
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3992613.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3992613.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3992578.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3992578.');
21/11/2023, 08:38 EPS
https://simulado.estacio.br/alunos/ 3/6
56
 164
-143
-56
143
Respondido em 04/11/2023 20:06:22
 5. Ref.: 7925951
O "Selection Sort", ou ordenação por seleção, é outro algoritmo simples de ordenação. O princípio básico deste
método é dividir o array em duas partes: a parte já ordenada e a parte não ordenada.
 
Em relação à e�ciência para grandes conjuntos de dados, como o ¿Selection Sort¿ se comporta?
Depende do tipo de dados.
Muito e�ciente.
Medianamente e�ciente.
Altamente otimizado para grandes conjuntos.
 Ine�ciente.
Respondido em 04/11/2023 20:06:28
 6. Ref.: 4053474
Assinale a alternativa correta a respeito dos algoritmos de ordenação bubble sort e quick sort: 
O quick sort efetua a ordenação da lista, realizando trocas de ordem sucessivas de elementos
subsequentes. 
O quick sort tem um tempo de execução logarítmico no pior caso. 
O bubble sort tem um tempo de execução logarítmico em média. 
 O bubble sort e o quick sort têm um tempo de execução quadrático 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. 
Respondido em 04/11/2023 20:06:32
 7. Ref.: 3990633
Analise a seguinte árvore binária e assinale a alternativa correta.
javascript:alert('C%C3%B3digo da quest%C3%A3o: 7925951.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 7925951.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 4053474.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 4053474.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3990633.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3990633.');
21/11/2023, 08:38 EPS
https://simulado.estacio.br/alunos/ 4/6
 
"B" tem grau de saída 3 e "C" grau 2. 
"A" é �lho de todos. 
"B" e "C" são caules da árvore. 
 TA é a subárvore enraizada em "A", portanto toda a árvore. 
Com exceção do nó "A", que é raiz, os demais nós são conhecido como folhas. 
Respondido em 04/11/2023 20:06:38
 8. Ref.: 3990631
A estrutura abaixo representa uma célula de uma árvore em linguagem C; 
typedef struct _no { 
int chave; 
struct _no *esq, *dir; 
} no; 
Assinale a alternativa correta sobre qual sequência será impressa ao executar um caminhamento na árvore
abaixo, conforme o código escrito em linguagem C a seguir: 
void ordem (no *arvore) {  
if (arvore != NULL) { 
printf ( "%d", arvore -> chave); 
ordem ( arvore -> esq ); 
ordem ( arvore -> dir ); 
} 
} 
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3990631.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3990631.');
21/11/2023, 08:38 EPS
https://simulado.estacio.br/alunos/ 5/6
AEXYBCD
YXEABBC
 ABCDEXY
CBDAXEY 
ABDCEYX
Respondido em 04/11/2023 20:06:41
 9. Ref.: 6115445
Para as a�rmações abaixo representamos um grafo pela letra G e seus os conjuntos de vértices por V(G) e de arestas
A(G).
I - Para todo grafo G, a soma dos graus de seus vértices será sempre o dobro do número de suas arestas.
II - Todo e qualquer grafo G possui um número par de vértices de grau ímpar.
III - Se um grafo G possui apenas as arestas A(G)={(a,c),(a,h), (h,e),(h,g),(h,c), (c,e)}, podemos dizer que este grafo
possui 6 nós.
IV - Se um grafo G possui apenas as arestas A(G)={(a,b),(a,c), (b,a), (b,c),(c,a),(c,b)}, podemos dizer que esse grafo
possui 3 vértices e é um grafo completo.
Considerando as a�rmações acima, assinale a alternativa correta:
Apenas as a�rmações I e II estão corretas.
Apenas a a�rmação I está correta.
Apenas as a�rmações I e III estão corretas.
 Apenas as a�rmações I, III e IV estão corretas.
 Apenas as a�rmações I, II e IV estão corretas.
Respondido em 04/11/2023 20:14:03
 10. Ref.: 6114407
A teoria dos grafos é estudada desde o século XVII e permite a modelagem de situações da vida real como: rede de
computadores, rede de comunicação, a Web (ligações físicas entre nós de rede), as redes sociais.
Diante da importância da teoria dos grafos, faz-se necessário o entendimento claro dos conceitos que a de�ne, como
podemos observar abaixo:
I - Em algumas literaturas, o grafo é nomeado como um modelo matemático e, em outras, como uma estrutura;
II - A função dos grafos é a de simpli�car problemas complexos, em especial problemas matemáticos, de computação
e de engenharia;
III - Um grafo pode ser representado por um conjunto de pontos, chamados nós, e outro de pares de pontos,
chamados arestas; cada aresta liga um par de pontos (extremidades) que a determina;
IV - Um grafo pode ter duas arestas diferentes com o mesmo par de pontas (nós);
V -  A representação usual de um grafo é feita por um conjunto de linhas (arestas) a ligar pontos (vértices ou nós).
Assim, avalie as a�rmações acima e marque a alternativa correta.
Apenas as a�rmações II, III, IV e V estão corretas.
 Apenas as a�rmações I e II estão corretas.
 Apenas as a�rmações I, II, III e V estão corretas.
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6115445.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6115445.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6114407.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6114407.');
21/11/2023, 08:38 EPS
https://simulado.estacio.br/alunos/ 6/6
Apenas as a�rmações III e V estão corretas.
Apenas as a�rmações I, II e III estão corretas.
Respondido em 04/11/2023 20:14:08