Exercicios Lista

Prévia do material em texto

Obs: Para os exercícios abaixo considere as listas encadeadas como: 
 Linear Simplesmente Encadeada ; 
 Linear Duplamente Encadeada; 
 Circular Simplesmente Encadeada ; 
 Circular Duplamente Encadeada; 
1. Escreva um algoritmo que calcule o comprimento de uma lista L1: 
2. Escreva um algoritmo que recebe duas listas (L1 e L2) e retorna um valor lógico: 
Verdadeiro, se L1 = L2 e Falso, se L1 <> L2. 
3. Escreva um algoritmo copia (L1, L2) para montar uma cópia L2 da lista L1; 
4. Escreva um algoritmo diferença (L, L1, L2) para construir a lista L igual à diferença 
L1-L2; 
5. Escreva um algoritmo Comuns (L1,L2) , que deve retornar um valor inteiro igual ao 
número de valores comuns às duas listas ordenadas L1 e L2; 
6. Escreva um algoritmo insere (L, x, P) para inserir um nó com informação antes do nó 
cujo endereço é dado pela variável P, na lista L; 
7. Escreva um algoritmo remove-esq (L, P) para remover da lista duplamente encadeada 
circular L, o nó localizado após aquele cujo endereço é dado pela variável P; 
8. Escreva um algoritmo remove-k (L, k) para remover o k-ésimo nó da lista encadeada L; 
9. Escreva um algoritmo destrói (L) para remover todos os nós da lista encadeada L; 
10. Escreva um algoritmo copia (L1, L2) para montar uma cópia L2 da lista L1 (ambas 
duplamente encadeada circular), de modo que os elementos de L2 estejam em L1 na 
ordem inversa. (30 pontos) 
11. Escreva um algoritmo remove-k (L, k) para remover o k-ésimo nó da lista linear 
simplesmente encadeada L; (30 pontos) 
12. Escreva um algoritmo que recebe uma lista circular duplamente encadeada e elimina os 
nós de ordem par (segundo, quarto, sexto, etc.) (30 pontos) 
13. Escreva um algoritmo ÉInversa (L1, L2) que retorna 1 se a lista L1 tem os mesmos 
elementos de L2 na ordem inversa, -1 se L1 tem menos elementos que L2 e 0 se L1 tem 
mais elementos que L2 (30 pontos) 
14. Considere uma lista circular duplamente encadeada. Faca um algoritmo que transforma 
esta lista em uma lista linear simplesmente encadeada (quebra a ligação do ultimo pro 
primeiro e as ligações de cada nó pro seu anterior pro anterior). Não pode alterar a 
vizinha dos nós da lista (exceto no ponto onde o circulo é quebrado) e não pode fazer 
alocação de novas estruturas do tipo Nó. ( 30 pontos) 
15. Escreva um algoritmo copia (L1, L2) para montar uma cópia L2 da lista L1( ambas 
duplamente encadeada linear), de modo que os elementos de L2 estejam em L1 na ordem 
inversa. (40 pontos) 
16. Receber duas listas circulares simplesmente encadeadas (L1 e L2), incluir todos os nós de 
L2 em L1, de maneira intercalada. Não pode alocar novos nós. A lista L1 ficara com um 
nó de L1, sempre seguido de um nó de L2 
17. Receber uma lista linear simplesmente encadeada e eliminar os nós de ordem impar( 
primeiro, terceiro, quinto, etc.) 
18. Considere uma lista circular duplamente encadeada. Faca um algoritmo que transforma 
esta lista em uma lista linear simplesmente encadeada (quebra a ligação do ultimo pro 
primeiro e as ligações de cada nó pro seu anterior pro anterior). Não pode alterar a 
vizinha dos nós da lista (exceto no ponto onde o circulo é quebrado) e não pode fazer 
alocação de novas estruturas do tipo NODE. ( 30 pontos) 
19. Escreva um algoritmo copia (L1, L2) para montar uma cópia L2 da lista L1( ambas 
duplamente encadeada linear), de modo que os elementos de L2 estejam em L1 na ordem 
inversa. (40 pontos) 
20. Escreva um algoritmo remove-k (L, k) para remover o k-ésimo nó da lista encadeada L; 
(30 pontos) 
21. Considere uma lista onde cada um de seus nós é do tipo Nó de lista duplamente 
encadeada. No entanto durante sua construção os encadeamentos foram realizados como 
se fosse uma lista linear simplesmente encadeada. Faca um algoritmo que recebe o 
gerente desta lista e corrige os encadeamentos para que esta lista fique realmente como 
lista circular duplamente encadeada. ( 40 pontos)