Lista EDA 2º estágio

Prévia do material em texto

Universidade Federal de Campina Grande
Centro de Engenharia Eletrica e Informática (CEEI)
Departamento de Sistemas e Computação (DSC)
Graduação em Ciência da Computação
Disciplina: Estruturas de Dados e Algoritmos
Lista de exercícios 
TAD Lineares, BT, BST & Heaps
1. O que é um TAD? Por que ele é importante?
2. Qual a diferença entre LIFO e FIFO? Quais estruturas de dados que você conhece
implementam essas políticas de acesso, respectivamente?
3. Considere a seguinte pilha abaixo de tamanho 5:
5
8
2
3
1
Indique o estado final da pilha após a execução das seguintes operações
desconsidere o lançamento das exceções):
 if (isFull()) push(10);
 pop();
 pop();
 if (isEmpty()) push(10);
 pop();
 push(5);
 pop();
 pop();
 if (top() == 3) pop();
 if (isEmpty()) pop();
 push(5);
 push(8);
 push(2);
4. Que estratégia você usaria para implementar uma pilha de tamanho ilimitado e por 
quê?
5. Escreva um pseudo-código que remove um item “x” fornecido pelo usuário da pilha 
usando apenas as operações de empilhar, desempilhar, verificar topo e criar. Ao final, 
a lista deve ser igual à original, exceto pela ausência do item removido. 
6. Escreva um programa em pseudo-código utilizando pilhas para verificar se uma ex-
pressão matemática tem os parênteses agrupados de forma correta, isto é: se o nú-
mero de parênteses à esquerda e à direita são iguais; e se todo fechamento de parên-
tese corresponde a algum parêntese que foi aberto anteriormente.
boolean verificaParenteses(String str) {
...
}
7. Modifique o método insert da lista simplesmente encadeada para que ele insira os 
elementos em ordem crescente. Use como base o seguinte pseudo-código:
function listInsert(item) {
 auxHead = head;
 if (head .isNIL()) {
 newHead = new SingleLinkedListNode(item);
 newHead.next = head;
 head = newHead;
 } else {
 previous = null
 while(!auxHead.next.isNIL() && auxHead.next.data < item) {
 previous = auxHead
 auxHead = auxHead.next;
 }
 newNode = new SingleLinkedListNode(item);
 newNode.next = auxHead.next;
 auxHead.next = newNode;
 }
}
8. Qual a diferença entre uma lista simplesmente encadeada e uma duplamente encade-
ada? Qual a vantagem de uma sobre a outra? 
9. Descreva:
a. Árvore;
b. Árvore binária;
c. Árvore binária de busca.
 
10. Dado a seguinte BST abaixo, imprima-a em pré-ordem, ordem e pós-ordem.
11. Dado a seguinte BST abaixo, remove os seguintes elementos e escreva a árvore re-
sultante após cada operações: 
54,17,19
12.Mostre como implementar uma pilha usando apenas uma fila de prioridade (heap) e 
uma instância de uma variável adicional. Dica: procure pensar que os dados armaze-
nados contém uma chave e dados satélites. A chave é usada para ordenar os elemen-
tos.
13.O vetor [23,17,14,6,13,10,1,5,7,12 ] representa uma heap? Justifique sua resposta.