Estruturas de Dados I
Segundo Período de 2008
Gabarito da Primeira Prova
1 a Questão
•
O programa que se segue é testador de MyQueue (fila)e MyStack (pilha). Qual a saída produzida? Como fica a
situação final de Myqueue? Como fica a situação final de MyStack?
MyQueue q;
MyStack s;
q = new MyQueue();
s = new MyStack();
s.push(new Integer(1));
s.push(new Integer(2));
System.out.print(s.pop());
s.push(new Integer(3));
s.push(new Integer(4));
q.enqueue(s.pop());
s.push(new Integer(1));
q.enqueue(new Integer(1));
q.enqueue(new Integer(3));
System.out.print(q.dequeue());
s.push(q.dequeue());
System.out.print(q.dequeue());
System.out.print(s.pop());
System.out.print(s.pop());
1 a Questão – Solução (1)
MyQueue q;
MyStack s;
q = new MyQueue();
s = new MyStack();
s.push(new Integer(1));
s.push(new Integer(2));
System.out.print(s.pop());
s.push(new Integer(3));
s.push(new Integer(4));
q.enqueue(s.pop());
s.push(new Integer(1));
q.enqueue(new Integer(1));
q.enqueue(new Integer(3));
System.out.print(q.dequeue());
s.push(q.dequeue());
System.out.print(q.dequeue());
System.out.print(s.pop());
System.out.print(s.pop());
Pilha
Fila
Saída
2
1
1 a Questão – Solução (2)
MyQueue q;
MyStack s;
q = new MyQueue();
s = new MyStack();
s.push(new Integer(1));
s.push(new Integer(2));
System.out.print(s.pop());
s.push(new Integer(3));
s.push(new Integer(4));
q.enqueue(s.pop());
s.push(new Integer(1));
q.enqueue(new Integer(1));
q.enqueue(new Integer(3));
System.out.print(q.dequeue());
s.push(q.dequeue());
System.out.print(q.dequeue());
System.out.print(s.pop());
System.out.print(s.pop());
Pilha
Fila
Saída
2
1
1 a Questão – Solução (3)
MyQueue q;
MyStack s;
q = new MyQueue();
s = new MyStack();
s.push(new Integer(1));
s.push(new Integer(2));
System.out.print(s.pop());
s.push(new Integer(3));
s.push(new Integer(4));
q.enqueue(s.pop());
s.push(new Integer(1));
q.enqueue(new Integer(1));
q.enqueue(new Integer(3));
System.out.print(q.dequeue());
s.push(q.dequeue());
System.out.print(q.dequeue());
System.out.print(s.pop());
System.out.print(s.pop());
Pilha
Fila
Saída
2
4
3
1
1 a Questão – Solução (4)
MyQueue q;
MyStack s;
q = new MyQueue();
s = new MyStack();
s.push(new Integer(1));
s.push(new Integer(2));
System.out.print(s.pop());
s.push(new Integer(3));
s.push(new Integer(4));
q.enqueue(s.pop());
s.push(new Integer(1));
q.enqueue(new Integer(1));
q.enqueue(new Integer(3));
System.out.print(q.dequeue());
s.push(q.dequeue());
System.out.print(q.dequeue());
System.out.print(s.pop());
System.out.print(s.pop());
Pilha
Fila
4
Saída
2
3
1
1 a Questão – Solução (5)
MyQueue q;
MyStack s;
q = new MyQueue();
s = new MyStack();
s.push(new Integer(1));
s.push(new Integer(2));
System.out.print(s.pop());
s.push(new Integer(3));
s.push(new Integer(4));
q.enqueue(s.pop());
s.push(new Integer(1));
q.enqueue(new Integer(1));
q.enqueue(new Integer(3));
System.out.print(q.dequeue());
s.push(q.dequeue());
System.out.print(q.dequeue());
System.out.print(s.pop());
System.out.print(s.pop());
Pilha
Fila
4
Saída
2
1
3
1
1
3
1 a Questão – Solução (6)
MyQueue q;
MyStack s;
q = new MyQueue();
s = new MyStack();
s.push(new Integer(1));
s.push(new Integer(2));
System.out.print(s.pop());
s.push(new Integer(3));
s.push(new Integer(4));
q.enqueue(s.pop());
s.push(new Integer(1));
q.enqueue(new Integer(1));
q.enqueue(new Integer(3));
System.out.print(q.dequeue());
s.push(q.dequeue());
System.out.print(q.dequeue());
System.out.print(s.pop());
System.out.print(s.pop());
Pilha
Fila
3
1
1
3
1
Saída
2
4
1 a Questão – Solução (7)
MyQueue q;
MyStack s;
q = new MyQueue();
s = new MyStack();
s.push(new Integer(1));
s.push(new Integer(2));
System.out.print(s.pop());
s.push(new Integer(3));
s.push(new Integer(4));
q.enqueue(s.pop());
s.push(new Integer(1));
q.enqueue(new Integer(1));
q.enqueue(new Integer(3));
System.out.print(q.dequeue());
s.push(q.dequeue());
System.out.print(q.dequeue());
System.out.print(s.pop());
System.out.print(s.pop());
Pilha
Fila
Saída
2
3
1
4
3
1
1
2 a Questão
Escreva uma função que receba um fila de inteiros q como
argumento e retorne uma nova fila. Esta nova fila conterá os
últimos n elementos de q na mesma ordem que apareciam na
fila original. Por exemplo, para se q contiver {a, b, c, d, e, f}e n
for 4, então o retorno será uma fila contendo {c, d, e, f}. Se q
contiver menos de n elementos o retorno será uma fila com os
elementos não modificados.
Basta declarar, não precisando definir, as variáveis MyStack e
MyQueue.
MyQueue possui apenas os métodos clear(), enqueue(),
dequeue() e isEmpty().
Supõe-se que a pilha e a fila nunca transbordam.
Primeira solução (1)
public static MyQueue fn(MyQueue q, int n)
{
/* Retorna uma fila com os últimos n
elementos de q (em ordem).
** Caso q contenha menos do que n
elementos retorna
** uma fila com os elementos sem
modificação.
*/
MyQueue q1; // guarda o conteúdo de q
int count, i; // contadores
Primeira solução (2)
// cópia da fila q para a fila q1
count = 0;
q1 = new MyQueue();
while (!q.isEmpty()) {
q1.enqueue(q.dequeue());
count++;
}
Primeira solução (3)
/* Eliminação de count – n objetos de q1.
** Considerar o caso no qual n seja
maior do que count
*/
if(count < n) {
i = 0;
while (i < count) {
q.dequeue();
i ++;
}
}
Primeira solução (4)
/* cópia de n elementos de q1 para
q (q estava vazia)
*/
while (!q1.isEmpty()) {
q.enqueue(q1.dequeue());
}
return q;
}
Segunda solução (1)
public static MyQueue fn(MyQueue q, int n) {
/* Retorna uma fila com os últimos n elementos
de q (em ordem).
** Caso q contenha menos do que n elementos
retorna
** uma fila com os elementos sem modificação.
*/
MyStack s1;
// guarda o conteúdo de q em ordem inversa
MyStack s2;
// guarda o conteúdo de q em ordem direta
int count; // contador
Segunda solução (2)
// cópia da fila para a pilha
s1 = new MyStack();
while (!q.isEmpty()) {
s1.push(q.dequeue());
}
Segunda solução (3)
/* Pop de n elementos para s2.
** Considerar o caso no qual n seja maior do
** que o tamanho de s1.
*/
s2 = new MyStack();
count = 0;
while ((count < n) && (!s1.isEmpty())) {
s2.push(s1.pop());
count++;
}
Segunda solução (4)
// pop de todos os elementos para q
// (q estava vazia)
while (!s2.isEmpty()) {
q.enqueue(s2.pop());
}
return q;
}
3 a Questão
Escreva uma função que receba um fila de inteiros q
como argumento e retorna (em ordem reversa) cada
terceiro elemento de q iniciando com o último
elemento. Por exemplo, se q contiver
{a,b,c,d,e,f,g,h} então o retorno será uma fila
contendo {h,e,b}
Basta declarar, não precisando definir, as variáveis
MyStack e MyQueue. MyQueue possui apenas os
métodos clear(), enqueue(), dequeue() e
isEmpty(). Supõe-se que a pilha e a fila nunca
transbordam.
3 a Questão – Solução (1)
public static MyQueue fn(MyQueue q) {
/* Retorna uma fila contendo todo
** terceiro elemento
** da fila q em ordem inversa.
*/
MyStack s; // guarda o conteúdo de q em
ordem inversa
int count; // contador
3 a Questão – Solução (2)
// cópia da fila para a pilha
s = new MyStack();
while (!q.isEmpty()) {
s.push(q.dequeue());
}
3 a Questão – Solução (3)
// Pop cada terceiro elemento para q (q está vazia)
count = 0;
while (!s.isEmpty()) {
if ((count % 3) == 0) {
q.enqueue(s.pop());
} else {
s.pop(); // descartar
}
count++; // incrementa contador
}
return q;
}
4 a Questão
Escrever um método mergeLists() que recebe duas
lista encadeadas a e b de objetos NodeA. (A classe
NodeA contém um único Comparable e está exibida a
seguir).
Nenhuma das listas possui valores duplicados e
estão classificadas em ordem ascendente.
O método deve retornar uma nova lista encadeada,
classificada pelo mesmo critério, que contém cópias
das referencias de todos os elementos de a e b (sem
duplicatas).
Listas vazias são passadas como null. Os métodos
não fornecidos devem ser definidos.
Classe NodeA
Classe NodeA:
public class NodeA {
private Comparable data;
private NodeA next; // link para o próximo nó
public NodeA(Comparable newData) {
// Construtor de conversão. O ponteiro é colocado em null.
data = newData;
next = null;
}
public Comparable getData() {
// Retorna uma referência ao dado deste nó.
return data;
}
public NodeA getNext() {
// Retorna uma referência ao próximo nó da lista.
return next;
}
public NodeA setNext(NodeA nextNode) {
// Estabelece referência ao próximo nó da lista.
next = nextNode;
}
}
4 a Questão – Solução (1)
NodeA mergeLists(NodeA a, NodeA b) {
/* Retorna uma lista que contém cópias das referências
** a todos os elementos das listas a e b, sem duplicatas
** preservando a classificação existente.
** Considera-se que as listas não estão vazias.
*/
NodeA newlist; // referência à lista intercalada de elementos
NodeA tempref; /* referência auxiliar na travessia da lista
** intercalada. Sempre aponta para o ultimo
** elemento adicionado à lista. */
/* O mais fácil é fazer newlist apontar para um nó temporário
** que possa ser removido mais tarde. */
4 a Questão – Solução (2)
newlist = new NodeA(null);
tempref = newlist; // inicialização de tempref
/* Intercalação das duas listas, fazendo uma
** cópia de cada elemento único.
*/
while ((a != null) || (b != null)) {
4 a Questão – Solução (3)
/* Como as listas estão classificadas em ordem ascendente,
** pode-se adicionar à lista intercalada qualquer elemento
** em uma lista que seja menor que o menor dos elementos
** que restam na outra lista.
** Se em ambas as listas ocorrer o mesmo elemento um única
** cópia dele é adicionada à lista intercalada.
** Caso uma lista tenha sido percorrida (== null),
** adicionar todos os elementos da outra à lista
intercalada.
*/
4 a Questão – Solução (4)
while ((a != null) || (b != null)) {
if ((b == null) || (a.getData().compareTo(b.getData()) < 0)) {
tempref.setNext(new NodeA(a.getData())); // adicionar novo nó
tempref = tempref.getNext(); // avançar referência ao novo nó
a = a.getNext(); // avançar referência ao próximo nó a ser
// testado
} else if ((a == null) || (a.getData().compareTo(b.getData()) > 0)) {
tempref.setNext(new NodeA(b.getData())); // adicionar novo nó
tempref = tempref.getNext(); // avançar referência ao novo nó
b = b.getNext(); // avançar referência ao próximo nó a ser
// testado
}
4 a Questão – Solução (5)
((b == null) || (a.getData().compareTo(b.getData()) < 0))
/* Desde que o elemento corrente de a é menor do que o menor
** dos elementos que restaram em b (ou b é null),
** ele não pode estar em b.
** Adicionar os elementos que aparecem apenas na lista a.
** Deve-se usar `||' em vez do OU lógico `|' para evitar
** ocorrência de null reference exception na execução.
*/ ((a == null) || (a.getData().compareTo(b.getData()) > 0))
/* Desde que o elemento corrente de b é menor do que o menor
** dos elementos que restaram em a (ou a é null),
** ele não pode estar em a.
** Adicionar os elementos que aparecem apenas na lista b.
** Deve-se usar `||' em vez do OU lógico `|' para evitar
** ocorrência de null reference exception na execução.
*/
4 a Questão – Solução (6)
else {
/* O elemento aparece tanto em a quanto em b.
/* Adicionar uma das cópias e avançar ambas as referências.
*/
tempref.setNext(new NodeA(a.getData())); //adicionar novo nó
tempref = tempref.getNext(); //avançar referência ao novo nó
a = a.getNext();
b = b.getNext();
}
}
/* Retornar a nova lista
** (ignorando o nó dummy criado no início). */
return newlist.getNext();
}
5 a Questão
O trecho de código abaixo utiliza uma estrutura de dados já
definida MyStack e vai ser usado para verificar qual a seqüência
de operações utilizada para gerar uma determinada saída.
Sendo x um char, considere-se as abreviaturas
I  s.push(x); e
E  System.out.print(s.pop());
A ordem na qual os dados poderão ser empilhados é
exclusivamente a,b,c,d,e.
Desta maneira a seqüência de operações “IEIIEE” produziria a
saída “ACB”.
Indique, justificando, qual a seqüência de operações que
poderia produzir a saída “ADBC”
5 a Questão – Solução (1)
MyStack s;
char a,b,c,d,e,f;
a=’A’;
b=’B’;
c=’C’;
d=’D’;
e=’E’;
f=’F’;
s = new MyStack();
5 a Questão – Solução (2)
Não existe seqüência que produza a
saída “ADBC”.
Depois da saída de um objeto da pilha
todos os objetos que entraram na pilha
antes dele só podem sair em ordem
inversa à de entrada.
5 a Questão – Solução (3)
IE significa empilhar A e desempilhar A
IEIIIE significa






Empilhar A
Desempilhar A
Empilhar B
Empilhar C
Empilhar D
Desempilhar D
Saída desejada: “ADBC”
Na pilha ficam C e B que sempre sairão na
ordem inversa da entrada