Gabarito estrutura de Dados -Presencial

Prévia do material em texto

11/10/2021 11:17 Aluno AVA
https://santacruz.portalava.com.br/aluno/prova-online/confirma-prova 2/14
PROVA DE DEPENDÊNCIA
Realize esta prova

PROVA ONLINE
Realize esta prova

PROVA PRESENCIAL
Prova Finalizada em 08/10/2021 19:43: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
Sobre as pilhas, listas e filas, assinale a alternativa correta.
a )
Criar uma interface que represente todas as coleções têm pouca utilidade, uma vez que ela praticamente só
permitiria iteração.
b )
Uma operação comum a todas essas coleções é que podem ser iteradas.
c )
O método isCheia está presente apenas nas coleções estáticas.
d )
É uma boa prática utilizar essas coleções por meio de sua implementação mais específica, deixando as interfaces
apenas como uma questão de código.
e )
O método buscaIndice poderia ser implementado como método padrão para todas as coleções por meio dos
iteradores.
Ver justificativa da resposta
Justificativa
Todas as classes (filas, listas e pilhas) podem ser limpas, permitem uma forma de adição sem parâmetros, possuem
os métodos isVazia e isCheia e podem ser iteradas. A criação de uma hierarquia de classes que agrupe as coleções
tem várias vantagens:
oPermite que recebamos qualquer coleção por parâmetro e, assim, permite interoperabilidade entre as estruturas.
Isso é particularmente interessante pois todas as coleções podem ser iteradas com iteradores;
oPermite a criação de vários métodos padrão;
oFacilita o estudo da biblioteca, uma vez que basta entender que todas as coleções possuem o grupo de métodos
isVazia, IsCheia, limpar, adicionar e o iterador, e assim, não será necessário reestudar seu propósito a cada nova
coleção conhecida.
O método buscaIndice não pode ser implementado como método padrão em todas as classes por causa da pilha.
Como definimos que sua operação busca índices do início ao fim da estrutura, seu comportamento na pilha seria
invertido. Isso é uma decisão de projeto. Algumas bibliotecas de coleções fornecem os métodos busca e
buscaReversa, em que uma ocorre na ordem natural da coleção e outra na ordem inversa.
https://santacruz.portalava.com.br/aluno/prova-online/UWZMblViUk9kYlhkeDhVLzBsVS9MYWE1YjFsOXlDRHNDWTgxWDVHMnkxbHdEcSs4bnhyZSthV3dxSkVtYXFHMlZ2bFFaTVdzSTVUSHQvZ1Z1bzUzN2dkRHJjaDdhK1lVTzMyUERzUkNjSzhGbm54b1djd09WWFRGaFVuaUxmNC9TUGc2WWRXUHI4QXcyMkx2WXRMak55TEJwM2hZaGJaOE52SWJVeVpHREM0VGQ2NE9JUExNZ2RFNkE4YzVoTSsxbTN3bnVqMGVvTlBZaUJMeUtkejBQeVZ1Ymh5QWM3M1RLeE95ZzNUV2NQUDdmOHdQbjFidXlnN2RaNWF6cjdHUk1DREk1NU0wc0VIR2d2STVTeTA3Z3lZTWF0eVlNWG5ObHZtTnlRQlB0am1zMk92NXQ2NkZTSlRoNXdLOUlOVXRSV0lNRHNhWTQwRkh6dERJMit0Qk5RPT0
https://santacruz.portalava.com.br/aluno/prova-online/aWNRdXBPSnU5UG9iTW82YXR5YytlT1FkbXJxcmRxMjNLUmZMZGFOdWRFL3ZkdUx2YklFd3dhT0ZyMGZMa3lvQnFCaGVoMWJ1dmwvYUtsUlI2MERtcDFQcXNvMGtjS2JzRkJwRDdxZWJYdXB1TjRSajZEdk9TTjBmSGNnMitMVmFXdHJpZVZCOEt4ZGdwLzZsNFlOUFgvaDZpSCswWUE3bTNheGtBTEtySDNRRmVLbVhKcXdHMTJEYXZhZ2JsZWROWnR4eS9OclZYQXUxdlM0NU94dklYVjlRcHNoUnBjMUVWVTlvZk1yd3M1UmRXVE5uRlMwLzJRWjc3blRnY3VIZy9RK3F1Umh4d2xZNXJLV3BYS2J4cXRsSU1JYmdLMWczRXNtR0oyNkhtRlUwYTZBTkVFYmk5N0xPU0tSY3o0ZVdMeVFFd0Yzb0hzdEFZY2ZKSjNNRTdDOVdvMUFBdUNMTFZsUWluUnpMRWRLdEVTVHZlUTVFT3Y5anVDdDJ6eFdQ
https://santacruz.portalava.com.br/aluno/prova-online/OTNvZElrNk1LeFFMU1NoRmtWZ2c5aTRyR0xsOGtZRW1GVDZ1bGFuSi9qOU1aQm16T1NDbjVULzlSMWhHY3JhTEZSSVFUN2czL1IrSmZ2aW5OcUxUMzV4NHNNUlhmNDhWZklDRm9mKzhyZjdsZDZydEk3U2prRkRRY1ZZLzF0WWM4d2pkZ2phL1Fobjd3WThVZVMzMEh2dHUwYjNLaHJCRTBHZGFBeXkrMldMWXJua0x0YlZ3MkVVaXJuMFVpcVNhV1MrM2ZzaGcwWm01WFphSlBROXo5RVZHMllkWkphTmk1Q2ovZlJ6a2dMeFZ0UElWME9OWS94eXNheml0ZTBXKzJJQzg4NGZyUVpYT0hRMVhnSGx4V3BYR0ptZFRHNi83dnptdVVVVzJmcElFR3lKeFVHTjJDZ2kxemYyeG1QdldvbzN4eUpDa05XNWJXOXhpcVZmRDd1Ymc4OERUNHRzMUgvd2E3Wktwc252empNTDFBQlJjbnUwTGZYWklmY0dR
https://santacruz.portalava.com.br/aluno/sala-de-aula
javascript:;
11/10/2021 11:17 Aluno AVA
https://santacruz.portalava.com.br/aluno/prova-online/confirma-prova 3/14
Por fim, lembre-se de que utilizar as coleções por meio das suas interfaces, no lugar das classes concretas, é
considerada uma boa prática, pois isso nos permite alterar a implementação das coleções livremente, sem afetar o
resto do sistema.
QUESTÃO 2
Observe o código a seguir e, então, assinale a alternativa que completa as lacunas.
a )
1. fim-inicio 2. p-1 3. p
b )
1. fim 2. p+1 3. p-1
c )
1. inicio+fim 2. p-1 3. p
d )
1. fim 2. p-1 3. p+1
e )
1. fim 2. fim 3. fim
Ver justificativa da resposta
Justificativa
O quick sort deve ser feito em três etapas:
1. Separar, de início até fim.
05:3805:38
javascript:;
11/10/2021 11:17 Aluno AVA
https://santacruz.portalava.com.br/aluno/prova-online/confirma-prova 4/14
2. Ordenar a lista da esquerda, sem o pivô, ou seja, de inicio até p-1.
3. Ordenar a lista da direita, após o pivô: de p+1 até fim.
QUESTÃO 3
Sobre os conceitos de tamanho e capacidade de uma lista, assinale a alternativa correta.
a )
Os índices válidos de uma lista variam de 0 até a capacidade da lista subtraída de um.
b )
Em uma lista dinâmica, o tamanho é irrelevante, já que ela nunca estará cheia.
c )
A variável tamanho da lista indica o índice do último elemento.
d )
O tamanho da lista é indicado pelo tamanho do vetor de dados (dados.length).
e )
A capacidade refere-se à quantidade máxima de elementos que podem ser inseridos na lista.
Ver justificativa da resposta
Justificativa
O tamanho refere-se à quantidade de elementos disponíveis na lista. Já a capacidade é a quantidade máxima de
elementos que podem ser inseridos na lista. Os índices válidos em uma lista estão no intervalo de 0 até o tamanho da
lista subtraído de um. As listas dinâmicas têm a capacidade limitada apenas pela memória e, por isso, seu tamanho é
um atributo relevante. 
03:1203:12
javascript:;
11/10/2021 11:17 Aluno AVA
https://santacruz.portalava.com.br/aluno/prova-online/confirma-prova 5/14
QUESTÃO 4
Com relação às operações na estrutura de dados fila, assinale a alternativa correta.
a )
Para verificar se a fila circular está vazia, basta verificar se o valor da variável topo é nulo.
b )
O overhead da fila estática é grande e possui 4 bytes para cada nó, mais 8 bytes do topo e da base.
c )
A limpeza de uma fila encadeada não tem custo de desalocação associado, pois basta definir o topo e a base para
null.
d )
A inserção em uma fila circular tem custo próximo de zero, pois não há alocações envolvidas no processo.
e )
A fila circular não é uma estrutura sequencial, visto que os dados não estão dispostos de maneira linear.
Ver justificativa da resposta
Justificativa
A fila circular é uma estrutura estática e sequencial. O "círculo" na memória é apenas um truque implementado com
os índices do vetor. Porém, os dados ainda estarão dispostos lado a lado em um vetor e podem ser desalocados ou
alocados com uma grande operação. Portanto, ela compartilha todas as características das estruturas sequenciais:
1. Tem overhead de apenas 2 bytes (os inteiros para o topo e a base), não utilizando estrutura de nós.
2. Não tem custo de desalocação associado na remoção, adição ou limpeza, pois a estrutura será
alocada/desalocada uma única vez.
A fila encadeada desalocará os nós. Lembre-se de que sempre que eles ficam sem referências, a desalocação é feita
pelo garbage collector, mesmo que um comando de desalocação não exista explicitamente no código.
03:1303:13
javascript:;
11/10/2021 11:17 Aluno AVA
https://santacruz.portalava.com.br/aluno/prova-online/confirma-prova 6/14
QUESTÃO 5
Analise a árvore a seguir e, depois, marque a alternativa correta.
a )
Uma ordem possível de inserção dos nós para a geração dessa árvore é: I, E, G, A, J, K, L.
b )
O sucessor do nó I é o nó J.
c )
A impressão dos nós em pré-ordem seria: A, G, E, K, J, L e I, nesta ordem.
d )
Caso a árvore fosse AVL, ela seria balanceada após a inserção do nó K, por meio de uma rotação à esquerda.
e )
A impressão dos nós em pós-ordem seria: I, E, A, G, L, J e K, nesta ordem.Ver justificativa da resposta
Justificativa
04:5304:53
javascript:;
11/10/2021 11:17 Aluno AVA
https://santacruz.portalava.com.br/aluno/prova-online/confirma-prova 7/14
QUESTÃO 6
Sobre a lista ordenada, assinale a alternativa correta.
a )
O primeiro passo para criar uma lista ordenada está na implementação da função quicksort.
b )
O valor do ponto de inserção é definido ao final da busca por -(fim+1), evitando ambiguidade caso ele seja 0.
c )
A estrutura de lista encadeada é mais eficiente para implementação de uma lista ordenada por conter nós.
d )
05:4005:40
11/10/2021 11:17 Aluno AVA
https://santacruz.portalava.com.br/aluno/prova-online/confirma-prova 8/14
Se o valor da busca não for encontrado, o ponto de inserção estará localizado na variável inicio.
e )
O método adicionarOrdenado pode ser usado em listas não ordenadas, embora seja menos eficiente.
Ver justificativa da resposta
Justificativa
A lista ordenada utiliza o processo de busca binária em cada elemento inserido, sendo esse o primeiro passo da
criação desse tipo de lista. Esse processo utiliza duas variáveis de controle, inicio e fim, que são atualizadas sempre
que o elemento central não for igual ao buscado. Ela faz isso localizando o elemento do meio. Essa característica
implica em acesso direito a posições determinadas da lista, o que não é possível em listas encadeadas, tornando-a
ineficiente nesse tipo de lista.
O processo termina quando o elemento for encontrado ou quando o valor de inicio for maior do que o de fim. No
último caso, a variável inicio estará posicionada no ponto de inserção, isto é, no local onde o elemento deve ser
inserido. Retornamos o valor de -(inicio+1), evitando ambiguidade caso inicio pare na posição 0 e garantindo que o
resultado da função de busca seja sempre negativo, caso o elemento não seja encontrado.
Observe que esse processo é totalmente inviável em listas não ordenadas, uma vez que não podemos inferir se um
elemento está antes ou depois do elemento central nessa caso.
QUESTÃO 7
Selecione a alternativa que contém apenas exemplos de memória de armazenamento volátil.
a )
Disco rígido e disco SSD.
b )
Memória RAM e disco rígido (HD).
c )
03:0103:01
javascript:;
11/10/2021 11:17 Aluno AVA
https://santacruz.portalava.com.br/aluno/prova-online/confirma-prova 9/14
Memória cache e memória SSD.
d )
Memória cache e memória RAM.
e )
Memória RAM e memória flash.
Ver justificativa da resposta
Justificativa
Uma característica da memória de armazenamento volátil é que a informação se perde quando o computador é
desligado, sendo exemplos apenas a memória cache e a memória RAM. Discos como o disco rígido e SSD não se
apagam. Mas cuidado: os pendrives nada mais são do que pentes de memória flash, que também não se apagam ao
ficar sem energia. 
QUESTÃO 8
Considerando a estrutura de dados pilha, qual é o que será impresso pelo código a seguir?
a )
A B E
b )
O código lança uma exceção devido ao underflow.
c )
01:4901:49
javascript:;
11/10/2021 11:17 Aluno AVA
https://santacruz.portalava.com.br/aluno/prova-online/confirma-prova 10/14
A B C
d )
C B E
e )
O código lança uma exceção devido ao overflow.
Ver justificativa da resposta
Justificativa
A pilha remove os elementos na ordem inversa da qual foram inseridos. Inicialmente, foram inseridos os elementos
A, B e C. Como são feitas duas remoções, o código inicia imprimindo C B. Sobra na pilha ainda o valor A. Em
seguida, são inseridos os valores D e E. Em uma nova remoção, o valor E é removido e impresso. A impressão
final, portanto, é C B E. Como a pilha nunca ficou vazia ou ultrapassou a quantidade de três elementos em seu
interior, nenhuma exceção é disparada.
QUESTÃO 9
Sobre a implementação da classe MapaHash, marque a alternativa correta.
a )
O mapa será considerado vazio se a lista de buckets estiver nula.
b )
A variável tamanho indica a quantidade de buckets presente no interior de um mapa.
c )
Ao ser criado de modo padrão, a lista buckets possui tamanho 16 e todas as suas posições nulas.
d )
O fator de carga indica a carga máxima a que um mapa pode ser submetido antes de realizar a operação de rehash.
03:3203:32
javascript:;
11/10/2021 11:17 Aluno AVA
https://santacruz.portalava.com.br/aluno/prova-online/confirma-prova 11/14
e )
A carga do mapa fica armazenada em uma variável no interior do mapa e, por padrão, tem o valor 0,75.
Ver justificativa da resposta
Justificativa
A implementação do MapaHash contém três variáveis em seu interior:
1.A lista de buckets: em que cada elemento contém uma lista encadeada da estrutura Mapa.Par. Por padrão, ela
possuirá 16 listas vazias.
2.A variável tamanho: indica a quantidade de elementos já inseridos no mapa. O mapa é considerado vazio sempre
que o tamanho for 0.
3.O fator de carga: índica a carga máxima a que o mapa pode ser submetido antes do rehash. Trata-se de uma
variável double inicializada cujo valor padrão é 0,75.
QUESTÃO 10
Analise a árvore binária de busca a seguir e, então, marque a alternativa correta.
a )
A árvore foi formada inserindo os nós na ordem: 12, 10, 14, 8, 3 e 5.
b )
A iteração em pós-ordem visitará os nós 3, 5, 8, 10, 12 e 14, nesta ordem.
c )
A altura do nó 12 é 2, visto que tem dois filhos.
d )
02:5402:54
javascript:;
11/10/2021 11:17 Aluno AVA
https://santacruz.portalava.com.br/aluno/prova-online/confirma-prova 12/14
A altura da árvore é 3, devido aos nós mais profundos estarem no terceiro nível.
e )
A iteração em pré-ordem visitará os nós 8, 3, 5, 12, 10 e 14, nesta ordem.
Ver justificativa da resposta
Justificativa
QUESTÃO 11
Considerando a estrutura de dados fila, o que é impresso pelo código a seguir?
a )
04:4304:43
javascript:;
11/10/2021 11:17 Aluno AVA
https://santacruz.portalava.com.br/aluno/prova-online/confirma-prova 13/14
O código lança uma exceção devido ao overflow.
b )
A B C
c )
C B E
d )
O código lança uma exceção devido ao underflow.
e )
A B E
Ver justificativa da resposta
Justificativa
A fila remove os elementos na ordem na qual foram inseridos. Inicialmente, foram inseridos os elementos A, B e C.
Como são feitas duas remoções, o código inicia imprimindo A B. Sobra, na pilha, o valor C ainda. Em seguida, são
inseridos os valores D e E. Em uma nova remoção, o valor C é removido e impresso. A impressão final, portanto, é
A B C. Como a fila nunca ficou vazia ou ultrapassou a quantidade de três elementos em seu interior, nenhuma
exceção é disparada. 
QUESTÃO 12
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 )
04:3004:30
javascript:;
11/10/2021 11:17 Aluno AVA
https://santacruz.portalava.com.br/aluno/prova-online/confirma-prova 14/14
 Voltar
A inserção na pilha encadeada tem custo próximo de zero, pois a estrutura do nó é muito pequena.
c )
Para verificar se uma pilha encadeada está cheia, basta testar se o topo é do tamanho do vetor de dados.
d )
A remoção na pilha retira todos os elementos da pilha e segue a ordem na qual os elementos foram inseridos.
e )
A operação de iteração permite remover todos os elementos da pilha de uma só vez.
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.
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.
03:4903:49
https://santacruz.portalava.com.br/aluno/prova-online/inicio
javascript:;