P3 ED 2011.1

Prévia do material em texto

Universidade Federal Fluminense - Pólo Universitário de Rio das Ostras
Professor: Dalessandro Soares Vianna Data: 29/11/2011
Disciplina: Estrutura de Dados Prova: P3
Curso: ..Ciência da Computação........Professor: Dalessandro Soares Vianna......................
Nome do Aluno: .............................................................................. Matrícula: ..............................
Obs.: A Questão 3 ou a Questão 4 pode ser trocada pela Questão 5.
Questão 1 (2,5): Deseja-se implementar um Tipo Abstrato de Dados (TAD) para 
manipulação da estrutura de dados “árvore binária de inteiros”. Deve-se permitir que o 
usuário faça atualizações (inserções e remoções) na árvore binária, verifique se um elemento 
existe na árvore, busque um elemento na árvore e realize diferentes tipos de impressões da 
árvore inteira (largura e em profundidade). Para isso foram implementadas as seguintes 
funções: arvore *Inserir (arvore *a, int v); arvore *Remover (arvore *a, int v); int Altura 
(arvore *a); int Existe (arvore *a, int v); arvore *Busca (arvore *a, int v); void 
ImprimePosOrdem (arvore *a); void ImprimePreOrdem (arvore *a) ; void ImprimeNivel 
(arvore *a, int nivel); void ImprimeLargura (arvore *a); e int Vazia (arvore *a). 
- Informe como ficaria o TAD descrito acima, ou seja, como ficariam os arquivos “arvore.h” e 
“arvore.c”. 
Questão 2 (2,5): Deseja-se, trabalhando com notas de $8,00, $7,00, $3,00 e $1,00, dar o troco 
com o menor número de notas possível. Para isso, uma função deve ser implementada, a qual 
deve receber, entre outras coisas, o valor a ser pago e também o valor fornecido pelo cliente.
Questão 3 (2,5): Implemente uma função que receba como parâmetro de entrada um grafo G 
e que retorne como saída o grafo G completo, ou seja, a função deve completar o grafo, 
inserindo as arestas que não estão presentes.
 
Questão 4 (2,5): O problema de Cobertura de Arestas na área de Grafos consiste em 
encontrar um subconjunto de vértices V’ que estão interligados a todas as arestas do grafo. 
Uma função possível para encontrar V’ está descrita abaixo:
Passo 1- Encontre o vértice v de maior grau.
Passo 2- Insira v em V’ e remova todas as arestas que contem v do grafo.
Passo 3- Se existir ainda arestas no grafo, retorne ao Passo 1. Caso contrário, retorne V’. 
-Implemente a função descrita acima.
___________________________________________________________________________
Questão 5 (2,5): Implemente uma função que receba como parâmetros um grafo G e um 
valor inteiro y e retorne todos os caminhos que começam e terminam no vértice y. 
Obs.: y é o único vértice que pode se repetir duas vezes no caminho.