Estrutura de Dados - Prova Substitutiva

Prévia do material em texto

04/11/2021 23:33 Aluno AVA
https://santacruz.portalava.com.br/aluno/prova-online/confirma-prova 1/12
Toggle navigation 
Olá, ADRIAN GABRIEL BUCK MACHADO
 Tira duvidas
 Sala de Aula
 Notas
 Sair

Olá, ADRIAN GABRIEL BUCK MACHADO
 Tira duvidas
 Sala de Aula
 Notas
 Sair
HOME 
 Sala de Aula
 Notas
ESTRUTURAS DE DADOS

Situação: 
CONCLUÍDO
1. Home
2. Meus cursos
3. Sala de Aula
4. ESTRUTURAS DE DADOS
Atividades relacionadas

PROVA DE DEPENDÊNCIA
 Prova Finalizada em 04/11/2021 23:33:16

 2
https://santacruz.portalava.com.br/
https://santacruz.portalava.com.br/aluno/tira-duvidas
https://santacruz.portalava.com.br/aluno/sala-de-aula
https://santacruz.portalava.com.br/aluno/notas
https://santacruz.portalava.com.br/logout
https://santacruz.portalava.com.br/aluno/tira-duvidas
https://santacruz.portalava.com.br/aluno/sala-de-aula
https://santacruz.portalava.com.br/aluno/notas
https://santacruz.portalava.com.br/logout
https://santacruz.portalava.com.br/aluno
https://santacruz.portalava.com.br/aluno/sala-de-aula
https://santacruz.portalava.com.br/aluno/notas
https://santacruz.portalava.com.br/
https://santacruz.portalava.com.br/aluno
https://santacruz.portalava.com.br/aluno/sala-de-aula
https://santacruz.portalava.com.br/aluno/prova-online/T1kyMk1MNlduNmFHb3VFNDhWNXNVb0VmOTM4YnFRM0pqZENrRHY3UE9ITEp2VUNYeDY4cjdESW9QWVNlaGJoNVhudGVwTTFEN0FaU2xzdE9WUWR2TGpOQzlqZk5LR0E5N1NGMCtta1hNTnc3SjEzMnpxY0laSlNPYmx3bU51cDNWRlZMUUQ3K2hCem40OFhUTjd0NXd3WG5BT09TYS9vVXYwc2J0dG9WNEU2Mm1FbExXM2szSlRlNDBhZkRoUmFnb3pFcmdrNDBnRkp3N1NPL1NvaGNLWURkRkFobGlFYjR4V0VUY2paeHJRV3o1aENsOWQwNm9aSXIrQ28xckMrMG00cFZoUGZVaWlCQk5wM2RSRHhCNndxNCtFZGZJd1lZOGNBVzVrdjdIU1BmYkQ4RGdDZUwrQ0NCZURPMnBHb0dDSEN2dGg0dy9WdDVDNC92V3ppOFRRPT0
https://santacruz.portalava.com.br/aluno/prova-online/cnJ4OGp1SWhEaHJGQklWVDRFWGJxZUd3bjVOa0ZmeEtLWWR5bUkvVEtJcDVNQUVpYzlKQ1dzZ2tjcVF3L0gzWEFWYmpGVHNTa1VndlU2T2hiSTBjWUg1eUpuMUdMZVZaRk8rVk9SbUZVUmRJMVR1ZFlpYXB2YjBTM1dMWDNsVk9vQ1JhaVhncldNam0zdHRzUHJJY2l2TE9GZFJYOHVUUXhGeHlvL1lNNGVCNXY0ellhbWhJVUhDN3hYbXdUdWwwN0Y1NHBzdmR1U0lTK3dDVlBaQ3c5a3FNZXZuU0ZhOEJhR2J5WE9UTm1kNjVCUFNKZHQ0SG84QVpxREhnck9hWFNwREF6RnNIeUR5SXpuVyt1NU01SE1ybUlWMDNNT05iem5jMTQvMkxlMXp6U0NlNlVic3BhUEtHRVd0R3VOT2UxNXAweDU5SkpPZk9ibFVtc2NOdzE0OTYrYitoSzB4ejFMK2xDTFVFeWdHRE9QNEpmaUxTMDhuNGRVSlJjelpC
04/11/2021 23:33 Aluno AVA
https://santacruz.portalava.com.br/aluno/prova-online/confirma-prova 2/12
PROVA ONLINE
Realize esta prova

PROVA PRESENCIAL
Prova Finalizada em 19/10/2021 21:59:25
 Voltar para videoaulas
 Prova Online Liberada com Senha
Disciplina: 101578 - ESTRUTURAS DE DADOS
Abaixo estão as questões e as alternativas que você selecionou:
QUESTÃO 1
Considerando a estrutura de dados pilha, o que será impresso pelo código a seguir?
a )
O código lança uma exceção devido ao overflow.
b )
O código imprime C B A e lança exceção por causa do underflow.
c )
A B C
d )
C B A
e )
C A B
Ver justificativa da resposta
Justificativa
Na pilha, os elementos são removidos na ordem inversa da qual foram inseridos. As três primeiras remoções,
portanto, imprimem C B A. Porém, a pilha, então, fica vazia e uma quarta remoção é feita. Assim, ela
disparará exceção por causa do underflow. Em uma pilha encadeada, não há exceção por overflow, visto que
ela pode ocupar toda a memória disponível. 
https://santacruz.portalava.com.br/aluno/prova-online/cnJ4OGp1SWhEaHJGQklWVDRFWGJxZUd3bjVOa0ZmeEtLWWR5bUkvVEtJcDVNQUVpYzlKQ1dzZ2tjcVF3L0gzWEFWYmpGVHNTa1VndlU2T2hiSTBjWUg1eUpuMUdMZVZaRk8rVk9SbUZVUmRJMVR1ZFlpYXB2YjBTM1dMWDNsVk9vQ1JhaVhncldNam0zdHRzUHJJY2l2TE9GZFJYOHVUUXhGeHlvL1lNNGVCNXY0ellhbWhJVUhDN3hYbXdUdWwwN0Y1NHBzdmR1U0lTK3dDVlBaQ3c5a3FNZXZuU0ZhOEJhR2J5WE9UTm1kNjVCUFNKZHQ0SG84QVpxREhnck9hWFNwREF6RnNIeUR5SXpuVyt1NU01SE1ybUlWMDNNT05iem5jMTQvMkxlMXp6U0NlNlVic3BhUEtHRVd0R3VOT2UxNXAweDU5SkpPZk9ibFVtc2NOdzE0OTYrYitoSzB4ejFMK2xDTFVFeWdHRE9QNEpmaUxTMDhuNGRVSlJjelpC
https://santacruz.portalava.com.br/aluno/prova-online/MjVydEJFcGt2eVhrS2lEOHgzM2hkU3JRK29RajMwYjFyR1F0bWMvWlhFTG1kQXR3encxQVlxbExIcTVhVmhqSmE3SXpiSVQxZUNQNU10OGpLbFdKRmZ5RzM0Zk9RdVY3YTNJOTllYkZ3VlNaQnVPNnlKY2lhZWZWRGcrSWlQeksweHVrYTdCTVNzY2lnbzdKUms5Sit5ZllocGJjanZJOENBNmNaNUVHbXJvTlhhR1FYS1VldmlCRlMrNElLTXdTSHZhUENHYU5ja0w1VVVyWWJwZkZQMlhqK1R4TmpEWVBvdDJRYmNoekFMNFhvbVdyUUpYQ1MzUG10ZXFlZWpRSkJOemdLSGtuaVIxc210STRWUUIwZTRzY015VlR3SFMvUWxQMEs2bTZOR04zMHArbEtsSUpyMFFTQko4UjAxUTV1dXhLZE52VjQwenhTdjdzNDlIR2dhN1BETXVGQ2dvd3NKMURKMnovRGJHelhJazZ0NzdYakZRb2xCVXBHWGhT
https://santacruz.portalava.com.br/aluno/sala-de-aula
javascript:;
04/11/2021 23:33 Aluno AVA
https://santacruz.portalava.com.br/aluno/prova-online/confirma-prova 3/12
QUESTÃO 2
Considere a lista a seguir, que será usada no processo de escolha do quick sort.
Agora, assinale a alternativa correta sobre o processo de escolha, considerando o processo de média dos três.
a )
O pivô terá valor 8.
b )
O pivô terá valor 20.
c )
O pivô terá valor 7.
d )
O pivô terá valor -8.
e )
O pivô terá valor 64.
Ver justificativa da resposta
Justificativa
O processo de média dos três é realizado da seguinte forma:
1. Obtém-se os elementos inicial (100), central (8) e final (20) da lista.
2. Ordena-se os três: 8, 20, 100.
3. Escolhe-se o elemento do meio, obtendo como resposta o valor 20.
Apesar do nome, não é feito um cálculo de média (100+20+8) / 3 = 42,8.
javascript:;
04/11/2021 23:33 Aluno AVA
https://santacruz.portalava.com.br/aluno/prova-online/confirma-prova 4/12
QUESTÃO 3
Sobre o bubble sort (algoritmo da bolha), selecione a alternativa correta.
a )
Nesse algoritmo, o número de comparações e trocas é praticamente igual e elevado, o que o torna
praticamente inviável na prática.
b )
Esse algoritmo é diferente do quick sort, pois o bubble sort utiliza a estratégia de dividir para conquistar, em
vez de força bruta.
c )
Tem um número de trocas igual ao número de comparações; portanto, é mais vantajoso quando o tamanho
dos dados é grande.
d )
Por ter uma implementação simples, ele se torna um algoritmo bastante viável para a maioria das aplicações
práticas.
e )
.
Ver justificativa da resposta
Justificativa
00:0000:00
javascript:;
04/11/2021 23:33 Aluno AVA
https://santacruz.portalava.com.br/aluno/prova-online/confirma-prova 5/12
QUESTÃO 4
Quanto às operações na estrutura de dados pilha, assinale a alternativa correta.
a )
A limpeza da pilha estática é feita alterando o valor do topo para -1 e removendo as referências dentro do
vetor dados.
b )
A operação de iteração permite remover todos os elementos da pilha de uma só vez.
c )
A remoção na pilha retira todos os elementos da pilha e segue a ordem na qual os elementos foram inseridos.
d )
A inserção na pilha encadeada tem custo próximo de zero, pois a estrutura do nó é muito pequena.
e )
Para verificar se uma pilha encadeada está cheia, basta testar se o topo é do tamanho do vetor de dados.
Ver justificativa da resposta
Justificativa
As operações possíveis para as todas as pilhas são:
Adicionar: insere o elemento no topo da pilha. Terá custo próximo de zero na pilha estática, uma vez que não
há novas alocações de memória. Porém, na encadeada, o custo será maior, já que essa pilha faz uma nova
alocação a cada novo elemento.
Remover: remove o elemento do topo da pilha, ou seja, na ordem inversa da qual foi inserido.
Limpeza: elimina todos os elementos da pilha. No caso da pilha estática, basta definirmos o valor do topo
para -1. Na pilha encadeada, toda memória será desalocada ao se definir o topo para nulo.
Verificar se está cheia: permite que testemos se a pilha atingiu sua capacidade máxima. No caso da pilha
estática, basta verificar se o topo atingiu a capacidade de dados. A pilha dinâmica (encadeada) nunca estará
cheia, pois seu limite é definido apenas pela memória do processo.
javascript:;
04/11/2021 23:33 Aluno AVA
https://santacruz.portalava.com.br/aluno/prova-online/confirma-prova 6/12
Verificar se está vazia: permite que testemos se a pilha não contém elementos.
Iteração: permite consultar os elementos da pilha em ordem sequencial, sem removê-los.QUESTÃO 5
Sobre o processo de adição em uma lista duplamente encadeada, marque a alternativa correta.
a )
A busca do nó a ser adicionado tem um custo de processamento linear, sendo o custo máximo igual ao
tamanho total da lista.
b )
Em uma inserção no índice 4, o nó proximo será definido localizando o nó de número 5.
c )
Se for uma adição ao fim da lista, a variável anterior do nó será inicialmente atribuída ao topo.
d )
A adição no topo da lista tem custo alto, uma vez que envolverá um grande volume de movimentação de
dados.
e )
A adição no meio da lista tem custo próximo de 0, já que não envolve o deslocamento de elementos para
direita.
Ver justificativa da resposta
Justificativa
O processo de adição na lista encadeada tem as seguintes características:
1.Inicialmente, localiza-se o nó a ser inserido. Esse processo tem um custo de processamento linear.
Entretanto, como a lista pode ser navegada em duas direções, seu custo máximo será sempre o de metade do
tamanho da lista, quando a adição é feita no meio da lista.
2.Se o nó estiver sendo inserido ao final da lista, o topo passará a ser seu anterior. Por isso, a variável
anterior será atribuída ao topo. Posteriormente, a variável próximo do nó topo será atribuída ao nó
adicionado. Então, a variável topo será atribuída ao novo nó e o tamanho adicionado em um. Um processo
00:0000:00
javascript:;
04/11/2021 23:33 Aluno AVA
https://santacruz.portalava.com.br/aluno/prova-online/confirma-prova 7/12
similar é feito na base. Por isso, adicionar nessas duas posições tem custo próximo de 0. O custo envolve
somente a alocação do novo nó, já que não há busca nessas posições.
3.Em uma adição no meio da lista, o nó que atualmente ocupa a posição desejada será colocado
posteriormente ao nó sendo inserido. Por isso, a variável próximo, no início do processo de inserção, será
definida para o nó de mesmo índice ao da posição de inserção.
QUESTÃO 6
Sobre o processo de localização do MapaHash, marque a alternativa correta.
a )
O método hashcode da chave retorna diretamente a posição do bucket.
b )
A operação lógica return hash & (buckets.length-1) é uma alternativa rápida para redução do hash em mapas
de qualquer tamanho.
c )
Caso um objeto não seja encontrado no mapa, não haverá qualquer informação sobre sua localização.
d )
A redução do hashcode pode ser feita por meio do operador de resto entre o número gerado e o tamanho do
vetor, seguido da remoção do sinal.
e )
A iteração é feita através do comando for each, uma vez que os iteradores do mapa estão implementados.
Ver justificativa da resposta
Justificativa
O processo de localização dentro do mapa é realizado da seguinte forma:
1.Calcula-se o código hash da chave, utilizando a função hashCode. O valor retornado é um número inteiro
qualquer e precisará ser reduzido para o intervalo do mapa;
2.Reduz-se o código. Apresentamos duas formas possíveis de se fazer isso: por meio do operador de resto
entre o número gerado e o tamanho do vetor, removendo-se o sinal; ou, para os casos em que o tamanho do
mapa é um múltiplo de 2, por meio da operação lógica hash & (buckets.length-1).
javascript:;
04/11/2021 23:33 Aluno AVA
https://santacruz.portalava.com.br/aluno/prova-online/confirma-prova 8/12
3.Localiza-se o bucket por meio do código calculado. Observe que essa informação sempre estará presente,
mesmo que não haja um objeto no mapa.
4.Busca-se a chave na lista encontrada. Utiliza-se, para isso, os iteradores diretamente, pois isso permite
remover o objeto encontrado caso necessário.
5.Constrói-se um objeto de Localização com os itens descritos acima.
QUESTÃO 7
Sobre as funções hash, marque a alternativa correta.
a )
Uma estratégia possível para uma boa função hash é utilizar números aleatórios, aumentando assim a
distribuição do resultado.
b )
A função hashcode deve gerar somente números positivos, pois não há índices negativos em um vetor, que
não poderiam ser acessados.
c )
Deve utilizar os campos presentes no método equals, podendo utilizar menos campos, mas não mais.
d )
Caso a função seja perfeitamente distribuída, não haverá colisões na tabela hash, garantindo máxima
eficiência.
e )
Para melhorar a distribuição, é importante que objetos de instâncias diferentes, mas considerados iguais,
retornem códigos hash diferentes.
Ver justificativa da resposta
Justificativa
A regra de ouro de uma função hash é que "os objetos considerados iguais devem retornar códigos iguais";
isto é, essa função deve retornar o mesmo número para dois objetos iguais. Assim, uma função hashCode
jamais poderá considerar mais campos do que os presentes no método equals, embora possa considerar
menos.
00:0000:00
javascript:;
04/11/2021 23:33 Aluno AVA
https://santacruz.portalava.com.br/aluno/prova-online/confirma-prova 9/12
Uma boa função tentará gerar uma boa distribuição de códigos, pois isso minimiza as chances de colisão de
códigos hash. Entretanto, por mais bem distribuída que seja a função, colisões numa tabela hash poderão
sempre ocorrer, pois esta comporta mais elementos do que seu número de buckets.
Note que a função hashcode permite que o hash gerado seja qualquer número inteiro. Isso inclui números
negativos ou números muito grandes. Por isso, realizamos o processo de redução do hashcode ajustando-o
para um intervalo desejado.
QUESTÃO 8
Sobre a implementação dos métodos presentes no MapaHash, assinale a alternativa correta.
a )
A função contem retorna falso caso se busque uma chave que está associada a nulo.
b )
Caso um valor já exista no mapa, o método adicionar não o inserirá no mapa e retornará falso.
c )
A função limpar elimina todos os elementos dentro do mapa, além de reduzir o tamanho da lista de buckets
para seu valor inicial.
d )
A operação de rehash criará uma nova lista de buckets, sendo obrigada a recalcular a posição de todos os
elementos no mapa.
e )
A função get dispara uma exceção caso a chave não esteja presente no mapa, e retorna nulo, caso ela esteja
associada a esse valor.
Ver justificativa da resposta
Justificativa
Listamos as operações do mapa:
oadicionar: insere um elemento no mapa. Caso haja um elemento já associado à chave, ele será substituído e
o valor antigo será retornado. Caso o fator de carga do mapa seja atingido após a adição, o método também
javascript:;
04/11/2021 23:33 Aluno AVA
https://santacruz.portalava.com.br/aluno/prova-online/confirma-prova 10/12
fará o rehash, criando uma lista de buckets maior e recalculando a posição de todos os elementos no mapa.
olimpar: remove todos os elementos no interior dos buckets. A quantidade de buckets não é alterada.
oget: retorna o elemento associado à chave ou nulo, caso não haja um elemento associado à chave.
ocontem: retorna true se há um valor associado à chave, incluindo o valor nulo.
QUESTÃO 9
A respeito dos conceitos de profundidade e altura, assinale a alternativa correta.
a )
A raiz de uma árvore tem profundidade zero.
b )
A altura da árvore é definida pela altura da folha mais distante da raiz.
c )
Dois nós de mesmo nível, isto é, filhos de um mesmo nó pai terão exatamente a mesma altura.
d )
Os conceitos de profundidade e altura não podem ser aplicados a árvores binárias de busca.
e )
A altura de um nó considera o menor caminho possível entre ele e a sua folha.
Ver justificativa da resposta
Justificativa
Relembrando os conceitos de profundidade e altura:
1. Profundidade: é a quantidade de nós entre o nó atual e a raiz, que tem profundidade zero.
2. Altura: é a quantidade de nós entre o nó sendo analisado e a folha, considerando o caminho mais longo
possível. A altura do nó raiz é considerada a altura da árvore, que é também igual à profundidade do nó mais
profundo.
Observe que nós em um mesmo nível podem ter alturas diferentes, uma vez que seus filhos podem ter
profundidades diferentes.
00:0000:00
javascript:;
04/11/2021 23:33 Aluno AVA
https://santacruz.portalava.com.br/aluno/prova-online/confirma-prova 11/12
QUESTÃO 10
Sobre as classificações das estruturas com relação a seus limitesde dados e sua disposição dos elementos na
memória, é correto afirmar que:
a )
uma estrutura sequencial cheia terá um overhead maior do que uma estrutura encadeada cheia.
b )
uma estrutura estática de grande capacidade com poucos elementos consumirá menos memória do que uma
dinâmica.
c )
estruturas estáticas possuem uma quantidade fixa de dados que conseguem suportar, geralmente definida
durante sua criação.
d )
estruturas dinâmicas não disparam o erro de underflow, uma vez que não possuem limite de elementos na
memória.
e )
o custo de limpeza em uma pilha estática é maior do que o custo em uma pilha dinâmica.
Ver justificativa da resposta
Justificativa
Quanto ao limite de dados, as estruturas podem ser classificadas de duas formas: 1) estáticas: possuem uma
quantidade fixa de dados que conseguem suportar, geralmente definida em sua criação; 2) dinâmicas:
possuem tamanho variável, com a quantidade de elementos geralmente limitado pela memória. Esta última
não dispara o erro de overflow, visto que nunca ficará cheia.
Já quanto à disposição dos dados, podem ser classificadas como: 1) sequenciais: os elementos estão lado a
lado; 2) encadeadas: os elementos ficam dispersos na memória.
As estruturas estáticas precisam alocar memória no momento de sua criação. Assim, seu custo em memória
sempre será total, mesmo que nenhum elemento seja inserido. Por outro lado, alocações e desalocações em
pilhas e filas estáticas têm custo próximo a 0. Quando se encontra cheia, seu overhead é muito pequeno (4
00:0000:00
javascript:;
04/11/2021 23:33 Aluno AVA
https://santacruz.portalava.com.br/aluno/prova-online/confirma-prova 12/12
 Voltar
bytes). Já as estruturas dinâmicas alocam memória à medida que são usadas, mas precisam de 4 bytes em
cada nó. Isso também tem a consequência de espalhar os elementos pela memória, além dos custos maiores
de alocação/desalocação.
https://santacruz.portalava.com.br/aluno/prova-online/inicio