Lista4_TAD_ListaEnc_ArvBin_BST

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 e BST 
 
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 
expressã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êntese 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: 
 
8. Qual a diferença entre uma lista simplesmente encadeada e uma duplamente 
encadeada? 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. 
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; 
 } 
} 
 
11. Dado a seguinte BST abaixo, remove os seguintes elementos e escreva a 
árvore resultante após cada operações: 
54,17,19