Estrutura de dados apol

Prévia do material em texto

Questão 1/10 - Estrutura de Dados 
O algoritmo de ordenação rápida, também conhecido como quick sort, é um dos algoritmos 
estudados na AULA 2. 
Acerca deste algoritmo, assinale a alternativa CORRETA. 
Nota: 10.0 
 A A complexidade do quick 
sort é O(n²). Isso significa 
que ele sempre terá a 
mesma eficiência de um 
bubble sort. 
Somente o pior caso do 
bubble e do quick são 
iguais. Se considerarmos 
cenários melhores o quick 
sort se sai bem melhor que 
o bubble sort. Veja o 
experimento feito na AULA 
PRÁTICA 1 para mais 
detalhes. 
 B O quick sort trabalha com o 
conceito de pivô, que é o 
elemento usado nas 
comparações, comparando 
sempre o seu valor com 
todos os valores do lado 
direito do pivô, enquanto 
que o lado esquerdo 
permanece já ordenado. 
Ambos os lados são 
comparados, esquerdo e 
direito. 
 C O quick sort trabalha com o 
conceito de pivô, que é o 
elemento usado nas 
comparações, comparando 
sempre o seu valor com 
todos os valores do lado 
esquerdo do pivô, enquanto 
que o lado direito 
permanece já ordenado. 
Ambos os lados são 
comparados, esquerdo e 
direito. 
 D O quick sort trabalha com 
uma troca de valores 
utilizando uma variável 
auxiliar, da mesma 
maneira feita no bubble 
sort. 
Você acertou! 
AULA 2 – TEMA 4 – 
CORRETO. 
 E O quick sort só pode ser 
executado para um 
tamanho de conjunto de 
dados máximo igual a 1000, 
pois mais do que isso o uso 
de memória pelo algoritmo é 
muito grande. 
O limite máximo dependerá 
da memória disponível, não 
sendo limitado ao valor de 
1000. 
 
 
Questão 2/10 - Estrutura de Dados 
Uma função que implementa o algoritmo bubble sort pode ser vista abaixo. Todo o resto do 
algoritmo foi omitido para que analisemos somente o método de ordenação. No código, 
TAMANHOVETOR refere a um valor inteiro que corresponde a dimensão do vetor de dados. 
 
1 - void BubbleSort(int vet[]) { 
2 - int aux; 
3 - for (int n = 1; n <= TAMANHOVETOR; n++) { 
4 - for (int i = 0; i < (TAMANHOVETOR - 1); i++) { 
5 - if (vet[i] < vet[i + 1]) { 
6 - aux = vet[i]; 
7 - vet[i] = vet[i + 1]; 
8 - vet[i + 1] = aux; 
9 - } } } } 
Acerca deste algoritmo, assinale a alternativa CORRETA: 
Nota: 10.0 
 A Na linha 5, o sinal de 
MENOR está incorreto. O 
algoritmo do bubble sort 
deve apresentar um sinal de 
MAIOR nesta linha. 
Tanto faz o sinal. Invertendo 
sinal inverte a forma como 
irá ordenar, o que não 
caracteriza um erro. 
 B Não é possível substituir os 
laços de repetição do tipo 
PARA (FOR) por um laço do 
tipo REPITA (DO-WHILE). 
É possível implementar com 
qualquer laço de repetição. 
 C Não é possível substituir os 
laços de repetição do tipo 
PARA (FOR) por um laço do 
tipo ENQUANTO (WHILE). 
É possível implementar com 
qualquer laço de repetição. 
 D Na linha 3, seria possível 
fazer a variável n iniciar 
em zero e terminar em 
(TAMANHOVETOR-1) 
Você acertou! 
CORRETO. AULA 2 – 
TEMA 2 e conceitos básicos 
de programação e 
algoritmos. 
 E A variável chamada de aux 
neste código tem como 
objetivo armazenar 
temporariamente o vetor de 
dados completo, para 
posteriormente ser 
ordenado. 
Ela serve para ajudar na 
troca individual de cada 
elemento. 
 
 
Questão 3/10 - Estrutura de Dados 
A complexidade de um algoritmo pode ser mensurada matematicamente em termos de uma 
função de custo do algoritmo. 
Acerca da função custo de um algoritmo, assinale a alternativa CORRETA: 
Nota: 10.0 
 A A ordem de como os dados 
de entradas estão 
organizados não tem 
impacto no desempenho do 
algoritmo em tempo de 
execução. 
Tem impacto. Conforme 
mostrado na AULA 1 – 
TEMA 2. 
 B O custo matemático de um 
algoritmo é dado, 
exclusivamente, pelo custo 
de tempo de execução de 
um algoritmo. 
É dado pelo tempo de 
execução e pelo uso de 
memória, embora este 
segundo não esteja sendo 
investigado em nossa 
disciplina. 
 C O custo matemático de 
tempo de execução de um 
algoritmo pode ser 
mensurado através da 
contagem de instruções 
em uma linguagem de alto 
nível. 
Você acertou! 
AULA 1 – TEMA 2. 
CORRETO. 
 D A função custo é dada em 
função do tamanho do 
conjunto de dados de 
entrada n, ou seja, em 
função da quantidade de 
instruções a serem 
executadas. 
n representa a quantidade 
de dados a serem 
manipulados, como por 
exemplo, um vetor de 
entrada de tamanho n. E 
não significa as instruções 
contadas. 
 E O custo de tempo de 
execução de um algoritmo 
corresponde a quantos 
núcleos paralelos o 
algoritmo está sendo 
executado. 
Tempo de execução 
significa o quão rápido um 
algoritmo executa para 
resolver um problema. Não 
tendo relação com o 
paralelismo. 
 
 
Questão 4/10 - Estrutura de Dados 
Uma função que implementa parte do algoritmo merge sort pode ser vista abaixo. Todo o resto 
do algoritmo foi omitido para que analisemos somente este método. O algoritmo completo pode 
ser visto no material PDF da Aula 2. 
No código, inicio e fim são variáveis inteiras que correspondem a posições no vetor de dados, 
parteinteira significa truncar em zero casas decimais o respectivo cálculo da linha 6 e intercala 
refere-se a uma função que realiza a ordenação neste método. 
 
1. Função mergesort(X, inicio, fim) 
2. Var 
3. Meio: inteiro 
4. Inicio 
5. Se (inicio < fim) então 
6. Meio <- parteinteira((inicio + fim) / 2) 
7. mergesort(X, inicio, meio) 
8. mergesort(X, meio + 1, fim) 
9. Intercala(X, inicio, fim, meio) 
10. Fimse 
11. funfunção 
 
A assumindo que a dimensão do vetor de dados X é 10, e que a primeira chamada da função 
mergesort foi realizada com os seguintes parâmetros: Função mergesort(X, 0, 9). 
Acerca deste algoritmo, assinale a alternativa INCORRETA: 
Nota: 10.0 
 A Na segunda instância 
aberta da função mergesort 
na memória do programa, a 
variável inicio vale zero e a 
variável meio vale 2. 
 B Na primeira instância aberta 
da função mergesort na 
memória do programa, a 
variável meio corresponde 
ao valor 4. 
 C Na segunda instância 
aberta da função 
mergesort na memória do 
programa, a variável inicio 
vale zero e a variável fim 
vale 2. 
Você acertou! 
Fim vale 4. 
 D Na terceira instância aberta 
da função mergesort na 
memória do programa, a 
variável inicio vale zero e a 
variável fim vale 2. 
 E Na primeira instância aberta 
da função mergesort na 
memória do programa, a 
variável inicio vale zero e a 
variável fim vale 9. 
 
 
Questão 5/10 - Estrutura de Dados 
Uma implementação do algoritmo de ordenação do tipo bubble sort pode ser visto abaixo. As 
partes que envolvem impressão de dados na tela e leitura de dados foram omitidas para um 
melhor entendimento do que é necessário na questão. 
 
 X[TAMANHOVETOR], i, j, aux: inteiro 
 para i de 1 até TAMANHOVETOR faça 
 para j de 0 até (TAMANHOVETOR - 2) faça 
 se (X[j] > X[j + 1]) então 
 aux <- X[j] 
 X[j] <- X[j + 1] 
 X[j + 1] <- aux 
 fimse 
 fimpara 
 fimpara 
Acerca deste algoritmo, assinale a alternativa CORRETA: 
 
Nota: 10.0 
 A O algoritmo apresentado no 
exercício realizado a 
ordenação de dados 
numéricos, inteiros, em 
ordem decrescente. 
Ordenação é crescente. 
 B As linhas de código que 
correspondem a troca dos 
valores usando uma 
variável auxiliar poderiam 
ser também escritas da 
seguinte maneira: 
aux <- X[j+1] 
X[j+1] <- X[j] 
X[j] <- aux 
Você acertou! 
AULA 2 – TEMA 2. 
CORRETO. 
 C Se precisarmos ordenar 
dados não numéricos, como 
caracteres, precisaremos 
repensar em toda a lógica 
do bubble sort, não sendo 
possível adaptar o código 
facilmente. 
Basta adaptarmos a linha 
da condicional para 
funcionar com outro tipo de 
dado. 
 D Não é possível implementar 
o bubble sort com laços de 
repetição do tipo enquanto. 
É possível implementar com 
qualquer tipo de laço, para, 
enquanto ou repita. 
 E A complexidade deste 
algoritmo, para o pior caso, 
é O(logn). 
Complexidade O(n²). 
 
 
Questão 6/10 - Estruturade Dados 
No último tópico da AULA 2 vimos algoritmos de busca. 
Acerca de algoritmos de busca sequencial e binária, assinale a alternativa INCORRETA: 
Nota: 10.0 
 A Uma busca binária pode 
ser implementada 
utilizando o princípio de 
dividir para conquistar, e 
portanto, complexidade 
O(n²). 
Você acertou! 
O(logn) 
 B A busca binária só 
funcionará com um vetor de 
dados já ordenado. 
Portanto, além de sua 
complexidade, existe a 
complexidade atrelada a 
uma possível ordenação 
prévia dos dados. 
 C O algoritmo de busca 
sequencial pode ser 
implementado com um só 
laço de repetição, 
caracterizando O(n). 
 D A busca sequencial poderá 
funcionar com um conjunto 
de dados ordenação ou não 
ordenado. 
 E A busca binária realiza seu 
algoritmo de localização do 
dado dividindo o conjunto 
de dados ao meio, e 
comparando o valor central 
com o buscado. 
 
 
Questão 7/10 - Estrutura de Dados 
Uma função que implementa parte do algoritmo quick sort pode ser vista abaixo. Todo o resto do 
algoritmo foi omitido para que analisemos somente este método. O algoritmo completo pode ser 
visto no material PDF da Aula 2. 
No código, a função chamada de particao refere-se à função que localiza um pivô no vetor de 
dados e faz as respectivas trocas dos valores, ordenando seguindo algum critério. 
No código, vet é o vetor de dados, e troca é a função que realiza uma troca entre dois valores 
destoantes utilizando uma variável auxiliar. 
 
1. int particao(int vet[], int p, int u) 
2. { 
3. int pivo, pivo_pos, i, j; 
4. pivo_pos = (p + u) / 2; 
5. pivo = vet[pivo_pos]; 
6. 
7. i = p - 1; 
8. j = u + 1; 
9. while (i < j) 
10. { 
11. do 
12. { 
13. j--; 
14. } while (vet[j] > pivo); 
15. 
16. do 
17. { 
18. i++; 
19. } while (vet[i] < pivo); 
20. 
21. if (i < j) 
22. troca(vet, i, j); 
23. } 
24. return j; 
25. } 
Acerca deste algoritmo, assinale a alternativa INCORRETA: 
Nota: 10.0 
 A A variável pivo_pos localiza 
a posição a qual conterá o 
valor de referência para 
comparações com todos os 
outros valores do vetor. 
 B Na linha 11 até a linha 14 
comparamos o pivô com 
todos os valores ao lado 
direito do mesmo. Caso um 
valor seja menor que o pivô, 
ele deve ser colocado para 
uma posição anterior a do 
pivô, ou no máximo, no local 
do pivô. 
 C Na linha 16 até a linha 19 
comparamos o pivô com 
todos os valores ao lado 
esquerdo do mesmo. Caso 
um valor seja maior que o 
pivô, ele deve ser colocado 
para uma posição posterior 
a do pivô, ou no máximo, no 
local do pivô. 
 D A troca (linha 21 e 22) pode 
acontecer entre um valor do 
lado esquerdo e do lado 
direito, ou entre o próprio 
pivô e um dos valores 
destoantes de cada um dos 
lados. 
 E Na linha 4 acessamos a 
posição do pivô no vetor e 
na linha 5 acessamos a 
posição correspondente 
do vetor conforme 
calculado na linha 4. 
Você acertou! 
Primeiro localizamos a 
posição (linha 4) e depois o 
valor daquela posição (linha 
5). 
 
 
Questão 8/10 - Estrutura de Dados 
Assuma um vetor de dimensão 10 com dados numéricos e inteiros colocados na seguinte 
ordem: 
 
| 05 | 07 | 08 | 14 | 24 | 29 | 56 | 77 | 78 | 88 | 
Suponha que você deseja implementar um algoritmo de busca para localizar algum dado neste 
vetor já ordenado de maneira crescente. Você resolve testar a busca sequencial e a busca 
binária. 
Acerca destes algoritmos e analisando o vetor acima, assinale a alternativa CORRETA: 
Nota: 10.0 
 A No algoritmo de busca 
sequencial, o valor 24 seria 
localizado na 6ª tentativa, 
se fizermos uma varredura 
da esquerda para a direita. 
Na 5ª tentativa. 
 B No algoritmo de busca 
binária, o valor 24 seria 
localizado na 3ª tentativa. 
Na 1ª tentativa. 
 C No algoritmo de busca 
sequencial, o valor 77 seria 
localizado mais rapidamente 
que se comparado com a 
busca binária. 
Binária se sairia mais 
rápida. 
 D No algoritmo de busca 
sequencial, o valor 07 
seria localizado mais 
rapidamente que se 
comparado com a busca 
binária. 
Você acertou! 
CORRETO. Levará menos 
iterações. 
 E Em nenhum cenário de 
busca o algoritmo 
sequencial irá localizar o 
valor antes da busca 
binária. 
É possível que sim, a 
sequencial ache antes. 
Dependerá o valor buscado 
e onde ele se localizado no 
vetor. 
 
 
Questão 9/10 - Estrutura de Dados 
O algoritmo de ordenação por intercalação, também conhecido como merge sort, é um dos 
algoritmos estudados na AULA 2. 
Acerca deste algoritmo, assinale a alternativa CORRETA. 
Nota: 10.0 
 A A complexidade do merge 
sort é O(logn), pois o 
algoritmo trabalha com o 
princípio de dividir para 
conquistar. 
O(n.logn), pois temos duas 
funções. 
 B O processo do merge sort 
consiste em dividir uma 
estrutura de dados de 
tamanho n (um vetor por 
exemplo) em 4 partes e 
ordenar estar partes, 
agregando-as 
posteriormente. 
O processo do merge sort 
consiste em dividir uma 
estrutura de dados de 
tamanho n (um vetor por 
exemplo) em n partes de 
tamanho unitário. 
 C Ao dividir o conjunto de 
dado em duas partes 
menores, o merge sort 
sempre calcula a posição 
central da ruptura, que é 
dada pela média entre os 
valores posição inicial com 
a posição final, 
arredondando para cima. 
É feito um truncamento 
somente da parte inteira. 
 D A intercalação é realizada 
utilizando um vetor 
auxiliar para ir 
armazenando os dados 
que vão sendo ordenados 
naquele momento. 
Você acertou! 
AULA 2 – TEMA 3. Figura 
10. 
 E A função merge sort pode 
ser implementada de forma 
recursiva, ou seja, 
realizando chamadas de si 
mesma até que o conjunto 
de dados seja indivisível. A 
ordenação só ocorre 
quando as partes menores 
forem agregadas 
novamente. 
A ordenação ocorre nas 
partes menores e 
indivisíveis. 
 
 
Questão 10/10 - Estrutura de Dados 
O segundo assunto de nossa disciplina diz respeito a algoritmos de ordenação de dados. 
Acerca deste assunto, assinale a alternativa INCORRETA: 
Nota: 0.0 
 A Algoritmos de ordenação 
são empregados com o 
objetivo de ordenar 
conjuntos de dados a partir 
de uma determinada 
métrica, como por exemplo, 
ordenar nomes de pessoas 
em ordem alfabética 
crescente. 
 B Existem os mais diversos 
algoritmos de ordenação, 
sendo que cada um deles 
apresentará uma 
complexidade distinta em 
tempo de execução e de 
uso de memória e, portanto, 
devem ser minuciosamente 
escolhidos de acordo com a 
aplicação. 
 C A permuta de grandes 
quantidades de dados para 
ordenação tende a ser 
custoso 
computacionalmente. O uso 
de variáveis ponteiros 
servem para auxiliar e 
otimizar este processo 
ordenando somente os 
endereços ao invés de todo 
o conjunto de dados. 
 D Um algoritmo de ordenação 
é um método que descreve 
como é possível colocar, em 
uma ordem específica, um 
conjunto de dados qualquer. 
 E A lógica algorítmica de 
cada método de 
ordenação difere para 
cada tipo de estrutura de 
dados que se deseja 
manipular. 
AULA 2 – TEMA 1. A 
estrutura de dados não 
muda a lógica de 
funcionamento do algoritmo 
de ordenação, só muda a 
estrutura a ser manipulada.