APOL1 - ESTRUTURA DE DADOS - NOTA 100

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
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: 10.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.
Você acertou!
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 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: 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 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
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 nestevetor 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 7/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²).
Questão 8/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 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
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.