ed_4semestre - UNIP

Prévia do material em texto

ESTUDOS DISCIPLINARES 
4º SEMESTRE 
 
 
 
 
 
 
 
 
 
 
1-C) 
Utilizando a formula 2^N-1. Onde N e o numero de discos consegue se calcular o numero 
mínimo de movimentos. No exercício ha 5 discos. Substituindo na formula 2^5-1 = 31 
2-B) 
Encapsulamento consiste na separação de aspectos internos e externos de um objeto. Este 
mecanismo é utilizado amplamente para impedir o acesso direto ao estado de um objeto (seus 
atributos), disponibilizando externamente os métodos que acessam (getters) e alteram 
(setters) estes estados. Logo qualquer processamento a ser realizado sobre os dados 
encapsulado em um TAD não pode ser executado por intermédio de procedimentos externos 
3-B) 
Nesse algoritmo vai ser gerarado um fatorial. Por exemplo, se o valor de A for igual a 4. Então 
seria o 4 multiplicado por 4 - 1, 3 - 1 e 2 - 1. Teria a expressão 4 x 3 x 2 x 1. E é uma função 
recursiva, pois calcula dados que estão "antes do seu valor". 
4-C) 
Uma pilha é um conjunto ordenado de itens, no qual novos itens podem ser inseridos e a partir 
do qual podem ser eliminados itens de uma extremidade, chamada topo da pilha 
5- E) 
A resposta correta é “eu arquivo adoro estrutura e de dados”, pois a ordem infixa é feita da 
seguinte forma: começa pela esquerda, passa pela a raiz, e depois na sub-árvore da direita. 
6- D) 
para se obter a expressão A+B*C e de acordo com a arvore apresentada. Deve se utilizar o 
Atravessamento infixa (ou em-ordem). No atravessamento infixa, começa pela a sub-árvore 
esquerda, passa pela a raiz e depois a sub-árvore direita. Assim teremos ‘A’(sub-árvore 
esquerda) depois o ‘+’(que e a raiz) e a sub-árvore direita. Como a sub-árvore da direita e uma 
raiz, continua se aplicando a mesma regra. ‘B’(sub-árvore esquerda) depois ‘*’ (que e a raiz) e 
o ‘C’(sub-árvore direita). 
7- E) 
I O algoritmo visita cada nó da árvore binária exatamente uma vez ao longo do percurso. 
Correto - Pelo processo da árvore binária, temos um pré-processo estabelecido, logo se tem 
uma ordem onde a árvore é percorrida, tendo todos os seus nós visitados apenas 1 vez. 
II O algoritmo só funcionará corretamente se o procedimento pop () for projetado de forma a 
retornar λ caso a pilha esteja vazia. 
Correto - Ocorre sim à utilização da pilha, isso porque o algoritmo organiza os nós não 
visitados em forma de coleção. Sendo o Pop a operação que retorna ao valor nulo. 
III Empilhar e desempilhar ponteiros para nós da árvore são operações que podem ser 
implementadas com custo constante. 
Correto - Ambas operações podem ser geradas usando estruturas encadeadas ou estáticas 
IV A complexidade do pior caso para o procedimento preordem() é O(n) 
Correto - É necessária a visitação de todos os nós, a cada visita um número de operações é 
gerado. No caso representamos pela função O(n) onde o é número de operações constantes e 
n os passos. 
8- A) 
Fila: primeiro a entrar é o último a sair 
Pilha: último a entrar é o primeiro a sair 
No exercício vemos que ha uma inversão da primeira para a segunda estrutura então logo ela 
e uma pilha. Da segunda para a terceira estrutura a ordem foi mantida então a terceira 
estrutura é uma fila. Analisando as alternativas só a alternativa A esta correta. 
9-C) 
Uma árvore é balanceada quando as alturas das sub-árvores de cada nó não podem ser 
diferenciar em mais de 1 unidade. Por exemplo, no item III a sub-árvore da direita tem altura 2 
e sua sub-árovre esquerda altura 3, assim 3-2 = 1 é um nó balanceado. Analisando os itens 
percebesse que I,II,III possuem nós balanceados. 
Já no item IV os 2 nós filhos da raiz possuem sub-árvores desbalanceadas. Os dois nós uma de 
suas sub-árvores é vazia e a outra possui altura 2, assim 2-0 = 2 não é um nó balanceado. 
10-C) 
I - E um vetor. É uma variável que armazena várias variáveis do mesmo tipo. 
II - E uma lista. É uma estrutura de dados abstrata que implementa uma coleção ordenada de 
valores, onde o mesmo valor pode ocorrer mais de uma vez. 
III- E um grafo. Uma forma de organizar dados, definida a partir de um conjunto de 
vértices/nós e um conjunto de arestas são utilizadas para ligar 2 vértices. 
IV -E uma arvore. É uma estrutura de dados que se caracteriza por uma relação de hierarquia 
entre os elementos que a compõem