7256 Algoritmos e estruturas de dados

Exercícios / Listas

1. Considerando a classe ListaEncadeada, o que o interpretador do Python exibe após cada uma destas operações serem executadas? Tente prever a resposta e depois use a janela de interações do Python para verificar se elas estão corretas.

   >>> xs = ListaEncadeada()
   >>> xs.insere_inicio(8)
   >>> xs.insere_fim(2)
   >>> xs
   ?
   >>> xs.insere_inicio(5)
   >>> len(xs)
   ?
   >>> xs.remove_inicio()
   ?
   >>> xs
   ?
   >>> xs.remove_inicio()
   ?
   >>> xs.remove_inicio()
   ?
   >>> xs.remove_inicio()
   ?
   >>> xs
   ?

2. Considere o seguinte método definido na classe ListaEncadeada:

   def f(self):
       p = self._primeiro
       q = None
       while p != None:
           w = p.prox
           p.prox = q
           q = p
           p = w
       self._primeiro = q
       self._ultimo = p

   Qual é o resultado da execução deste método se a lista tiver os elementos 4, 6, 8, 1? (Faça a execução no papel, usando um desenho, depois use a janela de interações para conferir a resposta). Complete a definição do método escolhendo nomes mais apropriados, fazendo uma descrição do propósito da função e escrevendo testes. Corrija o código para passar em todos os testes se for necessário.

3. Defina uma função que copie uma lista (do Python) para uma lista encadeada.

4. Defina uma função que copie uma lista encadeada para uma lista (do Python).

5. Supondo que não existisse o campo _ultimo na classe ListaEncadeada qual seria o tempo de execução necessário para inserir e remover no final da lista. Explique.

6. Defina um método soma que some todos os elementos de uma lista encadeada. Faça a análise do tempo de execução deste método.

7. Defina um método maximo que encontre o valor máximo de uma lista encadeada. Faça a análise do tempo de execução deste método.

8. Defina um método limpa que remove todos os elementos de uma lista encadeada. Faça a análise do tempo de execução deste método.

9. Defina um método rotaciona que rotaciona um elemento de uma lista encadeada do início para o fim. Faça a análise do tempo de execução deste método.

10. Defina um método remove_todos que remova todas as ocorrências de um determinado valor de uma lista encadeada. Faça a análise do tempo de execução deste método.

11. Defina um método igual que recebe como parâmetro duas listas encadeadas e verifique se as duas listas são iguais, isto é, tem o mesmo conteúdo. Faça a análise do tempo de execução deste método.

12. Defina um método insere_ordenado que insere um novo elemento em uma lista encadeada ordenada de forma que a lista continue ordenada. Faça a análise do tempo de execução deste método.

13. Usando a definição anterior, defina um método ordenada que a partir de uma lista encadeada crie uma nova lista encadeada ordenada. Faça a análise do tempo de execução deste método.

14. Defina a classe PilhaArranjo que implementa uma pilha usando internamente uma lista do Python (ao invés de ListaEncadeada).

15. Defina a classe FilaArranjo que implementa uma fila usando internamente uma lista do Python (ao invés de ListaEncadeada).