Prof. Sérgio Souza Costa

Disciplina: Estrutura de Dados

Curso: Licenciatura em Informática

Conteúdo: Pilhas, Filas, Recursão, Busca

  1. O que será impresso na tela

    s=Stack()
q=Queue()
s.push(85)
s.push(34)
q.enqueue (s.pop())
q.enqueue (s.pop())
s.push(92)
s.push(q.dequeue())
print (s.pop())
print (s.pop())

  2. No material da disciplina foi apresentado um código que verifica se uma dada expressão formada por parênteses está balanceada. Agora teste a implementação passando a seguinte expressão:

    ( 1 + 2 ) * (4 + (3 + 5) )

    O algoritmo irá funcionar corretamente ? Caso contrário, corrija o algoritmo para analisar apenas o balanceamento dos parenteses.

  3. Simule a avaliação da seguinte expressão pós-fixa: a b + c * d /, onde: a = 2, b =4, c = 3, d= 36

    Expressão Elemento Ação Pilha
    2 4 + 3 * 36 / iniciar pilha p:[]
    4 + 3 * 36 / 2 empilhar p:[2]
    + 3 * 36 / 4 empilhar p:[4, 2 ]
    3 * 36 / + des … p:[6]

  4. Modifique a implementação da avaliação posfixa dada nos slides para suportar números com qualquer quantidade de dígitos, inclusive valores em ponto flutuante, como na seguinte expressão: 45.5 83 + 75.4 *

  5. Para exercitar a recursão, codifique pelo menos duas funções entre as propostas a seguir:

    1. A função que retorna o enésimo elemento da sequência Fibonacci.

      Untitled

    2. Codifique uma função recursiva para calcular a divisão inteira utilizando apenas subtrações.

    3. Fazer uma função recursiva que retorne o maior número de uma dada lista, sem usar a função max do Python.

    4. Codifique uma função recursiva que calcula o tamanho de uma dada lista, sem usar a função len.

  6. Baseada no pressuposto que alguns valores são mais buscados que outros, existe uma estrategia que tenta melhorar a eficiência da busca sequencial denominada de movimentação para o início. A abordagem é sempre que uma pesquisa obtiver êxito, o valor recuperado é movido para o início da lista. Então, modifique a implementação iterativa feita em sala de aula para implementar essa abordagem.

  7. Suponha que você tenha a lista ordenada [3, 5, 6, 8, 11, 12, 14, 15, 17, 18] e que você esteja usando o algoritmo recursivo da busca binária. Qual grupo de números mostra corretamente a sequência de comparações usadas para encontrar a chave 16?

    A. 11, 14, 17 B. 18, 17, 15 C. 14, 17, 15 D. 12, 17, 15