Lista de execícios 1 sobre Estrutura de dados

Prévia do material em texto

Estruturas de Dados
Prof. Eduardo Alchieri
1° Lista de Exercícios 
1. Dê o conceito de:
a) Algoritmo:
b) Tipo de dados:
c) Tipo abstrato de dados:
d) Estruturas de dados:
2. Quais são as principais vantagens e as principais desvantagens de cada uma das 
seguintes estruturas fundamentais: vetores e listas ligadas. Indique quando devemos 
utilizar uma ou outra destas estruturas.
3. Dadas duas listas ligadas l1 e l2, faça uma função que concatena estas duas listas. 
Considere que as listas são simplesmente encadeadas e ainda possuem um referência 
(ponteiro) primeiro para o primeiro elemento e uma referência ultimo para o último 
elemento. Considere ainda que cada elemento possui uma referência dado para o dado 
armazenado e uma referência proximo para o próximo elemento (ou null caso seja o 
último elemento).
4. Implemente as duas operações principais de uma pilha (empilhe e desempilhe) 
utilizando como estrutura interna para armazenamento de dados uma fila (com as suas 
funções enfileirar e desenfileirar e estaVazia). Considerando que o custo para acesso à 
fila é O(1) tanto para a função enfileirar quando desenfileirar, calcule o custo dos 
algoritmos desenvolvidos. Obs.: Podem utilizar quantas filas forem necessárias.
5. Um palíndromo é uma palavra (ou frase) que possui a propriedade de poder ser lida 
tanto da direita para a esquerda como da esquerda para a direita. Exemplos de 
palíndromos: aça, ama, arara, reter. Faça uma função que recebe como parâmetro uma 
palavra (ou frase) e retorne verdadeiro caso a palavra seja um palíndromo, no contrário 
retorne falso. A função deve obrigatoriamente utilizar as estruturas de dados estudadas 
(pilhas, filas, deques, árvores, etc..). 
Considere que existe a seguinte função:
• getCaracteres(palavra), que retorna um vetor com os caracteres de palavra. 
Exemplo: getCaracteres(`”arara”) retorna um vetor v de tamanho 5, onde: v[0] == “a”; 
v[1] == “r”; v[2] == “a”; v[3] == “r” e v[4] == “a”.
• Protótipo da função a ser desenvolvida: boolean palindromo(palavra)
6. Quais são as principais diferenças entre uma árvore binária e uma árvore binária de 
busca?
7. Implemente um algoritmo recursivo que retorne a quantidade de folhas de uma árvore
 binária. Protótipo da função: int folhas(No raiz)
8. Implemente um algoritmo recursivo que compara se duas árvores binárias são iguais.
 Protótipo da função: boolean iguais(No raiz1, No raiz2)
9. A altura de um nó x em uma árvore binária é a distância entre x e o seu descendente 
mais afastado + 1. Implemente um algoritmo recursivo que calcule a altura de um nó x 
passado como parâmetro. Protótipo: int altura(No x)
10. Porque é importante que uma árvore binária de busca sempre esteja balanceada?
	Estruturas de Dados
	Prof. Eduardo Alchieri