Exercício do Conhecimento

Prévia do material em texto

Estrutura de Dados
Atividade anterior Próxima atividade
Iniciado em terça, 2 Jun 2020, 19:22
Estado Finalizada
Concluída em terça, 2 Jun 2020, 19:40
Tempo
empregado
18 minutos 42 segundos
Avaliar 0,8 de um máximo de 1,0(80%)



0.
1.
2.
3.
https://aula.fael.edu.br/mod/folder/view.php?id=19551&forceview=1
https://aula.fael.edu.br/mod/page/view.php?id=69656&forceview=1
https://aula.fael.edu.br/course/view.php?id=3450
javascript:void(0)
javascript:void(0)
javascript:void(0)
javascript:void(0)
Questão 1
Correto
“Dada uma lista de números em um arquivo de entrada, queremos imprimi-los em ordem
crescente. Ao lermos os números, eles podem ser inseridos em uma estrutura de dados”.
TENENBUAM, A. M. Estruturas de dados usando C. São Paulo, 1995 (adaptado)
I- Com base nas informações apresentadas, avalie as asserções a seguir e a relação
proposta entre elas.
Uma árvore binária de busca é a estrutura de dados favorável para representar esta
situação.
PORQUE
II- Uma árvore binária de busca é uma estrutura de dados de árvore binária baseada em
nós, onde todos os nós da sub árvore esquerda possuem um valor ordenável inferior ao nó
raiz e todos os nós da sub árvore direita possuem um valor ordenável superior ao nó raiz.
Então, ao percorrer essa árvore usando in-ordem conseguimos mostrar os elementos em
ordem crescente.
A respeito dessas asserções, assinale a opção correta:
Escolha uma:
a. A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
Gabarito: A alternativa correta é as asserções I e II são proposições verdadeiras, e a II é uma
justi�cativa correta da I. Uma árvore binária de busca (ou árvore binária de pesquisa) é uma estrutura
de dados de árvore binária baseada em nós, onde todos os nós da subárvore esquerda possuem um
valor numérico inferior ao nó raiz e todos os nós da subárvore direita possuem um valor superior ao
nó raiz (esta é a forma padrão, podendo as subárvores serem invertidas, dependendo da aplicação).
O objetivo desta árvore é estruturar os dados de forma a permitir busca binária. Quando temos
busca binária, precisamos dos dados “ordenados” para que ela surta o efeito esperado. Como os
números a serem retirados do arquivo precisam ser mostrados em ordem crescente podemos
utilizar uma árvore binária de busca para armazená-los. Portanto, a asserção I é verdadeira. Já a
b. As asserções I e II são proposições verdadeiras, e a II é uma justi�cativa correta da I.




0.
1.
2.
3.
https://aula.fael.edu.br/course/view.php?id=3450
javascript:void(0)
javascript:void(0)
javascript:void(0)
javascript:void(0)
A resposta correta é: As asserções I e II são proposições verdadeiras, e a II é uma justi�cativa
correta da I..
asserção II também é verdadeira, e é uma justi�cativa válida da asserção I. 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.
c. A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
d. As asserções I e II são proposições falsas.
e. As asserções I e II são proposições verdadeiras, mas a II não é uma justi�cativa correta da
I.



0.
1.
2.
3.
https://aula.fael.edu.br/course/view.php?id=3450
javascript:void(0)
javascript:void(0)
javascript:void(0)
javascript:void(0)
Questão 2
Correto
“Torre de Hanói é um jogo que consiste em uma base contendo três pinos, em um dos
quais são dispostos alguns discos uns sobre os outros, em ordem crescente de diâmetro, de
cima para baixo. O problema consiste em passar todos os discos de um pino para outro
qualquer, usando um dos pinos como auxiliar, de maneira que um disco maior nunca �que
em cima de outro menor em nenhuma situação. O número de discos pode variar sendo que
o mais simples contém apenas três”.
Disponível em <https://pt.wikipedia.org/wiki/Torre_de_Hanoi>;
Acesso em 04 de dezembro de 2019
Com base nas informações apresentadas, avalie as asserções a seguir e a relação proposta
entre elas.
I- Uma pilha é a estrutura de dados favorável para programar estes pinos do jogo.
PORQUE
II- Uma pilha é uma estrutura de dados que permite a inserção de elementos por uma
extremidade e a remoção pela extremidade oposta.
A respeito dessas asserções, assinale a opção correta:
Escolha uma:
a. A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
b. As asserções I e II são proposições verdadeiras, e a II é uma justi�cativa correta da I.
c. As asserções I e II são proposições verdadeiras, mas a II não é uma justi�cativa correta da
I.
d. As asserções I e II são proposições falsas.
e. A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.



0.
1.
2.
3.
https://pt.wikipedia.org/wiki/Torre_de_Hanoi%3E
https://aula.fael.edu.br/course/view.php?id=3450
javascript:void(0)
javascript:void(0)
javascript:void(0)
javascript:void(0)
A resposta correta é: A asserção I é uma proposição verdadeira, e a II é uma proposição falsa..
Gabarito: A alternativa correta é a asserção I é uma proposição verdadeira, e a II é uma
proposição falsa. Nesta questão é explorada a relação entre pilhas e �las e a aplicação delas na
construção do jogo “torre de Hanoi”. Uma pilha (em inglês: stack) é uma estrutura de dados baseada
no princípio de Last In First Out (LIFO), ou seja, "o último que entra é o primeiro que sai",
caracterizando um empilhamento de dados. Pilhas são fundamentalmente compostas por duas
operações: push (empilhar) que adiciona um elemento no topo da pilha e pop (desempilhar) que
remove o último elemento adicionado. Uma �la (em inglês: queue) é uma estrutura de dados
baseada no princípio de First In First Out (FIFO), ou seja, "o primeiro que entra é o primeiro que sai"
ou "primeiro a chegar, primeiro a ser servido". Filas são fundamentalmente compostas por duas
operações: insert (en�leirar) que adiciona um elemento no �m da �la e remove (desen�leirar) que
remove o primeiro elemento adicionado. Como a Torre de Hanoi possui 3 pinos que funcionam como
“pilhas”, a asserção I é verdadeira. Já a asserção II é falsa, pois quem permite a inserção de elementos
por uma extremidade e a remoção pela extremidade oposta é a “�la” e não a pilha. Os conteúdos
necessários estão nos capítulos 1, 2 e 3 do livro texto, e nas videoaulas 1, 2, 3 e 4 da Unidade 1.




0.
1.
2.
3.
https://aula.fael.edu.br/course/view.php?id=3450
javascript:void(0)
javascript:void(0)
javascript:void(0)
javascript:void(0)
Questão 3
Correto
Seja o seguinte trecho de código: 
Analisando o código fonte apresentado, pode-se concluir que:



0.
1.
2.
3.
https://aula.fael.edu.br/course/view.php?id=3450
javascript:void(0)
javascript:void(0)
javascript:void(0)
javascript:void(0)
Escolha uma:
A resposta correta é: A estrutura de dados representa uma Pilha e a função Mostra imprime a
string inserida de forma invertida..
a. A estrutura de dados representa uma Fila e a função Mostra imprime a string inserida de
forma invertida.
b. A estrutura de dados representa uma Pilha e a função Mostra imprime a string da mesma
forma que foi inserida.
c. A estrutura de dados representa uma Fila e a função Mostra imprime a string da mesma
forma que foi inserida.
d. A estrutura de dados não é de uma Pilha, nem de uma Fila.
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 �la ou uma lista, dependendo do comportamento das funções de inserção
e remoção. A função insere é chamada colocando um elemento sempre no �m do encadeamento. E
na hora da remoção, o último elemento é inserido, mostrando um comportamento de uma pilha. 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 �ca 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 nasvideoaulas: Unidade 1, aula 3;
Unidade 1, aula 4.
e. A estrutura de dados representa uma Pilha e a função Mostra imprime a string inserida de
forma invertida.




0.
1.
2.
3.
https://aula.fael.edu.br/course/view.php?id=3450
javascript:void(0)
javascript:void(0)
javascript:void(0)
javascript:void(0)
Questão 4
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 classi�caçã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. QuickSort.
b. HeapSort.
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
�utuar 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 �nal 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 e�ciente, 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
c. Ordenação por Bolha.




0.
1.
2.
3.
https://aula.fael.edu.br/course/view.php?id=3450
javascript:void(0)
javascript:void(0)
javascript:void(0)
javascript:void(0)
A resposta correta é: Ordenação por Bolha..
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 �nal 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 de�nições apresentadas, o
método descrito foi o da Bolha. Os conteúdos necessários estão no capítulo 9 do livro texto.
d. Ordenação por Inserção Direta.
e. Ordenação por Seleção Direta.



0.
1.
2.
3.
https://aula.fael.edu.br/course/view.php?id=3450
javascript:void(0)
javascript:void(0)
javascript:void(0)
javascript:void(0)
Questão 5
Incorreto
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 �m
respectivamente, é:
Escolha uma:
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 a�rma 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 é �lho
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 é �lho 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
b. 1, 5, 7, 11, 15, 21, 27, 33, 39 e 78.




0.
1.
2.
3.
https://aula.fael.edu.br/course/view.php?id=3450
javascript:void(0)
javascript:void(0)
javascript:void(0)
javascript:void(0)
A resposta correta é: 27, 33, 39, 11, 15, 21, 5, 1, 78 e 7..
�lhos. 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.
c. 27, 11, 33, 1, 5, 7, 21, 15, 39 e 78.
d. 27, 1, 11, 78, 33, 15, 21, 39, 5 e 7.
e. 27, 33, 39, 11, 15, 21, 5, 1, 78 e 7.



0.
1.
2.
3.
https://aula.fael.edu.br/course/view.php?id=3450
javascript:void(0)
javascript:void(0)
javascript:void(0)
javascript:void(0)