Simulado Prog Gabarito

Prévia do material em texto

Nome do(a) Aluno(a): 
PROGRAMAÇÃO II 1/6 
 
 
GRADUAÇÃO A DISTÂNCIA 
ATIVIDADE ACADÊMICA: PROGRAMAÇÃO II 
GRAU B 
DATA: / / . 
 
 
POLO: ............................................................. 
 
CURSO: ................................................................................................. 
 
............................................................................................................... 
 
............................... 
Rubrica Nota 
Nome do(a) Aluno(a) Número 
 
Orientações gerais para realização da avaliação: 
- A avaliação é individual; 
- Deve ser utilizada caneta azul ou preta para responder as questões; 
- É permitida a utilização de uma folha A4, construída pelo aluno, frente e verso. Não é permitido o 
compartilhamento de materiais entre os alunos. 
 
 
1. (1,5 PONTOS) 1 - Primeira questão: Marque V para as alternativas verdadeiras e F para as alternativas falsas: 
 
 
F 
Para haver polimorfismo, é necessário haver sobrecarga de métodos. 
F Uma classe abstrata possui apenas métodos abstratos. 
V A estrutura de dados que segue uma política de inserção e remoção chamada FIFO (First In First Out) e 
permite inserção em um extremo e remoção em outro é a Fila. 
F Na sobrecarga de métodos, os novos métodos gerados na sobrecarga devem ter a mesma assinatura do 
método sobrecarregado. 
V Listas lineares gerais permitem inserção e remoção de qualquer chave da lista. 
 
 
 
Nome do(a) Aluno(a): 
PROGRAMAÇÃO II 2/6 
 
 
 
2. (2,0 PONTOS) 2 - Segunda questão: Considerando o código abaixo, mostre como ficaria o conteúdo do vetor 
queue do objeto fila f (classe CircularQueue - implementação de fila circular com alocação estática) 
após a execução do código abaixo. Indique valor das variáveis first (inicio da fila) e last (final da fila). 
 
 public static void main(String args) { 
 CircularQueue f = new CircularQueue(5); 
 try { 
 f.enqueue(4); 
 f.enqueue(3); 
 f.enqueue(1); 
 f.enqueue(2); 
 f.enqueue(7); 
 } catch (OverflowException e) { 
 System.out.println(e); 
 } 
 try { 
 f.dequeue(); 
 f.dequeue(); 
 } catch (UnderflowException e) { 
 System.out.println(e); 
 } 
 try { 
 f.enqueue(1); 
 f.enqueue(2); 
 } catch (OverflowException e) { 
 System.out.println(e); 
 } 
 try { 
 f.dequeue(); 
 } catch (UnderflowException e) { 
 System.out.println(e); 
 } 
 try { 
 
Nome do(a) Aluno(a): 
PROGRAMAÇÃO II 3/6 
 
 f.enqueue(3); 
 } catch (OverflowException e) { 
 System.out.println(e); 
 } 
.> } 
 
 
 
RESPOSTA: 
4 3 1 2 7 
FIRST LAST 
 1 2 7 
 FIRST LAST 
1 2 1 2 7 
 LAST FIRST 
1 2 2 7 
 LAST FIRST 
1 2 3 2 7 
FINAL LAST FIRST
 
Nome do(a) Aluno(a): 
PROGRAMAÇÃO II 4/6 
 
 
3. (2,5 PONTOS) 3 – Terceira questão: Implemente o seguinte método na classe List (implementação de lista 
duplamente encadeada): 
 
public void insertInTheMiddle(String thisOne) 
 
Este método deve inserir a chave referenciada por thisOne no meio da lista. Se a lista contém n elementos, a 
String referenciada por thisOne deve ser inserida na posição (
2
n
)+1, onde (
2
n
) é truncado caso n seja ímpar. 
 
RESPOSTA: 
 
 
public void insertInTheMiddle(String thisOne ) { 
 if (firstNode!= null && lastNode!= null ){ 
 Node ant, current = firstNode; 
 int c=0; 
 while ( current != null ) { 
 c++; 
 current = current.getNext(); 
 } 
 //procura o centro da lista 
 c=c/2; 
 current= ant = firstNode; 
 for(int i=1; i<=c; i++){ 
 ant = current; 
 current = current.getNext(); 
 } 
 //insere novo nodo entre o ant e o current 
 Node novo = new Node( thisOne, current ); 
 current.setPrevious(novo); 
 ant.setNext(novo); 
 novo.setPrevious(ant); 
 } 
 } 
 
Nome do(a) Aluno(a): 
PROGRAMAÇÃO II 5/6 
 
 
4. (2,0 PONTOS) 4 – Quarta questão: Monte a árvore binária de pesquisa (desenhe) inserindo os nós abaixo na 
ordem apresentada: 
a. 5,2,8,10,1,7,4,18,9 
b. Realize o caminhamento em pré-ordem, pós-ordem e in-ordem na árvore resultante 
c. Mostre quais nodos são visitados na pesquisa pelo nó 9. 
d. Execute a remoção por fusão no nó 8 e desenhe a árvore resultante 
 
RESPOSTA: 
a) 
 
 
 
 
 
b) em-ordem: 1 ,2, 4, 5, 7, 8, 9, 10, 18 
 pré-ordem: 5, 2, 1, 4, 8, 7, 10, 9, 18 
 pós-ordem: 1, 4, 2, 7, 9, 18, 10, 8, 5 
 
c) 5, 8, 10, 9 
 
d) 
 
 
 
 
 
 
5 
2 8 
1 4 7 10 
9
9 
18 
5 
2 7 
1 4 10 
9
9 
18 
 
Nome do(a) Aluno(a): 
PROGRAMAÇÃO II 6/6 
 
(2,0 PONTOS) 5 – Quinta questão: Faça a inserção do nó 97 na árvore AVL abaixo. Indique caso ocorra alguma 
rotação e desenhe a árvore resultante. 
 
 
RESPOSTA: 
 Fator(93) = h(esq=0 - dir=2) = -2 
 Fator(98) = h(esq=1 e dir=0) = 1 
 Não é balanceada, necessita rotação dupla à esquerda: 
 Rotação simples à direita: Rotação simples à esquerda: 
 
 
 
 
 
 
97 
78 
73 93 
97 
98 
78 
73 
93 
97 
98