prova_2_coletanea_respostas

Prévia do material em texto

UNIVERSIDADE FEDERAL DA PARAÍBA
CENTRO DE INFORMÁTICA
Disciplina: [1107186] Estrutura de Dados
Prof. Christian Azambuja Pagot.
Prova II
Questão 1
A Red-Black Tree é uma árvore binária de pesquisa, autobalanceada, e em que cada nó possui uma cor:
vermelho (red) ou preto (black). As Red Black Trees mantém o balanceamento através da manutenção de cinco
invariantes. Uma destas invariantes determina que o filho de um nó vermelho deve ser sempre preto. 
Escreva uma função, em C/C++, que percorra uma árvore binária e determine se a invariante
mencionada anteriormente é mantida. A estrutura de cada nó desta árvore é definida como:
struct Node { 
int color;  // 0 = black, 1 = red
struct Node left;  
struct Node right; }
Abaixo segue o protótipo da função a ser escrita. Esta função receberá como parâmetro um ponteiro para
o no raís (root) da árvore:
bool TestColors(struct Node* root) 
Se a árvore respeitar a invariante, a função deve retornar true. Caso contrário, a função deve retornar 
false.
Resposta
bool RecTestColors(struct Node* node, int parent_color)
{
  if (node)
    if ((parent_color != ­1) && (node­>color == 1) && (parent_color == 1))
      return false;
    else
      return RecTestColors(node­>left, node­>color) && RecTestColors(node­>right, node­>color);
  else
    return true;
}
bool TestColors(struct Node* root)
{
  return RecTestColors(root, ­1);
}
Questão 2
O array abaixo representa um binary heap? Explique sua resposta.
0 1 2 3 4 5 6 7 8 9
7 12 18 25 13 17 19 40 30 31
Resposta
Não. Aparentemente seria um min heap, pois o menor valor é o primeiro elemento do array. Porém, 17 é “filho” 
de 18, que é um valor maior. Assim, a estrutura não respeita a invariante do min nem do max heap, não 
representando, portando, uma binary heap.
Questão 3
Dada uma tabela hash com 11 buckets e a seguinte função de hash h:
h(k) = k mod 11
Insira as chaves [22, 1, 13, 11, 24, 33, 18, 42, 31] na ordem dada (da esquerda para a direita) em uma
tabela hash:
1. Assumindo que a tabela hash resolve as colisões por meio de encadeamento (chainning). 
2. Assumindo que a tabela hash resolve as colisões por meio de endereçamento aberto (linear probing). 
Respostas
Questão 4
Um grafo bicolorido, ou bipartido, é um grafo cujos nós podem ser separados em dois grupos, U e V,
disjuntos, de tal forma que cada aresta conecta um nó de U com um nó de V. Estes dois conjuntos, U e V, podem
ser vistos como um grafo com duas cores: se todos os nós de U têm a cor branca, e todos os nós de V têm a cor
preta, cada aresta do grafo conecta dois vértices de cores diferentes.
Adapte o algoritmo de BFS (Breadth First Search), apresentado abaixo, para determinar se um grafo é
bipartido ou não.
BFS (G, s)
 for each vertex u in G.V – {s}
     u.state = UNDISCOVERED
 s.state = DISCOVERED
 Q = {}
 Enqueue(Q, s)
 while not (Q == {})
     u = Dequeue(Q)
     for each v in G.Adj[u]
         if v.state == UNDISCOVERED
             v.state = DISCOVERED
 Enqueue(Q, v)
Resposta
bool BFS (G, s) 
 for each vertex u in G.V – {s} 
     u.state = UNDISCOVERED 
     s.color = ­1
 s.state = DISCOVERED
 s.color = 0 
 Q = {} 
 Enqueue(Q, s) 
 while not (Q == {}) 
     u = Dequeue(Q) 
     for each v in G.Adj[u] 
         if (v.state == UNDISCOVERED)
             if (u.color == 0)
                 v.color = 1
             else
                 v.color = 0
             v.state = DISCOVERED 
      Enqueue(Q, v) 
         else 
             if (u.color == v.color)
                 return false 
 return true
Questão 5
Calcule o overhead (razão entre o espaço ocupado pelos dados e o espaço total ocupado) para cada uma
das implementações de árvore binária abaixo:
1. Todos os nós armazenam dados, possuem dois ponteiros para os filhos e um ponteiro para o pai. O
campo de dados requer 4 bytes e cada ponteiro requer 8 bytes.
Supondo uma árvore completa com n nós folha:
O espaço ocupado pelos dados das folhas é 4n bytes.
O espaço ocupado pelos dados dos nós internos é 4n-4 bytes.
O espaço total ocupado pelos dados é 8n-4 bytes.
O espaço ocupado pelos ponteiros das folhas é 24n bytes.
O espaço ocupado pelos ponteiros dos nós internos é 24n-24 bytes.
O espaço total ocupado pelos ponteiros é 48n-24 bytes.
O espaço total total ocupado pela árvore é de 56n-28 bytes.
A razão entre o espaço ocupado pelos ponteiros e o espaço total é 48n-24 / 56n-28, ou 12n-6 /
14n-7.
Para n grande demais, o termo constante perde importância e a equação se aproxima de 12n/
14n, ou 6n/7n.
Assim, para uma árvore completa, a quantidade de espaço desperdiçada com os ponteiros
é de aproximadamente 85%.
2. Somente os nós folha armazenam dados; nós internos possuem dois ponteiros para os filhos. O campos
de dados requer 4 bytes e cada ponteiro requer 8 bytes.
Supondo uma árvore completa com n nós folha:
As folhas dessa árvore precisãrão de 4n bytes de espaço (dados). 
Os nós internos dessa árvore precisarão de 16(n-1), ou 16n-16 bytes de espaço (ponteiros). 
Assim, o espaço total ocupado pela árvore é de 4n+16n-16, ou 20n-16 bytes.
A razão entre o espaço ocupado pelos ponteiros e o espaço total é 16n-16 / 20n-16, ou 4n-4 /
5n-4.
Para n grande demais, o termo constante perde importância e a equação se aproxima de 4n/ 5n.
Assim, para uma árvore completa, a quantidade de espaço desperdiçada com os ponteiros
é de aproximadamente 80%.
Questão 6
Duas árvores são idênticas quando as suas estruturas e os valores de seus nós correspondentes são iguais.
Com base nesta informação, escreva uma função em linguagem C que verifique se duas árvores binárias são
idênticas. A função deve retornar true (verdadeiro) se as duas árvores forem idênticas ou false (falso) caso
contrário. O protótipo desta função deve ser: 
bool CompareTrees(Node* t1, Node* t2)
onde t1 é o ponteiro para a raíz da primeira árvore e t2 é o ponteiro para a raíz da segunda árvore. Node é um 
struct que define a estrutura dos nós das árvores, e é definido da seguinte forma:
struct Node
{
     int value;
     Node* left;
     Node* right;
}
Resposta
int CompareTree(struct Node *t1, struct Node *t2)
{
  if ((t1 == NULL) && (t2 == NULL))
    return 1;
  else
    if (((t1 == NULL) && (t2 != NULL)) || ((t1 != NULL) && (t2 == NULL)))
      return 0;
    else
      if (t1­>value == t2­>value)
        return CompareTree(t1­>left, t2­>left) && 
               CompareTree(t1­>right, t2­>right);
      else
        return 0;
}
Questão 7
Com base no grafo representado pela lista de adjacência abaixo, 
Responda: 
3.1 - Desenhe o grafo representado por esta lista de adjacência.
3.2 - Escreva a matriz de adjacência que representa o mesmo grafo.
Questão 8
Dado um grafo não direcionado, descrito por uma matriz ou lista de adjacência, desenvolva um 
algoritmo que determine se este grafo é uma árvore. Uma árvore é um grafo não-direcionado, 
conectado e acíclico!
Exemplifique o funcionamento do algoritmo desenvolvido, mostrando como ele verifica cada 
um dos requisitos que definem uma árvore.
1
2
3
4
5
6
3
6 4
1 4
3 1
1 4
	Questão 1
	Questão 2
	Questão 3
	Questão 4
	Questão 5
	Questão 6
	Questão 7
	Questão 8