(AS-V) ESTRUTURA DE DADOS LINEARES

Prévia do material em texto

Pergunta 1
Resposta Selecionada:
c. 
Respostas: a. 
b. 
c. 
d. 
e. 
Comentário
da resposta:
Considere o seguinte trecho de algoritmo, representado em pseudocódigo:
1 - para i←1 até n faça
2 -     para j←1 até n faça
3 -        V[i][j]←i+j.
Nesse contexto, avalie as afirmações a seguir e selecione a alternativa correta dentre as disponíveis.
I - O número de instruções executadas pelo trecho de algoritmo é exatamente 2n2+2n+1.
II - Quando o tamanho da instância de entrada dobra, o número de instruções executadas é
multiplicado por dois.
III - Sob a ótica da análise da eficiência assintótica, o tempo de execução do trecho de algoritmo é
proporcional a T(n)=n2.
IV - Pode-se classificar o tempo de execução do trecho de algoritmo como linear no tamanho da
entrada.
É correto o que se afirma em I e III, apenas.
É correto o que se afirma em II e IV, apenas.
É correto o que se afirma em I e II, apenas.
É correto o que se afirma em I e III, apenas.
É correto o que se afirma em I e IV, apenas.
 
É correto o que se afirma em II e III, apenas.
 
Para o exemplo apresentado, quando o tamanho da instância dobra, o número de
instruções quadriplica e classificamos como quadrático no tamanho da entrada.
Pergunta 2
Resposta Selecionada:
a. 
Respostas:
a. 
b. 
c. 
A=[1,3,8,7,6,3,2,1,6,3],
O algoritmo de ordenação por contagem, ou Counting Sort, executa um número de instruções
proporcional a n. A premissa para esse algoritmo é que a entrada seja um arranjo de inteiros maiores
ou iguais a 0 e menores ou iguais a k. Nesse sentido, é preciso que se conheça previamente o maior
valor no arranjo. Nesse contexto, considere o seguinte arranjo de entrada A
considerando que o algoritmo Counting Sort utiliza um arranjo auxiliar C que, inicialmente, armazenará
a frequência dos valores de A, o estado inicial de C para esse exemplo é:
C=[0,2,1,3,0,0,2,1,1]
 
C=[0,2,1,3,0,0,2,1,1]
 
C=[0,3,2,2 1,1,2,1,1]
 
C=[1,2,2,3,1,1,2,1,1]
0,2 em 0,2 pontos
0,2 em 0,2 pontos
d. 
e. 
Comentário
da
resposta:
C=[1,2,3,3,0,0,2,1,1]
 
C=[0,1,2,3,4,0,4,2,1]
  Inicialmente, o arranjo auxiliar armazena as frequências dos valores em A como sendo
o valor do indexador em C, cada valor armazenado em C descreve a quantidade de
vezes que o valor do indexador aparece em A.
Pergunta 3
Resposta Selecionada:
c. 
Respostas: a. 
b. 
c. 
d. 
e. 
Comentário da
resposta:
A=[0.12;0.23;0.85;0.47;0.21;0.33;0.60;0.41;0.15;0.10].
Considere o seguinte arranjo:
Considere, ainda, que o arranjo anterior será submetido, como instância de entrada, ao algoritmo
Bucket Sort. Nesse contexto, avalie as afirmações a seguir e selecione a alternativa correta dentre as
disponíveis.
I - A lista em B[0] é vazia.
II - A lista em B[1] tem dois elementos.
III - A lista em B[2] tem três elementos.
IV - A lista em B[3] tem um elemento.
É correto o que se afirma em I e IV, apenas.
É correto o que se afirma em II e IV, apenas.
É correto o que se afirma em I e II, apenas.
É correto o que se afirma em I e IV, apenas.
É correto o que se afirma em II e III, apenas.
 
É correto o que se afirma em I e III, apenas.
 
Após a execução do algoritmo, teremos: B[0]=∅, B[1]=0.10→0.12→0.15,
B[2]=0.21→0.23 e B[3]=0.33.
Pergunta 4
Resposta Selecionada: b. 
Respostas: a. 
Sobre o desempenho de algoritmos de ordenação, avalie as afirmações abaixo e selecione a
alternativa correta dentre as disponíveis.
I - O algoritmo Bucket Sort tem melhor desempenho que o algoritmo Bubble Sort.
II - O algoritmo Insertion Sort tem melhor desempenho que o algoritmo Counting Sort.
III - O algoritmo Counting Sort tem melhor desempenho que o algoritmo Insertion Sort.
IV - O algoritmo Bubble Sort tem melhor desempenho que o algoritmo Counting Sort.
É correto o que se afirma em I e III, apenas.
É correto o que se afirma em II e III, apenas.
0,2 em 0,2 pontos
0,2 em 0,2 pontos
b. 
c. 
d. 
e. 
Comentário
da
resposta:
É correto o que se afirma em I e III, apenas.
É correto o que se afirma em I e II, apenas.
É correto o que se afirma em II e IV, apenas.
É correto o que se afirma em I e IV, apenas.
Os algoritmos Counting Sort e Bucket Sort são algoritmos de ordenação em tempo
linear. Os algoritmos Bubble Sort e Insertion Sort são algoritmos de ordenação em
tempo quadrático. Os algoritmos em tempo linear têm melhores desempenhos que os
em tempo quadrático.