ATIVIDADE 2 - ENG SOFT - ESTRUTURA DE DADOS II - 2020 52

Prévia do material em texto

02/06/2020 Unicesumar - Ensino a Distância
1/9
ATIVIDADE 2 - ENG SOFT - ESTRUTURA DE DADOS II - 2020/52
Período:18/05/2020 08:00 a 02/06/2020 23:59 (Horário de Brasília)
Status:ABERTO
Nota máxima:0,50
Gabarito:Gabarito será liberado no dia 03/06/2020 00:00 (Horário de Brasília)
Nota obtida:
1ª QUESTÃO
Alguns algoritmos são capazes de organizar vetores de maneira crescente ou decrescente. As motivações
para se ordenar um vetor vão desde buscar por contatos na agenda do celular a lista de compras e vendas
realizadas diariamente em uma organização. Os algoritmos Bubblesort, Selectionsort, Insertionsort e
Shellsort são capazes de ordenar um conjunto de dados armazenados em um vetor, de maneira exata. O
algoritmo Shellshort, no entanto, é o mais eficiente dentro dos algoritmos classificados como de
complexidade quadrática. Esse algoritmo é uma técnica refinada do método de ordenação por inserção. 
Oliveira, P. M. de;  Pereira, R. de L. Estrutura de Dados II. Maringá-Pr.: Unicesumar, 2019. 
Com base no excerto acima, assinale a alternativa que explica corretamente um algoritmo de complexidade
quadrática.
ALTERNATIVAS
Um algoritmo em que há dois laços aninhados.
Um algoritmo que escolhe um elemento como pivô.
Converte um dado em um índice, que é a posição na qual tal dado será armazenado.
Esse método permite a inserção e remoção de elementos em filas de prioridade em tempo logarítmico.
2ª QUESTÃO
Os algoritmos de ordenação de implementação mais simplificada são os algoritmos Bubblesort,
Selectionsort, Insertionsort e Shellsort, contudo, todos esses métodos são capazes de ordenar um conjunto
de dados armazenados em um vetor, de maneira exata. A técnica de ordenação Bubblesort é de simples
implementação e de alto custo computacional. 
Oliveira, P. M. de;  Pereira, R. de L. Estrutura de Dados II. Maringá-Pr.: Unicesumar, 2019. 
Analise as afirmações a seguir: 
I, Não possui recursividade e têm dois laços de repetição aninhados.
II. Tem potencial para executar um número muito menor de repetições.
III. Busca o menor valor em todo o vetor e posiciona-o no início da tabela.
IV. Compara os valores de dois a dois e empurra o maior valor para o final. 
Sobre o Bubblesort é correto o que se afirma em:
ALTERNATIVAS
02/06/2020 Unicesumar - Ensino a Distância
2/9
I e II, apenas.
I e III, apenas.
I e IV, apenas.
II e III, apenas.
II e IV, apenas.
3ª QUESTÃO
O método de ordenação Heapsort remete a estrutura de dados de filas de prioridade. Uma fila de
prioridades agrupa elementos de forma que cada um dos elementos pode ter maior ou menor importância
para a aplicação. Sendo assim, nesse tipo de estrutura é possível inserir elementos a qualquer instante e em
qualquer posição do arranjo, de acordo com sua prioridade. Já a remoção é sempre feita no elemento de
maior prioridade. 
Oliveira, P. M. de;  Pereira, R. de L. Estrutura de Dados II. Maringá-Pr.: Unicesumar, 2019. 
Analise as afirmações a seguir sobre a ordenação Heapsort: 
I. Utiliza-se de uma árvore binária na qual posiciona os valores menores da raiz na sua subárvore esquerda e
os maiores na subárvore direita.
II. Utiliza-se da técnica de dividir para conquistar, que consiste em dividir o arranjo pela metade até que
existam apenas arranjos com um único elemento. A ordenação acontece durante o retorno da recursividade.
III. Sempre armazena na raiz de uma árvore binária, o elemento de maior valor entre todos os dados
armazenados, e realiza a ordenação dos dados de modo a trocar a raiz com a última posição não ordenada
do vetor.
IV. Utiliza-se e um pivô para o processo de particionamento, em que os valores menores que o pivô ficam
numa sublista e os maiores em outra. Essa técnica garante a posição final do pivô, e que os elementos
menores precedam os elementos maiores.
É correto o que se afirma em:
ALTERNATIVAS
I, apenas.
III, apenas.
I e III, apenas.
II e IV, apenas.
I, II, III e IV.
4ª QUESTÃO
Os métodos de ordenação Bubblesort e Selectionsort têm uma implementação mais simplificada. O método
terceiro Insertionsort utiliza um laço de repetição interno para tentar otimizar a ordenação. Já o Shellsort
realiza a ordenação de um vetor considerando o conceito de gaps. A técnica de ordenação Mergesort utiliza
um conceito conhecido por dividir para conquistar de forma recursiva. Essa abordagem é bem mais
complexa, porém o seu esforço computacional é reduzido. 
Oliveira, P. M. de;  Pereira, R. de L. Estrutura de Dados II. Maringá-Pr.: Unicesumar, 2019. 
Com base no texto acima, assinale a alternativa que define adequadamente esforço computacional.
ALTERNATIVAS
02/06/2020 Unicesumar - Ensino a Distância
3/9
Está associado a utilização de laços aninhados.
Consiste em pegar um vetor muito grande e divide-lo em dois vetores menores.
Tem como objetivo retornar o mais rapidamente possível todos os elementos de um vetor para uma posição na
memória.
Se refere a quantidade de vezes que o laço mais interno de um algoritmo é repetido ou a quantidade de vezes que
uma chamada recursiva é realizada.
Se refere a toda estrutura, vetorial ou dinâmica, que possível percorrer todos os elementos seguindo, ponteiros,
variáveis, utilizando operações quadráticas ou recursivas.
5ª QUESTÃO
As árvores AVL nos dão ferramentas para rotacionar nós desbalanceados em busca de uma árvore binária
tão balanceada quanto possível. O conceito de balanceamento está relacionado à altura das subárvores que
compõem uma árvore binária. A altura de uma subárvore é igual ao número de nós visitados desde a raiz
até o nó folha mais distante. Por definição, uma subárvore vazia possui altura -1.
 
OLIVEIRA, P. M.; PEREIRA, R. L. Estrutura de Dados II. Maringá-Pr.: Unicesumar, 2019.
 
Assina a alternativa que conceitua corretamente um nó balanceado.
ALTERNATIVAS
Quando o fator de balanceamento absoluto dos nós das subárvores seja seja maior ou igual a 2.
Quando o valor absoluto da diferença entre as alturas das subárvores esquerda e direita seja maior ou igual a 1.
Quando o valor absoluto da diferença entre as alturas das subárvores esquerda e direita seja menor ou igual a -1.
Quando o valor absoluto da diferença entre as profundidades das subárvores esquerda e direita seja menor ou igual
a 1.
Quando o fator absoluto da diferença entre as profundidades das subárvores esquerda e direita seja maior ou igual a
-1.
6ª QUESTÃO
02/06/2020 Unicesumar - Ensino a Distância
4/9
Para ordenar um vetor um desenvolvedor da sua equipe escreveu o seguinte método de ordenação:
 
int algoritmo(int vec
, int tamanho){
  int i, j, min, qtd=0, tmp;
  for (i = 0; i < tamanho-1; i++){
     min = i;
     for (j = (i+1); j < tamanho; j++) {
        if(vec
j
< vec
min
)
           min = j;
        qtd++;
     }
     if (i != min) {
        tmp = vec
i
;
        vec
i
= vec
min
;
        vec
min
= tmp;
     }
  }
  return(qtd);
}
Você foi convidado a analisar o programa e indicar o método de ordenação de que ele aplicou.
 
Assinale a alternativa correspondente ao método de ordenação utilizado por seu colega.
ALTERNATIVAS
02/06/2020 Unicesumar - Ensino a Distância
5/9
Shellsort
Quicksort
Bubblesort
Insertionsort
Selectionsort
7ª QUESTÃO
A ordenação Insertionsort 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.
 
OLIVEIRA, P. M.; PEREIRA, R. L. Estrutura de Dados II. Maringá-Pr.: Unicesumar, 2019.
 
Sendo assim, analise as afirmações a seguir:
 
I. O InsertionSort não é um algoritmo inerentemente recursivo.
II. O InsertionSort também é conhecido como método de ordenação por inserção.
III. O algoritmo InsertionSort possui dois laços de repetição aninhados, sugerindo lentidão na execução.
IV. Pelo fato de possuir dois laços de repetição aninhados, o InsertionSort não é capaz de ser mais veloz que
os algoritmos SelectionSort e BubbleSort.
 
É correto o que se afirma em:
ALTERNATIVAS
I e III, apenas.
II e IV, apenas.
I, II e III,apenas.
II, III e IV, apenas.
I, II, III e IV.
8ª QUESTÃO
02/06/2020 Unicesumar - Ensino a Distância
6/9
Os algoritmos de ordenação utilizam métodos capazes de ordenar um conjunto de dados armazenados em
um vetor, de maneira exata.
 
OLIVEIRA, P. M.; PEREIRA, R. L. Estrutura de Dados II. Maringá-Pr.: Unicesumar, 2019.
 
Avalie as afirmativas sobre os algoritmos BubbleSort e SelectionSort:
 
I – A técnica de ordenação BubbleSort também é conhecida por ordenação por flutuação ou método da
bolha.
II – Apesar de ser uma técnica de simples implementação, o SelectionSort possui alto consumo
computacional.
III – Ambos, SelectionSort e BubbleSort, estão entre os piores desempenhos entre os algoritmos de
ordenação existentes.
IV – O método SelectionSort seleciona e ordena um elemento arbitrário do arranjo e, então, chama a si
mesmo recursivamente, para ordenar uma porção menor do arranjo.
 
É correto o que se afirma em:
ALTERNATIVAS
III, apenas.
I e II, apenas.
I, II e III, apenas.
I, II e IV, apenas.
II, III e IV, apenas.
9ª QUESTÃO
O algoritmo Shellshort é o mais eficiente dentro dos algoritmos classificados como de complexidade
quadrática, ou seja, aqueles algoritmos com dois laços de repetição aninhados.
 
OLIVEIRA, P. M.; PEREIRA, R. L. Estrutura de Dados II. Maringá-Pr.: Unicesumar, 2019.
 
Com base nessa explicação, assinale a alternativa correta.
ALTERNATIVAS
02/06/2020 Unicesumar - Ensino a Distância
7/9
O ShellSort é uma otimização do algoritmo SelectionSort.
O ShellSort necessita de memória auxiliar para realizar ordenação.
O nome do algoritmo ShellSort se deve ao fato de ele implementar o conceito de "concha" de dados.
O conceito de GAP, utilizado no ShellSort, é uma maneira de aproximar elementos que estão muito distantes dentro
do vetor.
Devido à sua similaridade com a busca binária, de maneira geral, o ShellSort utiliza uma estrutura em árvore, para
realizar sua busca.
10ª QUESTÃO
02/06/2020 Unicesumar - Ensino a Distância
8/9
A equipe de engenheiros de software da empresa XPTO necessita realizar a ordenação de um vetor, para
que certa funcionalidade de busca obtenha ganho em desempenho. Diante dessa demanda, um dos
desenvolvedores da equipe intuitivamente desenvolveu o seguinte código em linguagem C:
 
int algoritmo(int vec
, int tamanho){
   int qtd, i, j, tmp;
   qtd = 0;
   for (i = 0; i < tamanho-1; i++){
      for (j = i+1; j < tamanho; j++){
         if (vec
i
> vec
j
){
            tmp = vec
i
;
            vec
i
= vec
j
;
            vec
j
= tmp;
         }
         qtd++;
      }
   }
   return(qtd);
}
 
Assinale a alternativa que corresponde ao algoritmo implementado pelo programador.
ALTERNATIVAS
02/06/2020 Unicesumar - Ensino a Distância
9/9
Ordenação por flutuação, BubbleSort.
Ordenação por seleção, SelectionSort.
Ordenação por inserção, InsertionSort.
Ordenação utilizando concha, ShellSort.
Ordenação por troca de partição, QuickSort.