ATIVIDADE SUB - ESTRUTURA DE DADOS II - 52-2022

Prévia do material em texto

07/12/2022 17:41 Unicesumar - Ensino a Distância
about:blank 1/7
ATIVIDADE SUB - ESTRUTURA DE DADOS II - 52/2022
Período:11/08/2022 08:00 a 28/08/2022 23:59 (Horário de Brasília)
Status:ENCERRADO
Nota máxima:3,00
Gabarito:Gabarito será liberado no dia 19/09/2022 00:00 (Horário de Brasília)
Nota obtida:2,10
1ª 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.
2ª QUESTÃO
Algoritmos de ordenação complexos não necessariamente garantem que a ordenação seja feita de maneira
rápida em todas as ocasiões. Todavia, algoritmos de ordenação, apesar de possuírem implementações
bastante específicas e distintas, apresentam algumas características em comum que podem quebrar um
galho enorme na vida de desenvolvedores.
 
OLIVEIRA, Pietro Martins de; LEON, Rogério de. Estrutura de Dados II. Maringá-PR, Unicesumar, 2019.
 
 
Com base em seus conhecimentos sobre os algoritmos Mergesort, Quicksort e Heapsort, avalie as
afirmações que se seguem:
 
I. O Heapsort necessita de memória auxiliar para construir sua Heap.
II. No caso médio, para um arranjo de tamanho n, os três algoritmos realizam cerca de n log n comparações
para ordenar.
III. Dentre os três algoritmos recém mencionados, apenas o Heapsort não se aproveita do conceito de
dividir-para-conquistar.
 
É 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.
3ª QUESTÃO
07/12/2022 17:41 Unicesumar - Ensino a Distância
about:blank 2/7
Algoritmos de ordenação mais rápidos geralmente adicionam alguma complexidade quanto à compreensão
de seu funcionamento, especialmente para iniciantes. Todavia, é de suma importância conhecê-los para que,
em um futuro ocasional, o profissional de desenvolvimento não passe por apuros em suas implementações.
 
(Fonte: OLIVEIRA, Pietro Martins de; LEON, Rogério de. Estrutura de Dados II. Maringá-PR, Unicesumar,
2019.)
 
Observe o pseudocódigo a seguir:
 
Com base no pseudocódigo apresentado acima, avalie as afirmações a seguir:
 
I. O método Merge() não necessita de memória auxiliar para funcionar corretamente.
II. Pode-se dizer que esse método de ordenação utiliza o conceito dividir-para-conquistar.
III. Recursivamente, o Mergesort() divide o arranjo original em dois, até que se tenha um conjunto de sub-
arranjos de tamanho unitário.
 
É 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
07/12/2022 17:41 Unicesumar - Ensino a Distância
about:blank 3/7
Para resolver problemas de maneira eficiente, pode-se tentar eliminar soluções inviáveis, encurtando a
resolução. A busca binária e a busca em árvore binária são dois exemplos de algoritmos que "podam"
soluções errôneas, para encurtar o caminho até uma solução.
 
OLIVEIRA, Pietro Martins de; LEON, Rogério de. Estrutura de Dados II. Maringá-PR, Unicesumar, 2019.
 
 
Considerando uma busca em árvore binária ordenada que se inicie em 20, caso o usuário decida por buscar
o valor alvo igual a 25, qual seria a ordem de visitação dos nós?
 
ALTERNATIVAS
20, 21, 31, 30
20, 21, 31
20, 3, 8, 7
20, 21, 31, 40
20, 21
5ª QUESTÃO
Para resolver o problema do desbalanceamento de árvores binárias de busca, os pesquisadores Adelson-
Velskii e Landis, em 1962, criaram um algoritmo que leva as iniciais de seus nomes. As árvores AVL são,
nesse sentido, árvores nas quais todos os nós encontram-se balanceados.
 
OLIVEIRA, Pietro Martins de; LEON, Rogério de. Estrutura de Dados II. Maringá-PR, Unicesumar, 2019.
 
Observe a árvore binária AVL a seguir:
Com base na árvore representada na ilustração acima, avalie as afirmações que se seguem:
 
I. Pode-se dizer que a altura do nó 25 é igual a 2.
II. Não podemos dizer que é uma árvore estritamente binária.
III. Para balancear essa árvore, é preciso realizar rotação dupla.
 
É correto o que se afirma em:
 
ALTERNATIVAS
07/12/2022 17:41 Unicesumar - Ensino a Distância
about:blank 4/7
I, apenas.
I e II, apenas.
I e III, apenas.
II e III, apenas.
I, II e III.
6ª QUESTÃO
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:
 
ALTERNATIVAS
I, apenas.
I e II, apenas.
I e III, apenas.
II e III, apenas.
I, II e III.
7ª QUESTÃO
07/12/2022 17:41 Unicesumar - Ensino a Distância
about:blank 5/7
Dependendo da forma com a qual os dados são inseridos em uma árvore binária, tal estrutura de dados
pode acabar apresentando muita ineficiência em suas operações, sejam operações de inserção, remoção ou
busca de dados. Para tentar amenizar tais situações existem os algoritmos de balanceamento AVL.
 
OLIVEIRA, Pietro Martins de; LEON, Rogério de. Estrutura de Dados II. Maringá-PR, Unicesumar, 2019.
 
 
Com base na árvore representada a ilustração acima, avalie as afirmações que se seguem:
 
I. É correto dizer que a altura de um nó folha é igual a 0.
II. Para balancear essa árvore é preciso executar uma rotação simples à direita
III. Os nós 5 e 17 estão apresentam sinais de que a árvore está desbalanceada.
 
É correto o que se afirma em:
 
ALTERNATIVAS
I, apenas.
I e II, apenas.
II e III, apenas.
II e III, apenas.
I, II e III.
8ª QUESTÃO
Os sistemas digitais do mundo atual realizam diversas tarefas repetitivas ininterruptamente. Uma das tarefas
repetitivas mais realizadas pelas máquinas são as operações de busca em arranjos lineares. Para isso,
existem uma gama de algoritmos distintos que realizam a mesma tarefa sob estruturas lineares distintas,
como por exemplo, os algoritmos de busca sequencial e de busca binária.
 
OLIVEIRA, Pietro Martins de; LEON, Rogério de. Estrutura de Dados II. Maringá-PR, Unicesumar, 2019.
 
Com base em seus conhecimentos sobre os algoritmos de Busca Sequencial Indexada e Busca Binária, avalie
as afirmações que se seguem:
 
I. A Busca Binária é um bom algoritmo para se aplicar em arranjos estáticos.
II. A Busca Sequencial Indexada depende de o arranjo estarordenado para poder interromper a busca em
algumas situações.
III. A Busca Binária pode ser feita em arranjos desordenados.
 
É 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.
9ª QUESTÃO
07/12/2022 17:41 Unicesumar - Ensino a Distância
about:blank 6/7
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
I, apenas.
I e II, apenas.
I e III, apenas.
II e III, apenas.
I, II e III.
10ª QUESTÃO
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
07/12/2022 17:41 Unicesumar - Ensino a Distância
about:blank 7/7
I, apenas.
I e II, apenas.
I e III, apenas.
II e III, apenas.
I, II e III.