ESTRUTURAS DE DADOS -Online

Prévia do material em texto

19/09/21, 20:28 Aluno AVA
Prova Online
Disciplina: 101578 - ESTRUTURAS DE DADOS
Abaixo estão as questões e as alternativas que você selecionou:
QUESTÃO 1
O quick sort utiliza a estratégia "dividir para conquistar". Em relação a esse algoritmo, assinale a alternativa correta.
a )
Ao separar a lista, elementos menores que o pivô devem ser colocados à sua esquerda, enquanto os maiores, à direita, na ordem em que aparecem.
b )
Um bom algoritmo para a escolha de um pivô perfeitamente balanceado é tirar a média de todos os elementos da lista.
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 )
Na lista encadeada, o ideal é trabalhar com outras listas independentes, copiando dados de uma lista para outra.
e )
Esse algoritmo se torna inviável para listas encadeadas, uma vez que ele cria e remove muitos nós, ao trabalhar com sublistas.
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:;
19/09/21, 20:28 Aluno AVA
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 2
Sobre as interfaces Iterable e Iterator, disponibilizadas pelo Java, marque a alternativa correta.
a )
A interface Iterator deve ser implementada em todas as classes interessadas em iteração. Exemplo: public class Lista implements Iterator.
b )
O método remove elimina da lista o próximo elemento a ser iterado com o comando next.
c )
Quando o iterador é criado, ele é posicionado no primeiro elemento da coleção, pois este será retornado na primeira chamada a next.
d )
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.
e )
O método next retorna o elemento apontado pelo iterador e então avança para o próximo elemento da coleção.
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 3
Considere a lista a seguir.
javascript:;
19/09/21, 20:28 Aluno AVA
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 )
-9, -6, 6, 0, 2, -1, 10
c )
-6, -9, -1, 0, 2, 10, 6
d )
-6, -1, -9, 0, 6, 10, 2
e )
-6, -9, -1, 6, 10, 0, 2
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.
javascript:;
19/09/21, 20:28 Aluno AVA
QUESTÃO 4
Sobre o bubble sort (algoritmo da bolha), selecione a alternativa correta.
a )
.
b )
Tem um número de trocas igual ao número de comparações; portanto, é mais vantajoso quando o tamanho dos dados é grande.
c )
Por ter uma implementação simples, ele se torna um algoritmo bastante viável para a maioria das aplicações práticas.
d )
Esse algoritmo é diferente do quick sort, pois o bubble sort utiliza a estratégia de dividir para conquistar, em vez de força bruta.
e )
Nesse algoritmo, o número de comparações e trocas é praticamente igual e elevado, o que o torna praticamente inviável na prática.
Ver justificativa da resposta
Justificativa
javascript:;
19/09/21, 20:28 Aluno AVA
QUESTÃO 5
Observe o código a seguir e, então, assinale a alternativa que completa as lacunas.
a )
1. fim 2. fim 3. fim
b )
1. fim-inicio 2. p-1 3. p
c )
1. fim 2. p+1 3. p-1
d )
1. fim 2. p-1 3. p+1
e )
19/09/21, 20:28 Aluno AVA
1. inicio+fim 2. p-1 3. p
Ver justificativa da resposta
Justificativa
O quick sort deve ser feito em três etapas:
1. Separar, de início até fim.
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 6
Selecione a alternativa que contém apenas características de dispositivos de memória não volátil.
a )
Alto custo, acesso rápido e tamanho pequeno.
b )
Apaga-se ao desligar, baixo custo e alta disponibilidade.
c )
Próximo ao processador, acesso rápido e tamanho pequeno.
d )
Alto custo, acesso lento e tamanho pequeno.
e )
Baixo custo, acesso lento e memória em abundância.
Ver justificativa da resposta
javascript:;
javascript:;
19/09/21, 20:28 Aluno AVA
Justificativa
Os dispositivos não voláteis, também chamados de dispositivo de armazenamento, fornecem memória em abundância a um custo relativamente baixo, se comparado ao
custo da memória volátil. Porém, comparado às alternativas voláteis, seu acesso também é lento e, por isso, são usados como memória secundária. São exemplos: HDs,
disquetes, DVDs e pendrives. 
QUESTÃO 7
Considerando a estrutura de dados pilha, qual é o que será impresso pelo código a seguir?
a )
O código lança uma exceção devido ao underflow.
b )
A B C
c )
A B E
d )
C B E
e )
O código lança uma exceção devido ao overflow.
Ver justificativa da resposta
Justificativa
javascript:;
19/09/21, 20:28 Aluno AVA
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 8
Quanto às árvores binárias de busca, assinale a alternativa correta.
a )
A disposição dos nós na árvore dependerá da ordem de inserção de seus elementos.
b )
São chamadas de binárias porque os valores em seus nós só podem conter os dígitos zero (0) e um (1).
c )
Cada nó pode ter apenas dois elementos: o nó pai e o nó filho.
d )
A busca binária é utilizada para realizar a localização de um nó dentro da árvore.
e )
A melhor disposição possível da árvore binária é obtida ao inserir nós de maneira ordenada.
Ver justificativa da resposta
javascript:;