Exercício do Conhecimento

Prévia do material em texto

22/03/2020 Exercício do Conhecimento
https://aula.fael.edu.br/mod/quiz/review.php?attempt=3496017&cmid=67936 1/9
Estrutura de DadosEstrutura de Dados
Atividade anterior Próxima atividade
Iniciado em
domingo, 22 Mar 2020, 11:41
Estado
Finalizada
Concluída em
domingo, 22 Mar 2020, 11:58
Tempo empregado
16 minutos 53 segundos
Avaliar
0,4 de um máximo de 1,0(40%)
https://aula.fael.edu.br/mod/folder/view.php?id=19551&forceview=1
https://aula.fael.edu.br/mod/quiz/view.php?id=63684&forceview=1
22/03/2020 Exercício do Conhecimento
https://aula.fael.edu.br/mod/quiz/review.php?attempt=3496017&cmid=67936 2/9
QuestãoQuestão 1
Incorreto
Uma função é denominada recursiva quando ela é chamada novamente dentro de seu
corpo. Implementações recursivas tendem a serem menos eficientes, porém facilitam
a codificação e seu entendimento.
CELES, W.; CERQUEIRA, R.; RANGEL, J. L. Introdução a estruturas de
dados. Rio de Janeiro, 2004 (adaptado)
Considere a função recursiva f(), a qual foi escrita em linguagem C:
Suponha que a função f() é acionada com os seguintes parâmetros de entrada:
f( {2,-6,8,-2,0,4}, 6);
Neste caso, o valor de retorno da função f() será:
Escolha uma:
Gabarito: A alternativa correta é 8. Esta questão exige o conhecimento
sobre recursividade e a escrita de funções recursivas. A função recursiva F recebe um
vetor como primeiro parâmetro, e o seu tamanho como segundo parâmetro. Se o tamanho
do vetor for igual a 1, o único elemento é retornado. Caso o vetor tenha mais que um
elemento, a função é chamada recursivamente para N-1 elementos e o resultado é
colocado em X. Então X é comparado com o último elemento do vetor e o maior dos dois é
retornado. Então, pela análise do algoritmo, ele retorna o maior elemento do vetor.
Portanto a resposta correta é o número 8 para o exemplo dado. Os conteúdos
necessários estão no capítulo 6 do livro texto, e nas videoaulas: Unidade 3, aula 2.
a.
00
b.
-6-6
c.
22
d.
22/03/2020 Exercício do Conhecimento
https://aula.fael.edu.br/mod/quiz/review.php?attempt=3496017&cmid=67936 3/9
Sua resposta está incorreta.
A resposta correta é:
88
.
-2-2
e.
88
22/03/2020 Exercício do Conhecimento
https://aula.fael.edu.br/mod/quiz/review.php?attempt=3496017&cmid=67936 4/9
QuestãoQuestão 2
Correto
“Seja X um vetor de inteiros, do qual os primeiros N elementos devem ser ordenados
de modo que X[i] < X[j], para 0 <= i < j < N. A ideia básica por trás desta classificação
é percorrer o vetor sequencialmente várias vezes. Cada passagem consiste em
comparar cada elemento no vetor com seu sucessor (X[i] com X[i+1]) e trocar os dois
elementos se eles não estiverem na ordem correta. Depois da primeira passagem, o
maior elemento estará na sua posição correta dentro do vetor e é retirado do
processo de ordenação. O processo é repetido diversas vezes até que reste apenas
um elemento”.
TENENBUAM, A. M. Estruturas de dados usando C. São Paulo, 1995 (adaptado)
De acordo com o exposto, o método descrito denomina-se:
Escolha uma:
A resposta correta é: Ordenação por Bolha..
Gabarito: A alternativa correta é a Ordenação por
Bolha. É mencionado 5 algoritmos de ordenação:
• Ordenação por Bolha: usa a ideia de percorrer o vetor diversas vezes, e a cada
passagem fazer flutuar para o topo o maior elemento da sequência. Essa movimentação
lembra a forma como as bolhas em um tanque de água procuram seu próprio nível, e
disso vem o nome do algoritmo.
• Ordenação por Seleção Direta: é um algoritmo baseado em se passar sempre o menor
valor do vetor para a primeira posição (ou o maior dependendo da ordem requerida),
depois o segundo menor valor para a segunda posição, e assim sucessivamente com os n
− 1 elementos restantes, até os últimos dois elementos.
• Ordenação por Inserção Direta: é um algoritmo de ordenação que, dado uma estrutura
(array, lista) constrói um vetor final fazendo-se uma inserção por vez, e mantendo a
coleção sempre ordenada.
• QuickSort: é um método de ordenação muito rápido e eficiente, inventado por C.A.R.
Hoare em 1960. O quicksort adota a estratégia de divisão e conquista. A estratégia
consiste em rearranjar as chaves de modo que as chaves "menores" precedam as chaves
"maiores". Em seguida o quicksort ordena as duas sublistas de chaves menores e maiores
recursivamente até que a lista completa se encontre ordenada.
• HeapSort: é um algoritmo de ordenação generalista, e faz parte da família de algoritmos
de ordenação por seleção. O heapsort utiliza uma estrutura de dados chamada “heap”,
para ordenar os elementos à medida que os insere na estrutura. Assim, ao final das
inserções, os elementos podem ser sucessivamente removidos da raiz da heap, na ordem
desejada, lembrando-se sempre de manter a propriedade de max-heap. A heap pode ser
representada como uma árvore (uma árvore binária com propriedades especiais) ou como
um vetor. De acordo com as definições apresentadas, o método descrito foi o da Bolha.
Os conteúdos necessários estão no capítulo 9 do livro texto.
a. Ordenação por Bolha.
b. Ordenação por Inserção Direta.
c. HeapSort.
d. Ordenação por Seleção Direta.
e. QuickSort.
22/03/2020 Exercício do Conhecimento
https://aula.fael.edu.br/mod/quiz/review.php?attempt=3496017&cmid=67936 5/9
QuestãoQuestão 3
Correto
Seja a seguinte árvore binária de busca: 
Tendo como base a árvore acima, e que não houve balanceamento na árvore após
as inserções, a única forma correta de estes números terem sido inseridos, do início
para o fim respectivamente, é:
Escolha uma:
A resposta correta é: 27, 33, 39, 11, 15, 21, 5, 1, 78 e 7..
a. 1, 7, 5, 21, 15, 11, 78, 39, 33 e 27.
Gabarito: A alternativa correta é 27, 33,
39, 11, 15, 21, 5, 1, 78 e 7. Existem várias sequencias diferentes de inserção que geram
esta árvore. Porém, como o enunciado afirma que não houve balanceamento, concluímos
que os elementos inseridos por primeiro devem estar mais no topo da árvore, enquanto
os elementos inseridos por último devem estar mais no fundo (próximo das folhas) da
mesma. A sequência de inserção 1, 5, 7, 11, 15, 21, 27, 33, 39 e 78 é incorreta, pois
como o 1 é filho do 5, ele não pode ter sido inserido por primeiro. Seguindo a mesma
lógica, a sequência 27, 11, 33, 1, 5, 7, 21, 15, 39 e 78 também é incorreta. E a sequência
1, 7, 5, 21, 15, 11, 78, 39, 33 e 27 também é incorreta. Como o 78 é filho do 39, isso
invalida a sequência 27, 1, 11, 78, 33, 15, 21, 39, 5 e 7. A única sequência válida é a 27,
33, 39, 11, 15, 21, 5, 1, 78 e 7, pois todos os nós pais vem antes dos seus nós filhos. Os
conteúdos necessários estão no capítulo 7 do livro texto, e nas videoaulas: Unidade 3,
aula 3; Unidade 3, aula 4; Unidade 4, aula 1; Unidade 4, aula 2.
b. 27, 33, 39, 11, 15, 21, 5, 1, 78 e 7.
c. 1, 5, 7, 11, 15, 21, 27, 33, 39 e 78.
d. 27, 11, 33, 1, 5, 7, 21, 15, 39 e 78.
e. 27, 1, 11, 78, 33, 15, 21, 39, 5 e 7.
22/03/2020 Exercício do Conhecimento
https://aula.fael.edu.br/mod/quiz/review.php?attempt=3496017&cmid=67936 6/9
QuestãoQuestão 4
Incorreto
Seja o seguinte trecho de código: 
Analisando o código fonte apresentado, pode-se concluir que:
Escolha uma:
a. A estrutura de dados representa uma Fila e a função Mostra imprime a string inserida
de forma invertida.
Gabarito: A alternativa correta é a estrutura de
dados representa uma Pilha e a função imprime mostra a string inserida de forma
invertida. Nesta questão, temos uma estrutura de dados linear que pode ser uma pilha,
uma fila ou uma lista, dependendo do comportamento das funções de inserção e
b. A estrutura de dados representa uma Pilha e a função Mostra imprime a string da
mesma forma que foi inserida.
22/03/2020 Exercício do Conhecimento
https://aula.fael.edu.br/mod/quiz/review.php?attempt=3496017&cmid=67936 7/9
A resposta correta é: A estrutura de dados representa uma Pilha e a função Mostra
imprime a string inserida de forma invertida..
remoção. A função insere é chamada colocando um elemento sempre no fim do
encadeamento. E na hora da remoção, o último elemento é inserido, mostrando um
comportamento de umapilha. Já a função mostra varre os nós do topo até a base,
mostrando a palavra inserida de forma invertida, pois o último caractere inserido fica no
topo, e a função de imprimir começa a mostrar pelo topo. Os conteúdos necessários estão
nos capítulos 2 e 3 do livro texto, e nas videoaulas: Unidade 1, aula 3; Unidade 1, aula 4.
c. A estrutura de dados não é de uma Pilha, nem de uma Fila.
d. A estrutura de dados representa uma Pilha e a função Mostra imprime a string inserida
de forma invertida.
e. A estrutura de dados representa uma Fila e a função Mostra imprime a string da
mesma forma que foi inserida.
22/03/2020 Exercício do Conhecimento
https://aula.fael.edu.br/mod/quiz/review.php?attempt=3496017&cmid=67936 8/9
QuestãoQuestão 5
Incorreto
A operação "percorre" tem como objetivo percorrer a árvore numa dada ordem,
enumerando os seus nós. Quando um nó é enumerado, diz-se que ele foi "visitado".
Existem três formas de se percorrer uma árvore binária:
Pré-ordem (ou profundidade): visita-se a raiz primeiro, depois se percorre a sub
árvore esquerda em pré-ordem e depois se percorre a sub árvore direita em pré-
ordem;
Ordem Simétrica ou in-ordem: percorre-se a sub árvore esquerda em ordem
simétrica, depois visita-se a raiz e por último se percorre a sub árvore direita em
ordem simétrica;
Pós-ordem: percorre-se a sub árvore esquerda em pós-ordem; depois se percorre a
sub árvore direita em pós-ordem e por último visita-se a raiz.
Podemos implementar o percurso de árvores binárias em C por meio de rotinas
recursivas que refletem as definições do percurso. Usamos a representação de nós
dinâmicos para árvores binárias.
A partir do contexto apresentado, é correto afirmar que as funções A, B e C
implementam, respectivamente:
Escolha uma:
22/03/2020 Exercício do Conhecimento
https://aula.fael.edu.br/mod/quiz/review.php?attempt=3496017&cmid=67936 9/9
A resposta correta é: os percursos pós-ordem, in-ordem e pré-ordem..
a. os percursos in-ordem, pós-ordem e pré-ordem.
Gabarito: A alternativa
correta é os percursos pós-ordem, in-ordem e pré-ordem. Existem três formas de se
percorrer uma árvore binária:
• Pré-ordem (ou profundidade): visita-se a raiz primeiro, depois se percorre a sub árvore
esquerda em pré-ordem e depois se percorre a sub árvore direita em pré-ordem;
• Ordem Simétrica ou in-ordem: percorre-se a sub árvore esquerda em ordem simétrica,
depois visita-se a raiz e por último se percorre a sub árvore direita em ordem simétrica;
• Pós-ordem: percorre-se a sub árvore esquerda em pós-ordem; depois se percorre a sub
árvore direita em pós-ordem e por último visita-se a raiz.
Podemos implementar o percurso de árvores binárias em C por meio de rotinas recursivas
que refletem as definições do percurso. Usamos a representação de nós dinâmicos para
árvores binárias.
De acordo com as definições apresentadas, a função A imprime o nó raiz após visitar as 2
sub arvores, representando um percurso “pós-ordem”.
Já a função B imprime o nó raiz após visitar a sub arvore esquerda e antes de visitar a
sub árvore direita, representando um percurso “in-ordem”.
A função C, como última opção, imprime o nó raiz antes visitar as 2 sub arvores,
representando um percurso “pré-ordem”.
Os conteúdos necessários estão nos capítulos 6 e 7 do livro texto, e nas videoaulas:
Unidade 3, aula 2; Unidade 3, aula 3; Unidade 3, aula 4; Unidade 4, aula 1; Unidade 4,
aula 2.
b. os percursos pré-ordem, in-ordem e pós-ordem.
c. os percursos pós-ordem, in-ordem e pré-ordem.
d. os percursos in-ordem, pré-ordem e pós-ordem.
e. os percursos pré-ordem, pós-ordem e in-ordem.