Listas encadeadas
UnB-\(\gamma\)

Table of Contents

1. Exercícios

  1. Resolva utilizando lista encadeada http://br.spoj.com/problems/VIVO/
  2. http://www.urionlinejudge.com.br/judge/problems/view/1340
  3. http://www.urionlinejudge.com.br/judge/problems/view/1062
  4. 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.
  5. http://br.spoj.com/problems/JASPION/
  6. 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.
  7. Escreva uma função que copie um vetor para uma lista encadeada. Faça duas versões: uma iterativa e uma recursiva.
  8. Escreva uma função que copie uma lista encadeada para um vetor. Faça duas versões: uma iterativa e uma recursiva.
  9. Escreva uma função que faça uma cópia de uma lista dada.
  10. Escreva uma função que concatena duas listas encadeadas (isto é, "amarra" a segunda no fim da primeira).
  11. Escreva uma função que conta o número de células de uma lista encadeada.
  12. 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.
  13. 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.
  14. 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.
  15. 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.
  16. Descreva, em linguagem C, a estrutura de uma das célula de uma lista duplamente encadeada.
  17. 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?)
  18. 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?)
  19. 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?
  20. 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.

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

     1: struct celula
 2: {
 3:     int conteudo;
 4:     struct celula *prox;
 5: };
 6: 
 7: void insere( int x, celula *p) {
 8:     struct celula nova;
 9:     nova.conteudo = x;
10:     nova.prox = p->prox;
11:     p->prox = &nova;
12: }

  22. Suponha dada uma lista encadeada que armazena números inteiros. Cada célula da lista tema estrutura abaixo. 

    1: struct cel {
2:        int         conteudo;
3:           struct cel *prox;
4: };
    • 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.

Author: Bruno Ribas

Created: 2023-01-25 Wed 11:33

Validate