apol 1 estrutura de dados

Prévia do material em texto

Questão 1/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ê assinalou essa alternativa (D) 
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 2/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ê assinalou essa alternativa (D) 
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 3/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ê assinalou essa alternativa (D) 
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 4/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ê assinalou essa alternativa (B) 
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 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ê assinalou essa alternativa (C) 
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 
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 varreduraaté 
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ê assinalou essa alternativa (C) 
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 7/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ê assinalou essa alternativa (D) 
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 8/10 - Estrutura de Dados 
O algoritmo de ordenação por intercalação, também conhecido como merge sort, 
é um dos algoritmos estudados na AULA 2. 
Acerca deste algoritmo, assinale a alternativa CORRETA. 
Nota: 10.0 
 
A A complexidade do merge sort é O(logn), pois o algoritmo trabalha com o princípio de dividir para conquistar. 
O(n.logn), pois temos duas funções. 
 
B O processo do merge sort consiste em dividir uma estrutura de dados de tamanho n (um vetor por exemplo) em 4 partes e 
ordenar estar partes, agregando-as posteriormente. 
O processo do merge sort consiste em dividir uma estrutura de dados de tamanho n (um vetor por exemplo) em n partes de tamanho 
unitário. 
 
C Ao dividir o conjunto de dado em duas partes menores, o merge sort sempre calcula a posição central da ruptura, que é 
dada pela média entre os valores posição inicial com a posição final, arredondando para cima. 
É feito um truncamento somente da parte inteira. 
 
D A intercalação é realizada utilizando um vetor auxiliar para ir armazenando os dados que vão sendo ordenados naquele 
momento. 
Você assinalou essa alternativa (D) 
Você acertou! 
AULA 2 – TEMA 3. Figura 10. 
 
E A função merge sort pode ser implementada de forma recursiva, ou seja, realizando chamadas de si mesma até que o 
conjunto de dados seja indivisível. A ordenação só ocorre quando as partes menores forem agregadas novamente. 
A ordenação ocorre nas partes menores e indivisíveis. 
 
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ê assinalou essa alternativa (E) 
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 
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ê assinalou essa alternativa (B) 
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 umamaior.