Questão 1510862 de Tecnologia da Informação - Legalle Concursos 2023

Questão

ID 1510862

Disciplina: Tecnologia da Informação

Assunto: Conceitos Básicos de Algoritmos e Estrutura de Dados

Ano: 2023 Banca: Legalle Concursos Órgão: Defensoria Pública do Estado do Pará

O procedimento FIND-MAX-CROSSING-SUBARRAY, pela técnica de divisão e conquista, toma como entrada o arranjo A e os índices low, mid e high, e retorna uma tupla que contém os índices que demarcam um subarranjo máximo que cruza o ponto médio, juntamente com a soma dos valores em um subarranjo máximo.

Analise a estrutura a seguir.

FIND-MAX-CROSSING-SUBARRAY(A, low, mid, high)

1 left-sum = -∞

2 sum = 0

3 for i = mid downto low

4 ___ sum = sum + A[i]

5 ___ if sum > left-sum

6 ___ ___ left-sum = sum

7 ___ ___ max-left = i

8 right-sum = -∞

9 sum = 0

10 for j = mid+ 1 to high

11 ___ sum = sum + A[i]

12 ___ if sum > right-sum

13 ___ right-sum = sum

14 ___ max-right = j

15 return (max-left, max-right, left-sum + right-sum)

Acerca das funções descritas acima, assinale a alternativa CORRETA.

Alternativa A:
As linhas 1-7 acham um subarranjo maxImo da metade esquerda, A[low ._. mid]. Visto que esse subarranjo deve conter A[mid], o laço downto das linhas 3-7 inicia o índice i em mid e prossegue até low, de modo que todo subarranjo que ele considera é da forma A[i ._. low].
Alternativa B:
As linhas 1-2 inicializam as variáveis sum, que contêm a maior soma encontrada até então, e left-sum, que contém as somas das entradas em A[i . _. mid].
Alternativa C:
Sempre que encontrarmos, na linha 5, um subarranjo A[i ._ . mid] com uma soma de valores menor do que left-sum, atualizaremos left-sum para a soma desse subarranjo na linha 6, e na linha 7 atualizaremos a variável max-left para registrar esse índice i.
Alternativa D:
As linhas 8-14 funcionam de modo análogo para a metade direita, A[mid+1 ._. high]. Aqui, o laço for das linhas 10-14 inicia o índice j em mid+1 e prossegue até right-sum, de modo que todo subarranjo que ele considera é da forma A[mid + 1 ._. i].
Alternativa E:
A linha 15 retorna os índices max-left e max-right que demarcam um subarranjo máximo que cruza o ponto médio, juntamente com a soma left-sum+right-sum dos valores no subarranjo A[max left ._. max-right].

Estatísticas Cadernos

Questão 1510862

Continue estudando na plataforma