Prova AV Algoritmos e Complexidade

Prévia do material em texto

<p>A</p><p>B</p><p>C</p><p>D</p><p>E</p><p>1 Marcar para revisão</p><p>Ano: 2010 Banca: FCC Órgão: TRT � 20ª</p><p>REGIÃO �SE� Prova: FCC � 2010 � TRT �</p><p>20ª REGIÃO �SE� - Técnico Judiciário -</p><p>Tecnologia da Informação</p><p>Objeto que se constitui parcialmente ou é</p><p>definido em termos de si próprio. Nesse</p><p>contexto, um tipo especial de</p><p>procedimento (algoritmo) será utilizado,</p><p>algumas vezes, para a solução de alguns</p><p>problemas. Esse procedimento é</p><p>denominado:</p><p>Recursividade</p><p>Rotatividade</p><p>Repetição</p><p>Interligação</p><p>Condicionalidade</p><p>2 Marcar para revisão</p><p>A complexidade de algoritmos é uma</p><p>medida que indica os recursos</p><p>necessários para a execução de um</p><p>00</p><p>hora</p><p>: 35</p><p>min</p><p>: 17</p><p>seg</p><p>Ocultar</p><p>Questão 1 de 10</p><p>Respondidas �10� Em branco �0�</p><p>Finalizar prova</p><p>1 2 3 4 5</p><p>6 7 8 9 10</p><p>Prova AV Algoritmos e Complexidade</p><p>A</p><p>B</p><p>C</p><p>D</p><p>E</p><p>algoritmo em função do tamanho da</p><p>entrada.</p><p>Como expressamos a complexidade do</p><p>"Bubble Sort" quando o tempo</p><p>computacional varia de forma quadrática</p><p>com o tamanho do problema?</p><p>O(log n)</p><p>O(n log n)</p><p>O(n)</p><p>O(n )2</p><p>O(n )3</p><p>3 Marcar para revisão</p><p>�IBGE � Analista Censitário - Análise de</p><p>Sistemas - Desenvolvimento de</p><p>Aplicações - Web Mobile - 2017�</p><p>Observe a figura a seguir que ilustra</p><p>relações entre colegas e seus interesses:</p><p>O tipo de Banco de Dados NoSQL, não</p><p>relacional, que armazena tais</p><p>informações, utilizando estruturas de</p><p>A</p><p>B</p><p>C</p><p>D</p><p>E</p><p>A</p><p>B</p><p>vértices e arestas, com propriedades</p><p>associadas, é o:</p><p>Colunar</p><p>Documento</p><p>Grafo</p><p>Chave-valor</p><p>Tabular</p><p>4 Marcar para revisão</p><p>No algoritmo abaixo, os parâmetros</p><p>da função valor são recebidos e são</p><p>impressos na própria função. Assim</p><p>sendo, o valor da variável u exibido na</p><p>última linha da função é: #Algoritmo# var</p><p>x,y: inteiro; inicio x� 4; y� 2; valor(x,y);</p><p>fim. #Sub-rotina# valor(inteiro: u, v) inicio</p><p>u � u * 2; v � v + u; u � u - 1;</p><p>escreva(u); fim sub-rotina; #Marque a</p><p>opção que mostra o valor</p><p>correto exibido da variável u.</p><p>4</p><p>5</p><p>C</p><p>D</p><p>E</p><p>A</p><p>B</p><p>C</p><p>D</p><p>E</p><p>7</p><p>8</p><p>10</p><p>5 Marcar para revisão</p><p>O algoritmo de ordenação "Shell Sort",</p><p>ou simplesmente "Shell Sort", é um</p><p>algoritmo de classificação de</p><p>comparação.</p><p>O método de ordenação "Shell Sort" é</p><p>derivado de qual outro método de</p><p>ordenação?</p><p>Bubble Sort.</p><p>Merge Sort.</p><p>Quick Sort.</p><p>Insertion Sort.</p><p>Selection Sort.</p><p>6 Marcar para revisão</p><p>A</p><p>B</p><p>C</p><p>D</p><p>E</p><p>Após a inserção de um nó, é necessário</p><p>verificar cada um dos nós ancestrais</p><p>desse nó inserido, relativamente à</p><p>consistência com as regras estruturais</p><p>de uma árvore AVL.</p><p>PORQUE</p><p>O fator de balanceamento de cada nó,</p><p>em uma árvore AVL, deve pertencer ao</p><p>conjunto formado por ��2, �1, 0, �1, �2�.</p><p>Analisando-se as afirmações acima,</p><p>conclui-se que:</p><p>as duas afirmações são</p><p>verdadeiras, e a segunda</p><p>justifica a primeira.</p><p>as duas afirmações são</p><p>verdadeiras, e a segunda não</p><p>justifica a primeira.</p><p>a primeira afirmação é</p><p>verdadeira, e a segunda é</p><p>falsa.</p><p>a primeira afirmação é falsa, e a</p><p>segunda é verdadeira.</p><p>as duas afirmações são falsas.</p><p>7 Marcar para revisão</p><p>Observe a árvore binária a seguir:</p><p>A</p><p>B</p><p>C</p><p>D</p><p>E</p><p>O caminhamento central (infixado) sobre</p><p>essa árvore produz a sequência de</p><p>visitação:</p><p>D � B � H � E � J � I � K � A � F -</p><p>C � G</p><p>A � B � C � D � E � F � G � H � I -</p><p>J � K</p><p>A � B � D � E � H � I � J � K � C -</p><p>F � G</p><p>J � K � I � H � E � D � B � F � G -</p><p>C � A</p><p>D � H � J � K � I � E � B � F � G -</p><p>C � A</p><p>8 Marcar para revisão</p><p>�FCC � ARTESP � Agente de Fiscalização</p><p>à Regulação de Transporte - Tecnologia</p><p>A</p><p>B</p><p>C</p><p>D</p><p>E</p><p>de Informação - 2017�</p><p>Considere a estrutura abaixo que</p><p>representa um problema de rotas em</p><p>pequena escala:</p><p>Considere, por hipótese, que se solicitou</p><p>a um Agente de Fiscalização à Regulação</p><p>de Transporte da ARTESP utilizar alguma</p><p>estratégia lógica para, partindo do ponto</p><p>1, chegar ao ponto 6 usando a menor</p><p>rota. De um mesmo ponto pode haver</p><p>mais de uma rota, com distâncias</p><p>diferentes. A lógica correta utilizada pelo</p><p>Agente, em função dos pontos a serem</p><p>percorridos, foi:</p><p>�1� �2,3� �2,4� �5,6� �6�,</p><p>caminho mais curto 1�2�5�6.</p><p>�1� �2� �4� �6�, caminho mais</p><p>curto 1�2�4�6.</p><p>�1� �3,2� �4,5� �6�, caminho</p><p>mais curto 1�3�4�6.</p><p>�6� �5,4� �3,1� �1�, caminho mais</p><p>curto 6�4�3�1, que é igual a 1�3�</p><p>4�6.</p><p>�6� �4� �5,3� �2,1� �1�, caminho</p><p>mais curto 6�4�3�5�2�1, que é</p><p>igual a 1�2�5�3�4�6.</p><p>9 Marcar para revisão</p><p>Analise o custo computacional dos</p><p>algoritmos a seguir, que calculam o valor</p><p>de polinômio de grau n da forma</p><p>onde os coeficientes são números de</p><p>ponto flutuante armazenados no vetor</p><p>[a..n], e o valor de n é maior que zero.</p><p>Todos os coeficientes</p><p>podem assumir qualquer valor, exceto o</p><p>coeficiente   que é diferente de zero.</p><p>ALGORITMO 1:</p><p>soma = a[0]</p><p>repita para i=1 até n</p><p>se a[i] 0.0 então</p><p>potencia = x</p><p>repita para j = 2 até i</p><p>potencia = potencia * x</p><p>fim repita</p><p>soma = soma + a[i]</p><p>fim se</p><p>fim repita</p><p>imprima(soma)</p><p>ALGORITMO 2:</p><p>soma = a[n]</p><p>repita para i = n-1 até 0 passo -1</p><p>soma = soma * x + a[i]</p><p>fim repita</p><p>imprima(soma)</p><p>Com base nos algoritmos 1 e 2, avalie</p><p>as asserções a seguir e a relação</p><p>proposta entre elas.</p><p>��</p><p>Os algoritmos possuem a mesma</p><p>complexidade assintótica</p><p>PORQUE</p><p>��</p><p>an</p><p>A</p><p>B</p><p>C</p><p>D</p><p>E</p><p>Para o melhor caso, ambos possuem a</p><p>complexidade O(n)</p><p>A respeito dessas asserções, assinale a</p><p>opção correta:</p><p>as duas asserções são</p><p>proposições verdadeiras, mas a</p><p>segunda é uma justificativa</p><p>correta da primeira.</p><p>as duas asserções são</p><p>proposições verdadeiras e a</p><p>segunda não é a justificativa</p><p>correta da primeira.</p><p>a primeira asserção é uma</p><p>proposição verdadeira e a</p><p>segunda uma proposição falsa.</p><p>a primeira asserção é uma</p><p>proposição falsa e a segunda</p><p>uma proposição verdadeira.</p><p>tanto a primeira quanto a</p><p>segunda asserção são</p><p>proposições falsas.</p><p>10 Marcar para revisão</p><p>Ano: 2017 Banca: CONSULPLAN Órgão:</p><p>TRE�RJ Prova: CONSULPLAN � 2017 �</p><p>TRE�RJ � Técnico Judiciário -</p><p>Programação de Sistemas</p><p>Analise as afirmativas a seguir a respeito</p><p>de algoritmos recursivos.</p><p>A</p><p>B</p><p>C</p><p>D</p><p>E</p><p>I. Diz-se que uma rotina é recursiva se a</p><p>sua definição envolver uma chamada a</p><p>ela mesma. Neste sentido, o termo</p><p>recursão é equivalente ao termo indução</p><p>utilizado por matemáticos.</p><p>II. Cada algoritmo recursivo possui um</p><p>algoritmo iterativo equivalente e vice-</p><p>versa, mas que pode ter mais ou menos</p><p>complexidade em sua construção.</p><p>III. Uma função recursiva possui duas</p><p>partes: caso base e caso recursivo.</p><p>IV. Um algoritmo pode ser chamado de</p><p>iterativo quando ele requer a repetição</p><p>implícita de um processo até que</p><p>determinada condição seja satisfeita.</p><p>V. A recursividade possibilita a escrita de</p><p>um código mais enxuto, com maior</p><p>legibilidade e simplicidade.</p><p>Assinale a alternativa que possui alguma</p><p>afirmação INCORRETA.</p><p>I e II</p><p>I e V</p><p>II e III</p><p>III e IV</p><p>I e IV</p>