Apol 1 Estrutura de Dados 2020

Prévia do material em texto

SE AJUDOU DEIXE UMA CURTIDA 
 
Questão 1/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 2/10 - Estrutura de Dados 
No terceiro assunto de nossa disciplina estudamos estruturas de dados que se comportam como uma 
FILA. 
Acerca de FILAS, assinale a alternativa CORRETA: 
Nota: 10.0 
 
A Uma fila onde o primeiro elemento é o 66, o segundo é o 33 e o terceiro é o 99. Inserir na fila significaria inserir um elemento que aponte para o valor 66. 
Inseriria depois do valor 99 (inserção no final da fila). 
 
B Em uma fila, podemos ter a inserção dos dados início desta fila. 
Inserção somente no final. 
 
C Em uma fila, podemos ter a remoção dos dados final ou no meio desta fila. 
Remoção somente no início. 
 
D Em uma fila trabalhamos com o conceito de: “o primeiro que entra é o primeiro que sai”. 
Você acertou! 
Correto. FIFO. 
 
E Uma fila onde o primeiro elemento é o 66, o segundo é o 33 e o terceiro é o 99. Remover da fila significaria remover o elemento 99. 
Removeria o 66 (remoção no início da fila). 
 
Questão 3/10 - Estrutura de Dados 
No terceiro assunto de nossa disciplina estudamos uma nova estrutura de dados denominada de LISTA 
ENCADEADA. 
Acerca de listas encadeadas, assinale a alternativa CORRETA: 
Nota: 10.0 
 
A Uma lista encadeada trabalha com alocação sequencial na memória. De maneira similar a uma estrutura de dados do tipo vetor. 
Uma lista é não sequencial. 
 
B Uma lista encadeada trabalha com o conceito de índice. Ou seja, podemos acessar qualquer posição da lista usando o seu índice como referência. 
Não existe o conceito de índice em uma lista encadeada. 
 
C O acesso a qualquer dado em uma lista pode ser feito com a mesma eficiência em tempo de execução, caracterizando uma complexidade de acesso aos dados como O(1). 
Complexidade de acesso é O(n). 
 
D Podemos localizar o próximo elemento da lista encadeada através do uso de uma variável que armazena o endereço do próximo elemento da lista. 
Você acertou! 
CORRETO. Basta usar uma variável do tipo ponteiro. 
 
E Cada elemento de uma lista encadeada só poderá armazenar dados do tipo numérico. Não é permitido o uso de dados do tipo caractere ou lógico, por exemplo. 
Qualquer tipo de dados é permitido. 
 
Questão 4/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 5/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 6/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 7/10 - Estrutura de Dados 
No terceiro assunto de nossa disciplina estudamos uma nova estrutura de dadosdenominada 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: 10.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. 
Você acertou! 
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 8/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 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 
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 algoritmo contendo 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²).