June 2023 2 44 Report
O algoritmo de Ordenação por Mesclagem, recursivo, é um exemplo de aplicação da estratégia dividir para conquistar. Esse algoritmo divide recursivamente a lista em porções cada vez menores e, quando não é mais possível dividir, o algoritmo passa a mesclar ordenadamente as porções menores em porções cada vez maiores. A figura abaixo apresenta, na primeira linha, a lista original a ser ordenada.



Ao aplicar o algoritmo de Ordenação por Mesclagem, a primeira chamada recursiva é processada para uma sublista e a última mesclagem envolve duas listas. Qual a alternativa que apresenta, nessa ordem, essas três listas?
45-33-26-62-13-87-51-34

[45, 33, 26, 62], [13, 26, 45, 62], [33, 34, 51, 87]


[33, 45, 26, 62], [26, 33, 45, 62], [13, 34, 51, 87]


[33, 45, 26, 62], [13, 34, 51, 87], [26, 33, 45, 62]


[33, 45, 26, 62], [26, 13, 45, 62], [33, 34, 51, 87]


[45, 33, 26, 62], [26, 33, 45, 62], [13, 34, 51, 87]
Please enter comments
Please enter your name.
Please enter the correct email address.
You must agree before submitting.

Lista de comentários

More Questions From This User See All
Quais das afirmativas abaixo são verdadeiras relativamente a esse grafo? I. O grafo é cíclico, conexo, não orientado e ponderado. II. O grafo contém 7 nós e 8 arestas. III. A ordem de descoberta dos nós em um percurso de largura seria A-B-E-M-D-C-J. IV. A ordem de descoberta dos nós em um percurso em profundidade seria A-B-D-C-E- M-J. Todas as afirmativas são corretas. II, III e IV são corretas. I, II, III são corretas. I, II e IV são corretas I e II são corretas.
Responda
Sempre que temos um conjunto de tarefas para fazer, sabemos que demoramos um certo tempo para realizar cada tarefa. Sempre que pretendemos realizar todas elas, a ordem em que vamos realizá-las não interfere no tempo total que dedicaremos: o tempo total é a soma do tempo de todas as tarefas. Mas, e se cada tarefa tiver uma data-limite para ser entregue? Nesse caso, podemos considerar uma estratégia que minimize o tempo total de eventuais atrasos que tenhamos relativamente às datas-limite de cada tarefa. Essa estratégia é definida pelo algoritmo de Data devida mais próxima. Algoritmo Data devida mais próxima Dada a lista de tarefas e as datas-limite de cada tarefa: Ordenar a lista de tarefas em ordem crescente relativamente às datas-limite de cada tarefa. Realizar as tarefas de acordo com a ordem definida. Seja o conjunto de tarefas e número de dias que faltam para elas sejam concluídas: TM: faltam 13 dias. TK: faltam 21 dias. TX: faltam 18 dias. TR: faltam 15 dias. A ordem sugerida pelo algoritmo de Data devida mais próxima é: TK, TX, TR, TM TM, TR, TK, TX TM. TK, TX, TR TR, TX, TM, TK TM, TR, TX, TK
Responda
Selmer Johnson propôs um algoritmo que corresponde à solução ótima para definir a ordem na qual um conjunto de objetos passa por duas máquinas (uma depois da outra), com tempos diferentes em cada máquina Dadas máquinas M1 e M2 que operam em sequência M1 → M2 Dada uma lista de objetos e o tempo que utiliza de cada máquina Selecionar o objeto que utiliza o menor tempo possível independentemente da máquina Se o tempo for na M1: alocar esse objeto primeiro Se o tempo for na M2: alocar esse objeto por último … e repetir o processo Considere o cenário daquele dia em que vamos lavar e secar toda a roupa da casa. Organizamos a roupa suja em vários conjuntos de peças de roupa (por cor, por tipo, por quantidade de sujeira etc.). Cada um desses conjuntos deve passar primeiro pela máquina de lavar e depois pela máquina de secar, e cada um consome um tempo diferente em cada máquina. O algoritmo de Selmer Johnson ajuda a definir a ordem em que vamos lavar os conjuntos de modo a terminar a tarefa toda o mais rápido possível. Como exemplo, para os conjuntos de roupas abaixo, a ordem que define o menor tempo é CORES, CAMA, BANHO, BRANCAS. BRANCAS: lavar 45 min, secar 25 min CORES: lavar 20 min, secar 30 min BANHO: lavar 40 min, secar 40 min CAMA: lavar 35 min, secar 50 min A ordem que terminar a tarefa em menor tempo é: CORES, CAMA, BANHO, BRANCAS. Sejam as seguintes afirmações: O conjunto CORES é o primeiro da sequência porque ele tem o menor tempo na máquina de lavar. O conjunto BRANCAS é o último da sequência porque ele tem o menor tempo na máquina de secar. O conjunto BRANCAS é o último da sequência porque ele tem o maior tempo na máquina de lavar. O conjunto CAMA é o segundo da sequência porque ele tem o maior tempo na máquina de secar. O conjunto BANHO é o terceiro da sequência porque ele o mesmo tempo nas duas máquinas. Selecione a alternativa que lista as afirmações verdadeiras. I, II, III e IV são verdadeiras. Todas são verdadeiras. I, II e V são verdadeiras. I e II são verdadeiras. I, II e III são verdadeiras.
Responda
O algoritmo de Dijkstra calcula a menor distância entre dois nós em um grafo cujas arestas possuem pesos. O grafo ilustrado na figura representa um conjunto de cidades e o custo das conexões entre elas. Considerando a aplicação do algoritmo de Dijkstra no grafo, quais das afirmações são verdadeiras? A distância computada pelo algoritmo entre os nós 0 e 1 é igual a 3. A distância computada pelo algoritmo entre os nós 0 e 2 é igual a 5. A distância computada pelo algoritmo entre os nós 0 e 3 é igual a 4. A distância computada pelo algoritmo entre os nós 0 e 4 é igual a 5. III e VI são verdadeiras. II e V são verdadeiras. Apenas I é verdadeira. Apenas IV é verdadeira. Todas são verdadeiras.
Responda
O algoritmo de Ordenação por Inserção explora a estratégia que adotamos quando ordenamos, por exemplo, as cartas de um baralho. A figura abaixo apresenta, na primeira linha, a lista original a ser ordenada de menor a maior. Aplique o algoritmo de Ordenação por Inserção para gerar a primeira configuração na qual há mudança de posições. 94,71,0,62,48,80 Selecione a alternativa que apresenta a configuração da lista quando chegar a vez do 62 ser processado. [0, 48, 71, 62, 94, 80] [80, 94, 48, 62, 71] [94, 0, 71, 62, 48, 80] [71, 0, 94, 62, 48, 80] [71, 94, 0, 62, 48, 80].
Responda
Um algoritmo recursivo chama a si mesmo para resolver instâncias menores do problema. É essencial que, antes da chamada recursiva do algoritmo, seja avaliada a condição de término da recursão: caso isso não ocorra, a chamada recursiva será realizada indefinidamente. O algoritmo de Ordenação por Mesclagem é recursivo: o uso da recursão explicita a estratégia de dividir para conquistar adotada. O diagrama de blocos da figura representa o algoritmo de Ordenação por Mesclagem. Considerando os elementos da figura que estão indicados pelas letras de A a E, escolha a alternativa que descreve, correta e respectivamente, a estratégia do algoritmo. Bloco(s) que avalia(m) a continuidade da recursão. Bloco(s) que prepara(m) a divisão do problema. Bloco(s) que ativa(m) a recursão para resolver uma parte menor do problema. Bloco(s) que realiza(m) a mesclagem ordenada das partes menores do problema. A, B, C e D, E, nessa ordem. A, C e D, B, E, nessa ordem. E, B, C e D, A, nessa ordem. A, B, E, C e D, nessa ordem. A, C e D, E, B, nessa ordem.
Responda
Um algoritmo recursivo chama a si mesmo para resolver instâncias menores do problema. Considerando a sentença: É __________ que, antes da chamada _________ do algoritmo, seja avaliada a condição de __________ da recursão: caso isso não ocorra, a chamada recursiva será realizada __________. Escolha a alternativa que completa, correta e respectivamente, as lacunas: essencial, recursiva, encerramento, indefinidamente essencial, inicial, início, indefinidamente opcional, recursiva, encerramento, apenas uma vez opcional, inicial, início, indefinidamente essencial, recursiva, encerramento, apenas uma vez
Responda
O algoritmo de Ordenação por Seleção utiliza a mesma estratégia do algoritmo de Busca pelo Maior/Menor que estudamos na semana anterior: ele aplica a estratégia de identificar o menor ou maior valor, depois de colocar um valor na posição correta, replica a estratégia para o restante da lista. Aplique seu conhecimento sobre esse algoritmo de ordenação para avaliar as afirmações abaixo e a relação entre elas. O algoritmo de Ordenação por Seleção tem ordem de complexidade de tempo de O(n2). O algoritmo de Ordenação por Seleção realiza o mesmo número de comparações, independentemente de os valores da lista estarem aleatoriamente distribuídos, ordenados na ordem desejada, ordenados na ordem inversa à desejada, ou quando a lista tem poucos valores diferentes entre seus itens. As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa da I. As asserções I e II são proposições verdadeiras, e a II é uma justificativa da I. As asserções I e II são proposições falsas. A asserção I é uma proposição falsa, e a II é uma proposição verdadeira. A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
Responda
O algoritmo de Ordenação por Seleção utiliza a estratégia do algoritmo de Busca pelo Maior/Menor, aplicando-a para versões cada vez menores da lista. A figura abaixo apresenta, na primeira linha, a lista original a ser ordenada. A segunda lista apresentada mostra a configuração da lista depois da identificação do menor elemento. Aplique o algoritmo de Ordenação por Seleção para gerar as próximas três configurações da lista. Selecione a alternativa que apresenta as três próximas configurações da lista. [2, 10, 59, 31, 27, 15, 38] -> [2, 10, 15, 59, 27, 31, 38] -> [2, 10, 15, 27, 31, 59, 38] [2, 10, 59, 31, 27, 15, 38] -> [2, 10, 15, 27, 31, 59, 38] -> [2, 10, 15, 27, 31, 59, 38] [2, 10, 59, 31, 27, 15, 38] -> [2, 10, 15, 31, 27, 59, 38] -> [2, 10, 15, 27, 31, 59, 38]. [2, 10, 59, 31, 27, 15, 38] -> [2, 10, 15, 31, 27, 38, 59] -> [2, 10, 15, 27, 31, 38, 59] [2, 10, 31, 59, 27, 15, 38] -> [2, 10, 15, 31, 59, 27, 38] -> [2, 10, 15, 27, 31, 59, 38]
Responda
O algoritmo de Ordenação por Seleção utiliza a mesma estratégia do algoritmo de Busca pelo Maior/Menor que estudamos na semana anterior: ele aplica a estratégia de identificar o menor ou maior valor, depois de colocar um valor na posição correta, replica a estratégia para o restante da lista. Aplique seu conhecimento sobre esse algoritmo de ordenação para avaliar as afirmações abaixo e a relação entre elas. O algoritmo de Ordenação por Seleção tem ordem de complexidade de tempo de O(n2). O algoritmo de Ordenação por Seleção realiza o mesmo número de comparações, independentemente de os valores da lista estarem aleatoriamente distribuídos, ordenados na ordem desejada, ordenados na ordem inversa à desejada, ou quando a lista tem poucos valores diferentes entre seus itens. A asserção I é uma proposição falsa, e a II é uma proposição verdadeira. As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa da I. As asserções I e II são proposições verdadeiras, e a II é uma justificativa da I. A asserção I é uma proposição verdadeira, e a II é uma proposição falsa. As asserções I e II são proposições falsas.
Responda

Helpful Links

Helpful Social

Copyright © 2025 ELIBRARY.TIPS - All rights reserved.