Algoritmos e Estrutura de Dados I - AE22CP - 2013/2

Bruno César Ribas

Exercícios

O que é Algoritmo?
Resolva utilizando lista encadeada http://br.spoj.com/problems/VIVO/
http://www.urionlinejudge.com.br/judge/problems/view/1340
http://www.urionlinejudge.com.br/judge/problems/view/1062
Resolva o problema do Gomercindo Detetive utilizando lista encadeadas
Crie uma lista encadeada estática que faça inserção ordenada e:
- Imprima os elementos da lista em ordem inversa usando:
  - Recursão;
  - Uma pilha auxiliar.
http://br.spoj.com/problems/JASPION/
Crie uma lista encadeada que faça inserção ordenada e:
- Imprima os elementos da lista em ordem inversa usando:
  - Recursão;
  - Uma pilha auxiliar.
Resolva utilizando uma lista encadeada: http://www.urionlinejudge.com.br/judge/problems/view/1110

Por que a seguinte versão de insere não funciona?

  struct celula
  {
      int conteudo;
      struct celula *prox;
  };
  
  void insere( int x, celula *p) {
      struct celula nova;
      nova.conteudo = x;
      nova.prox = p->prox;
      p->prox = &nova;
  }

Escreva uma função que copie um vetor para uma lista encadeada. Faça duas versões: uma iterativa e uma recursiva.
Escreva uma função que copie uma lista encadeada para um vetor. Faça duas versões: uma iterativa e uma recursiva.
Escreva uma função que faça uma cópia de uma lista dada.
Escreva uma função que concatena duas listas encadeadas (isto é, "amarra" a segunda no fim da primeira).
Escreva uma função que conta o número de células de uma lista encadeada.
Escreva uma função que verifica se duas listas dadas são iguais, ou melhor, se têm o mesmo conteúdo. Faça duas versões: uma iterativa e uma recursiva.
Escreva uma função que desaloca (função free) todos os nós de uma lista encadeada. Estamos supondo, é claro, que cada nó da lista foi originalmente alocado por malloc.
Escreva uma função que inverte a ordem das células de uma lista encadeada (a primeira passa a ser a última, a segunda passa a ser a penúltima etc.). Faça isso sem usar espaço auxiliar; apenas altere os ponteiros. Dê duas soluções: uma iterativa e uma recursiva.
Digamos que um texto é um vetor de caracteres contendo apenas letras, espaços e sinais de pontuação. Digamos que uma palavra é um segmento maximal de texto que consiste apenas de letras. Escreva uma função que recebe um texto e imprime uma relação de todas as palavras que ocorrem no texto juntamente com o número de ocorrências de cada palavra.
Descreva, em linguagem C, a estrutura de uma das célula de uma lista duplamente encadeada.
Escreva uma função que remove de uma lista duplamente encadeada a célula apontada por p. (Que dados sua função recebe? Que coisa devolve?)
Escreva uma função que insira em uma lista duplamente encadeada, logo após a célula apontada por p, uma nova célula com conteúdo y. (Que dados sua função recebe? Que coisa devolve?)
Problema de Josephus. Imagine que temos n pessoas dispostas em círculo. Suponha que as pessoas estão numeradas 1 a n no sentido horário. Começando com a pessoa de número 1, percorra o círculo no sentido horário e elimine cada m-ésima pessoa enquanto o círculo tiver duas ou mais pessoas. Qual o número do sobrevivente?
Suponha dada uma lista encadeada que armazena números inteiros. Cada célula da lista tema estrutura abaixo.
```
  struct cel {
         int         conteudo;
            struct cel *prox;
  };
```
Escreva uma função que transforme a lista em duas: a primeira contendo as células cujo conteúdo é par e a segunda aquelas cujo conteúdo é ímpar.
Um grupo de sobreviventes do apocalipse zumbi esta circundado por uma horda de zumbis. Não existe esperanças de vitória contra essa horda e os sobreviventes planejam uma fuga a cavalo. A questão principal nesse momento é que o grupo só dispõe de um único cavalo. É necessário estabelecer um critério de sorteio para ver qual sobrevivente fará uso desse cavalo para escapar do massacre. Regras do sorteio:
- É sorteado um número N e o nome de um sobrevivente;
- Iniciando no sobrevivente eles começam a contar no sentido contrário;
- O sobrevivente no qual a contagem N é finalizada é retirado do circulo;
- Todo sobrevivente que sair do circulo não entra mais no processo;
- O último sobrevivente é o felizardo para escapar com o cavalo. Implemente utilizando uma lista encadeada circular.
Resolva o problema do Gomercindo Detetive utilizando lista duplamente encadeada, resolva utilizando duas abordagens:
- Considere que a leitura já coloca os elementos na posição da lista baseadas no Identificador da pista;
- Rearrange o identificador da próxima pista baseada na posição em que foi inserida na lista encadeada.
http://br.spoj.com/problems/MEGADAMA/
http://br.spoj.com/problems/SUDOIME/
http://br.spoj.pl/problems/MACACO/

--
Last Modified: Tue Nov 26 09:40:36 2013.