Apol 1 Estrutura de Dados

Prévia do material em texto

Questão 1/10 - Estrutura de Dados 
A recursividade é um recurso de programação bastante empregado, e consiste no ato de uma 
função em um código realizar chamadas de si mesmo, abrindo diferentes instâncias de uma 
mesma função na memória do programa. 
Acerca de recursividade e algoritmos recursivos, assinale a alternativa INCORRETA: 
Nota: 10.0 
 A Diversos problemas computacionais que poderiam ser resolvidos utilizando 
algoritmos iterativos, ou seja, laços de repetição, podem também ser resolvidos 
usando recursividade. 
 B Um algoritmo recursivo terá uma complexidade logarítmica, apresentando 
um desempenho inferior em tempo de execução superior a um algoritmo 
construído de forma iterativa. 
Você acertou! 
AULA 1 – TEMA 4. O desempenho em tempo de execução é superior. 
 C Uma possível desvantagem de um algoritmo recursivo é o seu uso de memória 
mais elevado, uma vez que diversas instâncias de uma mesma função precisam 
ser alocadas na memória. 
 D Um algoritmo que executa uma função denominada de soma, e que realiza a 
chamada de uma função denominada compara, não pode ser considerado um 
algoritmo recursivo, uma vez que não realizada chamadas de si mesma. 
 E Um algoritmo recursivo comumente serve para resolver problemas do tipo “dividir 
para conquistar”, onde dividimos um problema em partes menores e mais fáceis 
de solucionar, para posteriormente agregar as pequenas soluções em uma maior. 
 
 
Questão 2/10 - Estrutura de Dados 
No primeiro assunto de nossa disciplina investigamos o que são estruturas de dados e como 
podemos classificá-las em tipos. 
Acerca deste assunto, assinale a alternativa INCORRETA: 
Nota: 10.0 
 A Um dado que pode ser decomposto em partes mais simples, é considerado um 
dado estruturado e, portanto, uma estrutura de dados. 
 B Os tipos de dados manipulados por um algoritmo podem ser classificados em duas 
categorias distintas: os atômicos, que são dados indivisíveis, e os dados 
compostos, que podem ser divisíveis em mais partes menores. 
 C Podemos classificar uma estrutura de dados como sendo do tipo 
homogênea (como registros) ou do tipo heterogênea (como vetores e 
matrizes). 
Você acertou! 
AULA 1 – TEMA 1. Podemos classificar uma estrutura de dados como sendo do 
tipo heterogênea (como registros) ou do tipo homogênea (como vetores e 
matrizes). 
 D Uma estrutura homogênea é aquela cujo tipo dos dados nela armazenados são de 
um único tipo, como inteiro, real, caractere ou lógico 
 E Uma estrutura contendo dados do tipo caractere e do tipo real pode ser 
considerada uma estrutura de dados heterogênea. 
 
 
Questão 3/10 - Estrutura de 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 4/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 5/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 6/10 - Estrutura de Dados 
Chamamos de análise assintótica de algoritmos quando encontramos a complexidade de um 
algoritmo de maneira aproximada através de uma curva de tendência. Este tipo de análise e é a 
mais adotada para compararmos desempenho de algoritmos. 
Acerca da análise assintótica de um algoritmo, assinale a alternativa INCORRETA: 
Nota: 10.0 
 A Um algoritmo com três laços de repetição não encadeados contém uma 
complexidade assintótica, para o pior caso, O(n). 
 B Na análise assintótica, fazemos o conjunto de dados de entrada da função custo 
tender ao infinito, mantendo na equação somente o termo de maior grau, ou seja, 
aquele que mais cresce na equação. 
 C Um algoritmo com três laços de repetição aninhados contém uma complexidade 
assintótica, para o pior caso, O(n³). 
 D A complexidade assintótica para o pior caso, também conhecida como BigO, 
representa o pior cenário para um algoritmo, ou seja, quando mais instruções 
precisam ser executadas, levando mais tempo para finalizar a execução. 
 E A complexidade assintótica para o pior caso de um algoritmocontendo dois 
laços de repetição aninhados, sendo que o segundo laço só será executado 
caso uma condicional simples seja verdadeira, será O(n). 
Você acertou! 
AULA 1 – TEMA 3. O pior caso (BigO) nos diz que todas as linhas devem ser 
executadas, ou seja, a condicional será sempre verdadeira, e ambos laços de 
repetição serão sempre executados, sendo assim, complexidade O(n²). 
 
 
Questão 7/10 - Estrutura de Dados 
O algoritmo abaixo foi desenvolvido empregando uma lógica iterativa: 
Função Calcula (n: inteiro, x: inteiro): inteiro 
 y: inteiro 
 para i de 0 até n faça 
 se (x < 0) então 
 para i de 0 até n faça 
 y = y + 1 
 fimpara 
 senão 
 para i de 0 até x faça 
 y = y + 1 
 fimpara 
 fimse 
 fimpara 
 retorne y 
Fimfunção 
Acerca ao algoritmo acima, e trabalhando com os conceitos de complexidade assintótica e 
recursividade, assinale a alternativa CORRETA: 
Nota: 10.0 
 A A função contém três laços de repetição, sendo que todos os três laços podem 
acabar sendo executados cada vez que esta função por chamada. 
Como o valor de x recebido como parâmetro nunca muda dentro da mesma 
chamada da função, teremos somente 2 laços sendo executados por vez devido a 
condicional composta. 
 B A complexidade da função, para o pior caso será O(n³). 
Como temos somente 2 laços aninhados, a complexidade será O(n²). 
 C A função não realiza chamadas de si mesma, portanto pode ser considerada uma 
função recursiva. 
Uma função recursiva é a que realizada chamadas de si mesma. 
 D Caso exista a possibilidade de implementação deste algoritmo usando uma 
função recursiva, e sem uso de laços de repetição, a complexidade em 
tempo de execução da implementação irá melhorar. 
Você acertou! 
AULA 1 – TEMA 3, 4 E 5. Sim, pois implementando com recursividade teremos 
uma complexidade atrelada a um crescimento logarítmico. 
 E Caso substituíssemos todos os laços de repetição do tipo para, por laços do tipo 
enquanto, o desempenho do algoritmo em tempo de execução irá melhorar 
significativamente, uma vez que o laço enquanto tem um custo inferior ao do para. 
O custo de todos os três tipos de laços de repetição é o mesmo na análise de 
complexidade e, virtualmente não faz diferença qual você utiliza. 
 
 
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 
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 10/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²).