Atividade 2 - Estrutura de dados II

Prévia do material em texto

08/09/2021 13:25 Unicesumar - Ensino a Distância
1/7
ATIVIDADE 2 - ESOFT - ESTRUTURA DE DADOS II - 52/2021
Período:07/06/2021 08:00 a 21/06/2021 23:59 (Horário de Brasília)
Status:ENCERRADO
Nota máxima:1,00
Gabarito:Gabarito será liberado no dia 22/06/2021 00:00 (Horário de Brasília)
Nota obtida:1,00
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
Observe as colunas a seguir: 
 
Associe as colunas dos métodos de ordenação acima de acordo com a coluna da descrição. 
Assinale a alternativa que faz a associação correta dos métodos de ordenação de cima para baixo na tabela. 
ALTERNATIVAS
08/09/2021 13:25 Unicesumar - Ensino a Distância
2/7
1, 2 e 3, respectivamente.
1, 3 e 2, respectivamente.
2, 1 e 3, respectivamente.
2, 3 e 1, respectivamente.
3, 2 e 1, respectivamente.
3ª QUESTÃO
Um algoritmo é considerado de complexidade quadrática se houver nele dois laços aninhados. Já um
algoritmo que utiliza a técnica de dividir para conquistar sugere que um problema complexo
seja dividido em dois problemas menores, e cada um desses sejam divididos novamente em partes menores
ainda, até que se encontre uma parte pequena e simples suficiente para que seja resolvido. 
OLIVEIRA, P. M.; PEREIRA, R. L. Estrutura de Dados II. Maringá-Pr.: Unicesumar, 2019. 
Com base nos dois conceitos apresentados, analise os seguintes métodos: 
I-Shellsort 
II-Heapsort 
III- Quicksort  
IV-Mergesort   
V- Bubblesort 
VI- Insertionsort  
VII- Selectionsort  
Assinale a alternativa que apresenta apenas algoritmos com complexidade quadrática.
ALTERNATIVAS
I, II, III e IV, apenas.
I, III, V e VII, apenas.
I, V, VI e VII, apenas.
II, IV, VI e VII, apenas.
III, IV, VI e VII, apenas.
4ª QUESTÃO
As grandes massas de dados ficam armazenados em dispositivos de memória secundária, como disco rígido,
disco óptico, fita magnética, memória flash, dentre outros. Entretanto todo dado, para ser manipulado,
precisa necessariamente estar na memória principal. Alguns algoritmos são especializados em realizar
buscas em arquivos de chaves primárias, outros por chaves secundárias. Alguns são mais rápidos
em arquivos menores, outros ideais para grandes quantidades de informações. 
OLIVEIRA, P. M.; PEREIRA, R. L. Estrutura de Dados II. Maringá-Pr.: Unicesumar, 2019. 
Considerando o excerto acima, assinale a alternativa correta a respeito dos algoritmos de busca.
ALTERNATIVAS
08/09/2021 13:25 Unicesumar - Ensino a Distância
3/7
O algoritmo de busca binária utiliza o conceito de lista circular.
A busca binária e a busca sequencial fazem uso da técnica de recursão.
A busca binária e a busca sequencial executam processamento repetitivo.
A implementação do algoritmo de busca sequencial repete da fase da busca como uma subtarefa da anterior.
Em um vetor ordenado o algoritmo de busca faz a pesquisa completa, mesmo que um valor fora do parâmetro de
busca seja encontrado.
5ª QUESTÃO
Em uma agência de locação de veículos, o gerente te solicitou fazer uma lista com as quantidades de
locações nos últimos 12 meses. Por ser uma lista pequena e rápida de fazer você criou o seguinte algoritmo
de busca. 
int busca(int *vec, int arg){ 
 return(vec[arg]); 
} 
Nesse algoritmo o parâmetro vec representa o arquivo e arg é o mês que o usuário deseja saber quantos
veículos foram alugados. O vetor abaixo tem em cada posição a quantidade de locações do mês.  
Porém, na primeira execução de busca no arquivo 
int arquivo[] = {10, 12, 8, 6, 9, 13, 12, 17, 15, 25, 12, 15};  
ao informar o mês 6 o algoritmo trouxe 12 ao invés de 13. Seu gerente pediu então que fizesse uma
correção. 
Assinale a alternativa que corrige esse problema.
ALTERNATIVAS
return(achou);
return(vec[arg-1]);
return(vec[arg+1]);
int tam = sizeof(arquivo)/sizeof(int);
while ((i < tam) && (achou == -1)){
 if (vec[i]==arg){
 achou = i;
 }
 i++;
}
6ª QUESTÃO
08/09/2021 13:25 Unicesumar - Ensino a Distância
4/7
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.
7ª QUESTÃO
08/09/2021 13:25 Unicesumar - Ensino a Distância
5/7
Observe o código a seguir:
 
int algoritmo(int vec
, int tamanho){
   int i, j, qtd=0, tmp;
   for(i = 1; i < tamanho; i++){
      j = i;
      while((vec
j
< vec
j − 1
) && (j!=0)){
         tmp = vec
j
;
         vec
j
= vec
j − 1
;
         vec
j − 1
= tmp;
         j--;
         qtd++;
      }
   }
   return(qtd);
}
 
O método __________ de ordenação foi utilizado nessa solução.
 
Assinale a alternativa que complete essa afirmação corretamente.
ALTERNATIVAS
08/09/2021 13:25 Unicesumar - Ensino a Distância
6/7
Badsort
Shellsort
Bubblesort
Insertionsort
Selectionsort
8ª QUESTÃO
Considere o algoritmo a seguir: 
void ordena(int x[], int tam){
     int temp = 0;
 for (int i = 0; i < tam; i++){ 
 for (int j = (tam-1); j >= (i+1); j--){ 
 if (x[j] < x[j-1]){ 
 temp = x[j]; 
 x[j] = x[j-1]; 
 x[j-1] = temp; 
 } 
 } 
 } 
} 
Esse algoritmo tem por finalidade ordenar um vetor X com tam posições. 
Analisando o algoritmo, assinale a alternativa que corresponde a esse método de ordenação.
ALTERNATIVAS
Mergesort
Shellsort
Bubblesort
Insertionsort
Selectionsort
9ª 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 denó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
08/09/2021 13:25 Unicesumar - Ensino a Distância
7/7
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.
10ª QUESTÃO
Analise a definição a seguir:
 
A implementação desse algoritmo consistem em procurar o menor valor a partir da primeira posição do de
um vetor. Encontrando o menor valor troca-se com a primeira posição. Feito isso, repete o mesmo processo
para a segunda posição do vetor, procurando o segundo menor valor armazenado no vetor para realizar a
troca de posição dos valores. Esse processo se repete até que o vetor esteja ordenado.
 
Assinale a alternativa correta em relação ao método de ordenação descrito acima.
ALTERNATIVAS
Shellsort
Bubblesort
Withoutsort
Insertionsort
Selectionsort