Questão nº 54

Questão de Tecnologia da Informação · CESGRANRIO BASA 02/2021 (nº 54)

CESGRANRIO2021Técnico Científico - Tecnologia da InformaçãoTecnologia da Informação

Sejam dois arrays de inteiros, com zero ou mais elementos cada, ordenados ascendentemente. Deseja-se escrever uma
função que receba esses dois arrays como parâmetros e insira os seus elementos em um terceiro array, também recebido
como parâmetro, de modo que os elementos inseridos no terceiro array permaneçam ordenados ascendentemente, como
no exemplo abaixo.

Exemplo:

```java
int v1[]={10,20,30,40,50};
int v2[]={5,10,15,20};
```

O conteúdo do terceiro array, após a chamada da função de intercalação, será

```
{5,10,10,15,20,20,30,40,50}
```

Nesse contexto, considere a seguinte função main de um programa Java:

```java
public class Main {
public static void main(String[] args) {
int v1[]={10,20,30,40,50};
int v2[]={5,10,15,20};
int v3[]=new int [v1.length + v2.length];
int p1=0,p2=0,p3=0;

intercala(v1,p1,v2,p2,v3,p3);
}
}
```

Qual função deve ser inserida na classe `Main` para que a intercalação do array v1 com o array v2 seja feita corretamente?

static void intercala(int v1[],int p1,int v2[],int p2,int v3[],int p3) {
     if(p1 == v1.length && p2 == v2.length)
          return;
     if(v1[p1] < v2[p2]) {
          v3[p3++]=v1[p1++];
          intercala(v1,p1,v2,p2,v3,p3);
     }
     else {
          v3[p3++]=v2[p2++];
          intercala(v1,p1,v2,p2,v3,p3);
     }
}

static void intercala(int v1[],int p1,int v2[],int p2,int v3[],int p3) {
     if(p1 == v1.length && p2 == v2.length)
          return;
     if(p1 < v1.length)
          if(p2 < v2.length)
               if(v1[p1] < v2[p2]) {
                    v3[p3++]=v1[p1++];
                    intercala(v1,p1,v2,p2,v3,p3);
               }
               else {
                    v3[p3++]=v2[p2++];
                    intercala(v1,p1,v2,p2,v3,p3);
               }
          else {
               v3[p3++]=v1[p1++];
               intercala(v1,p1,v2,p2,v3,p3);
          }
     else
          if(p2 < v2.length) {
               v3[p3++]=v2[p2++];
               intercala(v1,p1,v2,p2,v3,p3);
          }
}

static void intercala(int v1[],int p1,int v2[],int p2,int v3[],int p3) {
     if(p1 < v1.length && p2 < v2.length)
          intercala(v1,p1+1,v2,p2+1,v3,p3+1);
     else
          if(p1 < v1.length && p2 == v2.length)
               intercala(v1,p1+1,v2,p2,v3,p3+1);
          else
               if(p1 == v1.length && p2 < v2.length)
                    intercala(v1,p1,v2,p2+1,v3,p3+1);
               else
                    return;
     if(p1 < v1.length)
          if(p2 < v2.length)
               if(v1[p1] < v2[p2])
                    v3[p3]=v1[p1];
               else
                    v3[p3]=v2[p2];
          else
               v3[p3]=v1[p1];
     else
          v3[p3]=v2[p2];
}

D```java
static void intercala(int v1[],int p1,int v2[],int p2,int v3[],int p3) {
while(p1 < v1.length && p2 < v2.length)
if(v1[p1] < v2[p2]) {
v3[p3]=v1[p1];
p3+=1;
p1+=1;
}
else
if(v1[p1] > v2[p2]) {
v3[p3]=v2[p2];
p3+=1;
p2+=1;
}
else {
v3[p3]=v1[p1];
p1+=1;
p3+=1;
v3[p3]=v2[p2];
p3+=1;
p2+=1;
}
}
```

static void intercala(int v1[],int p1,int v2[],int p2,int v3[],int p3) {
     while(p1 < v1.length || p2 < v2.length)
          if(v1[p1] < v2[p2]) {
               v3[p3]=v1[p1];
               p3++;
               p1++;
          }
          else
               if(v1[p1] > v2[p2]) {
                    v3[p3]=v2[p2];
                    p3++;
                    p2++;
               }
               else {
                    v3[p3]=v1[p1];
                    p1++;
                    p3++;
                    v3[p3]=v2[p2];
                    p3++;
                    p2++;
               }
}

Resposta comentada

Gabarito Alternativa B

Recursividade é quando uma função chama a si mesma para resolver um problema menor, até chegar a um caso-base que encerra as chamadas. Aqui, a cada passo, copiamos o menor elemento entre os dois arrays e avançamos o ponteiro correspondente, repetindo até esgotar ambos.

(A) Incorreta: Não verifica se um dos arrays já terminou antes de acessar v1[p1] ou v2[p2], causando ArrayIndexOutOfBoundsException quando um deles se esgota (ex.: após copiar todo o v2, ainda tenta comparar v1[p1] com v2[p2] inexistente).
(B) Correta: Trata corretamente os casos de fim de um dos arrays: se p1 == v1.length, copia o restante de v2; se p2 == v2.length, copia o restante de v1; e quando ambos terminam, retorna. A comparação v1[p1] < v2[p2] só ocorre quando ambos têm elementos, evitando erros de índice. O caso de empate (valores iguais) cai no else, copiando de v2, o que mantém a ordem (não é necessário desempatar).
(C) Incorreta: Primeiro faz chamadas recursivas avançando os ponteiros sem copiar nada, e só depois tenta preencher v3[p3] — mas os ponteiros já foram alterados, então os valores copiados ficam errados e a ordem não é preservada.
(D) Incorreta: Usa while (iteração) em vez de recursão, e não trata o caso de um array terminar antes do outro — após o while, os elementos restantes do array maior não são copiados, resultando em lacunas no v3.
(E) Incorreta: A condição while(p1 < v1.length || p2 < v2.length) permite acessar v1[p1] ou v2[p2] quando um deles já terminou, causando ArrayIndexOutOfBoundsException (mesmo problema da A, mas em versão iterativa).

Armadilha da banca: A alternativa (A) parece elegante e curta, mas esquece de verificar se os ponteiros estão dentro dos limites — o erro clássico de quem não testa os casos de borda (um array vazio ou um array menor que o outro). A alternativa (B) é a única que cobre todos os cenários com segurança, por isso é o gabarito.

Fonte: CESGRANRIO BASA 02/2021 Técnico Científico - Tecnologia da Informação. Reproduzida para fins de estudo.

Questão de Tecnologia da Informação · CESGRANRIO BASA 02/2021 (nº 54)

Resposta comentada

Continue estudando