Prova Online Estrutura de Dados 2

Prévia do material em texto

Abaixo estão as questões e as alternativas que você selecionou: 
QUESTÃO 1 
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 ) 
 Cada nó pode ter apenas dois elementos: o nó pai e o nó filho. 
 
 
c ) 
 A melhor disposição possível da árvore binária é obtida ao inserir nós de maneira ordenada. 
 
 
d ) 
 A busca binária é utilizada para realizar a localização de um nó dentro da árvore. 
 
 
e ) 
 São chamadas de binárias porque os valores em seus nós só podem conter os dígitos zero (0) e 
um (1). 
 
Ver justificativa da resposta 
Justificativa 
Uma árvore é considerada binária de busca se possuir as seguintes limitações: 
oCada nó pode conter apenas dois nós filhos, que chamaremos de nó esquerdo e nó direito. 
oValores menores ou iguais ao nó atual devem ser inseridos do lado esquerdo. Já os maiores, à 
direita. 
Esse tipo de árvore é utilizado para implementar um mapa ordenado e pode apresentar 
quaisquer valores. A ordem de inserção dos elementos definirá o desenho da árvore. Uma 
árvore balanceada possuirá uma boa distribuição dos nós entre os lados direito e esquerdo, 
obtendo uma performance similar à da busca binária. 
Caso os nós sejam adicionados de maneira ordenada, a árvore obterá sua pior configuração 
possível, uma vez que os nós se posicionarão apenas de um lado. Chamamos essa condição 
de árvore desbalanceada. 
 
QUESTÃO 2 
Sobre as pilhas, listas e filas, assinale a alternativa correta. 
 
 
a ) 
javascript:;
 O método isCheia está presente apenas nas coleções estáticas. 
 
 
b ) 
 É 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. 
 
 
c ) 
 Uma operação comum a todas essas coleções é que podem ser iteradas. 
 
 
d ) 
 Criar uma interface que represente todas as coleções têm pouca utilidade, uma vez que ela 
praticamente só permitiria iteração. 
 
 
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 
javascript:;
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. 
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 3 
Sobre os conceitos de referência e valor, assinale a alternativa correta. 
 
 
a ) 
 Um dos problemas das referências é que as atribuições possuem custo por gerarem cópias dos 
dados. 
 
 
b ) 
 Um vetor de tipos primitivos irá alocar todos os seus valores na pilha. 
 
 
c ) 
 As variáveis locais trabalham por cópia e, por isso, são criadas no heap. 
 
 
d ) 
 Um vetor de objetos em Java irá alocar a memória para todos os objetos de maneira contínua. 
 
 
e ) 
 Uma classe contendo um campo idade (inteiro), um campo nome (String) e um vetor contém 1 
tipo primitivo e 2 referências. 
 
Ver justificativa da resposta 
javascript:;
Justificativa 
Em Java, as referências sempre serão utilizadas para objetos. Deve-se observar que Strings e 
vetores também são considerados objetos, e objetos sempre serão alocados na memória heap. 
Apenas variáveis locais de tipos primitivos terão seus dados alocados na stack. 
Isso gera três consequências importantes: 
1.Uma variável local de um vetor de tipo de primitivo será apenas uma referência no stack. O 
vetor em si estará alocado de maneira contínua, mas no heap. 
2.Um vetor de objetos também estará no heap. Porém, apenas as referências aos objetos que 
ele contém estarão em seu interior de maneira contínua. Os objetos em si também estarão no 
heap, mas podem estar dispersos. 
3.Raramente, o Java fará cópias acidentais de dados. Isso porque somente variáveis na pilha 
são copiadas automaticamente - ou seja, variáveis do tipo primitivo ou referências, mas não os 
dados para onde as referências apontam. Assim, vetores ou objetos inteiros, que possuem 
muitos dados, nunca são copiados automaticamente. 
 
QUESTÃO 4 
Qual destas estruturas permite agrupar diferentes tipos de dados em uma 
estrutura mais complexa na linguagem Java? 
 
 
a ) 
 Vetor. 
 
 
b ) 
 Classe. 
 
 
c ) 
 Referência. 
 
 
d ) 
 Método. 
 
 
e ) 
 Variável de tipo primitivo. 
 
Ver justificativa da resposta 
Justificativa 
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 5 
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: 
 
 
a ) 
 toda estrutura com base em nós será dinâmica. 
 
 
b ) 
 um nó é uma estrutura de apoio das estruturas sequenciais. 
 
 
c ) 
 em uma estrutura sequencial, os nós ficam dispersos na memória. 
 
 
javascript:;
d ) 
 a fila circular é um exemplo de estrutura encadeada. 
 
 
e ) 
 não é possível criar uma estrutura sequencial dinâmica. 
 
Ver justificativa da resposta 
Justificativa 
Há duas classificações possíveis para as implementações de qualquer estrutura de dados. 
Quanto ao limite de dados, as estruturas podem ser estáticas ou dinâmicas. Estruturas estáticas 
possuem uma quantidade fixa de dados que são capazes de comportar, geralmente definida no 
momento de sua criação. Já estruturas dinâmicas não possuem essa limitação, tendo sua 
capacidade máxima definida apenas pela quantidade de memória disponível para o processo. As 
estruturas encadeadas utilizam uma estrutura chamada nó, que tem como propósito a alocação 
de memória à medida que os elementos são inseridos, encadeando elementos entre si. 
Embora o vetor seja estático, é possível criar estruturas dinâmicas com ele. Basta que a 
estrutura copie os dados para novos vetores quando necessário, ou que ela encadeie vetores 
entre si. 
Quanto à disposição dos dados na memória, as estruturas podem ser sequenciais ou 
encadeadas. Estruturas sequenciais possuem os dados colocados lado a lado na memória, 
sendo a fila circular um de seus exemplos. Em estruturas dinâmicas, os dados encontram-se 
dispersos em diversos endereços de memória. Por fim, é possível criar estruturassequenciais 
dinâmicas. 
 
QUESTÃO 6 
Quanto ao algoritmo de busca por seleção (selection sort), marque a 
alternativa correta. 
 
 
a ) 
 
 
 
javascript:;
b ) 
 O algoritmo de selection sort é inviável para a lista encadeada, pois nesta estrutura sua 
implementação se torna demasiado complexa. 
 
 
c ) 
 Por trocar apenas o menor elemento a cada iteração, é incorreto afirmar que esse algoritmo 
utiliza a estratégia de força bruta. 
 
 
d ) 
 Na lista encadeada, é melhor que se troque os dados do que os nós, pois os nós implicarão na 
atualização de vários elementos (anterior, próximo etc.). 
 
 
e ) 
 O algoritmo se beneficia do fato de que trocas geralmente têm um custo mais alto do que 
comparações, sendo, em geral, mais indicado que o bubble sort. 
 
Ver justificativa da resposta 
Justificativa 
O algoritmo de selection sort tenta minimizar o número de trocas, porque essa operação pode ter 
um custo bastante significativo, caso os dados sejam compostos (custo que pode ser reduzido 
em listas encadeadas trocando-se os nós em vez dos dados). 
A cada iteração, busca-se o menor elemento da lista e este é movimentado para o início da lista, 
após o último elemento ordenado. Isso garante que, no pior caso, uma lista com n elementos 
sofrerá apenas (n - 1) trocas. Por isso, esse algoritmo é mais recomendado do que o bubble sort. 
Sua implementação é simples tanto em listas sequenciais quanto encadeadas. Entretanto, esse 
algoritmo ainda utiliza a estratégia de força bruta, sendo vantajoso apenas para listas muito 
pequenas, com tamanho em torno de, no máximo, 20 elementos. 
 
QUESTÃO 7 
Sobre os métodos set e get, assinale a alternativa correta. 
javascript:;
 
 
a ) 
 O método get da lista estática tem um custo alto, pois envolve deslocar para a esquerda todos 
os elementos excluídos. 
 
 
b ) 
 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. 
 
 
c ) 
 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. 
 
 
d ) 
 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. 
 
 
e ) 
 As listas encadeadas não devem possuir método get e set, uma vez que o acesso direto a um 
nó não existe. 
 
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. 
javascript:;
 
 
 
QUESTÃO 8 
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 da árvore é 3, devido aos nós mais profundos estarem no terceiro nível. 
 
 
d ) 
 A iteração em pré-ordem visitará os nós 8, 3, 5, 12, 10 e 14, nesta ordem. 
 
 
e ) 
 A altura do nó 12 é 2, visto que tem dois filhos. 
 
Ver justificativa da resposta 
Justificativa 
 
 
 
javascript:;