Questões de Concurso Sobre grafos em algoritmos e estrutura de dados

A respeito de algoritmos e estruturas de dados, assinale a alternativa correta.

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 adjacentes a 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

Entre os diversos tipos de algoritmos utilizados para atravessar grafos, esse código implementa o algoritmo

Sobre estruturas de dados, assinale a alternativa CORRETA.

Seja S o grafo de fluxo 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

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.

 

Com base no grafo de fluxo acima, 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 é:

Tendo como entrada um grafo acíclico dirigido ponderado G = (V, E), pode-se calcular o caminho mínimo de origem única,

A obtenção das componentes fortemente conexas de um grafo dirigido G = (V, E) é feita da seguinte forma:

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

Considere a matriz de adjacência abaixo correspondente a um grafo direcionado ponderado.

Avalie as afirmações referentes ao menor caminho tendo como origem o vértice 1.

I. O menor caminho do vértice 1 até o vértice 7 passa pelos vértices 3 e 8.

II. O menor caminho do vértice 1 até o vértice 5 passa pelo vértice 2.

III. O menor caminho do vértice 1 até o vértice 9 passa pelos vértices 2 e 6.

IV. O menor caminho do vértice 1 até o vértice 8 passa pelos vértices 3 e 6.

V. O menor caminho do vértice 1 até o vértice 6 passa pelo vértice 4.

Está correto apenas o que se afirma em

Considere os grafos I e II mostrados abaixo.

É correto afirmar que

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?

Sobre o uso de grafos de causa e efeito, assinale a alternativa correta.

As regras de negócio de uma empresa de aluguel de carros foram descritas através de um grafo de causa e efeito conforme mostrado abaixo.
C1: idade > 23 E1: aluga C2: sem registro de multas E2: cobrança extra C3: é cliente frequente C4: aluguel para lazer


Considerando-se a lógica representada no grafo, assinale com V (verdadeiro) ou F (falso) as assertivas abaixo.
( ) Um cliente de 24 anos com registro de multa e em viagem de negócios pode alugar um carro. ( ) Um cliente de 24 anos sem registro de multas e em viagem de negócios pode alugar o carro e terá uma cobrança extra. ( ) Um cliente frequente de 23 anos com registro de multa não pode alugar um carro. ( ) Um cliente frequente e em viagem de negócios pode alugar o carro sem cobrança extra, mesmo que possua registro de multas na carteira.
A sequência correta de preenchimento dos parênteses, de cima para baixo, é

Considere o grafo abaixo. 

                        

A complexidade ciclomática é uma métrica que mede a complexidade de um determinado módulo (uma classe, um método, uma função etc.), a partir da contagem do número de caminhos independentes que ele pode executar até o seu fim. Um caminho independente é aquele que apresenta pelo menos uma nova condição (possibilidade de desvio de fluxo) ou um novo conjunto de comandos a serem executados. O resultado da complexidade ciclomática indica quantos testes, pelo menos, precisam ser executados para que se verifiquem todos os fluxos possíveis que o código pode tomar, a fim de garantir uma completa cobertura de testes.

(Adaptado de: https://www.treinaweb.com.br/blog/complexidade-ciclomatica-analise-estatica-e-refatoracao/)

Considerando que no grafo acima há 17 arestas e 13 nós, o cálculo da complexidade ciclomática resulta em