ATIVIDADE DE ESTUDO 4 - ESTRUTURA DE DADOS II - 52 2022 - UNICESUMAR

Prévia do material em texto

ATIVIDADE 4 - ESOFT - ESTRUTURA DE DADOS II - 52/2022
Período:20/06/2022 08:00 a 08/07/2022 23:59 (Horário de Brasília)
Status:ABERTO
Nota máxima:1,00
Gabarito:Gabarito será liberado no dia 09/07/2022 00:00 (Horário de Brasília)
Nota obtida:
1ª QUESTÃO
Unicesumar - Ensino a Distância https://studeo.unicesumar.edu.br/
1 of 8 07/07/2022 17:00
A técnica de ordenação Bubblesort também é conhecida por ordenação por flutuação ou por método da
bolha. Ela é de simples implementação e de alto custo computacional. Começando na primeira posição do
vetor, compara-se o valor dela com todos os demais elementos, trocando caso o valor da posição atual seja
maior do que o valor verificado.
 
(Fonte: OLIVEIRA, Pietro Martins de; LEON, Rogério de. Estrutura de Dados II. Maringá-PR, Unicesumar,
2019.)
 
Observe o código-fonte a seguir:
 
//Aplica o método do Bubblesort
int Bubblesort (int vec
){
   int i, j, tmp;
   for (i = 0; i < tamanho -1; i++){
      for (j = i+1; j < tamanho; j++){
         if (vec
i
< vec
j
){
            troca(&vec
i
, &vec
j
);
        }
     }
   }
}
//Considere que a função troca() inverte as posições dos parâmetros vec
i
e vec
j
dentro do vetor
 
Com base no código-fonte apresentado acima, avalie as afirmações a seguir:     
 
I. O Bubblesort, também conhecido como método da bolha, é conhecido por sua ineficiência.
II. Da forma como foi escrito, esse algoritmo irá ordenar vec em ordem decrescente.
III. A variável inteira tmp é desnecessária para que a ordenação seja feita corretamente.
 
É correto o que se afirma em:
 
ALTERNATIVAS
Unicesumar - Ensino a Distância https://studeo.unicesumar.edu.br/
2 of 8 07/07/2022 17:00
I, apenas.
I e II, apenas.
II e III, apenas.
II e III, apenas.
I, II e III.
2ª QUESTÃO
Você sabia que durante o processo de busca de dados em um arranjo linear é possível “cortar caminho”
para deixar de vasculhar regiões do vetor que provavelmente não contenham a resposta para a busca?
Quando se realiza a busca binária, pode ser muito mais rápido encontrar a posição de um elemento em um
arranjo, ou mesmo, dizer se o elemento está ausente no vetor.
 
OLIVEIRA, Pietro Martins de; LEON, Rogério de. Estrutura de Dados II. Maringá-PR, Unicesumar, 2019.
 
Observe o pseudocódigo a seguir:
 
//Função de Busca Binária
int BuscaBinaria(int vec
, int arg, int tam){
    int menor, maior, meio;
    menor = 0;
    maior = tam-1;
    while (menor <= maior){
       meio = (menor + maior)/2;
       if (arg == vec
meio
){
            return(meio);
        }
        if(arg < vec
meio
){
            maior = meio - 1;
        }
       else {
          menor = meio + 1;
       }
    }
    return(-1);
}
 
Com base no código-fonte apresentado acima, avalie as afirmações a seguir:
 
I. A fórmula para identificar a posição do meio do arranjo está incorreta no corpo da função BuscaBinaria()
acima.
II. Em caso de elemento ausente, este algoritmo irá retornar o valor inteiro -1.
III. Este algoritmo poderia ser implementado de forma recursiva.
 
É correto o que se afirma em:
 
ALTERNATIVAS
Unicesumar - Ensino a Distância https://studeo.unicesumar.edu.br/
3 of 8 07/07/2022 17:00
Daniel Corbetta
I, apenas.
I e II, apenas.
I e III, apenas.
II e III, apenas.
I, II e III.
3ª QUESTÃO
De modo geral, existe uma ampla gama de algoritmos de ordenação bastante conhecidos e bem
estudados. Para quem está iniciando sua carreira enquanto desenvolvedor(a), o interessante é
compreender bem os algoritmos de mais simples implementação, como o Bubblesort, Selectionsort e
Insertionsort.
 
(Fonte: OLIVEIRA, Pietro Martins de; LEON, Rogério de. Estrutura de Dados II. Maringá-PR, Unicesumar,
2019.)
 
Com base em seus conhecimentos sobre os algoritmos Bubblesort, Selectionsort e Insertionsort, avalie as
afirmações que se seguem:
 
I. Caso o arranjo a ser ordenador tenha tamanho igual a n, os três algoritmos recém mencionados farão
cerca de n² comparações.
II. No caso médio, o algoritmo Insertionsort fará apenas n comparações para ordenar o arranjo.
III. Nenhum dos algoritmos acima chega apresentar desempenho melhor do que o Mergesort, no melhor
caso.
 
É correto o que se afirma em:
 
ALTERNATIVAS
I, apenas.
I e II, apenas.
I e III, apenas.
II e III, apenas.
I, II e III.
4ª QUESTÃO
Unicesumar - Ensino a Distância https://studeo.unicesumar.edu.br/
4 of 8 07/07/2022 17:00
Daniel Corbetta
Daniel Corbetta
Daniel Corbetta
Um algoritmo bastante simples de implementar é o Selectionsort. Super intuitivo, ajuda novos estudantes
de estruturas de dados a compreender melhor como é possível ordenar um arranjo linear unidimensional.
Todavia, sua simplicidade de implementação tem um custo alto: o esforço computacional para executar
esse algoritmo não costuma ser dos melhores.
 
OLIVEIRA, Pietro Martins de; LEON, Rogério de. Estrutura de Dados II. Maringá-PR, Unicesumar, 2019.
 
Observe o código-fonte a seguir:
 
//Aplica o modo Selectionsort
int Selectionsort(int vec
, int tam){
   int i, j, min;
   for (i = 0; i < (tam-1); i++)
   {
      min = i;
      for (j = (i+1); j < tam; j++) {
          if(vec
j
< vec
min
) {
             min = j;
         }
      }
      if (i != min) {
         troca(&vec
i
, &vec
min
);
     }
  }
}
//Considere que a função troca() inverte as posições dos parâmetros vec
i
e vec
j
dentro do vetor
Com base no código-fonte apresentado acima, avalie as afirmações a seguir:     
 
I. O algoritmo Selectionsort, acima, ordena o vetor em ordem crescente.
II. Esse algoritmo é tão ineficiente quanto o Bubblesort.
III. As variáveis i e j fazem com que esse algoritmo seja tão rápido quanto o Quicksort.
 
É correto o que se afirma em:
 
Unicesumar - Ensino a Distância https://studeo.unicesumar.edu.br/
5 of 8 07/07/2022 17:00
ALTERNATIVAS
I, apenas.
I e II, apenas.
I e III, apenas.
II e III, apenas.
I, II e III.
5ª QUESTÃO
Unicesumar - Ensino a Distância https://studeo.unicesumar.edu.br/
6 of 8 07/07/2022 17:00
Daniel Corbetta
Daniel Corbetta
A ordenação Insertionsort também é conhecida como ordenação por inserção. É de implementação simples
e traz bons resultados. A técnica consiste em remover o primeiro elemento da lista, e procurar sua posição
ideal no vetor e reinseri-lo na tabela. O processo é repetido para todos os elementos.
 
(Fonte: OLIVEIRA, Pietro Martins de; LEON, Rogério de. Estrutura de Dados II. Maringá-PR, Unicesumar,
2019.)
 
Observe o código-fonte a seguir:
 
//Aplicando o Insertionsort
int Insertionsort (int vec
, int tam){
   int i, j;
   for(i = 1; i < tam; i++){
     j = i;
     while((vec
j
< vec
j − 1
) && (j!=0)){
       troca(&vec
j
, &vec
j − 1
);
       j--;
    }
  }
}
//Considere que a função troca() inverte as posições dos parâmetros vec
i
e vec
j
dentro do vetor
Com base no código-fonte apresentado acima, avalie as afirmações a seguir:     
 
I. A passagem de parâmetros do vetor vec
é feita por referência.
II. Dentro do laço while, o correto seria incrementar o valor de j (j++).
III. O algoritmo acima realiza a ordenação não-decrescente.
 
É correto o que se afirma em:
 
ALTERNATIVAS
Unicesumar - Ensino a Distância https://studeo.unicesumar.edu.br/
7 of 8 07/07/2022 17:00
I, apenas.
I e II, apenas.
I e III, apenas.
II e III, apenas.
I, II e III.
Unicesumar - Ensino a Distância https://studeo.unicesumar.edu.br/
8 of 8 07/07/2022 17:00
Daniel Corbetta