Av2 Algoritmo e Complexidade

Prévia do material em texto

1a Questão 
Respondido em 10/11/2022 19:39 
 Ref.: 201910264212 
 
 
Seja n o tamanho da entrada de um algoritmo para um problema P. 
Cada alternativa, que corresponde a um algoritmo distinto, apresenta o número de 
operações necessárias para resolver P. 
Considerando-se a análise assintótica (Big O notation), qual algoritmo possui menor 
complexidade? 
 
 
5 n2 + n 
 
 
500 + 100 n3 
 
2n 
 
100 + 10 log n 
 
15n + 256 
 
 
 
 2a Questão 
Respondido em 10/11/2022 19:41 
 Ref.: 201910328134 
 
 
Assinale a alternativa que define corretamente a técnica de função fatorial empregada no 
pseudocódigo a seguir. 
1. funcao fatorial(n) 
2. se n=1 então 
3. fatorial = 1 
4. senao 
5. fatorial = n * fatorial(n-1) 
6. fim funcao 
 
 
Árvore de Decisão. 
 
Backtracking. 
 
Árvore Rubro-Negra. 
 
Árvore Binária. 
 
Recursividade. 
 
 
 
 3a Questão 
Respondido em 10/11/2022 20:01 
 Ref.: 201910202917 
 
 
A recursividade é uma ferramenta poderosa para resolução de diversos problemas na 
computação. Alguns, que seriam solucionados com algoritmos complexos e difíceis de 
entender, conseguem ser resolvidos de forma elegante e bem mais simples. 
javascript:alert('C%C3%B3digo da quest%C3%A3o: 7703471/n/nStatus da quest%C3%A3o: Liberada para Uso.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 7767393/n/nStatus da quest%C3%A3o: Liberada para Uso.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 7642176/n/nStatus da quest%C3%A3o: Liberada para Uso.');
Diversos problemas complexos da computação são resolvidos utilizando programação 
dinâmica e/ou paradigmas de programação funcional. Essas técnicas e paradigmas são todas 
baseadas em programação recursiva, o que torna obrigatório o conhecimento adequado da 
recursividade. 
Sobre recursividade podemos afirmar: 
I ) Não é necesário entender a definição recursiva de um algoritmo para realizar sua 
implementação; 
II ) Ao elaborarmos algoritmos recursivos é importante testar os limites dos valores a serem 
inseridos (carregados) para, assim, avaliarmos em que tipos de aplicações devemos utilizar-
los; 
III) Um algoritmo recursivo deve chamar a si mesmo, recursivamente; 
IV ) Ao implementar algoritmos recursivos é importante consideramos a utilização da pilha 
da memória do computador, procedimento que pode levar a estouros da capacidade de 
memória; 
ssinale a alternativa correta: 
a) apenas as afirmações I, II e III são verdadeiras; 
b) apenas as afirmações II, III e IV são verdadeiras; 
c) apenas as afirmações I e IV são verdadeiras; 
d) apenas as afirmações I, II e IV são verdadeiras; 
e) todas as afirmações são verdadeiras; 
 
Asinale a alternativa correta: 
 
 
apenas as afirmações I e IV são verdadeiras; 
 
apenas as afirmações II, III e IV são verdadeiras; 
 
apenas as afirmações I, II e IV são verdadeiras; 
 
todas as afirmações são verdadeiras; 
 
apenas as afirmações I, II e III são verdadeiras; 
 
 
 
 4a Questão 
Respondido em 10/11/2022 19:43 
 Ref.: 201910263693 
 
 
A ordenação é uma operação comum em muitas aplicações. Muitos algoritmos foram 
desenvolvidos para executá-la. Sobre alguns desses algoritmos, é correto afirmar: 
 
 
o selection sort divide os itens em dois segmentos, ordena-os individualmente e 
depois mescla-os. 
 
o quick sort particiona os itens em dois segmentos separados por um elemento pivô 
e ordena-os recursivamente. 
 
o bubble sort busca um elemento fora de ordem em elementos sucessivos, depois 
insere o item no local apropriado. 
 
o insertion sort troca dois elementos adjacentes se estiverem fora de ordem, 
repetindo esse procedimento até que os itens estejam ordenados. 
 
O bubble sort é baseado em se passar sempre o menor valor do vetor para a 
primeira posição (ou o maior dependendo da ordem requerida), depois o segundo 
menor valor para a segunda posição e assim sucessivamente, até os últimos dois 
elementos. 
 
 
 
javascript:alert('C%C3%B3digo da quest%C3%A3o: 7702952/n/nStatus da quest%C3%A3o: Liberada para Uso.');
 5a Questão 
Respondido em 10/11/2022 19:55 
 Ref.: 201910183328 
 
 
Sobre o algoritmo de ordenação Quick sort, marque a opção incorreta: 
 
 Algoritmo de ordenação que adota a estratégia de divisão e 
conquista. A estratégia consiste em rearranjar as chaves de modo 
que as chaves menores precedam as chaves maiores. Em seguida 
ordena as duas sublistas de chaves menores e maiores 
recursivamente até que a lista completa se encontre ordenada. 
 É um algoritmo de ordenação não estável. 
 Algoritmo de ordenação cuja a complexidade computacional de pior 
caso é de ordem quadrática, ou seja, O(n2)O(n2), onde n é a 
quantidade de elementos do vetor. 
 Algoritmo de ordenação cuja a complexidade computacional de melhor 
caso é da ordem, O(n log n), onde n é a quantidade de elementos 
do vetor. 
 Algoritmo de ordenação cuja a complexidade computacional de melhor 
caso é de ordem quadrática, ou seja, O(n2)O(n2), onde n é a 
quantidade de elementos do vetor. 
 
 
 
 6a Questão 
Respondido em 10/11/2022 19:45 
 Ref.: 201910183522 
 
 
Seja o pseudocódigo abaixo que representa uma função Algoritmo-
Ordenar, que recebe por parâmetro um vetor A e o tamanho do vetor n e 
que é responsável por ordenar um vetor: 
1. Algoritmo-Ordenar(int vetor[ ], int n){ 
2. para j = n-1 até 1 faça 
3. para i = 1 até n-1 faça 
4. se A[i] > A[i+1] então 
5. aux = A[i]; 
6. A[i] = A[i+1]; 
7. A[i+1] = aux; 
8. fim-se 
9. fim-para 
10. fim-para 
11. } 
Marque a opção que apresenta de qual algoritmo de ordenação se trata o 
pseudocódigo acima: 
 
 Selection sort 
 Insertion sort 
 Quick sort 
 Merge sort 
 Bubble sort 
 
 
javascript:alert('C%C3%B3digo da quest%C3%A3o: 7622587/n/nStatus da quest%C3%A3o: Liberada para Uso.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 7622781/n/nStatus da quest%C3%A3o: Liberada para Uso.');
 
 7a Questão 
Respondido em 10/11/2022 19:46 
 Ref.: 201910328432 
 
 
Uma árvore AVL é uma árvore binária de busca autobalanceada que respeita algumas 
propriedades fundamentais. Como todas as árvores, ela tem uma propriedade chamada 
altura, que é igual ao valor da altura de sua raiz. 
 
Sabendo que a altura de uma folha é igual a um e que a altura de um nó pai é igual ao 
máximo das alturas de seus filhos mais um, qual estrutura NÃO pode representar uma 
árvore AVL? 
 
 
Uma árvore com três nós e altura igual a dois. 
 
Uma árvore com seis nós e altura igual a três. 
 
Uma árvore com três nós e altura igual a três. 
 
Uma árvore vazia. 
 
Uma árvore com dois nós. 
 
 
 
 8a Questão 
Respondido em 10/11/2022 19:57 
 Ref.: 201910181848 
 
 
Um problema comum em estruturas de dados do tipo árvores é determinar 
o como percorrer uma árvore binária. Existem algumas maneiras clássicas 
de fazer caminhamento em árvores binárias. Algumas delas são: 
1. Pré-ordem: Visitar primeiro a raiz, depois a sub-árvore esquerda e 
por último a sub-árvore direita. 
2. Em-ordem: Visitar primeiro a sub-árvore esquerda, depois a raiz e 
por último a sub-árvore direita. 
3. Pós-ordem: Visitar primeiro a sub-árvore esquerda, depois a sub-
árvore direita e por último a raiz. 
Seja uma Árvore Binária T gerada com a inserção dos seguintes nós: 4 - 2 - 
6 - 1 - 8 - 5. O resultado do caminhamento pré-ordem, em-ordem e pós-
ordem nessa árvore binária T é: 
 
 1. Pré-ordem: 4 - 2 - 1 - 6 - 5 - 8 
2. Em-ordem: 1 - 2 - 4 - 5 - 6 - 8 
3. Pós-ordem: 1 - 2 - 5 - 8 - 6 - 4 
 1. Pré-ordem: 4 - 2 - 1 - 6 - 8 - 5 
2. Em-ordem: 1 - 2 - 5 - 8 - 6 - 4 
3. Pós-ordem: 1 - 2 - 4 - 5 - 6 - 8 
 1. Pré-ordem: 4 - 2 - 1 - 6 - 8 - 5 
2. Em-ordem: 4 - 2 - 5 - 8 - 6 - 1 
3. Pós-ordem: 1 - 2 - 4 - 5 - 6 - 8 
 1. Pré-ordem: 1 - 2 - 4 - 5 - 6 - 8 
2. Em-ordem: 1 - 2 - 5 - 8 - 6 - 4 
3. Pós-ordem: 6 - 2 - 5 - 8 - 1 - 4 
javascript:alert('C%C3%B3digo da quest%C3%A3o: 7767691/n/nStatus da quest%C3%A3o: Liberadapara Uso.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 7621107/n/nStatus da quest%C3%A3o: Liberada para Uso.');
 1. Pré-ordem: 1 - 2 - 5 - 8 - 6 - 4 
2. Em-ordem: 1 - 2 - 4 - 5 - 6 - 8 
3. Pós-ordem: 4 - 2 - 1 - 6 - 5 - 8 
4. 
 
 
 
 9a Questão 
Respondido em 10/11/2022 20:03 
 Ref.: 201910203283 
 
 
As árvores formam uma estrutura de dados muito importante, compreender os conceitos e o 
funcionamento de árvores significa perceber como ocorre a manipulação de memória, a 
programação, a arquitetura de computadores e sistemas operacionais. 
As árvores têm aplicações diversas, estando presentes em sistemas simples de busca, 
bancos de dados, sistemas de arquivos e muitos outros. Assim, enriquece e capacita o 
profissional para lidar com os problemas inerentes à área de TI. 
Nesse contexto, ao falarmos de árvores binárias, podemos afirmar 
I) em árvores binárias um percurso é a visita sistemática aos elementos de uma estrutura 
de dados; 
II) existem três percursos distintos para árvores binárias: Percurso em pré-ordem, Percurso 
em ordem simétrica e Percurso em pós-ordem; 
III) podemos considerar que o conceito de árvore binária é recursivo, isto é, a estrutura foi 
definida em termos recursivos; 
IV) As árvores são uma estrutura de dados que auxiliam na resolução de problemas da 
busca, inserção e remoção. 
Assinale a alternativa correta: 
 
 
apenas as alternativas II e III são corretas 
 
apenas as alternativas I, II e III são corretas 
 
apenas as alternativas II, III e IV são corretas 
 
apena a alternativa IV esta correta 
 
todas as alternativas são corretas 
 
 
 
 10a Questão 
Respondido em 10/11/2022 19:54 
 Ref.: 201910203023 
 
 
Uma árvore binária T é uma estrutura de dados caracterizada ou por não ter elemento 
algum, ou por ter um elemento distinto, denominado raiz, com dois ponteiros para duas 
estruturas diferentes, denominadas subárvore esquerda e subárvore direita. 
javascript:alert('C%C3%B3digo da quest%C3%A3o: 7642542/n/nStatus da quest%C3%A3o: Liberada para Uso.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 7642282/n/nStatus da quest%C3%A3o: Liberada para Uso.');
 
Assim, considerando árvore binária acima (figura 01), seguem as afirmações: 
Nesse contexto podemos afirmar 
I) A é um nó raiz de T e B é um nó raiz de uma subárvore de T; 
II) B e C são nós filhos de A, assim como D e E são nós filhos de B; 
III) Caso seja incluído um percurso direto entre D e F, a figura deixa de representar uma 
árvore e passa a ser um grafo; 
IV) Os nós D, F, B e C são considerados nós folha. 
Assim, assinale a alternativa correta: 
 
 
 
 
todas as afirmações estão corretas 
 
apenas as afirmações II e IV são corretas 
 
apenas as afirmações I, II e III são corretas 
 
apenas as afirmações II, III e IV são corretas 
 
apenas as afirmações II e III são corretas 
 
 
 
 
 
 
Questões de Crédito Digital - 
 
 1a Questão 
Respondido em 10/11/2022 19:43 
 Ref.: 201906553365 
 
 
(Adaptado de: DPE-RJ - Técnico Superior Especializado - Tecnologia da Informação - 2019) 
Para que um sistema seja testado adequadamente, é preciso realizar uma quantidade 
mínima de testes. Para apoiar essa definição, foi criada a Complexidade Ciclomática de 
McCabe, com fundamentação na teoria dos grafos. Essa técnica define uma métrica de 
software que fornece uma medida quantitativa da complexidade lógica de um programa, 
apresentando um limite superior para a quantidade de casos de testes de software que 
devem ser conduzidos. 
 
A Complexidade Ciclomática pode ser calculada tanto pelo número de regiões quanto pelo 
número de arestas e nós. 
 
Complexidade é calculada pela fórmula CC = arestas - nós + 2 
 
Com base no grafo de fluxo anterior, correspondente a um trecho de código a ser testado, a 
quantidade mínima de testes que devem ser realizados para garantir que cada caminho do 
código tenha sido percorrido em ao menos um teste é: 
 
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3992624/n/nStatus da quest%C3%A3o: Liberada para Uso.');
 5 (cinco) 
 11 (onze) 
 3 (três) 
 4 (quatro) 
 6 (seis) 
 
 
 2a Questão 
Respondido em 10/11/2022 19:47 
 Ref.: 201908667328 
 
 
Seja G = (V, E) um grafo em que V é o conjunto de vértices e E é o conjunto de arestas. 
Com base nesse grafo, considere as afirmativas a seguir. 
I. Se G é um grafo com número de vértices ímpar, a soma dos graus também será ímpar. 
II. Se G é um grafo, a soma dos graus dos vértices é sempre o dobro do número de arestas. 
III. Se G é um grafo sem arestas, dizemos que G é um grafo vazio ou nulo. 
IV. Se G é um grafo conexo e sem ciclos dizemos que G é uma árvore. 
 
 
Somente as afirmativas II, III e IV são corretas. 
 
Somente as afirmativas III e IV são corretas. 
 
Somente as afirmativas I e IV são corretas. 
 
Somente as afirmativas I, II e III são corretas 
 
Somente as afirmativas I e II são corretas 
 
 
 3a Questão 
Respondido em 10/11/2022 19:45 
 Ref.: 201906553372 
 
 
(CESPE/CEBRASPE - TRT - 8ª Região (PA e AP) - Analista Judiciário - Tecnologia da 
Informação - 2016) 
 
A quantidade de grau total do grafo na figura é: 
 
 
17 
 
16 
 
13 
 
15 
 
14 
 
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6106587/n/nStatus da quest%C3%A3o: Liberada para Uso.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3992631/n/nStatus da quest%C3%A3o: Liberada para Uso.');
 
 4a Questão 
Respondido em 10/11/2022 20:10 
 Ref.: 201908667334 
 
 
Ciclos são estruturas muito importantes. São os ciclos que tornam grafos interessantes mas 
também complexos e difíceis de manipular. Um ciclo em um grafo é um caminho fechado. 
Portanto, todo ciclo tem comprimento maior que 1 e não tem arcos repetidos. Dizemos que 
um arco v-w pertence a um dado ciclo (ou que o ciclo passa pelo arco) se o vértice w é o 
sucessor de v no ciclo. Um ciclo é simples se não tem vértices repetidos exceto pelo último 
(que coincide com o primeiro). 
Disponível em: https://www.ime.usp.br/~pf/algoritmos_para_grafos/aulas/paths-and-
cycles.html. Acesso em: 30 abr. 2022 
Dado a definição são problemas que envolvem ciclos em grafos: 
 
 
Coloração em Grafos. 
 
Problema de densidade em grafos. 
 
Problema de emparelhamento em grafos. 
 
Problema do caixeiro viajante. 
 
Problema de planaridade em grafos. 
 
 
 5a Questão 
Respondido em 10/11/2022 19:44 
 Ref.: 201906553373 
 
 
(CESGRANRIO - Banco da Amazônia - Técnico Científico - Banco de Dados - 2014) 
 
O grafo anterior pode ser representado pela seguinte matriz: 
 
 
 
 
 
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6106593/n/nStatus da quest%C3%A3o: Liberada para Uso.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3992632/n/nStatus da quest%C3%A3o: Liberada para Uso.');
 
 
 
 
 
 
 
 6a Questão 
Respondido em 10/11/2022 20:13 
 Ref.: 201908676186 
 
 
Para as afirmaçõ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 afirmações acima, assinale a alternativa correta: 
 
 
Apenas as afirmações I, III e IV estão corretas. 
 
Apenas a afirmação I está correta. 
 
Apenas as afirmações I, II e IV estão corretas. 
 
Apenas as afirmações I e III estão corretas. 
 
Apenas as afirmações I e II estão corretas. 
 
 
 7a Questão 
Respondido em 10/11/2022 19:51 
 Ref.: 201906553371 
 
 
(IBGE - Analista Censitário - Análise de Sistemas - Desenvolvimento de Aplicações - Web 
Mobile -2017) 
Observe a figura a seguir que ilustra relações entre colegas e seus interesses: 
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6115445/n/nStatus da quest%C3%A3o: Liberada para Uso.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3992630/n/nStatus da quest%C3%A3o: Liberada para Uso.');
 
O tipo de Banco de Dados NoSQL, não relacional, que armazena tais informações, utilizando 
estruturas de vértices e arestas, com propriedades associadas, é o: 
 
 
Tabular 
 
Colunar 
 
Documento 
 
Grafo 
 
Chave-valor 
 
 
 8a Questão 
Respondido em 10/11/2022 19:51 
 Ref.: 201908676211 
 
 
O grafo G é definido por: 
V = { p | p é uma pessoa da família Azevedo } 
A = { (x,y) | < x é pai/mãe de y > } 
Dados do grafo G: 
V = { Solange, Livia, Roberto, Rodrigo, Ana, Emanoel} 
A = {(Solange, Livia), (Roberto, Livia), (Ana,Rodrigo), (Rodrigo, Emanoel), 
(Roberto,Rodrigo)} 
Considerando os dados acima, avalie as afirmações abaixo: 
I - Temos uma relação simétrica definida por A. 
II - O grafo G é considerado um grafo orientado e as conexões entre os vértices são 
chamadas de arcos. 
III - O grafo possui 05 arestas, caso se decida excluir o vértice Rodrigo, o grafo passará a 
ter apenas 03 arestas 
IV - O grafo G é considerado um grafo digrafo. 
Diante dos dados acima, assinale a alternativa correta: 
 
 
Apenas as alternativas I, III e IV estão corretas. 
 
Apenas as alternativas II e III estão corretas. 
 
Apenas as alternativas I, II e IV estão corretas. 
 
Apenas as alternativas I e III estão corretas. 
 
Apenas as alternativas II, III e IV estão corretas. 
 
 
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6115470/n/nStatus da quest%C3%A3o: Liberada para Uso.');