PROVA ONLINE 101578 ESTRUTURA DE DADOS

Prévia do material em texto

Prova Online 
Disciplina: 101578 - ESTRUTURAS DE DADOS 
Abaixo estão as questões e as alternativas que você selecionou: 
QUESTÃO 1 
Sobre as interfaces Iterable e Iterator, disponibilizadas pelo Java, marque 
a alternativa correta. 
 
 
a ) O método next retorna o elemento apontado pelo iterador e então avança para o 
próximo elemento da coleção. 
 
 
b ) Quando o iterador é criado, ele é posicionado no primeiro elemento da coleção, pois 
este será retornado na primeira chamada a next. 
 
 
c ) A interface Iterator deve ser implementada em todas as classes interessadas em 
iteração. Exemplo: public class Lista implements Iterator. 
 
 
d ) O método remove elimina da lista o próximo elemento a ser iterado com o comando 
next. 
 
 
e ) No método de remoção do iterador da listaEstatica, além do deslocamento para a 
esquerda, é necessário atualizar a variável atual do iterador. 
 
Ver justificativa da resposta 
Justificativa 
A interface Iterable deve ser implementada em todas as classes que permitem iteração. Sua 
única exigência é retornar um objeto do tipo Iterator, que percorrerá a coleção em si. O iterador 
inicialmente está posicionado antes do primeiro elemento da lista. O método hasNext() testa se 
há um próximo elemento a ser percorrido, e o método next() movimenta o iterador em uma 
posição e, posteriormente, retorna o elemento. Por fim, o método remove() remove o último 
elemento retornado pelo next. Na implementação do remove, temos que tomar o cuidado de 
voltar o iterador em uma posição, já que a exclusão provoca o deslocamento dos elementos. 
 
 
QUESTÃO 2 
A respeito do processo de busca binária, assinale a alternativa correta. 
 
 
a ) Uma das desvantagens desse processo é que ele só pode ser utilizado em listas com 
dados numéricos em ordenação ascendente. 
 
 
b ) Escolhe-se o elemento central da lista. Como a lista está ordenada, o elemento 
desejado só poderá estar à esquerda ou à direita dele, se não for ele mesmo. 
javascript:;
 
 
c ) Caso um elemento não seja encontrado, o marcador fim estará no ponto em que a 
inserção deve ser realizada. 
 
 
d ) Seu tempo de execução é linear, ou seja, caso o número de elementos da lista dobre, 
o número de comparações também dobrará. 
 
 
e ) O algoritmo é mais eficiente para listas encadeadas, visto que os nós podem ser 
acessados individualmente. 
 
Ver justificativa da resposta 
Justificativa 
A busca binária beneficia-se do fato de que, em uma lista ordenada, os elementos 
encontram-se dispostos de modo que podem ser divididos entre os menores que o central 
(com índices de inicio até central -1) e os maiores (de central+1 até fim). Isso permite que, 
a cada comparação feita, metade da lista seja descartada, bastando para isso atualizar os 
valores de inicio e fim, o que resulta em uma performance logarítmica - isto é, caso a lista 
dobrasse o número de elementos, apenas uma comparação a mais precisaria ser feita. 
O processo funciona para listas de qualquer tipo de dado, em ordem ascendente ou 
descendente, desde que um comparador adequado seja fornecido. Além disso, caso o 
elemento não seja encontrado, o marcador inicio será posicionado no ponto de inserção. 
Finalmente, é importante destacar que esse processo não é eficiente em listas 
encadeadas, visto que não é possível obter diretamente o elemento central. Nelas, 
usamos uma estrutura de dados conhecida como árvore binária. 
 
QUESTÃO 3 
Considere a lista a seguir. 
 
 
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 ) -6, -1, -9, 0, 6, 10, 2 
 
 
b ) -6, -9, -1, 6, 10, 0, 2 
 
 
c ) -9, -6, 6, 0, 2, -1, 10 
 
 
d ) -9, -6, -1, 0, 6, 2, 10 
 
 
javascript:;
e ) -6, -9, -1, 0, 2, 10, 6 
 
 
 
QUESTÃO 4 
Sobre vetores na linguagem Java, assinale a alternativa correta. 
 
 
a ) Vetores de objetos em Java se beneficiam especialmente do cache por manterem os 
dados lado a lado. 
 
 
b ) Cada índice de um vetor representa um endereço de memória único, sem qualquer 
relação com o de outros índices. 
 
 
c ) Após a alocação de um vetor de tipo primitivo, os dados ficarão dispersos na memória. 
 
 
d ) A memória de um vetor local de 50 inteiros será alocada em uma área contínua 
no heap. 
 
 
e ) Os dados de um vetor criados numa variável local, em Java, serão alocados no stack. 
 
Ver justificativa da resposta 
Justificativa 
No Java, os vetores são objetos e, portanto, suas variáveis locais serão referências para 
uma área de memória criada no heap, onde os dados serão armazenados. Vetores de 
tipos primitivos são alocados em uma área contínua de memória; e vetores de objetos 
alocam várias referências para objetos que ficarão dispersos pela memória, prejudicando o 
uso do cache. O número do índice de um vetor pode ser usado para calcular a posição de 
memória de qualquer dado em seu interior. 
 
 
 
 
javascript:;
QUESTÃO 5 
Marque a situação na qual uma pilha poderia ser usada. 
 
 
a )Ordenar elementos em ordem alfabética. 
 
 
b ) Implementar o recurso de voltar (CTRL+Z) em um aplicativo. 
 
 
c ) Agrupar elementos similares, de acordo com uma chave. 
 
 
d ) Criar uma lista de supermercado. 
 
 
e ) Criar uma aplicação que distribui senhas. 
 
Ver justificativa da resposta 
Justificativa 
As pilhas permitem a inclusão e a exclusão controladas em seu interior. Ambas sempre 
ocorrem no topo da estrutura, o que faz com que os elementos sejam removidos na ordem 
inversa da que foram inseridos. Por isso, ela é a estrutura perfeita para a implementação 
do recurso de voltar (CTRL+Z), mas é pouco útil para a implementação de listas em que os 
elementos precisam ser acessados em qualquer ordem (como a de supermercado) ou que 
exijam uma ordenação específica, como a ordem alfabética, ou mesmo, que possam ser 
acessados por uma chave. A distribuição de senhas é feita na ordem de chegada, 
portanto, é uma característica da estrutura de fila. 
QUESTÃO 6 
Sobre a implementação da classe MapaHash, marque a alternativa correta. 
 
 
a ) Ao ser criado de modo padrão, a lista buckets possui tamanho 16 e todas as suas 
posições nulas. 
 
 
b ) A carga do mapa fica armazenada em uma variável no interior do mapa e, por 
padrão, tem o valor 0,75. 
 
 
c ) O fator de carga indica a carga máxima a que um mapa pode ser submetido 
antes de realizar a operação de rehash. 
 
 
d ) O mapa será considerado vazio se a lista de buckets estiver nula. 
 
 
e ) A variável tamanho indica a quantidade de buckets presente no interior de um mapa. 
 
javascript:;
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 7 
O quick sort utiliza a estratégia "dividir para conquistar". Em relação a esse 
algoritmo, assinale a alternativa correta. 
 
 
a ) Na lista encadeada, o ideal é trabalhar com outras listas independentes, copiando 
dados de uma lista para outra. 
 
 
b ) Esse algoritmo se torna inviável para listas encadeadas, uma vez que ele cria e 
remove muitos nós, ao trabalhar com sublistas. 
 
 
c ) Em uma lista sequencial, que utiliza um vetor para armazenar seus elementos, a fase 
de conquistar desse algoritmo não realiza tarefa alguma. 
 
 
d )Um bom algoritmo para a escolha de um pivô perfeitamente balanceado é tirar a 
média de todos os elementos da lista. 
 
 
e )Ao separar a lista, elementos menores que o pivô devem ser colocados à sua 
esquerda, enquanto os maiores, à direita, na ordemem que aparecem. 
 
Ver justificativa da resposta 
Justificativa 
O algoritmo do quick sort ordena elementos de maneira recursiva, por meio dos seguintes 
passos: 
Escolher: define-se um pivô. Idealmente, esse pivô deveria ser igual à mediana da lista, 
mas, como seria computacionalmente inviável varrer a lista toda buscando a mediana 
perfeita, geralmente adota-se a estratégia de escolher o último elemento ou a mediana 
entre o primeiro, o último e o elemento do meio da lista (média dos três). 
Separar: gera-se de duas a três sublistas com elementos menores, iguais e maiores que o 
pivô (os elementos inferiores ou iguais ao pivô ficam à sua esquerda e os elementos 
maiores que o pivô, à sua direita), não importando sua ordem. No caso da lista sequencial, 
os elementos serão movidos e, portanto, as sublistas serão definidas apenas por intervalos 
de índices. No caso da lista encadeada, utilizam-se sublistas, tomando o cuidado apenas 
de movimentar nós, sem copiar dados. 
javascript:;
javascript:;
Conquistar: une-se as listas. No caso da lista sequencial, não é necessário fazer nada, 
uma vez que os elementos já estarão ordenados. No caso da lista encadeada, deve-se 
mesclar as sublistas. 
QUESTÃO 8 
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 busca do nó a ser adicionado tem um custo de processamento linear, sendo o custo 
máximo igual ao tamanho total da lista. 
 
 
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 meio da lista tem custo próximo de 0, já que não envolve o deslocamento 
de elementos para direita. 
 
 
e ) Em uma inserção no índice 4, o nó proximo será definido localizando o nó de número 
5. 
 
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. 
 
 
 
 
 
javascript:;