AVDS - ALGORITMO E COMPLEXIDADE

Prévia do material em texto

1 
 Questão 
Pontos: 1,25 / 1,25 
 
(CESGRANRIO - Transpetro - Analista de Sistemas Júnior - Processos de Negócio 
- 2018) 
Uma das medidas de qualidade do código de um software é a Complexidade, que pode 
ser medida por meio da complexidade ciclomática. 
Considere um grafo de fluxo que possui 5 nós e 12 arcos. Qual a complexidade 
ciclomática desse grafo? 
 
 9 
 
19 
 
11 
 
17 
 
15 
 
 
2 
 Questão 
Pontos: 1,25 / 1,25 
 
(FCC - ARTESP - Agente de Fiscalização à Regulação de Transporte - Tecnologia de 
Informação - 2017) 
Considere a estrutura abaixo que representa um problema de rotas em pequena escala: 
 
Considere, por hipótese, que se solicitou a um Agente de Fiscalização à Regulação de 
Transporte da ARTESP utilizar alguma estratégia lógica para, partindo do ponto 1, 
chegar ao ponto 6 usando a menor rota. De um mesmo ponto pode haver mais de uma 
rota, com distâncias diferentes. A lógica correta utilizada pelo Agente, em função dos 
pontos a serem percorridos, foi: 
 
 {1} {2,3} {2,4} {5,6} {6}, caminho mais curto 1-2-5-6. 
 {1} {3,2} {4,5} {6}, caminho mais curto 1-3-4-6. 
 {6} {4} {5,3} {2,1} {1}, caminho mais curto 6-4-3-5-2-1, 
que é igual a 1-2-5-3-4-6. 
 {6} {5,4} {3,1} {1}, caminho mais curto 6-4-3-1, que é igual 
a 1-3-4-6. 
 {1} {2} {4} {6}, caminho mais curto 1-2-4-6. 
 
 
3 Pontos: 1,25 / 1,25 
 Questão 
 
(CESGRANRIO - Banco da Amazônia - Técnico Científico - Banco de Dados - 2014) 
 
O grafo anterior pode ser representado pela seguinte matriz: 
 
 
 
 
 
 
 
 
 
 
 
 
 
4 
 Questão 
Pontos: 1,25 / 1,25 
 
(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: 
 
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: 
 
 
Chave-valor 
 
Tabular 
 
Colunar 
 Grafo 
 
Documento 
 
 
5 
 Questão 
Pontos: 0,00 / 1,25 
 
Sobre os tipos de grafos e suas características podemos afirmar: 
I - Um grafo G é nulo ou vazio quando o conjunto de arestas A(G) é vazio, ou seja, 
podemos ter vários vértices mas nenhuma aresta os interligando. 
II - Um grafo é conexo regular quando todos os seus vértices têm o mesmo grau, ou 
seja, possuem a mesma quantidade de arestas. 
III - Um grafo é ciclo quando todos os grafos possuem vértice grau 2, podemos dizer 
que é uma especialização do grafo conexo regular 
IV - A soma dos graus de saída (de entrada) de um grafo direcionado é sempre o 
dobro do número de arestas no grafo. 
considerando as afirmações acima, assinale a alternativa correta: 
 
 Apenas as afirmações I e II estão corretas. 
 
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, II e III estão corretas. 
 
Apenas as afirmações II e III estão corretas. 
 
 
6 
 Questão 
Pontos: 0,00 / 1,25 
 
Diante dos conceitos e formas de representação dos grafos, seguem as afirmações: 
I - Um grafo é uma estrutura formada basicamente por dois tipos de objetos: vértices 
(nós) e arestas. 
II - Um grafo direcionado é chamado de dígrafo, nesse tipo de grafo as arestas 
possuem flechas como indicativo de direção. 
III - Em um grafo os nós (vértices) são representados por círculos, e as linhas 
representam as arestas, que interligam os nós. 
IV - Um grafo é composto por no mínimo três arestas, cada aresta liga dois nós. 
Diante das afirmações acima, assinale a alternativa correta: 
 
 
Apenas a alternativa III é verdadeira. 
 Apenas as alternativas I, II e III são verdadeiras. 
 
Apenas a alternativa II é verdadeira. 
 
Apenas as alternativas I e III são verdadeiras. 
 Apenas a alternativa I é verdadeira. 
 
 
7 
 Questão 
Pontos: 0,00 / 1,25 
 
Um grafo é uma representação abstrata das relações existentes entre um conjunto de 
objetos. Ele é composto por vértices e arestas, que ligam estes vértices. Sobre o grau 
de um vértice, é correto afirmar: 
 
 
A quantidade de vértices é ímpar quando o grau de um vértice é ímpar. 
 
O grau de um vértice é igual à quantidade de vértices mais a quantidade de 
arestas de um grafo. 
 
O grau do vértice é igual à quantidade de vértices de um grafo. 
 O grau de um vértice é igual ao número de arestas de um grafo. 
 A soma dos graus de um grafo é igual ao dobro da quantidade de arestas. 
 
 
8 
 Questão 
Pontos: 1,25 / 1,25 
 
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 define, 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 simplificar 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 afirmações acima e marque a alternativa correta. 
 
 Apenas as afirmações I, II, III e V estão corretas. 
 
Apenas as afirmações I, II e III estão corretas. 
 
Apenas as afirmações III e V estão corretas. 
 
Apenas as afirmações I e II estão corretas. 
 
Apenas as afirmações II, III, IV e V estão corretas.