Exercícios: Estruturas de Dados e Algoritmos Python

1. Saída do Algoritmo Bubble Sort

Observe que dentro da função bubble_sort existe uma função print que mostra o passo a passo da ordenação. Mostre o que será apresentado na saída pela função print quando executamos o programa abaixo.

def bubble_sort(lista):
    elementos = len(lista) - 1
    # Loop externo para passagens
    for j in range(elementos):
        # Loop interno para comparações e trocas
        for i in range(elementos - j): # Otimização: reduzir o range a cada passagem
            if lista[i] > lista[i+1]:
                # Troca de elementos
                lista[i], lista[i+1] = lista[i+1], lista[i]
        print(lista) # Imprime o estado da lista após cada passagem completa
    return lista

vetor = [9, 5, 2, 8, 1, 0]
bubble_sort(vetor)

Saída esperada (após cada passagem completa do loop externo):

• [5, 2, 8, 1, 0, 9]
• [2, 5, 1, 0, 8, 9]
• [2, 1, 0, 5, 8, 9]
• [1, 0, 2, 5, 8, 9]
• [0, 1, 2, 5, 8, 9]

2. Diferença entre Pilha (Stack) e Fila (Queue)

Quando implementamos os tipos abstratos de dados Pilha e Fila, precisamos de variáveis para realizar o gerenciamento e controle das informações contidas neles. Explique a diferença entre essas estruturas:

• Pilha (Stack): Os elementos são removidos na ordem inversa à qual foram inseridos. O último elemento a entrar é o primeiro a sair (LIFO - Last-In, First-Out). Variáveis de controle geralmente envolvem um ponteiro para o topo.
• Fila (Queue): É uma estrutura de dados que admite inserção de novos elementos (geralmente no fim) e remoção de elementos antigos (geralmente do início). O primeiro elemento a entrar é o primeiro a sair (FIFO - First-In, First-Out). Variáveis de controle comuns são ponteiros para o início e o fim da fila.

3. Implementação de Pilha em Python

O código abaixo refere-se a qual tipo abstrato de dados? Explique como funciona cada um dos métodos.

O código implementa o tipo abstrato Pilha (Stack).

class TipoDeDados:
    # Método construtor: inicializa a pilha como uma lista vazia
    def __init__(self):
        self._tipos_de_dados = []

    # Método push: insere um novo valor (n) no topo da pilha
    def push(self, n):
        self._tipos_de_dados.append(n)

    # Método pop: remove e retorna o valor no topo da pilha
    def pop(self):
        if not self.isEmpty(): # Verifica se a pilha não está vazia antes de remover
            return self._tipos_de_dados.pop()
        return None # Ou lançar uma exceção

    # Método top: consulta (retorna) o valor no topo da pilha sem removê-lo
    def top(self):
        if not self.isEmpty():
            return self._tipos_de_dados[-1]
        return None # Ou lançar uma exceção

    # Método isEmpty: verifica se a pilha está vazia
    def isEmpty(self):
        return self._tipos_de_dados == []

Explicação dos Métodos:

• __init__(self): É o construtor da classe. Inicializa a estrutura de dados interna (_tipos_de_dados) como uma lista vazia, que representará a pilha.
• push(self, n): Adiciona o elemento n ao final da lista, que corresponde ao topo da pilha (operação LIFO).
• pop(self): Remove e retorna o último elemento da lista (o topo da pilha). Verifica antes se a pilha não está vazia.
• top(self): Retorna o último elemento da lista (o topo da pilha) sem removê-lo. Verifica antes se a pilha não está vazia.
• isEmpty(self): Retorna True se a lista estiver vazia (pilha vazia) e False caso contrário.

4. Listas Ligadas: Funcionamento e Inserção

Explique como funciona o tipo de dado abstrato de uma lista ligada. Implemente o código para adicionar um elemento após um valor x.

Funcionamento:

A lista ligada (ou encadeada) funciona por meio de uma estrutura de nós conectados. Cada nó contém um dado e um ponteiro (ou referência) para o próximo nó na sequência. O último nó da lista aponta para um valor nulo (None ou null), indicando o fim da lista. Existe também um ponteiro inicial (cabeça ou head) que aponta para o primeiro nó.

Implementação (Pseudocódigo/Conceitual):

Adicionar um novo nó n após o nó que contém o valor x:

# Assumindo uma estrutura de Nó com 'dado' e 'proximo'
# e uma função 'procurar(valor)' que retorna o nó com 'valor' ou None

def adicionar_apos(self, novo_no, valor_x):
    no_anterior = self.procurar(valor_x)
    if no_anterior is not None:
        # Guarda a referência original do próximo nó
        proximo_original = no_anterior.proximo
        # Faz o nó anterior apontar para o novo nó
        no_anterior.proximo = novo_no
        # Faz o novo nó apontar para o restante da lista
        novo_no.proximo = proximo_original
    else:
        print(f"Valor {valor_x} não encontrado na lista.")
        # Ou poderia adicionar no início/fim, dependendo da regra

Nota: O código original fornecido na pergunta parece misturar conceitos e sintaxe. O exemplo acima é uma representação mais comum da lógica de inserção.

5. Completando o Código de Pesquisa Binária

Complete o código abaixo que implementa o algoritmo de pesquisa binária:

def pesquisa_binaria(A, item):
    esquerda, direita = 0, len(A) - 1
    while esquerda <= direita:
        meio = (esquerda + direita) // 2
        if A[meio] == item:
            return meio # Item encontrado, retorna o índice
        elif A[meio] > item:
            direita = meio - 1 # Item está na metade esquerda
        else: # A[meio] < item
            esquerda = meio + 1 # Item está na metade direita
    return -1 # Item não encontrado