Complexidade de Algorítimos

Prévia do material em texto

COMPLEXIDADE DE ALGORITMOS 
 
Lupa Calc. 
 
 
 
 
 EEX0030_202001039252_TEMAS 
 
Aluno: JOÃO BATISTA MATTOS BEJARANO Matr.: 202001039252 
Disc.: COMPLEXIDADE DE 2021.3 EAD (GT) / EX 
 
 
Prezado (a) Aluno(a), 
 
Você fará agora seu TESTE DE CONHECIMENTO! Lembre-se que este exercício é opcional, mas não valerá ponto para sua 
avaliação. O mesmo será composto de questões de múltipla escolha. 
Após responde cada questão, você terá acesso ao gabarito comentado e/ou à explicação da mesma. Aproveite para se 
familiarizar com este modelo de questões que será usado na sua AV e AVS. 
 
 
 
 
1. 
 
 
Analise as seguintes afirmações relacionadas a conceitos básicos sobre Programação: 
 
I. Um procedimento é um conjunto de comandos para uma tarefa específica 
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 definir 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 afirmações verdadeiras. 
 
 I e II. 
 
 I e III. 
 
 II e IV. 
 II e III. 
 
 III e IV. 
Data Resp.: 04/11/2021 19:56:49 
 
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. 
 
 
 
 
 
2. 
 
Considere o algoritmo em pseudocódigo, descrito a seguir.  
https://simulado.estacio.br/bdq_simulados_exercicio_ensineme.asp
https://simulado.estacio.br/bdq_simulados_exercicio_ensineme.asp
javascript:diminui();
javascript:aumenta();
javascript:calculadora_on();
 
 
Calcule a complexidade do algoritmo, sabendo que a função f 
tem complexidade igual a O(n22).  
 
 
 O(n33) 
 
 O(n22log22(n)) 
 O(n44log(n)) 
 
 O(n33log(n)) 
 
 O(n55) 
Data Resp.: 04/11/2021 19:58:02 
 
Explicação: 
A resposta correta é: O(n44log(n)) 
 
 
 
 
 
3. 
 
 
Sobre o conceito de Algoritmos Recursivos, analise as afirmaçõ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. 
 
Nenhuma das afirmações está correta 
 
 
As afirmações I e II estão corretas 
 
 
Somente a afirmação I está correta 
 
 
Somente a afirmação III está correta 
 
 
Somente a afirmação II está correta 
Data Resp.: 04/11/2021 19:59:13 
 
Explicação: 
Resposta correta: Nenhuma das afirmações está correta 
 
 
 
 
 
4. 
 
 
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 afirmativas 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. 
https://simulado.estacio.br/bdq_simulados_exercicio_ensineme.asp
https://simulado.estacio.br/bdq_simulados_exercicio_ensineme.asp
 
 
Somente as afirmativas II e III estão corretas. 
 
 
Somente a afirmativa I está correta. 
 
 
Somente as afirmativas I e II estão corretas. 
 
Somente a afirmativa II está correta. 
 
 
Todas as afirmativas estão corretas. 
Data Resp.: 04/11/2021 20:04:20 
 
Explicação: 
Respsota correta: Somente a afirmativa II está correta 
 
 
 
 
 
5. 
 
 
A ordenação de elementos em um vetor pode ser executada a partir de diversos 
algoritmos conhecidos que são adequados para situações específicas. Sobre algoritmos 
de ordenação, analise as seguintes afirmativas: 
 
I. O algoritmo bubble sort é eficiente para ordenar poucos elementos, mas é lento para 
ordenar muitos itens. 
II. O algoritmo selection sort para ordenação crescente consiste em mover o menor 
valor do vetor para a primeira posição; depois, o segundo menor para a segunda 
posição; e assim sucessivamente, até os dois últimos valores. 
III. O algoritmo quick sort ordena os valores de um vetor por meio de sucessivas 
seleções do elemento correto a ser posicionado em um segmento ordenado. 
 
Está(ão) correta(s) a(s) afirmativa(s): 
 
 I, II e III 
 I e II 
 
 I apenas 
 
 II apenas 
 
 I e III 
Data Resp.: 04/11/2021 20:05:21 
 
Explicação: 
A resposta correta é: I e II 
 
 
 
 
 
6. 
 
Considere que os percentuais foram inseridos no vetor vet de 5 posições, a partir da 
posição 1, na seguinte sequência: 25.33, 27.72, 27.10, 26.90 e 27.31, ou seja, com os 
dados de 2008 até 2012. Um técnico em processamento de dados do TCE-RS utilizou 
um método para ordenar os dados de vet. O método realizou os seguintes passos no 
processo de ordenação: 
 
• Passo 1 - 25.33 27.72 27.10 26.90 27.31; 
• Passo 2 - 25.33 27.10 27.72 26.90 27.31; 
• Passo 3 - 25.33 26.90 27.10 27.72 27.31; 
• Passo 4 - 25.33 26.90 27.10 27.31 27.72. 
https://simulado.estacio.br/bdq_simulados_exercicio_ensineme.asp
https://simulado.estacio.br/bdq_simulados_exercicio_ensineme.asp
 
 
Trata-se do método de ordenação: 
 
 Selection sort 
 
 Bubble sort 
 
 Quick sort 
 Insertion sort 
 
 Fast sort 
Data Resp.: 04/11/2021 20:06:23 
 
Explicação: 
A resposta correta é: Insertion sort 
 
 
 
 
 
7. 
 
 
Analise a seguinte árvore binária e assinale a alternativa correta. 
 
 
 "A" é filho de todos. 
 
 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" e "C" são caules da árvore. 
 
 "B" tem grau de saída 3 e "C" grau 2. 
Data Resp.: 04/11/2021 20:08:08 
 
Explicação: 
A resposta correta é: TA é a subárvore enraizada em "A", portanto toda a 
árvore. 
 
 
 
 
 
8. 
 
A estrutura abaixo representa uma célula de uma árvore em linguagem C; 
typedef struct _no { 
int chave; 
struct _no *esq, *dir; 
} no; 
https://simulado.estacio.br/bdq_simulados_exercicio_ensineme.asp
https://simulado.estacio.br/bdq_simulados_exercicio_ensineme.asp
 
 
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 ); 
} 
} 
 
 ABDCEYX 
 
 AEXYBCD 
 
 CBDAXEY 
 
 YXEABBC 
 ABCDEXY 
Data Resp.: 04/11/2021 20:09:58 
 
Explicação: 
A resposta correta é: ABCDEXY 
 
 
 
 
 
9. 
 
 
(FCM - IFN-MG - Ciências da Computação: Teoria da Computação - 2018) 
Considere o grafo abaixo assim como sua representação por lista de adjacência: 
 
 
 
A Árvore em Largura e a Árvore em Profundidade, respectivamente, tendo como raiz o vértice 1, são: 
https://simulado.estacio.br/bdq_simulados_exercicio_ensineme.asp
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Data Resp.: 04/11/2021 20:11:55 
 
Explicação: 
Resposta correta: 
 
 
 
 
 
10. 
 
(COMPERVE - UFRN - Engenheiro - Engenharia da Computação - 2019) 
 
O código abaixo pode ser utilizado para atravessar um grafo: 
 
Entrada: um gráfico G e um vértice v de G 
 
Saída: todos os vértices alcançáveis de v marcados 
 
função DFS(G,v): 
 
 marque v 
 
 para todas as arestas adjacentesa v, faça 
 
 se vértice w não estiver marcado, então 
 
 Chame recursivamente DFS(G,w) 
 
 fim se 
 
 fim para 
 
fim função 
https://simulado.estacio.br/bdq_simulados_exercicio_ensineme.asp
 
 
Entre os diversos tipos de algoritmos utilizados para atravessar grafos, esse código implementa o algoritmo: 
 
 
Busca exaustiva ou brute force search. 
 
 
Busca pelo caminho mínimo (shortest path). 
 
Busca em profundidade ou depth first search. 
 
 
Busca melhor-primeiro ou best first search. 
 
 
Busca em largura ou breadth first search. 
Data Resp.: 04/11/2021 20:14:23 
 
Explicação: 
Resposta correta: Busca em profundidade ou depth first search. 
 
 
 
 
 
 
 Não Respondida Não Gravada Gravada 
 
 
 
Exercício inciado em 04/11/2021 19:55:29.