Estruturas de Dados

Prévia do material em texto

11/10/2021 19:35 Aluno AVA
https://santacruz.portalava.com.br/aluno/prova-online/confirma-prova 1/6
 Prova Online
Disciplina: 101578 - ESTRUTURAS DE DADOS
Abaixo estão as questões e as alternativas que você selecionou:
QUESTÃO 1
Sobre o bubble sort (algoritmo da bolha), selecione a alternativa correta.
a )
Esse algoritmo é diferente do quick sort, pois o bubble sort utiliza a estratégia de dividir para conquistar, em
vez de força bruta.
b )
Nesse algoritmo, o número de comparações e trocas é praticamente igual e elevado, o que o torna
praticamente inviável na prática.
c )
Por ter uma implementação simples, ele se torna um algoritmo bastante viável para a maioria das aplicações
práticas.
d )
.
e )
Tem um número de trocas igual ao número de comparações; portanto, é mais vantajoso quando o tamanho
dos dados é grande.
Ver justificativa da resposta
Justificativa
QUESTÃO 2
Sobre os métodos set e get, assinale a alternativa correta.
a )
Os métodos get das listas sequenciais (ListaEstatica e ListaVetor) tem implementações diferentes, uma vez
que a dinâmica deve considerar o crescimento da lista.
b )
As listas encadeadas não devem possuir método get e set, uma vez que o acesso direto a um nó não existe.
c )
Os métodos get e set, na lista encadeada, podem ter um alto custo, já que a lista sempre deve iterar até o
índice desejado.
d )
O método set pode causar o crescimento da lista sequencial dinâmica (ListaVetor), caso ele seja inserido após
o último elemento com a lista em sua capacidade máxima.
javascript:;
11/10/2021 19:35 Aluno AVA
https://santacruz.portalava.com.br/aluno/prova-online/confirma-prova 2/6
e )
O método get da lista estática tem um custo alto, pois envolve deslocar para a esquerda todos os elementos
excluídos.
Ver justificativa da resposta
Justificativa
Nas listas sequenciais, os métodos get e set simplesmente acessam o dado indicado no índice, diretamente no
vetor dados. Como o índice deve ser o de um elemento já presente na lista, não existe situação em que o
crescimento da lista ocorrerá e, portanto, ambas as implementações sequenciais serão iguais. Além disso, a
lista dinâmica (ListaVetor) nunca estará cheia.
Já na lista encadeada, os métodos precisam iterar até o elemento desejado, o que pode custar uma quantidade
de saltos igual a metade do tamanho da lista. Por isso mesmo, uma iteração sobre todos os elementos da lista
deve ser feita por meio de iteradores, e não de índices.
QUESTÃO 3
Sobre a estrutura árvore, assinale a alternativa correta.
a )
Nós que não possuem filhos são chamados de nós raiz. Um exemplo desse tipo de nó é o nó inicial da árvore.
b )
Uma estrutura de árvore possível, mas menos otimizada, conterá nós cíclicos, ou seja, apontando para
qualquer um de seus pais.
c )
Cada nó em uma árvore pode conter um conjunto de filhos, sendo que cada nó filho deve conter mais de um
pai.
d )
É utilizada para o armazenamento de dados de maneira hierárquica, em que um elemento possui elementos
subordinados.
e )
O sistema de pastas de um computador não é uma árvore, pois está organizado em pastas e arquivos em vez
de nós.
Ver justificativa da resposta
Justificativa
Árvores são utilizadas para armazenar dados hierárquicos e seguem algumas normas:
1. Os elementos da árvore são chamados de nós.
2. Um nó pode conter um conjunto de nós relacionados, denominados nós filhos.
3. Cada nó pode ter um único pai.
4. Nós não podem ser cíclicos, isto é, terem como filhos qualquer um de seus pais.
5. O nó principal, que dá origem à árvore, é chamado de nó raiz.
6. Nós que não possuem filhos são denominados nós folhas.
O exemplo mais clássico de árvore é a estrutura de pastas e arquivos, em que cada pasta ou arquivo
representa um nó da estrutura.
QUESTÃO 4
Sobre as classificações das estruturas com relação a seus limites de dados e sua disposição dos elementos na
memória, é correto afirmar que:
javascript:;
javascript:;
11/10/2021 19:35 Aluno AVA
https://santacruz.portalava.com.br/aluno/prova-online/confirma-prova 3/6
a )
estruturas dinâmicas não disparam o erro de underflow, uma vez que não possuem limite de elementos na
memória.
b )
estruturas estáticas possuem uma quantidade fixa de dados que conseguem suportar, geralmente definida
durante sua criação.
c )
o custo de limpeza em uma pilha estática é maior do que o custo em uma pilha dinâmica.
d )
uma estrutura sequencial cheia terá um overhead maior do que uma estrutura encadeada cheia.
e )
uma estrutura estática de grande capacidade com poucos elementos consumirá menos memória do que uma
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
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.
QUESTÃO 5
Sobre o processo de adição em uma lista duplamente encadeada, marque a alternativa correta.
a )
A adição no topo da lista tem custo alto, uma vez que envolverá um grande volume de movimentação de
dados.
b )
A adição no meio da lista tem custo próximo de 0, já que não envolve o deslocamento de elementos para
direita.
c )
A busca do nó a ser adicionado tem um custo de processamento linear, sendo o custo máximo igual ao
tamanho total da lista.
d )
Se for uma adição ao fim da lista, a variável anterior do nó será inicialmente atribuída ao topo.
e )
Em uma inserção no índice 4, o nó proximo será definido localizando o nó de número 5.
javascript:;
11/10/2021 19:35 Aluno AVA
https://santacruz.portalava.com.br/aluno/prova-online/confirma-prova 4/6
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
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 a lista ordenada, assinale a alternativa correta.
a )
O método adicionarOrdenado pode ser usado em listas não ordenadas, embora seja menos eficiente.
b )
A estrutura de lista encadeada é mais eficiente para implementação de uma lista ordenada por conter nós.
c )
O valor do ponto de inserção é definido ao final da busca por -(fim+1), evitando ambiguidade caso ele seja 0.
d )
Se o valor da busca não for encontrado, o pontode inserção estará localizado na variável inicio.
e )
O primeiro passo para criar uma lista ordenada está na implementação da função quicksort.
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
Considere a lista a seguir.
javascript:;
javascript:;
11/10/2021 19:35 Aluno AVA
https://santacruz.portalava.com.br/aluno/prova-online/confirma-prova 5/6
Depois de ser feito o processo de média dos três e uma iteração do algoritmo de separação de Lomuto, como
ficariam dispostos os elementos da lista?
a )
-9, -6, -1, 0, 6, 2, 10
b )
-6, -9, -1, 0, 2, 10, 6
c )
-6, -1, -9, 0, 6, 10, 2
d )
-6, -9, -1, 6, 10, 0, 2
e )
-9, -6, 6, 0, 2, -1, 10
Ver justificativa da resposta
Justificativa
Em seguida, o algoritmo de Lomuto rodará. A seguir, vemos sua execução passo a passo. Em destaque, está o
ponto de inserção do menor elemento e, sombreado em cinza, estão os elementos em suas posições finais. Já
as comparações mostram o elemento sendo processado a cada passo.
QUESTÃO 8
Sobre a implementação da função hashCode, assinale a alternativa correta.
a )
Não pode ser utilizado em tabelas hash, já que o seu resultado pode ser qualquer número inteiro.
b )
A variável result deve ser inicializada por um número primo qualquer.
c )
Combina valores entre campos utilizando-se de um número primo constante.
d )
Nunca retorna números negativos, já que não há qualquer condição que os utilize.
javascript:;
11/10/2021 19:35 Aluno AVA
https://santacruz.portalava.com.br/aluno/prova-online/confirma-prova 6/6
e )
Deve utilizar todos os campos presentes no método equals.
Ver justificativa da resposta
javascript:;