QUESTÕES DE ALGORITMOS

Prévia do material em texto

<p>QUESTÕES DE ALGORITMOS</p><p>Questão 1</p><p>Uma das etapas encontradas no algoritmo de Bellman-Ford está no processo de verificação de</p><p>ciclos negativos, importante para se garantir que os resultados gerados sejam condizentes com as</p><p>análises proporcionadas pelos algoritmos implementáveis na teoria dos grafos. A partir do exposto,</p><p>analise as asserções a seguir e a relação proposta entre elas.</p><p>I. O primeiro processo do algoritmo de Bellman-Ford faz a padronização dos valores de vértices</p><p>não relacionados.</p><p>Pois:</p><p>II. O processo que precede a verificação é o relaxamento, o qual é responsável por buscar o menor</p><p>caminho de menor custo entre os vértices.</p><p>A seguir, assinale a alternativa correta.</p><p>A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.</p><p>A asserção I é uma proposição verdadeira, e a asserção II é uma proposição falsa.</p><p>As asserções I e II são proposições falsas.</p><p>As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I.</p><p>As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa correta da</p><p>I. (Correta)</p><p>Resposta correta. A alternativa está correta, pois a asserção I é uma proposição verdadeira, já que a</p><p>primeira etapa dos processos do algoritmo visa à padronização dos vértices não relacionados. A</p><p>asserção II também é uma proposição verdadeira e não justifica a I, pois se expõe que o processo</p><p>de relaxamento busca o menor custo e isso está correto, porém, em cada asserção, é explicado o</p><p>funcionamento, mas ambas não se justificam.</p><p>Questão 2</p><p>Os algoritmos são sequências organizadas de execuções que são utilizadas para se garantir que</p><p>determinados problemas sejam resolvidos. No algoritmo de Dijkstra, isso não é diferente, pois o</p><p>objetivo é ter uma entrada de dados que permita fazer o processamento e, finalmente, que gere</p><p>uma saída na qual foi programada. Considerando o exposto, sobre o algoritmo de Dijkstra, analise</p><p>as afirmativas a seguir.</p><p>I. O ponto inicial é utilizado na letra “P” com o valor 1.</p><p>II. É atribuído o valor infinito para todos os vértices no início do algoritmo.</p><p>III. Nas interações do algoritmo, o infinito deve ser substituído pelos custos negativos encontrados</p><p>nos trajetos.</p><p>IV. Se existir um valor de menor custo no cruzamento de determinado vértice e se o algoritmo</p><p>encontrar um trajeto de menor custo entre dois vértices, então se sobrescreve o valor.</p><p>Está correto o que se afirma em:</p><p>I e II, apenas.</p><p>I, II e III, apenas.</p><p>II, III e IV, apenas.</p><p>II e III, apenas.</p><p>II e IV, apenas. (Correta)</p><p>Resposta correta. A alternativa está correta. A afirmativa II se apresenta de maneira adequada, pois,</p><p>quando a rotina do algoritmo de Dijkstra é iniciada, todos os vértices existentes no grafo recebem</p><p>o valor infinito. A afirmativa IV também se apresenta de maneira adequada, pois a função principal</p><p>do algoritmo é buscar o menor peso (custo) entre os vértices do grafo.</p><p>Questão 3</p><p>Os algoritmos são rotinas organizadas de algumas execuções que obedecem a alguns padrões da</p><p>lógica para a resolução de alguns problemas. Esses algoritmos podem possuir implementações</p><p>computacionais quando necessário ou apenas organizar os processos de determinadas atividades.</p><p>A respeito do algoritmo de Kruskal, analise as afirmativas a seguir e assinale V para a(s)</p><p>Verdadeira(s) e F para a(s) Falsa(s).</p><p>I. ( ) O primeiro passo do algoritmo de Kruskal visa selecionar a aresta externa de menor custo.</p><p>II. ( ) O segundo passo do algoritmo de Kruskal visa determinar a aresta selecionada com o custo</p><p>menor.</p><p>III. ( ) O terceiro passo do algoritmo de Kruskal visa considerar a árvore mínima geradora como A.</p><p>IV. ( ) O quarto passo do algoritmo de Kruskal visa acrescentar α em A se for formado um ciclo.</p><p>Assinale a alternativa que apresenta a sequência correta.</p><p>F, F, F, F.</p><p>F, F, V, V.</p><p>F, V, F, V.</p><p>V, F, F, F. (Correta)</p><p>V, V, F, F.</p><p>Resposta correta. A alternativa está correta, pois a afirmativa I é verdadeira, já que, na segunda</p><p>etapa, ocorre a seleção das arestas de menor custo, considerando que já encontrou, anteriormente,</p><p>o vértice inicial e atribuiu o valor zero. Assim, na etapa posterior, o algoritmo visa encontrar o</p><p>vértice não processado que possui o valor infinito.</p><p>Questão 4</p><p>Considere este caso hipotético: uma transportadora localizada na cidade “A” recebeu o mapa com</p><p>os municípios nos quais deverá fazer as entregas diariamente. Para otimizar as rotas, o gerente</p><p>operacional solicitou que, com base no algoritmo de Bellman-Ford, fosse desenvolvido um vetor</p><p>com os custos de deslocamento da cidade “A” para a cidade “E”, conforme pode ser observado na</p><p>seguinte figura:</p><p>(Imagem)</p><p>Fonte: Elaborada pelo autor.</p><p>Referente ao exposto, assinale a alternativa com o vetor otimizado, correspondente ao grafo</p><p>apresentado nessa figura.</p><p>Fonte: Elaborado pelo autor.</p><p>ABCDE</p><p>03103</p><p>Citar</p><p>CORRETA</p><p>Fonte: Elaborado pelo autor.</p><p>ABCD E</p><p>031NULL3</p><p>CORRETA</p><p>Fonte: Elaborado pelo autor.</p><p>ABCD E</p><p>032NULL3</p><p>Fonte: Elaborado pelo autor.</p><p>ABCD E</p><p>041NULL3</p><p>Fonte: Elaborado pelo autor.</p><p>ABCD E</p><p>231NULL3</p><p>Resposta correta. A alternativa está correta, pois, de A para B, o menor custo é A - E - C - B, com 3.</p><p>O menor custo de A para C é 1, com o trajeto A - E - C. O custo de A para D é infinito, pois não</p><p>existe relacionamento entre as duas arestas no grafo. O custo de A para E é 3, pois o trajeto</p><p>otimizado se dá por A diretamente para E.</p><p>Questão 5</p><p>A estrutura organizada no algoritmo de Bellman-Ford possui três elementos que o compõem. Tal</p><p>algoritmo determina como é organizado o fluxo de suas rotinas e isso permite um referencial</p><p>teórico, possibilitando, assim, que uma pessoa com conhecimentos e habilidades possa fazer uma</p><p>implementação por meio de uma linguagem de programação. Considerando o exposto, sobre o</p><p>algoritmo de Bellman-Ford, analise as afirmativas a seguir.</p><p>I. No processo de inicialização, ocorre a padronização dos valores que não possuem</p><p>relacionamento.</p><p>II. O relaxamento faz o cálculo do menor custo entre os vértices.</p><p>III. O processo de ajuste faz a transformação dos valores negativos em positivos, quando se</p><p>multiplica o valor negativo por - 1.</p><p>IV. Na verificação, o algoritmo se certifica de que não esteja ocorrendo ciclos negativos.</p><p>Está correto o que se afirma em:</p><p>I e II, apenas.</p><p>I, II e III, apenas.</p><p>I, II e IV, apenas. (Correta)</p><p>II e III, apenas.</p><p>II, III e IV, apenas.</p><p>Resposta correta. A alternativa está correta. Na afirmativa I, define-se que, no processo de</p><p>inicialização, ocorre a padronização dos valores, sendo esta a sua função no algoritmo. A afirmativa</p><p>II está correta, pois, no relaxamento, tem-se o processo do algoritmo, em que, de fato, é calculado</p><p>o menor custo. Já a afirmativa IV também está correta, pois, na verificação, é feita a checagem em</p><p>que não ocorrem ciclos negativos. Por fim, a afirmativa III está incorreta, porque o processo de</p><p>tornar o valor positivo ao ser multiplicado por - 1 não existe em teoria dos grafos.</p><p>Questão 6</p><p>O mapeamento dos custos de deslocamento é uma variável de extrema importância,</p><p>principalmente quando estamos falando a respeito do planejamento da otimização de rotas. O</p><p>grafo representado na seguinte figura demonstra o custo de deslocamento entre algumas cidades:</p><p>(Imagem)</p><p>Fonte: Elaborada pelo autor.</p><p>Com base no algoritmo de Floyd-Warshall, os valores foram expressos na matriz evidenciada no</p><p>seguinte quadro:</p><p>ABCD</p><p>A 0426</p><p>B ∞ 034</p><p>C ∞ ∞ 0 ∞</p><p>D ∞ ∞ 50</p><p>Fonte: Elaborado pelo autor.</p><p>A partir do exposto, analise as asserções a seguir e a relação proposta entre elas.</p><p>I. A matriz utilizou seis símbolos de ∞.</p><p>Pois:</p><p>II. São utilizados para expressar que não existe uma aresta que liga um vértice ao outro naquela</p><p>direção.</p><p>A seguir, assinale a alternativa correta.</p><p>A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.</p><p>A asserção I é uma proposição verdadeira, e a asserção II é uma proposição</p><p>falsa. (Selecionada)</p><p>As asserções I e II são proposições falsas.</p><p>As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I.</p><p>As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa</p><p>correta da I.</p><p>Resposta correta. A alternativa está correta. O total de arestas representadas no quadro é de seis,</p><p>mas apenas quatro representações devem ser consideradas, pois há repetição dos pares que são</p><p>representados pela interseção dos vértices, e a alternativa está correta ao afirmar que a asserção II</p><p>é verdadeira, pois as arestas de valor infinito são os caminhos que não existem entre os vértices.</p><p>Questão 7</p><p>Um algoritmo é uma sequência organizada de passos que são executados a fim de resolver</p><p>determinado problema. Sabendo disso, analise as afirmativas a seguir a respeito do algoritmo de</p><p>Prim e assinale V para as Verdadeiras e F para as Falsas.</p><p>I. ( ) O primeiro passo é estabelecer um ponto de partida para a árvore.</p><p>II. ( ) O segundo passo é atribuir o valor de custo infinito para todos os vértices que ainda não</p><p>foram incluídos.</p><p>III. ( ) O terceiro passo é atribuir os pesos para as arestas que estão ligadas à árvore mínima.</p><p>IV. ( ) O quarto passo é o que visa incluir na árvore mínima a aresta que possui o menor custo.</p><p>Assinale a alternativa que apresenta a sequência correta.</p><p>F, F, F, F.</p><p>F, V, F, V.</p><p>F, V, V, F.</p><p>V, F, V, V.</p><p>V, V, V, V. (Correta)</p><p>Resposta correta. A alternativa está correta. As quatro afirmativas estão corretas, pois, na primeira</p><p>afirmativa, é verdade que o primeiro passo estabelece o ponto inicial da árvore. Na segunda</p><p>afirmativa, atribui-se o valor infinito para todos os vértices que ainda não foram incluídos. Na</p><p>terceira, o peso das arestas que estão conectadas à árvore mínima é, de fato, atribuído. Na quarta,</p><p>é correta a afirmação que o algoritmo visa incluir na árvore mínima a aresta que possui o menor</p><p>custo.</p><p>Questão 8</p><p>Os algoritmos possibilitam uma sequência de ações que podem ser realizadas em determinado</p><p>tempo, permitindo que a análise seja feita com eficiência, considerando que o algoritmo de Prim</p><p>possui, entre outros, a função de otimização de arestas. Diante do exposto, analise as afirmativas a</p><p>seguir.</p><p>I. O algoritmo de Prim pode gerar mais de uma árvore mínima geradora.</p><p>II. O algoritmo de Prim exige um tempo polinomial para o cálculo da árvore mínima geradora.</p><p>III. O algoritmo de Prim pode ser utilizado em gráficos não direcionais.</p><p>Assinale a alternativa correta.</p><p>Apenas a afirmativa I é correta.</p><p>Apenas as afirmativas I e II são corretas.</p><p>Apenas as afirmativas II e III são corretas.</p><p>As afirmativas I, II e III estão corretas. (Correta)</p><p>Resposta correta. A alternativa está correta, pois a afirmativa I é verdadeira, já que é possível ter</p><p>mais de uma árvore mínima geradora, dependendo da estrutura do grafo e dos pesos das arestas.</p><p>A afirmativa II também é verdadeira, pois o algoritmo de Prim pode ser implementado em tempo</p><p>polinomial, e a afirmativa III é correta, pois o algoritmo de Prim é aplicável a grafos não direcionais.</p><p>Questão 9</p><p>Em análise de algoritmos, é importante que se compreenda a função do tempo que cada algoritmo</p><p>requer. A fim de avaliar essa função, há três características principais que são observadas. Sobre</p><p>isso, analise as afirmativas a seguir.</p><p>I. A função de tempo é uma métrica que pode ser calculada em função do tempo que um</p><p>determinado algoritmo leva para ser executado.</p><p>II. A complexidade de tempo pode ser obtida em relação ao número de dados que estão em</p><p>execução e que fazem parte da estrutura que é observada.</p><p>III. A complexidade do espaço é outra variável que deve ser observada em relação à quantidade de</p><p>informações que a memória do sistema irá utilizar.</p><p>Assinale a alternativa correta.</p><p>Apenas a afirmativa I é correta.</p><p>Apenas as afirmativas I e II são corretas.</p><p>Apenas as afirmativas II e III são corretas.</p><p>As afirmativas I, II e III estão corretas. (Correta)</p><p>Resposta correta. A alternativa está correta, pois todas as afirmativas estão corretas. A afirmativa I</p><p>diz respeito ao cálculo do tempo em função de cada algoritmo, a afirmativa II relaciona a</p><p>complexidade do tempo com o número de dados que estão sendo processados, e a afirmativa III</p><p>diz respeito à complexidade do espaço que leva em consideração a quantidade de informações</p><p>que a memória deve alocar durante a execução de um algoritmo.</p><p>Questão 10</p><p>Os grafos têm um grande espaço de aplicação. Pode-se utilizá-los para expressar diferentes</p><p>questões, como otimização e diversas relações. Assim, analise as afirmativas a seguir.</p><p>I. Os grafos podem ser usados para representar relacionamentos entre pessoas.</p><p>II. É possível utilizar os grafos para expressar uma rede de computadores.</p><p>III. Os grafos podem ser usados em operações financeiras de investimento.</p><p>IV. É possível representar árvores de decisão por meio de grafos.</p><p>Assinale a alternativa correta.</p><p>Apenas a afirmativa I é correta.</p><p>Apenas as afirmativas I e II são corretas.</p><p>Apenas as afirmativas II e III são corretas.</p><p>Apenas as afirmativas III e IV são corretas.</p><p>As afirmativas I, II, III e IV estão corretas. (Correta)</p><p>Resposta correta. A alternativa está correta, pois todas as afirmativas são verdadeiras. Os grafos são</p><p>uma estrutura que pode ser usada para representar relacionamentos sociais, redes de</p><p>computadores, operações financeiras e árvores de decisão.</p>