Baixe o app para aproveitar ainda mais
Prévia do material em texto
ANTÔNIO FLAVIO RODRIGUES DE SOUSA - RU: 2867268 Nota: 40 PROTOCOLO: 2020030128672683122DB6 Disciplina(s): Estrutura de Dados Data de início: 03/03/2020 20:55 Prazo máximo entrega: - Data de entrega: 15/03/2020 17:50 Atenção. Este gabarito é para uso exclusivo do aluno e não deve ser publicado ou compartilhado em redes sociais ou grupo de mensagens. O seu compartilhamento infringe as políticas do Centro Universitário UNINTER e poderá implicar sanções disciplinares, com possibilidade de desligamento do quadro de alunos do Centro Universitário, bem como responder ações judiciais no âmbito cível e criminal. Questão 1/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 2/10 - Estrutura de Dados No terceiro assunto de nossa disciplina estudamos estruturas de dados que se comportam como uma PILHA. Acerca de PILHA, assinale a alternativa INCORRETA: Nota: 10.0 A Em uma pilha construída utilizando listas encadeadas. Desempilhar nela significa remover o primeiro elemento desta pilha. Sim. Remoção no topo. B Uma pilha pode só pode ser construída empregando uma estrutura de dados que trabalhe de maneira não sequencial. Você acertou! Podemos construir com vetores (sequencial) ou listas (não sequencial). C Uma pilha trabalha com inserção e remoção no topo da pilha. Sendo impossível manipular qualquer outra posição da pilha. Sim. Estrutura do tipo FILO. D Em uma pilha construída utilizando listas encadeadas. Empilhar nela significa inserir antes do primeiro elemento desta pilha. Sim. Inserção no topo. E Em uma, a cada nova inserção, os elementos anteriores vão ficando para o final da pilha, só sendo possível removê-los desempilhando. Sim. FILO. Questão 3/10 - Estrutura de Dados Pilhas apresentam características de inserção e remoção na estrutura de dados seguindo a regra do primeiro que entra é o último que sai. Observe o código da pilha abaixo construída utilizando listas encadeadas. O código realiza a inserção de um novo elemento nesta pilha. 1. NovoElemento->dado = numero 2. se (Top == NULO) então 3. NovoElemento->prox = NULO 4. Senão 5. NovoElemento->prox = Top 6. fimse 7. Top = NovoElemento Considerando que NovoElemento é um novo elemento que será inserido nesta pilha e top é o elemento que está no topo da pilha, assinale a alternativa CORRETA acerca de pilhas implementadas com listas encadeadas: Nota: 0.0 A A linha 2 verifica se o topo da pilha está vazio. Caso esteja vazio, significa que não é possível inserir um novo elemento na pilha. É possível inserir, e a inserção se dá no próprio topo. B Se tivermos um só elemento na pilha, significa que a lista não terá um topo. Terá um topo e será o próprio único elemento. C Caso o topo não esteja vazio, fazemos o elemento do topo apontar para o novo elemento. O novo elemento apontará para o topo. Linha 5. D Na linha 7, o topo da pilha vira o novo elemento inserida, fazendo com que o antigo topo seja apagado. O antigo topo não é apagado, pois na linha 5 fazemos o novo elemento apontar para ele. E O topo da pilha é o único elemento que fica armazenado em uma variável conhecida pelo programa. Todos os outros elementos são acessados a partir dos ponteiros de referencia de cada elemento. Correto. Como este código está implementado com listas encadeadas, armazenamos somente o primeiro elemento. Questão 4/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 5/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: 0.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 valoresutilizando uma variável auxiliar, da mesma maneira feita no bubble sort. 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 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 O segundo assunto de nossa disciplina diz respeito a algoritmos de ordenação de dados. Acerca deste assunto, assinale a alternativa INCORRETA: Nota: 10.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. Você acertou! 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. Questão 8/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: 0.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) 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 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 SIMPLES, ou LISTA SIMPLESMENTE ENCADEADA. Acerca de listas encadeadas simples, assinale a alternativa INCORRETA: Nota: 0.0 A Uma lista encadeada simples pode ser do tipo circular. Isto significa que o seu último elemento conterá um ponteiro não nulo e que apontará de volta para ele mesmo, fechando círculo. O último elemento aponta para o início da lista de volta, e não para ele mesmo. B Uma lista encadeada simples conterá, em cada seu elemento, uma variável do tipo ponteiro que manterá o endereço do próximo elemento da lista encadeada. C O uso de ponteiros serve para que, embora cada elemento da lista encadeada esteja disperso na memória do programa, eles possam ser localizados e conectados em uma estrutura de dados. D Uma lista encadeada simples pode ser do tipo não circular. Isto significa que o seu último elemento conterá um ponteiro nulo (vazio). E Podemos realizar uma inserção em qualquer posição de uma lista encadeada, no início, no fim ou mesmo no meio desta lista. Questão 10/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: 0.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. Fim vale 4. D Na terceirainstâ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.
Compartilhar