Exercícios de Estruturas de Dados e Algoritmos: Árvores, Grafos e C

Questão 1: Árvore B*

Considere a seguinte Árvore B* de ordem m=2 (ou seja, os nós internos podem ter no mínimo dois elementos):

1. a. Inserções na Árvore B*

   Esquematize como ficaria a árvore após as seguintes inserções: 72, 75, 95, 110 e 115.

2. b. Remoções na Árvore B*

   Considerando as chaves do item (a) inseridas, esquematize como ficaria a árvore após as seguintes remoções: 60, 29, 45, 52 e 70.

Questão 2: Grafos e Busca em Largura (BFS)

Seja um grafo G cujos vértices são os inteiros de 1 a 8 e os vértices adjacentes a cada vértice são dados pela tabela abaixo:

Vértice | Vértice Adjacente
--------|------------------
1       | 4, 3 e 2
2       | 1, 3, 4 e 5
3       | 1, 2 e 4
...

Assuma que, em um caminhamento de G, os vértices adjacentes a um vértice dado são retornados na mesma ordem em que são listados na tabela acima.

1. a. Desenho do Grafo e Caminhamento em Largura

   Desenhe o grafo G e descreva a sequência de vértices de G visitada usando um caminhamento em largura (Busca em Largura), iniciando no vértice 1.

2. b. Pseudo-código e Estrutura de Dados da BFS

   Apresente o pseudo-código de como funciona o Algoritmo de Busca em Largura. Explique qual é a estrutura de dados de apoio à sua execução e como ela é utilizada no Algoritmo de Busca em Largura?

   Pseudo-código

   
   function busca_Largura (Inicio, Alvo) {
       entra_fila(Fila, Inicio)
       while naoVazia(Fila) {
           Nodo := sai_fila(Fila)
           if Nodo = Alvo {
               return Nodo
           }
           for each Filho in Expande(Nodo) {
               if naoVisitado(Filho) {
                   foi_visitado(Filho)
                   entra_fila(Fila, Filho)
               }
           }
       }
   }
   Estrutura = pilha
               

Questão 3: Otimização de Caminhos e Custo Mínimo

O prefeito de Campinas deseja construir 7 estradas para interligar 8 bairros de sua cidade, de forma que cada bairro possa ser alcançado de qualquer outro bairro através de uma ou mais estradas. O custo de construção de uma estrada é proporcional ao seu comprimento. As distâncias entre os pares de bairros são dados na matriz de adjacências abaixo:

  1   2   3   4   5   6   7   8
1 - 140 110 240 180 100 245 20
2 - -   165 75  115 80  85  55
3 - -   -   160 15  250 335 95
4 - -   -   -   60  230 195 130
...

Quais estradas devem ser construídas para que o custo das construções seja mínimo? Esquematize-as (desenhe-as). Qual é o custo total da construção destas pontes?

Questão 4: Implementação de Grafos com Matriz de Adjacências em C

Considere a estrutura de dados do tipo Matriz de Adjacências (Máx. 20 vértices) para representar um grafo G. Desenvolver (Programar) os seguintes algoritmos em C:

MAT
  0 1 2 3 4 5
0 0 1 1 0 1 0
1 1 0 1 0 0 1
2 1 1 0 0 0 0
3 0 0 0 0 1 1
4 1 0 0 1 0 0
5 0 1 0 1 0 0

1. a. Função para Verificar Adjacência

   Implemente em C uma função para verificar se o vértice v2 é adjacente ao vértice v1. Retorne 1 se verdadeiro ou 0, caso contrário.

2. b. Função para Apresentar o Grafo

   (1,5 ponto) Desenvolva uma função em C para apresentar o grafo G (imprimir cada aresta ou arco do grafo).

   
   Void imprime() {
       Int mat[5][5];
       Int j, i;
       For (i = 0; i <= 5; i++) {
           For (j = 0; j <= 5; j++) {
               Printf("Linha %d, Coluna %d", i, j);
           }
       }
   }
               

Questão 5: Análise de Matrizes de Adjacências