Estruturas de Dados - Segunda Prova Resolvida

Prévia do material em texto

Segunda prova
Estruturas de Dados 2009/1
Prof. Carla Koike
A compreensão do enunciado de cada questão também está sendo avaliada, portanto limite suas  
perguntas, durante a prova, ao estritamente necessário. Em caso de dúvida, deixe claro como você  
compreendeu e seu raciocínio para resolver a questão.
Nome: GABARITO
Matrícula:
1) Conceitue os termos identificados nos itens abaixo (2,0 pontos ­ 0,2 pontos cada item)
Sobre árvores:
a) Árvore de jogos
São árvores genéricas em que cada nó representa uma situação ou tabuleiro do jogo. Os filhos desse 
nó representam então as situações resultantes das possíveis jogadas.
b) Backbone
Arvore degenerada em lista, por meio de rotações, para fins de balanceamento 
estático. Pode ser a direita (os nós possuem somente filhos a direita) ou a 
esquerda (nós possuem somente filhos a esquerda).
c) DSW
Método de balanceamento estático: Por meios de rotações, a árvore é transformada 
em uma árvore degenerada em lista (backbone) que é, por meio de rotações, 
transformada em uma outra árvore, dessa vez balanceada 
d) Rotação a direita
Rotações alteram a estrutura local de uma árvore binária e afetam somente o nó 
rotacionado e seus filhos imediatos: os pais do nó rotacionado e os filhos de 
seus filhos permanecem inalterados . Por isso as rotações não alteram o 
ordenamento dentro da árvore. A rotação a direita inverte o filho a esquerda e 
seu pai, transformando­os em pai e filho a direita, respectivamente.
e) AVL
Método de balanceamento dinâmico que tenta assegurar que a árvore permanecerá 
balanceada cada vez que um nó é inserido ou deletado. cada nó deve possuir a 
informação adicional do fator de balancemento que é a diferença entre as alturas 
da sub­árvore da esquerda e da direita.
Sobre Grafos:
f) Grafo não direcionado
As arestas ou arcos não possuem direção e (A,B) é igual a (B,A). Self­loops 
(C,C) não são permitidos .
g) Arco incidente
É um arco direcionado chegando em um nó 
h) Circuito
Caminho que leva de um vértice a ele mesmo. 
i) Grafo Fortemente Conexo
Para todos os nós existem caminhos a partir de todos os outros nós .
j) Vértice alcançável
Um vértice x é alcançável a partir do vértice y se existe um caminho a partir de 
y até x .
2) Escreva uma função em C que verifique, via lista de adjacência, qual vértice possui a maior soma 
dos pesos dos arcos saindo desse vértice. Além da função, forneça a declaração das estruturas 
envolvidas e exemplo de um trecho de programa que utiliza essa função. (3,0 pontos) 
Possível solução:
struct Adj{ 
unsigned int vertice; 
unsigned int peso; 
struct Adj *prox; 
}; 
struct Node{ 
unsigned int vertice; 
struct Node *prox; 
struct Adj *nos; 
};
unsigned int MaiorSoma(struct Node *root){ 
 struct Node *temp; 
 unsigned int maior,soma,V; 
 maior = soma = 0; 
 V = 0; 
 struct Adj *aux_1; 
 for (temp = root;temp != NULL;temp= temp->prox){ 
 soma = 0; 
 for(aux_1=temp->nos;aux_1!=NULL;aux_1=aux_1->prox){ 
 soma+= aux_1->peso; 
 } 
 if (soma > maior) { 
 maior = soma; 
 V = temp->vertice; 
 } 
 printf("Visitando vertice %u\n",temp->vertice); 
 printf("Maior soma: %u, no vertice %u\n",maior,V); 
 } 
return V; 
}
int main(void){ 
struct Node *raiz=NULL; 
CriaListaNos(&raiz,5); 
/*Cria uma Lista de Conexoes (nos adjacentes) para cada vertice)*/ 
AddArc(raiz,0,1,1);AddArc(raiz,0,4,1);
...
MaiorSoma(raiz);
}
declaração das estruturas: 0.5
programa de chamada: 0.5
função 2.0
se não calcula para todos os vértices: ­1.0
se não calcula a soma de todos os arcos: ­1.0
se não obtém corretamente a maior das somas: ­1.0
erros de lógica, incoerências : ­0.5
3) Escreva uma função em C que realize a remoção por cópia em uma árvore binária.(3,0 pontos)
typedef long TipoChave; 
typedef struct Registro { 
  TipoChave Chave; 
  /* outros componentes */ 
} Registro; 
typedef struct No * Apontador; 
typedef struct No { 
  Registro Reg; 
  Apontador Esq, Dir; 
} No;
void Antecessor(Apontador q, Apontador *r) 
{ if ((*r)­>Dir != NULL) 
  { Antecessor(q, &(*r)­>Dir); 
    return; 
  } 
  q­>Reg = (*r)­>Reg; 
  q = *r; 
  *r = (*r)­>Esq; 
  free(q); 
} 
void Retira(Registro x, Apontador *p) 
{  Apontador Aux; 
  if (*p == NULL) 
  { printf("Erro : Registro nao esta na arvore\n"); 
    return; 
  } 
  if (x.Chave < (*p)­>Reg.Chave) 
  { Retira(x, &(*p)­>Esq); return; } 
  if (x.Chave > (*p)­>Reg.Chave) 
  { Retira(x, &(*p)­>Dir); return; } 
  if ((*p)­>Dir == NULL) 
  { Aux = *p; 
    *p = (*p)­>Esq; 
    free(Aux); 
    return; 
  } 
  if ((*p)­>Esq != NULL) 
  { Antecessor(*p, &(*p)­>Esq); 
    return; 
  } 
  Aux = *p; 
  *p = (*p)­>Dir; 
  free(Aux); 
}  
0.5 se verifica quantos filhos o nó tem
0.5 se recebe a raiz e navega na árvore em busca do elemento, ou 
se recebe o ponteiro do elemento a ser retirado.
1.0 se encontra antecessor ou sucessor
1.0 se copia o antecessor/sucessor e remove/libera a folha 
(remoção por cópia) (­0.3 se não remove)(­0.3 se copia valor 
errado)
erros de lógica, incoerências : ­0.5
4) Desenhe e descreva passo a passo as modificações  da seguinte árvore quando da aplicação das 
operações abaixo. Cada item é independente e aplicado a mesma árvore inicial desenhada abaixo. 
(2,0 pontos ­ 0,4 pontos cada item)
OBS: O símbolo  significa um ponteiro NULL. 
a) Nó B é rotacionado a direita em torno do Nó C
b) Nó F é removido por fusão
c) Nó G é rotacionado a esquerda em torno do Nó F
d) Árvore é balanceada usando método DSW
1 ­ Nó C é rotacionado a direita em torno do Nó A
2 – Nó B é rotacionado a direita em torno do Nó C
3 – Nó A é rotacionado a direita em torno do Nó B
4 – Nó D é rotacionado a direita em torno do Nó E
5 – Nó F é rotacionado a direita em torno do Nó H
6 – Nó G é rotacionado a direita em torno do Nó H
7 ­ Nó J é rotacionado a direita em torno do Nó G
8 – Nó K é rotacionado a direita em torno do Nó H
O backbone possui onze nós.
Como uma árvore de altura 3 possui 7 nós e uma árvore de altura 4 
possui 15 nós, a árvore terá altura 4.
15 – 11 = 4 que é o número inicial de rotações a serem realizados 
no backbone.
9 – Nó A rotaciona a esquerda em torno do Nó B
10 – Nó C rotaciona a esquerda em torno do Nó D
11 – Nó E rotaciona a esquerda em torno do Nó F
12 – Nó J rotaciona a esquerda em torno do Nó G
A partir dessa árvore, os nós são rotacionados alternadamente.
13 – Nó B rotaciona a esquerda em torno do Nó D
14 – Nó F rotaciona a esquerda em torno do Nó G
15 – Nó K rotaciona a esquerda em torno do Nó H
A árvore muda e os nós são rotacionados alternadamente:
16 – Nó D rotaciona em torno do Nó G
1. 2.
3. 4.
5. 6.
7. 8.
 
e) Nó H é removido por cópia