PROVA ESTRUTURAS DE DADOS 1

Prévia do material em texto

QUESTÃO 1 
Qual destas estruturas permite agrupar diferentes tipos de dados em 
uma estrutura mais complexa na linguagem Java? 
 
a ) Método. 
b ) Classe. 
c ) Vetor. 
d ) Referência. 
e ) Variável de tipo primitivo. 
 
Ver justificativa da resposta: 
 
A classe permite agrupar diferentes tipos de dado em um único tipo, criado pelo 
programador, na linguagem Java. Os vetores permitem agrupar apenas dados de mesmo 
tipo. As variáveis de tipo primitivo, tais como int, char e boolean, apenas armazenam 
valores simples. 
Embora apontem para classes e objetos, as referências em si apenas representam o local 
onde eles estão na memória (não confunda os dois conceitos). Por fim, os métodos são 
trechos do programa, não estruturas para armazenar dados, e representam ações que um 
objeto é capaz de executar. 
 
QUESTÃO 2 
Sobre as áreas de memória de um processo, assinale a alternativa 
correta. 
 
a ) A pilha é uma área de memória organizada, na qual criações e remoções de variáveis 
locais ocorrem rapidamente. 
 
b ) São áreas de memória de um processo: pilha, heap e garbage collector. 
 
c ) Uma das vantagens da pilha é que ela representa toda área de memória disponível no 
sistema. 
 
d ) As variáveis locais são automaticamente destruídas, pois são colocadas no heap. 
 
e ) O heap é uma área de memória organizada, em que alocações e desalocações 
ocorrem rapidamente. 
 
Ver justificativa da resposta: 
 
Um processo contém três áreas de memória: pilha, heap e read-only. A pilha é uma área 
de memória organizada, em que criações e remoções (alocações e desalocações) 
ocorrem de maneira rápida e automática. É nela que variáveis locais são criadas. Porém, a 
pilha tem espaço pequeno, variando de sistema operacional para sistema operacional. O 
heap representa toda a memória do sistema. Nele, a memória é criada e destruída 
manualmente, por meio dos comandos delete e free. 
 
 
 
QUESTÃO 3 
Sobre a estrutura árvore, assinale a alternativa correta. 
 
a ) O sistema de pastas de um computador não é uma árvore, pois está organizado em 
pastas e arquivos em vez de nós. 
 
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 ) É utilizada para o armazenamento de dados de maneira hierárquica, em que um 
elemento possui elementos subordinados. 
 
d ) 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. 
 
e ) Cada nó em uma árvore pode conter um conjunto de filhos, sendo que cada nó filho 
deve conter mais de um pai. 
 
Ver justificativa da resposta: 
 
Á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 estruturas mapa e conjunto, assinale a alternativa correta. 
 
a ) Os conjuntos representam coleções de objetos sem repetição, contendo uma interface 
muito mais simples que a dos mapas. 
 
 
b ) É possível adicionar várias vezes o valor nulo dentro dos conjuntos, pois ele 
representa a ausência de um objeto. 
 
c ) É possível acessar um elemento de um conjunto por índice, uma vez que cada 
elemento é uma chave. 
 
d ) Como conjuntos são implementados por meio de mapas, sua interface também não 
poderá herdar de Colecao. 
 
e ) O método getTamanho do mapa retornará o dobro do valor do mesmo método nos 
conjuntos, já as entradas contêm dois valores. 
 
 
 
Ver justificativa da resposta: 
 
Os conjuntos são coleções de elementos sem repetição e não podem possuir o valor nulo 
em seu interior. Eles são filhos de Colecao e tem uma interface simples. 
Observe que essas são exatamente as características da chave dos mapas e, por isso, 
uma das implementações simples de conjuntos que podemos fazer é utilizar um mapa em 
que todos os seus valores são nulos. 
Como cada par chave/valor representará um elemento do conjunto, vários métodos podem 
ser reaproveitados diretamente, como o método getTamanho. 
Observe que a interface Conjunto não possui o método get ou similar. Isso porque 
normalmente só queremos testar se um objeto está ou não dentro dele, o que é feito pelo 
método contem, ou listar todos os elementos por meio do iterador. 
 
QUESTÃO 5 
Sobre os algoritmos de ordenação, marque a alternativa correta. 
 
a )Ao final de cada etapa de separação do quick sort, garante-se que o pivô será o 
elemento central da lista. 
 
 b ) Caso o quick sort seja aplicado em uma lista encadeada, elementos iguais ao pivô 
não precisarão ser reprocessados. 
 
c ) Ao final de uma iteração do bubble sort, garante-se que o menor elemento já estará em 
sua posição final. 
 
d ) Ao final de uma iteração do selection sort, garante-se que o maior elemento já estará 
em sua posição final. 
 
e ) A performance do quick sort é melhorada na lista encadeada, pois sua etapa de 
conquistar não realiza tarefa alguma. 
 
Ver justificativa da resposta: 
 
O bubble sort trabalha movimentando o maior elemento para o final da lista. Já o selection 
sort escolhe o menor elemento e movimenta-o diretamente para o início da lista. 
No caso do quicksort, escolhe-se um pivô. Elementos menores que o pivô serão colocados 
à sua esquerda e maiores, à direita. Isso faz com que o pivô termine em sua posição final. 
Porém, essa posição não é necessariamente a do meio da lista, já que ele pode possuir 
qualquer valor. Como os elementos são movimentados, não há custo algum na sua etapa 
de conquistar. Sendo assim, na lista encadeada, essa etapa não realiza tarefa alguma. 
No caso da lista encadeada, geram-se sublistas para elementos menores, maiores ou 
iguais ao pivô. Isso traz como vantagem o fato de os elementos iguais não precisarem ser 
reprocessados, porém há um pequeno custo: a etapa de conquistar passa a ter que 
mesclar as listas. 
QUESTÃO 6 
Quanto ao processo de localização em uma árvore binária e a sua 
função privada de busca (acharNos), assinale a alternativa correta. 
 
 
a ) O valor da última comparação realizada, retornado quando o nó é encontrado, será 
negativo, se o nó estava à esquerda de seu pai, ou positivo, caso contrário. 
 
b ) A função retorna apenas duas informações: o nó onde o dado foi encontrado (nulo se 
não foi) e o seu nó pai (nulo se for a raiz). 
 
c ) Caso o dado não seja encontrado, tanto a informação do nó quanto o seu pai serão 
nulos. 
 
 d ) Se a raiz da árvore for nula, nenhuma chave será encontrada e a função de busca 
sempre retornará o valor falso. 
 
e ) A busca na árvore binária começa pelo elemento central e a busca se restringe à 
esquerda ou à direita. 
 
Ver justificativa da resposta: 
 
O processo de localização em uma árvore binária é descrito pelos seguintes passos: 
1. Inicia-se pelo nó raiz. 
2. Se o nó atual for nulo, a chave não foi encontrada. 
3. Caso contrário, teste se chave procurada é igual à do nó atual. Se for, retorne o valor 
associado, pois o elemento foi encontrado. Se não for, navegue para o nó à esquerda, 
caso a chave desejada seja menor, ou para direita, caso seja maior. Repita o passo 2. 
Observe que, em decorrência dos passos 1 e 2, se a raiz for nula, nenhuma chave jamais 
será encontrada, o que fará a função sempre retornar falso. Além disso, ela deve retornar 
informações adicionais, úteis nos métodos de adição e remoção. Isso é feito retornando a 
estrutura NosRetorno, que conterá a seguinte informação: 
1. O nó onde o dado foi encontrado, que será nulo, caso ele não seja encontrado. 
2. O nó pai, que seránulo, caso o valor seja encontrado na raiz. Caso o nó não seja 
encontrado, será o nó pai de onde o dado deveria estar. 
3. O valor da última comparação realizada. Caso o nó seja encontrado, esse valor será 
zero. Caso não seja, será negativo se ele devesse estar à esquerda do pai; e positivo, se 
tivesse que estar à direita. 
 
QUESTÃO 7 
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 ) A adição no topo da lista tem custo alto, uma vez que envolverá um grande volume de 
movimentação de dados. 
 
c ) Em uma inserção no índice 4, o nó proximo será definido localizando o nó de número 
5. 
 
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 ) Se for uma adição ao fim da lista, a variável anterior do nó será inicialmente atribuída 
ao topo. 
 
Ver justificativa da resposta: 
 
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 8 
O quick sort utiliza a estratégia "dividir para conquistar". Em relação a 
esse algoritmo, assinale a alternativa correta. 
 
a ) Um bom algoritmo para a escolha de um pivô perfeitamente balanceado é tirar a média 
de todos os elementos da lista. 
 
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 ) Na lista encadeada, o ideal é trabalhar com outras listas independentes, copiando 
dados de uma lista para outra. 
 
d ) Em uma lista sequencial, que utiliza um vetor para armazenar seus elementos, a fase 
de conquistar desse algoritmo não realiza tarefa alguma. 
 
e ) Ao separar a lista, elementos menores que o pivô devem ser colocados à sua 
esquerda, enquanto os maiores, à direita, na ordem em que aparecem. 
 
Ver justificativa da resposta: 
 
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. 
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.