Estrutura de Dados APOL 1

Prévia do material em texto

Questão 1/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 2/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 3/10 - Estrutura de Dados 
Filas apresentam características de inserção e remoção na estrutura de dados seguindo a regra do primeiro que entra é o 
primeiro que sai. Observe o código da fila abaixo construída utilizando listas encadeadas. O código realiza a inserção de um 
novo elemento nesta fila. 
 
1. NovoElemento->dado = numero 
2. se (Head == NULO) então 
3. Head = NovoElemento 
4. Senão 
5. ElementoVarredura = Head 
6. enquanto (ElementoVarredura->prox <> NULO) 
7. ElementoVarredura = ElementoVarredura->prox 
8. Fimenquanto 
9. ElementoVarredura->prox = NovoElemento 
10. NovoElemento->prox = NULO 
11. Fimse 
Considerando que NovoElemento é um novo elemento que será inserido nesta fila, ElementoVarredura é uma variável que 
servirá para localizar o local de inserção, Head é o elemento que está no início da fila, assinale a alternativa CORRETA 
acerca de filas implementadas com listas encadeadas: 
Nota: 10.0 
 
A O último elemento da lista encadeada deverá conter um ponteiro nulo, conforme indicado na linha 9. 
Na linha 10. 
 
B As linhas 6, 7 e 8 indicam nos dizem que, para realizar a inserção, precisamos varrer até localizarmos o último elemento, o qual não poderá conter um ponteiro nulo. 
O último conterá um ponteiro nulo. 
 
C Se o head estiver nulo, significa que podemos inserir um elemento após o head, mesmo que ele esteja nulo 
Head nulo significa inserir no local do próprio head. 
 
D A varredura pela posição de inserção inicia no primeiro elemento da lista, conforme indicado na linha 5. 
Você acertou! 
Correto. 
 
E Não seria possível substituir o laço de repetição enquanto por uma para-faça devido a condição de parada aplicada. 
É sempre possível substituir um laço de repetição por outro, basta fazer as devidas adaptações. 
 
Questão 4/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 5/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: 0.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. 
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 6/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 7/10 - Estrutura de Dados 
No terceiro assunto da disciplina estudamos a estrutura de dados do tipo lista encadeada. O código abaixo representa a 
inserção em uma lista encadeada. 
 
1. NovoElemento->dado = numero 
2. se (Head == NULO) então 
3. Head = NovoElemento 
4. Head->prox = NULO 
5. Senão 
6. NovoElemento->prox = Head 
7. Head = NovoElemento 
8. fimse 
Considerando que NovoElemento é um novo elemento que será inserido nesta lista e Head caracteriza o primeiro elemento 
da lista. Assinale a alternativa CORRETA sobre este algoritmo. 
Nota: 10.0 
 
A O algoritmo apresentado representa uma inserção no final de uma lista encadeada simples, pois um laço faz a varredura até localizar o final da lista e insere o novo 
elemento. 
Não existe laço que varre até o final da lista. 
 
B O algoritmo apresentado representa uma inserção no início de uma lista encadeada dupla, pois a linha 6 mostra o novo elemento apontando para o Head. 
A lista não é do tipo simples. 
 
C O algoritmo apresentado representa uma inserção no início de uma lista encadeada simples, pois a linha 6 mostra o novo elemento apontando para o Head. 
Você acertou! 
CORRETO – AULA 3 – TEMA 2. 
 
D O algoritmo apresentado representa uma inserção no final de uma lista encadeada dupla, pois um laço faz a varredura até localizar o final da lista e insere o novo 
elemento. 
Não existe laço que varre até o final da lista e alista é simples. 
 
E Baseado no algoritmo apresentado, podemos afirmar que este código pertence ao de uma lista encadeada simples e circular. 
Não podemos afirmar que a lista é circular, pois só saberemos caso víssemos o código de inserção no final da lista. 
 
Questão 8/10 - Estrutura de Dados 
No terceiro assunto da disciplina estudamos a estrutura de dados do tipo lista encadeada. O código abaixo representa a 
inserção em uma posição específica da lista encadeada simples. 
 
1. NovoElemento->dado = numero 
2. se (posicao == 0) então 
3. Head = NovoElemento 
4. Head->prox = NULO 
5. Senão 
6. ElementoVarredura = Head 
7. para i de 0 até posicao faça 
8. ElementoVarredura = ElementoVarredura->prox 
9. Fimpara 
10. ElementoAuxiliar = ElementoVarredura->prox 
11. ElementoVarredura->prox = NovoElemento 
12. NovoElemento->prox = ElementoAuxiliar 
13. Fimse 
Considerando que NovoElemento é um novo elemento que será inserido nesta lista, ElementoVarredura é uma variável que 
servirá para localizar o local de inserção, ElementoAuxiliar é uma variável temporária para auxiliar na inserção do dado, Head 
caracteriza o primeiro elemento da lista e prox é o ponteiro para o próximo elemento da lista. Assinale a alternativa 
INCORRETA sobre este algoritmo. 
Nota: 10.0 
 
A Nas linhas 7 a 9 temos o laço de repetição que localiza a posição em que o elemento será inserido. 
 
B Na linha 8, a variável ElementoVarredura salta de elemento em elemento da lista, sempre utilizando como referencia o ponteiro para o próximo elemento. 
 
C Nas linhas 10, 11 e 12 fazemos uma troca entre 2 valores da lista encadeada utilizando uma variável auxiliar. 
Você acertou! 
Errado, pois não temos uma troca, mas sim a inserção do novo elemento. 
 
D Na linha 10 uma variável auxiliar armazena temporariamente o elemento subsequente ao da posição desejada para inserção. 
 
E Na linha 12, o novo elemento, agora já inserido na respectiva posição da lista, aponta para o elemento armazenado na variável auxiliar, que corresponde ao elemento 
subsequente ao da posição inserida. 
 
Questão 9/10 - Estrutura de Dados 
No terceiro assunto de nossa disciplina estudamos uma nova estrutura de dados denominada de LISTA ENCADEADA. Um 
tipo de lista encadeada é a chamada de LISTA ENCADEADA DUPLA, ou LISTA DUPLAMENTE ENCADEADA. 
Acerca de listas encadeadas simples, assinale a alternativa CORRETA: 
Nota: 10.0 
 
A Uma lista encadeada dupla só permite a inserção no início desta lista. 
Permite em qualquer posição. 
 
B Uma lista encadeada dupla conterá, em cada elemento, dois ponteiros de endereços. Um endereço corresponderá ao primeiro elemento da lista e o outro endereço ao 
último elemento da lista. 
Um endereço é do elemento imediatamente subsequente e do anterior, e não do primeiro e último. 
 
C Uma lista encadeada dupla circular conterá em seu último elemento, o endereço do primeiro elemento da lista. E conterá no seu primeiro elemento, o endereço do último 
elemento da lista. Fechando dois círculos. 
Você acertou! 
CORRETO. 
 
D Os dados de uma lisa dupla podem ser acessados mais rapidamente que uma simples, devido ao emprego de um ponteiro a mais. 
Os ponteiros nada impactam no tempo de acesso da lista. 
 
E Uma lista encadeada dupla ocupa o dobro de memória do programa em relação a uma lista simples, pois precisa armazenar duas vezes os dados de cada elemento. 
O fato de existir um ponteiro a mais não impacta significativamente a ponto de dobra o uso de memória. 
 
Questão 10/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 localizadona 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.